1.1.2.4 The Non Root Node Data Placing Method

The method is to determine where in some non root node the data item making the object of current operation fits. Its signature is:

int (*) (void *, void *, unsigned *);

The first argument is the (application specified) operation context, the second the non root node and the third the address where the determination is to be stored. While the data item to be placed withing the non root node is not explicitly in the parameters list it is assumed to be included in the operation context.

The method is to return non zero if the data item is present in the node, zero otherwise. It is to indicate the data placing as the slot index of the greatest data item in the node less than the data item to be placed if the index is odd or if the following slot is used, as the slot index plus one otherwise. The index of the first slot is 0. The first slot is not used for data storage, but for node bitmap storage. The index of the first data proper slot is 1. If no data item stored by node is less than the data item to be placed the method is to indicate the data placing as 1.

The method is not indicated the size of the data items.

See Bitmapped B-tree Non Root Node Layout.

13 byte string data items example:

/*
 * the item to be placed is the operation context itself
 */
static int
pick(void *text, void *node, unsigned *pick)
{
    int status;
    unsigned half = HALF, slip = 0;

    /*
     * binary search data, for as long as refinement is 2 or greater
     */
    do {
	if (memcmp(text, (char *) node + 13 * (slip + half), 13) < 0) {
	} else {
	    slip += half;
	}

	half >>= 1;
    } while (half ^ 1);

    /*
     * examine the bitmap for the last binary search iteration
     */
    if (*(integral_q *) node & (integral_q) 2 << slip) {
	/*
	 * the _slip + 1_ slot is used
	 */
	if (memcmp(text, (char *) node + 13 * (slip + 1), 13) < 0) {
	    *pick = slip + 0;
	    if (slip) {
		if (memcmp(text, (char *) node + 13 * (slip + 0), 13)) {
		    status = 0;
		} else {
		    status = 1;
		}
	    } else {
		status = 0;
	    }
	} else {
	    *pick = slip + 1;
	    if (memcmp(text, (char *) node + 13 * (slip + 1), 13)) {
		status = 0;
	    } else {
		status = 1;
	    }
	}
    } else {
	/*
	 * the _slip + 1_ slot is not used
	 */
	*pick = slip + 1;
	if (slip) {
	    if (memcmp(text, (char *) node + 13 * (slip + 0), 13)) {
		status = 0;
	    } else {
		status = 1;
	    }
	} else {
	    if (1) {
		status = 0;
	    }
	}
    }

    return status;
}

Same 13 byte string data items example, fewer comparisons:

/*
 * the item to be placed is the operation context itself
 */
static int
pick(void *text, void *node, unsigned *pick)
{
    int record = 1, status;
    unsigned half = HALF, slip = 0;

    /*
     * binary search data, for as long as refinement is 2 or greater
     */
    do {
	int effect;

	effect = memcmp(text, (char *) node + 13 * (slip + half), 13);
	if (effect < 0) {
	} else {
	    slip += half;
	    record = effect;
	}

	half >>= 1;
    } while (half ^ 1);

    /*
     * examine the bitmap for the last binary search iteration
     */
    if (*(integral_q *) node & (integral_q) 2 << slip) {
	int effect;

	/*
	 * the _slip + 1_ slot is used
	 */
	effect = memcmp(text, (char *) node + 13 * (slip + 1), 13);
	if (effect < 0) {
	    *pick = slip + 0;
	    status = !record;
	} else {
	    *pick = slip + 1;
	    status = !effect;
	}
    } else {
	/*
	 * the _slip + 1_ slot is not used
	 */
	*pick = slip + 1;
	status = !record;
    }

    return status;
}

Unsigned long data items example:

/*
 * the item to be placed is stored where the operation context points
 */
static int
pick(void *text, void *node, unsigned *pick)
{
    int status;
    unsigned half = HALF, slip = 0;
    unsigned long fine, *high;

    fine = *(unsigned long *) text;

    high = node;

    /*
     * binary search data, for as long as refinement is 2 or greater
     */
    do {
	if (fine < high[slip + half]) {
	} else {
	    slip += half;
	}

	half >>= 1;
    } while (half ^ 1);

    /*
     * examine the bitmap for the last binary search iteration
     */
    if (*(integral_q *) node & (integral_q) 2 << slip) {
	/*
	 * the _slip + 1_ slot is used
	 */
	if (fine < high[slip + 1]) {
	    *pick = slip + 0;
	    if (slip) {
		if (fine ^ high[slip + 0]) {
		    status = 0;
		} else {
		    status = 1;
		}
	    } else {
		status = 0;
	    }
	} else {
	    *pick = slip + 1;
	    if (fine ^ high[slip + 1]) {
		status = 0;
	    } else {
		status = 1;
	    }
	}
    } else {
	/*
	 * the _slip + 1_ slot is not used
	 */
	*pick = slip + 1;
	if (slip) {
	    if (fine ^ high[slip + 0]) {
		status = 0;
	    } else {
		status = 1;
	    }
	} else {
	    if (1) {
		status = 0;
	    }
	}
    }

    return status;
}

In all examples integral_q is an application defined integral type of size matching the pointer size, HALF is half the pointer size expressed in bits.