Annotation of embedaddon/lighttpd/src/splaytree.c, revision 1.1
1.1 ! misho 1: /*
! 2: An implementation of top-down splaying with sizes
! 3: D. Sleator <sleator@cs.cmu.edu>, January 1994.
! 4:
! 5: This extends top-down-splay.c to maintain a size field in each node.
! 6: This is the number of nodes in the subtree rooted there. This makes
! 7: it possible to efficiently compute the rank of a key. (The rank is
! 8: the number of nodes to the left of the given key.) It it also
! 9: possible to quickly find the node of a given rank. Both of these
! 10: operations are illustrated in the code below. The remainder of this
! 11: introduction is taken from top-down-splay.c.
! 12:
! 13: "Splay trees", or "self-adjusting search trees" are a simple and
! 14: efficient data structure for storing an ordered set. The data
! 15: structure consists of a binary tree, with no additional fields. It
! 16: allows searching, insertion, deletion, deletemin, deletemax,
! 17: splitting, joining, and many other operations, all with amortized
! 18: logarithmic performance. Since the trees adapt to the sequence of
! 19: requests, their performance on real access patterns is typically even
! 20: better. Splay trees are described in a number of texts and papers
! 21: [1,2,3,4].
! 22:
! 23: The code here is adapted from simple top-down splay, at the bottom of
! 24: page 669 of [2]. It can be obtained via anonymous ftp from
! 25: spade.pc.cs.cmu.edu in directory /usr/sleator/public.
! 26:
! 27: The chief modification here is that the splay operation works even if the
! 28: item being splayed is not in the tree, and even if the tree root of the
! 29: tree is NULL. So the line:
! 30:
! 31: t = splay(i, t);
! 32:
! 33: causes it to search for item with key i in the tree rooted at t. If it's
! 34: there, it is splayed to the root. If it isn't there, then the node put
! 35: at the root is the last one before NULL that would have been reached in a
! 36: normal binary search for i. (It's a neighbor of i in the tree.) This
! 37: allows many other operations to be easily implemented, as shown below.
! 38:
! 39: [1] "Data Structures and Their Algorithms", Lewis and Denenberg,
! 40: Harper Collins, 1991, pp 243-251.
! 41: [2] "Self-adjusting Binary Search Trees" Sleator and Tarjan,
! 42: JACM Volume 32, No 3, July 1985, pp 652-686.
! 43: [3] "Data Structure and Algorithm Analysis", Mark Weiss,
! 44: Benjamin Cummins, 1992, pp 119-130.
! 45: [4] "Data Structures, Algorithms, and Performance", Derick Wood,
! 46: Addison-Wesley, 1993, pp 367-375
! 47: */
! 48:
! 49: #include "splaytree.h"
! 50: #include <stdlib.h>
! 51: #include <assert.h>
! 52:
! 53: #define compare(i,j) ((i)-(j))
! 54: /* This is the comparison. */
! 55: /* Returns <0 if i<j, =0 if i=j, and >0 if i>j */
! 56:
! 57: #define node_size splaytree_size
! 58:
! 59: /* Splay using the key i (which may or may not be in the tree.)
! 60: * The starting root is t, and the tree used is defined by rat
! 61: * size fields are maintained */
! 62: splay_tree * splaytree_splay (splay_tree *t, int i) {
! 63: splay_tree N, *l, *r, *y;
! 64: int comp, l_size, r_size;
! 65:
! 66: if (t == NULL) return t;
! 67: N.left = N.right = NULL;
! 68: l = r = &N;
! 69: l_size = r_size = 0;
! 70:
! 71: for (;;) {
! 72: comp = compare(i, t->key);
! 73: if (comp < 0) {
! 74: if (t->left == NULL) break;
! 75: if (compare(i, t->left->key) < 0) {
! 76: y = t->left; /* rotate right */
! 77: t->left = y->right;
! 78: y->right = t;
! 79: t->size = node_size(t->left) + node_size(t->right) + 1;
! 80: t = y;
! 81: if (t->left == NULL) break;
! 82: }
! 83: r->left = t; /* link right */
! 84: r = t;
! 85: t = t->left;
! 86: r_size += 1+node_size(r->right);
! 87: } else if (comp > 0) {
! 88: if (t->right == NULL) break;
! 89: if (compare(i, t->right->key) > 0) {
! 90: y = t->right; /* rotate left */
! 91: t->right = y->left;
! 92: y->left = t;
! 93: t->size = node_size(t->left) + node_size(t->right) + 1;
! 94: t = y;
! 95: if (t->right == NULL) break;
! 96: }
! 97: l->right = t; /* link left */
! 98: l = t;
! 99: t = t->right;
! 100: l_size += 1+node_size(l->left);
! 101: } else {
! 102: break;
! 103: }
! 104: }
! 105: l_size += node_size(t->left); /* Now l_size and r_size are the sizes of */
! 106: r_size += node_size(t->right); /* the left and right trees we just built.*/
! 107: t->size = l_size + r_size + 1;
! 108:
! 109: l->right = r->left = NULL;
! 110:
! 111: /* The following two loops correct the size fields of the right path */
! 112: /* from the left child of the root and the right path from the left */
! 113: /* child of the root. */
! 114: for (y = N.right; y != NULL; y = y->right) {
! 115: y->size = l_size;
! 116: l_size -= 1+node_size(y->left);
! 117: }
! 118: for (y = N.left; y != NULL; y = y->left) {
! 119: y->size = r_size;
! 120: r_size -= 1+node_size(y->right);
! 121: }
! 122:
! 123: l->right = t->left; /* assemble */
! 124: r->left = t->right;
! 125: t->left = N.right;
! 126: t->right = N.left;
! 127:
! 128: return t;
! 129: }
! 130:
! 131: splay_tree * splaytree_insert(splay_tree * t, int i, void *data) {
! 132: /* Insert key i into the tree t, if it is not already there. */
! 133: /* Return a pointer to the resulting tree. */
! 134: splay_tree * new;
! 135:
! 136: if (t != NULL) {
! 137: t = splaytree_splay(t, i);
! 138: if (compare(i, t->key)==0) {
! 139: return t; /* it's already there */
! 140: }
! 141: }
! 142: new = (splay_tree *) malloc (sizeof (splay_tree));
! 143: assert(new);
! 144: if (t == NULL) {
! 145: new->left = new->right = NULL;
! 146: } else if (compare(i, t->key) < 0) {
! 147: new->left = t->left;
! 148: new->right = t;
! 149: t->left = NULL;
! 150: t->size = 1+node_size(t->right);
! 151: } else {
! 152: new->right = t->right;
! 153: new->left = t;
! 154: t->right = NULL;
! 155: t->size = 1+node_size(t->left);
! 156: }
! 157: new->key = i;
! 158: new->data = data;
! 159: new->size = 1 + node_size(new->left) + node_size(new->right);
! 160: return new;
! 161: }
! 162:
! 163: splay_tree * splaytree_delete(splay_tree *t, int i) {
! 164: /* Deletes i from the tree if it's there. */
! 165: /* Return a pointer to the resulting tree. */
! 166: splay_tree * x;
! 167: int tsize;
! 168:
! 169: if (t==NULL) return NULL;
! 170: tsize = t->size;
! 171: t = splaytree_splay(t, i);
! 172: if (compare(i, t->key) == 0) { /* found it */
! 173: if (t->left == NULL) {
! 174: x = t->right;
! 175: } else {
! 176: x = splaytree_splay(t->left, i);
! 177: x->right = t->right;
! 178: }
! 179: free(t);
! 180: if (x != NULL) {
! 181: x->size = tsize-1;
! 182: }
! 183: return x;
! 184: } else {
! 185: return t; /* It wasn't there */
! 186: }
! 187: }
! 188:
! 189: #if 0
! 190: static splay_tree *find_rank(int r, splay_tree *t) {
! 191: /* Returns a pointer to the node in the tree with the given rank. */
! 192: /* Returns NULL if there is no such node. */
! 193: /* Does not change the tree. To guarantee logarithmic behavior, */
! 194: /* the node found here should be splayed to the root. */
! 195: int lsize;
! 196: if ((r < 0) || (r >= node_size(t))) return NULL;
! 197: for (;;) {
! 198: lsize = node_size(t->left);
! 199: if (r < lsize) {
! 200: t = t->left;
! 201: } else if (r > lsize) {
! 202: r = r - lsize -1;
! 203: t = t->right;
! 204: } else {
! 205: return t;
! 206: }
! 207: }
! 208: }
! 209: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to splaytree.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / lighttpd / src