---

3.2.2.3 The Root Node Data Placing Method

The method is to determine where in the 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 root node and the third the address where the determination is to be stored. While the data item to be placed withing the 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.

If a matching data item is present in the node, the method is to indicate the data placing as the index of a matching data item. Otherwise, it is to indicate the data placing as 0 if no data is stored in the node (i.e. if the node is empty) and as the slot index of the greatest data item less than the data item to be placed. The index of the first slot is 0. The first slot is not used for data storage, but for slot count 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 0.

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

See Bitmapped B-tree Root Node Layout.

13 byte string data items example:

/*
 * the item to be placed is the operation context itself
 */
static int
look(void *text, void *node, unsigned *pick)
{
    int status;
    unsigned size;

    /*
     * read the slot usage
     */
    size = *(integral_q *) node;
    if (size) {
	unsigned look = 1;
	void *call;

	/*
	 * binary search the node until one slot remains to be examined
	 */
	call = (char *) node + 13;

	size--;
	while (size) {
	    unsigned half;
	    void *slip;

	    half = (size + 1) >> 1;
	    slip = (char *) call + 13 * half;
	    if (memcmp(text, slip, 13) < 0) {
		size = half - 1;
	    } else {
		look += half;
		call = slip;
		size -= half;
	    }
	}

	if (memcmp(call, text, 13)) {
	    status = 0;

	    if (memcmp(text, call, 13) < 0) {
		look--;
	    } else {
	    }

	    *pick = look;
	} else {
	    status = 1;

	    *pick = look;
	}
    } else {
	status = 0;

	*pick = 0;
    }

    return status;
}

Unsigned long data items example:

/*
 * the item to be placed is stored where the operation context points
 */
static int
look(void *text, void *node, unsigned *pick)
{
    int status;
    unsigned size;

    /*
     * read the slot usage
     */
    size = *(integral_q *) node;
    if (size) {
	unsigned long *call, fine, *high;

	fine = *(unsigned long *) text;

	high = node;

	call = high + 1;

	/*
	 * binary search the node until one slot remains to be examined
	 */
	size--;
	while (size) {
	    unsigned half;
	    unsigned long *slip;

	    half = (size + 1) >> 1;
	    slip = call + half;
	    if (fine < *slip) {
		size = half - 1;
	    } else {
		call = slip;
		size -= half;
	    }
	}

	if (*call ^ fine) {
	    status = 0;

	    if (fine < *call) {
		call--;
	    } else {
	    }

	    *pick = call - high;
	} else {
	    status = 1;

	    *pick = call - high;
	}
    } else {
	status = 0;

	*pick = 0;
    }

    return status;
}

In both examples integral_q is an application defined integral type of size matching the pointer size.