<commit_before>/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.jackrabbit.oak.plugins.segment;

import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.base.Preconditions.checkState;
import static com.google.common.collect.Iterables.concat;
import static com.google.common.collect.Lists.newArrayListWithCapacity;
import static java.lang.Integer.bitCount;
import static java.lang.Integer.highestOneBit;
import static java.lang.Integer.numberOfTrailingZeros;

import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import com.google.common.base.Objects;
import com.google.common.collect.ComparisonChain;

class MapRecord extends Record {

    private static final int M = 0xDEECE66D;
    private static final int A = 0xB;
    static final long HASH_MASK = 0xFFFFFFFFL;

    static int getHash(String name) {
        return (name.hashCode() ^ M) * M + A;
    }

    /**
     * Number of bits of the hash code to look at on each level of the trie.
     */
    protected static final int BITS_PER_LEVEL = 5;

    /**
     * Number of buckets at each level of the trie.
     */
    protected static final int BUCKETS_PER_LEVEL = 1 << BITS_PER_LEVEL; // 32

    /**
     * Maximum number of trie levels.
     */
    protected static final int MAX_NUMBER_OF_LEVELS =
            (32 + BITS_PER_LEVEL - 1) / BITS_PER_LEVEL; // 7

    /**
     * Number of bits needed to indicate the current trie level.
     */
    protected static final int LEVEL_BITS = // 4, using nextPowerOfTwo():
            numberOfTrailingZeros(highestOneBit(MAX_NUMBER_OF_LEVELS) << 1);

    /**
     * Number of bits used to indicate the size of a map.
     */
    protected static final int SIZE_BITS = 32 - LEVEL_BITS;

    /**
     * Maximum size of a map.
     */
    protected static final int MAX_SIZE = (1 << SIZE_BITS) - 1; // ~268e6

    protected MapRecord(Segment segment, RecordId id) {
        super(segment, id);
    }

    boolean isLeaf() {
        Segment segment = getSegment();
        int head = segment.readInt(getOffset(0));
        if (isDiff(head)) {
            RecordId base = segment.readRecordId(getOffset(8, 2));
            return new MapRecord(segment, base).isLeaf();
        }
        return !isBranch(head);
    }

    public boolean isDiff() {
        return isDiff(getSegment().readInt(getOffset(0)));
    }

    MapRecord[] getBuckets() {
        Segment segment = getSegment();
        MapRecord[] buckets = new MapRecord[BUCKETS_PER_LEVEL];
        int bitmap = segment.readInt(getOffset(4));
        int ids = 0;
        for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
            if ((bitmap & (1 << i)) != 0) {
                buckets[i] = new MapRecord(
                        segment, segment.readRecordId(getOffset(8, ids++)));
            } else {
                buckets[i] = null;
            }
        }
        return buckets;
    }

    private List<MapRecord> getBucketList(Segment segment) {
        List<MapRecord> buckets = newArrayListWithCapacity(BUCKETS_PER_LEVEL);
        int bitmap = segment.readInt(getOffset(4));
        int ids = 0;
        for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
            if ((bitmap & (1 << i)) != 0) {
                RecordId id = segment.readRecordId(getOffset(8, ids++));
                buckets.add(new MapRecord(segment, id));
            }
        }
        return buckets;
    }

    int size() {
        Segment segment = getSegment();
        int head = segment.readInt(getOffset(0));
        if (isDiff(head)) {
            RecordId base = segment.readRecordId(getOffset(8, 2));
            return new MapRecord(segment, base).size();
        }
        return getSize(head);
    }

    MapEntry getEntry(String name) {
        checkNotNull(name);
        int hash = getHash(name);
        Segment segment = getSegment();

        int head = segment.readInt(getOffset(0));
        if (isDiff(head)) {
            if (hash == segment.readInt(getOffset(4))) {
                RecordId key = segment.readRecordId(getOffset(8));
                if (name.equals(segment.readString(key))) {
                    RecordId value = segment.readRecordId(getOffset(8, 1));
                    return new MapEntry(segment, name, key, value);
                }
            }
            RecordId base = segment.readRecordId(getOffset(8, 2));
            return new MapRecord(segment, base).getEntry(name);
        }

        int size = getSize(head);
        if (size == 0) {
            return null; // shortcut
        }

        int level = getLevel(head);
        if (isBranch(size, level)) {
            // this is an intermediate branch record
            // check if a matching bucket exists, and recurse 
            int bitmap = segment.readInt(getOffset(4));
            int mask = (1 << BITS_PER_LEVEL) - 1;
            int shift = 32 - (level + 1) * BITS_PER_LEVEL;
            int index = (hash >> shift) & mask;
            int bit = 1 << index;
            if ((bitmap & bit) != 0) {
                int ids = bitCount(bitmap & (bit - 1));
                RecordId id = segment.readRecordId(getOffset(8, ids));
                return new MapRecord(segment, id).getEntry(name);
            } else {
                return null;
            }
        }

        // this is a leaf record; scan the list to find a matching entry
        long h = hash & HASH_MASK;
        int p = 0;
        long pH = 0;
        int q = size - 1;
        long qH = HASH_MASK;
        while (p <= q) {
            checkState(pH <= qH);
            int i = p + (int) ((q - p) * (h - pH) / (qH - pH));
            checkState(p <= i && i <= q);
            long iH = segment.readInt(getOffset(4 + i * 4)) & HASH_MASK;
            int diff = Long.valueOf(iH).compareTo(Long.valueOf(h));
            if (diff == 0) {
                RecordId keyId = segment.readRecordId(
                        getOffset(4 + size * 4, i * 2));
                diff = segment.readString(keyId).compareTo(name);
                if (diff == 0) {
                    RecordId valueId = segment.readRecordId(
                            getOffset(4 + size * 4, i * 2 + 1));
                    return new MapEntry(segment, name, keyId, valueId);
                }
            }
            if (diff < 0) {
                p = i + 1;
                pH = iH;
            } else {
                q = i - 1;
                qH = iH;
            }
        }
        return null;
    }<commit_msg>OAK-1273: Reduce overhead when handling many parallel property indices<commit_after>/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.jackrabbit.oak.plugins.segment;

