bt_code.c

b树的实现

		NODES(btr, s)[0] = r;
		btreesplitchild(btr, s, 0, r);
		r = s;
	}
	/* finally insert the new node */
	btreeinsertnonfull(btr, r, k);
}

static void
btreeinsertnonfull(struct btree *btr, struct btreenode *x, bt_data_t k)
{
	int i;

	i = x->n - 1;
	if (x->leaf) {
		/* we are a leaf, just add it in */
		i = findkindex(btr, x, k, NULL);
		if (i != x->n - 1)
			memmove(KEYS(btr, x) + i + 2, KEYS(btr, x) + i + 1,
			    (x->n - i - 1) * sizeof k);
		KEYS(btr, x)[i + 1] = k;
		x->n++;
	} else {
		i = findkindex(btr, x, k, NULL) + 1;

		/* make sure that the next node isn't full */
		if (NODES(btr, x)[i]->n == 2 * btr->t - 1) {
			btreesplitchild(btr, x, i, NODES(btr, x)[i]);
			if (btr->cmp(k, KEYS(btr, x)[i]) > 0)
				i++;
		}
		btreeinsertnonfull(btr, NODES(btr, x)[i], k);
	}
}

bt_data_t
bt_delete(struct btree *btr, bt_data_t k)
{
	struct btreenode *x;
	bt_data_t r;

	r = nodedeletekey(btr, btr->root, k, 0);

	/*
	 * remove an empty, non-leaf node from root, this is the ONLY
	 * place that a tree can decrease in height
	 */
	if (btr->root->n == 0 && btr->root->leaf == 0) {
#ifdef STATS
		btr->numnodes--;
#endif
		x = btr->root;
		btr->root = NODES(btr, x)[0];
		free(x);
	}
	return r;
}

/*
 * remove an existing key from the tree, if the key doesn't exist in it,
 * unexpected results may happen.
 *
 * the s parameter is kinda special, for normal operation you need to pass
 * it as 0, if you want to delete the max node, pass it as 1, or if you
 * want to delete the min node, pass it as 2.
 */
