public void buildIndex()

in hollow/src/main/java/com/netflix/hollow/core/index/HollowHashIndexBuilder.java [106:256]
105 lines of code
17 McCabe index (conditional complexity)

    public void buildIndex() {
        matchIndexHashAndSizeArray = new GrowingSegmentedLongArray(memoryRecycler);

        BitSet populatedOrdinals = preindexer.getHollowTypeDataAccess().getTypeState().getPopulatedOrdinals();

        /// an initial guess at how big this table might be -- one match per top-level element.
        int guessNumberOfMatches = populatedOrdinals.cardinality();
        intermediateMatchHashTableSize = HashCodes.hashTableSize(guessNumberOfMatches);
        bitsPerIntermediateListIdentifier =  bitsRequiredToRepresentValue(intermediateMatchHashTableSize - 1);
        bitsPerIntermediateMatchHashEntry = bitsPerMatchHashKey + bitsPerIntermediateListIdentifier;

        intermediateMatchHashMask = intermediateMatchHashTableSize - 1;
        intermediateMatchHashTableSizeBeforeGrow = intermediateMatchHashTableSize * 7 / 10;
        matchCount = 0;

        /// a data structure which keeps canonical matches for comparison (the matchHashTable)
        intermediateMatchHashTable = new FixedLengthElementArray(memoryRecycler, (long)intermediateMatchHashTableSize * bitsPerIntermediateMatchHashEntry);

        /// a data structure which tracks lists of matches under canonical matches.
        MultiLinkedElementArray intermediateSelectLists = new MultiLinkedElementArray(memoryRecycler);

        HollowIndexerValueTraverser traverser = preindexer.getTraverser();


        int ordinal = populatedOrdinals.nextSetBit(0);
        while(ordinal != HollowConstants.ORDINAL_NONE) {
            traverser.traverse(ordinal);

            for(int i=0;i<traverser.getNumMatches();i++) {
                int matchHash = getMatchHash(i);

                long bucket = matchHash & intermediateMatchHashMask;
                long hashBucketBit = bucket * bitsPerIntermediateMatchHashEntry;
                boolean bucketIsEmpty = intermediateMatchHashTable.getElementValue(hashBucketBit, bitsPerTraverserField[0]) == 0;
                long bucketMatchListIdx = intermediateMatchHashTable.getElementValue(hashBucketBit + bitsPerMatchHashKey, bitsPerIntermediateListIdentifier);
                int bucketMatchHashCode = (int)matchIndexHashAndSizeArray.get(bucketMatchListIdx);

                while(!bucketIsEmpty && (bucketMatchHashCode != (matchHash & Integer.MAX_VALUE) || !intermediateMatchIsEqual(i, hashBucketBit))) {
                    bucket = (bucket + 1) & intermediateMatchHashMask;
                    hashBucketBit = bucket * bitsPerIntermediateMatchHashEntry;
                    bucketIsEmpty = intermediateMatchHashTable.getElementValue(hashBucketBit, bitsPerTraverserField[0]) == 0;
                    bucketMatchListIdx = intermediateMatchHashTable.getElementValue(hashBucketBit + bitsPerMatchHashKey, bitsPerIntermediateListIdentifier);
                    bucketMatchHashCode = (int)matchIndexHashAndSizeArray.get(bucketMatchListIdx);
                }

                int matchListIdx;

                if(bucketIsEmpty) {
                    matchListIdx = intermediateSelectLists.newList();
                    for(int j=0;j<preindexer.getNumMatchTraverserFields();j++)
                        intermediateMatchHashTable.setElementValue(hashBucketBit + offsetPerTraverserField[j], bitsPerTraverserField[j], traverser.getMatchOrdinal(i, j) + 1);

                    intermediateMatchHashTable.setElementValue(hashBucketBit + bitsPerMatchHashKey, bitsPerIntermediateListIdentifier, matchListIdx);

                    matchIndexHashAndSizeArray.set(matchListIdx, matchHash & Integer.MAX_VALUE);
                    matchCount++;

                    /// GROW IF NECESSARY!
                    if(matchCount > intermediateMatchHashTableSizeBeforeGrow) {
                        growIntermediateHashTable();
                    }

                } else {
                    matchListIdx = (int)intermediateMatchHashTable.getElementValue(hashBucketBit + bitsPerMatchHashKey, bitsPerIntermediateListIdentifier);
                }

                intermediateSelectLists.add(matchListIdx, traverser.getMatchOrdinal(i, preindexer.getSelectFieldSpec().getBaseIteratorFieldIdx()));
            }




            ordinal = populatedOrdinals.nextSetBit(ordinal + 1);
        }


        /// turn those data structures into a compact one optimized for hash lookup
        long totalNumberOfSelectBucketsAndBitsRequiredForSelectTableSize = calculateDedupedSizesAndTotalNumberOfSelectBuckets(intermediateSelectLists, matchIndexHashAndSizeArray);
        long totalNumberOfSelectBuckets = totalNumberOfSelectBucketsAndBitsRequiredForSelectTableSize & 0xFFFFFFFFFFFFFFL;
        long totalNumberOfMatchBuckets = HashCodes.hashTableSize(matchCount);

        int bitsPerFinalSelectBucketPointer = bitsRequiredToRepresentValue(totalNumberOfSelectBuckets);
        int bitsPerSelectTableSize = (int)(totalNumberOfSelectBucketsAndBitsRequiredForSelectTableSize >>> 56);
        int finalBitsPerMatchHashEntry = bitsPerMatchHashKey + bitsPerSelectTableSize + bitsPerFinalSelectBucketPointer;

        FixedLengthElementArray finalMatchArray = new FixedLengthElementArray(memoryRecycler, totalNumberOfMatchBuckets * finalBitsPerMatchHashEntry);
        FixedLengthElementArray finalSelectArray = new FixedLengthElementArray(memoryRecycler, totalNumberOfSelectBuckets * bitsPerSelectHashEntry);

        long finalMatchHashMask = totalNumberOfMatchBuckets - 1;

        long currentSelectArrayBucket = 0;

        for(int i=0;i<matchCount;i++) {
            long matchIndexHashAndSize = matchIndexHashAndSizeArray.get(i);
            int matchIndexSize = (int)(matchIndexHashAndSize >> 32);
            int matchIndexTableSize = HashCodes.hashTableSize(matchIndexSize);
            int matchIndexBucketMask = matchIndexTableSize - 1;

            HollowOrdinalIterator selectOrdinalIter = intermediateSelectLists.iterator(i);
            int selectOrdinal = selectOrdinalIter.next();
            while(selectOrdinal != HollowOrdinalIterator.NO_MORE_ORDINALS) {
                int selectBucket = HashCodes.hashInt(selectOrdinal) & matchIndexBucketMask;
                int bucketOrdinal = (int)finalSelectArray.getElementValue((currentSelectArrayBucket + selectBucket) * bitsPerSelectHashEntry, bitsPerSelectHashEntry) - 1;
                while(bucketOrdinal != HollowConstants.ORDINAL_NONE && bucketOrdinal != selectOrdinal) {
                    ///TODO: If select field type is not REFERENCE, then we should dedup -- unless we are reference counting for delta application
                    ///ordinals here with the same value for the specified field.
                    selectBucket = (selectBucket + 1) & matchIndexBucketMask;
                    bucketOrdinal = (int)finalSelectArray.getElementValue((currentSelectArrayBucket + selectBucket) * bitsPerSelectHashEntry, bitsPerSelectHashEntry) - 1;
                }

                if(bucketOrdinal == HollowConstants.ORDINAL_NONE)
                    finalSelectArray.setElementValue((currentSelectArrayBucket + selectBucket) * bitsPerSelectHashEntry, bitsPerSelectHashEntry, selectOrdinal + 1);

                selectOrdinal = selectOrdinalIter.next();
            }

            long finalMatchIndexBucket = matchIndexHashAndSize & finalMatchHashMask;
            long finalMatchIndexBucketBit = finalMatchIndexBucket * finalBitsPerMatchHashEntry;

            while(finalMatchArray.getElementValue(finalMatchIndexBucketBit, bitsPerTraverserField[0]) != 0) {
                finalMatchIndexBucket = (finalMatchIndexBucket + 1) & finalMatchHashMask;
                finalMatchIndexBucketBit = finalMatchIndexBucket * finalBitsPerMatchHashEntry;
            }

            long intermediateMatchHashBucket = matchIndexHashAndSize & intermediateMatchHashMask;
            long intermediateMatchIndexBucketBit = intermediateMatchHashBucket * bitsPerIntermediateMatchHashEntry;
            while(intermediateMatchHashTable.getElementValue(intermediateMatchIndexBucketBit + bitsPerMatchHashKey, bitsPerIntermediateListIdentifier) != i) {
                intermediateMatchHashBucket = (intermediateMatchHashBucket + 1) & intermediateMatchHashMask;
                intermediateMatchIndexBucketBit = intermediateMatchHashBucket * bitsPerIntermediateMatchHashEntry;
            }

            if(bitsPerMatchHashKey < 56) {
                long matchHashKey = intermediateMatchHashTable.getElementValue(intermediateMatchIndexBucketBit, bitsPerMatchHashKey);
                finalMatchArray.setElementValue(finalMatchIndexBucketBit, bitsPerMatchHashKey, matchHashKey);
            } else {
                finalMatchArray.copyBits(intermediateMatchHashTable, intermediateMatchIndexBucketBit, finalMatchIndexBucketBit, bitsPerMatchHashKey);
            }

            finalMatchArray.setElementValue(finalMatchIndexBucketBit + bitsPerMatchHashKey, bitsPerSelectTableSize, matchIndexSize);
            finalMatchArray.setElementValue(finalMatchIndexBucketBit + bitsPerMatchHashKey + bitsPerSelectTableSize, bitsPerFinalSelectBucketPointer, currentSelectArrayBucket);

            currentSelectArrayBucket += matchIndexTableSize;
        }

        this.finalMatchHashTable = finalMatchArray;
        this.finalSelectHashArray = finalSelectArray;
        this.finalBitsPerMatchHashEntry = finalBitsPerMatchHashEntry;
        this.finalBitsPerSelectTablePointer = bitsPerFinalSelectBucketPointer;
        this.finalBitsPerSelectTableSize = bitsPerSelectTableSize;
        this.finalMatchHashMask = finalMatchHashMask;
    }