import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.collect.Iterables.concat;
import static com.google.common.collect.Lists.newArrayListWithCapacity;
import static java.lang.Integer.bitCount;
import static java.lang.Integer.highestOneBit;
import static java.lang.Integer.numberOfTrailingZeros;

import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import com.google.common.base.Objects;
import com.google.common.collect.ComparisonChain;

class MapRecord extends Record {

    private static final int M = 0xDEECE66D;
    private static final int A = 0xB;
    static final long HASH_MASK = 0xFFFFFFFFL;

    static int getHash(String name) {
        return (name.hashCode() ^ M) * M + A;
    }

    /**
     * Number of bits of the hash code to look at on each level of the trie.
     */
    protected static final int BITS_PER_LEVEL = 5;

    /**
     * Number of buckets at each level of the trie.
     */
    protected static final int BUCKETS_PER_LEVEL = 1 << BITS_PER_LEVEL; // 32

    /**
     * Maximum number of trie levels.
     */
    protected static final int MAX_NUMBER_OF_LEVELS =
            (32 + BITS_PER_LEVEL - 1) / BITS_PER_LEVEL; // 7

    /**
     * Number of bits needed to indicate the current trie level.
     */
    protected static final int LEVEL_BITS = // 4, using nextPowerOfTwo():
            numberOfTrailingZeros(highestOneBit(MAX_NUMBER_OF_LEVELS) << 1);

    /**
     * Number of bits used to indicate the size of a map.
     */
    protected static final int SIZE_BITS = 32 - LEVEL_BITS;

    /**
     * Maximum size of a map.
     */
    protected static final int MAX_SIZE = (1 << SIZE_BITS) - 1; // ~268e6

    protected MapRecord(Segment segment, RecordId id) {
        super(segment, id);
    }

    boolean isLeaf() {
        Segment segment = getSegment();
        int head = segment.readInt(getOffset(0));
        if (isDiff(head)) {
            RecordId base = segment.readRecordId(getOffset(8, 2));
            return new MapRecord(segment, base).isLeaf();
        }
        return !isBranch(head);
    }

    public boolean isDiff() {
        return isDiff(getSegment().readInt(getOffset(0)));
    }

