public int findSlot()

in hyracks/hyracks-storage-am-btree/src/main/java/org/apache/hyracks/storage/am/btree/impls/FieldPrefixSlotManager.java [83:194]
96 lines of code
22 McCabe index (conditional complexity)

    public int findSlot(ITupleReference searchKey, ITreeIndexTupleReference frameTuple,
            ITreeIndexTupleReference framePrefixTuple, MultiComparator multiCmp, FindTupleMode mode,
            FindTupleNoExactMatchPolicy matchPolicy) throws HyracksDataException {
        if (frame.getTupleCount() <= 0)
            encodeSlotFields(TUPLE_UNCOMPRESSED, GREATEST_KEY_INDICATOR);

        int prefixMid;
        int prefixBegin = 0;
        int prefixEnd = frame.getPrefixTupleCount() - 1;
        int prefixMatch = TUPLE_UNCOMPRESSED;

        // bounds are inclusive on both ends
        int tuplePrefixSlotNumLbound = prefixBegin;
        int tuplePrefixSlotNumUbound = prefixEnd;

        // binary search on the prefix slots to determine upper and lower bounds
        // for the prefixSlotNums in tuple slots
        while (prefixBegin <= prefixEnd) {
            prefixMid = (prefixBegin + prefixEnd) / 2;
            framePrefixTuple.resetByTupleIndex(frame, prefixMid);
            int cmp = multiCmp.fieldRangeCompare(searchKey, framePrefixTuple, 0, framePrefixTuple.getFieldCount());
            if (cmp < 0) {
                prefixEnd = prefixMid - 1;
                tuplePrefixSlotNumLbound = prefixMid - 1;
            } else if (cmp > 0) {
                prefixBegin = prefixMid + 1;
                tuplePrefixSlotNumUbound = prefixMid + 1;
            } else {
                if (mode == FindTupleMode.EXCLUSIVE) {
                    if (matchPolicy == FindTupleNoExactMatchPolicy.HIGHER_KEY)
                        prefixBegin = prefixMid + 1;
                    else
                        prefixEnd = prefixMid - 1;
                } else {
                    tuplePrefixSlotNumLbound = prefixMid;
                    tuplePrefixSlotNumUbound = prefixMid;
                    prefixMatch = prefixMid;
                }

                break;
            }
        }

        int tupleMid = -1;
        int tupleBegin = 0;
        int tupleEnd = frame.getTupleCount() - 1;

        // binary search on tuples, guided by the lower and upper bounds on prefixSlotNum
        while (tupleBegin <= tupleEnd) {
            tupleMid = (tupleBegin + tupleEnd) / 2;
            int tupleSlotOff = getTupleSlotOff(tupleMid);
            int tupleSlot = buf.getInt(tupleSlotOff);
            int prefixSlotNum = decodeFirstSlotField(tupleSlot);

            int cmp = 0;
            if (prefixSlotNum == TUPLE_UNCOMPRESSED) {
                frameTuple.resetByTupleIndex(frame, tupleMid);
                cmp = multiCmp.compare(searchKey, frameTuple);
            } else {
                if (prefixSlotNum < tuplePrefixSlotNumLbound)
                    cmp = 1;
                else if (prefixSlotNum > tuplePrefixSlotNumUbound)
                    cmp = -1;
                else {
                    frameTuple.resetByTupleIndex(frame, tupleMid);
                    cmp = multiCmp.compare(searchKey, frameTuple);
                }
            }

            if (cmp < 0)
                tupleEnd = tupleMid - 1;
            else if (cmp > 0)
                tupleBegin = tupleMid + 1;
            else {
                if (mode == FindTupleMode.EXCLUSIVE) {
                    if (matchPolicy == FindTupleNoExactMatchPolicy.HIGHER_KEY)
                        tupleBegin = tupleMid + 1;
                    else
                        tupleEnd = tupleMid - 1;
                } else {
                    if (mode == FindTupleMode.EXCLUSIVE_ERROR_IF_EXISTS) {
                        return encodeSlotFields(prefixMatch, ERROR_INDICATOR);
                    } else {
                        return encodeSlotFields(prefixMatch, tupleMid);
                    }
                }
            }
        }

        if (mode == FindTupleMode.EXACT)
            return encodeSlotFields(prefixMatch, ERROR_INDICATOR);

        // do final comparison to determine whether the search key is greater
        // than all keys or in between some existing keys
        if (matchPolicy == FindTupleNoExactMatchPolicy.HIGHER_KEY) {
            if (tupleBegin > frame.getTupleCount() - 1)
                return encodeSlotFields(prefixMatch, GREATEST_KEY_INDICATOR);
            frameTuple.resetByTupleIndex(frame, tupleBegin);
            if (multiCmp.compare(searchKey, frameTuple) < 0)
                return encodeSlotFields(prefixMatch, tupleBegin);
            else
                return encodeSlotFields(prefixMatch, GREATEST_KEY_INDICATOR);
        } else {
            if (tupleEnd < 0)
                return encodeSlotFields(prefixMatch, GREATEST_KEY_INDICATOR);
            frameTuple.resetByTupleIndex(frame, tupleEnd);
            if (multiCmp.compare(searchKey, frameTuple) > 0)
                return encodeSlotFields(prefixMatch, tupleEnd);
            else
                return encodeSlotFields(prefixMatch, GREATEST_KEY_INDICATOR);
        }
    }