static bt_data_t
nodedeletekey(struct btree *btr, struct btreenode *x, bt_data_t k, int s)
{
	int i;
	int r;
	struct btreenode *xp, *y, *z;
	bt_data_t kp;
	int yn, zn;

	if (x == NULL)
		return 0;

	if (s) {
		if (!x->leaf)
			switch (s) {
			case 1:
				r = 1;
				break;
			case 2:
				r = -1;
				break;
			}
		else
			r = 0;
		switch (s) {
		case 1:
			i = x->n - 1;
			break;
		case 2:
			i = -1;
			break;
		default:
			i = 42;
			break;
		}
	} else
		i = findkindex(btr, x, k, &r);

	/*
	 * Case 1
	 * If the key k is in node x and x is a leaf, delete the key k from x.
	 */
	if (x->leaf) {
		if (s == 2)
			i++;
		kp = KEYS(btr, x)[i];
		memmove(KEYS(btr, x) + i, KEYS(btr, x) + i + 1,
		    (x->n - i - 1) * sizeof k);
		x->n--;
		return kp;
	}

	if (r == 0) {
		/*
		 * Case 2
		 * if the key k is in the node x, and x is an internal node
		 */
		if ((yn = NODES(btr, x)[i]->n) >= btr->t) {
			/*
			 * Case 2a
			 * if the child y that precedes k in node x has at
			 * least t keys, then find the predecessor k' of
			 * k in the subtree rooted at y.  Recursively delete
			 * k', and replace k by k' in x.
			 *
			 * Currently the deletion isn't done in a signle
			 * downward pass was that would require special
			 * unwrapping of the delete function.
			 */
			xp = NODES(btr, x)[i];
			kp = KEYS(btr, x)[i];
			KEYS(btr, x)[i] = nodedeletekey(btr, xp, NULL, 1);
			return kp;
		}
		if ((zn = NODES(btr, x)[i + 1]->n) >= btr->t) {
			/*
			 * Case 2b
			 * if the child z that follows k in node x has at
			 * least t keys, then find the successor k' of
			 * k in the subtree rooted at z.  Recursively delete
			 * k', and replace k by k' in x.
			 *
			 * See above for comment on single downward pass.
			 */
			xp = NODES(btr, x)[i + 1];
			kp = KEYS(btr, x)[i];
			KEYS(btr, x)[i] = nodedeletekey(btr, xp, NULL, 2);
			return kp;
		}
		if (yn == btr->t - 1 && zn == btr->t - 1) {
			/*
			 * Case 2c
			 * if both y and z have only t - 1 keys, merge k
			 * and all of z into y, so that x loses both k and
			 * the pointer to z, and y now contains 2t - 1
			 * keys.  Recersively delete k from y.
			 */
			y = NODES(btr, x)[i];
			z = NODES(btr, x)[i + 1];
			KEYS(btr, y)[y->n++] = k;
			memmove(KEYS(btr, y) + y->n, KEYS(btr, z),
			    z->n * sizeof k);
			memmove(NODES(btr, y) + y->n, NODES(btr, z),
			    (z->n + 1) * sizeof y);
			y->n += z->n;

			memmove(KEYS(btr, x) + i, KEYS(btr, x) + i + 1,
			    (x->n - i - 1) * sizeof k);
			memmove(NODES(btr, x) + i + 1, NODES(btr, x) + i + 2,
			    (x->n - i - 1) * sizeof k);
			x->n--;
			z = freebtreenode(z);
			return nodedeletekey(btr, y, k, s);
		}
	}
	/*
	 * Case 3
	 * if k is not present in internal node x, determine the root x' of
	 * the appropriate subtree that must contain k, if k is in the tree
	 * at all.  If x' has only t - 1 keys, execute step 3a or 3b as
	 * necessary to guarantee that we descend to a node containing at
	 * least t keys.  Finish by recursing on the appropriate child of x.
	 */
	i++;
	/* !x->leaf */
	if ((xp = NODES(btr, x)[i])->n == btr->t - 1) {
		/*
		 * Case 3a
		 * If x' has only t - 1 keys but has a sibling with at
		 * least t keys, give x' an extra key by moving a key
		 * from x down into x', moving a key from x''s immediate
		 * left or right sibling up into x, and moving the
		 * appropriate child from the sibling into x'.
		 */
		if (i > 0 && (y = NODES(btr, x)[i - 1])->n >= btr->t) {
			/* left sibling has t keys */
			memmove(KEYS(btr, xp) + 1, KEYS(btr, xp),
			    xp->n * sizeof k);
			memmove(NODES(btr, xp) + 1, NODES(btr, xp),
			    (xp->n + 1) * sizeof x);
			KEYS(btr, xp)[0] = KEYS(btr, x)[i - 1];
			KEYS(btr, x)[i - 1] = KEYS(btr, y)[y->n - 1];
			NODES(btr, xp)[0] = NODES(btr, y)[y->n];
			y->n--;
			xp->n++;
		} else if (i < x->n &&
		    (y = NODES(btr, x)[i + 1])->n >= btr->t) {
			/* right sibling has t keys */
			KEYS(btr, xp)[xp->n++] = KEYS(btr, x)[i];
			KEYS(btr, x)[i] = KEYS(btr, y)[0];
			NODES(btr, xp)[xp->n] = NODES(btr, y)[0];
			y->n--;
			memmove(KEYS(btr, y), KEYS(btr, y) + 1,
			    y->n * sizeof k);
			memmove(NODES(btr, y), NODES(btr, y) + 1,
			    (y->n + 1) * sizeof x);
		}
		/*
		 * Case 3b
		 * If x' and all of x''s siblings have t - 1 keys, merge
		 * x' with one sibling, which involves moving a key from x
		 * down into the new merged node to become the median key
		 * for that node.
		 */
		  else if (i > 0 &&
		    (y = NODES(btr, x)[i - 1])->n == btr->t - 1) {
			/* merge i with left sibling */
			KEYS(btr, y)[y->n++] = KEYS(btr, x)[i - 1];
			memmove(KEYS(btr, y) + y->n, KEYS(btr, xp),
			    xp->n * sizeof k);
			memmove(NODES(btr, y) + y->n, NODES(btr, xp),
			    (xp->n + 1) * sizeof x);
			y->n += xp->n;
			memmove(KEYS(btr, x) + i - 1, KEYS(btr, x) + i,
			    (x->n - i) * sizeof k);
			memmove(NODES(btr, x) + i, NODES(btr, x) + i + 1,
			    (x->n - i) * sizeof x);
			x->n--;
			free(xp);
			xp = y;
		} else if (i < x->n && (y = NODES(btr, x)[i + 1])->n ==
		    btr->t - 1) {
			/* merge i with right sibling */
			KEYS(btr, xp)[xp->n++] = KEYS(btr, x)[i];
			memmove(KEYS(btr, xp) + xp->n, KEYS(btr, y),
			    y->n * sizeof k);
			memmove(NODES(btr, xp) + xp->n, NODES(btr, y),
			    (y->n + 1) * sizeof x);
			xp->n += y->n;
			memmove(KEYS(btr, x) + i, KEYS(btr, x) + i + 1,
			    (x->n - i - 1) * sizeof k);
			memmove(NODES(btr, x) + i + 1, NODES(btr, x) + i + 2,
			    (x->n - i - 1) * sizeof x);
			x->n--;
			free(y);
		}
	}
	return nodedeletekey(btr, xp, k, s);
}

static struct btreenode *
freebtreenode(struct btreenode *x)
{
	return FREE(x);
}

bt_data_t
bt_max(struct btree *btr)
{
	return findmaxnode(btr, btr->root);
}

bt_data_t
bt_min(struct btree *btr)
{
	return findminnode(btr, btr->root);
}

static bt_data_t
findmaxnode(struct btree *btr, struct btreenode *x)
{
	if (x->leaf)
		return KEYS(btr, x)[x->n - 1];
	else
		return findmaxnode(btr, NODES(btr, x)[x->n]);
}

static bt_data_t
findminnode(struct btree *btr, struct btreenode *x)
{
	if (x->leaf)
		return KEYS(btr, x)[0];
	else
		return findminnode(btr, NODES(btr, x)[0]);
}

bt_data_t
bt_find(struct btree *btr, bt_data_t k)
{
	return findnodekey(btr, btr->root, k);
}

static bt_data_t
findnodekey(struct btree *btr, struct btreenode *x, bt_data_t k)
{
	int i;
	int r;

	while (x != NULL) {
		/*(for (i = 0; i < x->n && (r = btr->cmp(k, KEYS(btr, x)[i])) > 0;
		    i++);*/

		i = findkindex(btr, x, k, &r);

		if (i >= 0 && r == 0)
			return KEYS(btr, x)[i];
		if (x->leaf)
			return NULL;
		x = NODES(btr, x)[i + 1];
	}
	return NULL;
}