    MapRecord[] getBuckets() {
        Segment segment = getSegment();
        MapRecord[] buckets = new MapRecord[BUCKETS_PER_LEVEL];
        int bitmap = segment.readInt(getOffset(4));
        int ids = 0;
        for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
            if ((bitmap & (1 << i)) != 0) {
                buckets[i] = new MapRecord(
                        segment, segment.readRecordId(getOffset(8, ids++)));
            } else {
                buckets[i] = null;
            }
        }
        return buckets;
    }

    private List<MapRecord> getBucketList(Segment segment) {
        List<MapRecord> buckets = newArrayListWithCapacity(BUCKETS_PER_LEVEL);
        int bitmap = segment.readInt(getOffset(4));
        int ids = 0;
        for (int i = 0; i < BUCKETS_PER_LEVEL; i++) {
            if ((bitmap & (1 << i)) != 0) {
                RecordId id = segment.readRecordId(getOffset(8, ids++));
                buckets.add(new MapRecord(segment, id));
            }
        }
        return buckets;
    }

    int size() {
        Segment segment = getSegment();
        int head = segment.readInt(getOffset(0));
        if (isDiff(head)) {
            RecordId base = segment.readRecordId(getOffset(8, 2));
            return new MapRecord(segment, base).size();
        }
        return getSize(head);
    }

    MapEntry getEntry(String name) {
        checkNotNull(name);
        int hash = getHash(name);
        Segment segment = getSegment();

        int head = segment.readInt(getOffset(0));
        if (isDiff(head)) {
            if (hash == segment.readInt(getOffset(4))) {
                RecordId key = segment.readRecordId(getOffset(8));
                if (name.equals(segment.readString(key))) {
                    RecordId value = segment.readRecordId(getOffset(8, 1));
                    return new MapEntry(segment, name, key, value);
                }
            }
            RecordId base = segment.readRecordId(getOffset(8, 2));
            return new MapRecord(segment, base).getEntry(name);
        }

        int size = getSize(head);
        if (size == 0) {
            return null; // shortcut
        }

        int level = getLevel(head);
        if (isBranch(size, level)) {
            // this is an intermediate branch record
            // check if a matching bucket exists, and recurse 
            int bitmap = segment.readInt(getOffset(4));
            int mask = (1 << BITS_PER_LEVEL) - 1;
            int shift = 32 - (level + 1) * BITS_PER_LEVEL;
            int index = (hash >> shift) & mask;
            int bit = 1 << index;
            if ((bitmap & bit) != 0) {
                int ids = bitCount(bitmap & (bit - 1));
                RecordId id = segment.readRecordId(getOffset(8, ids));
                return new MapRecord(segment, id).getEntry(name);
            } else {
                return null;
            }
        }

        // use interpolation search to find the matching entry in this map leaf
        int shift = 32 - level * BITS_PER_LEVEL;
        long mask = -1L << shift;
        long h = hash & HASH_MASK;
        int p = 0;
        long pH = h & mask;   // lower bound on hash values in this map leaf
        int q = size - 1;
        long qH = pH | ~mask; // upper bound on hash values in this map leaf
        while (p <= q) {
            assert pH <= qH;

            // interpolate the most likely index of the target entry
            // based on its hash code and the lower and upper bounds
            int i = p + (int) ((q - p) * (h - pH) / (qH - pH));
            assert p <= i && i <= q;

            long iH = segment.readInt(getOffset(4 + i * 4)) & HASH_MASK;
            int diff = Long.valueOf(iH).compareTo(Long.valueOf(h));
            if (diff == 0) {
                RecordId keyId = segment.readRecordId(
                        getOffset(4 + size * 4, i * 2));
                RecordId valueId = segment.readRecordId(
                        getOffset(4 + size * 4, i * 2 + 1));
                diff = segment.readString(keyId).compareTo(name);
                if (diff == 0) {
                    return new MapEntry(segment, name, keyId, valueId);
                }
            }

            if (diff < 0) {
                p = i + 1;
                pH = iH;
            } else {
                q = i - 1;
                qH = iH;
            }
        }
        return null;
    }
{'fraction_non_alphanumeric': 0.10495528810596383, 'fraction_numerical': 0.011295636388085792, 'mean_word_length': 1.931415057154119, 'pattern_counts': {'":': 0, '<': 51, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1467084', 'n_tokens_mistral': 4388, 'n_tokens_neox': 4144, 'n_words': 1307}