00001
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036 #include "oq_alloc.h"
00037 #include "avl.h"
00038
00039
00040 #ifdef __KERNEL__
00041 # include <linux/kernel.h>
00042 # define OQ_PRINT(fmt, args...) printk(KERN_INFO fmt, ## args)
00043 # define OQ_PRINTLN(fmt, args...) printk(KERN_INFO "orbisquartus: " fmt, ## args)
00044 #else
00045 # include <stdio.h>
00046 # define OQ_PRINT(fmt, args...) fprintf(stderr, fmt, ## args)
00047 # define OQ_PRINTLN(fmt, args...) fprintf(stderr, fmt, ## args)
00048 #endif
00049
00050
00051 enum { LEFT = 0, RIGHT = 1 };
00052
00053
00054 static inline int maximum(int a, int b)
00055 {
00056 return a > b ? a :b;
00057 }
00058
00059 static inline int height(struct avlnode *tree)
00060 {
00061 if (tree == NULL)
00062 return -1;
00063 return tree->height;
00064 }
00065
00066
00067 static struct avlnode *rotate(struct avlnode *node, int direction)
00068 {
00069 struct avlnode *child;
00070 if (node == NULL)
00071 return NULL;
00072
00073 if (direction == LEFT) {
00074 child = node->right;
00075 node->right = child->left;
00076 child->left = node;
00077 } else {
00078 child = node->left;
00079 node->left = child->right;
00080 child->right = node;
00081 }
00082
00083 node->height = 1 + maximum(height(node->left), height(node->right));
00084 child->height = 1 + maximum(height(child->left), height(child->right));
00085
00086 return child;
00087 }
00088
00089
00090 static struct avlnode *double_rotate(struct avlnode *node, int direction)
00091 {
00092 struct avlnode *child, *parent;
00093 if (node == NULL)
00094 return NULL;
00095
00096 if (direction == LEFT) {
00097 child = node->right;
00098 parent = child->left;
00099 child->left = parent->right;
00100 parent->right = child;
00101 node->right = parent->left;
00102 parent->left = node;
00103 } else {
00104 child = node->left;
00105 parent = child->right;
00106 child->right = parent->left;
00107 parent->left = child;
00108 node->left = parent->right;
00109 parent->right = node;
00110 }
00111 parent->height = 1 + maximum(height(parent->left),
00112 height(parent->right));
00113 node->height = 1 + maximum(height(node->left), height(node->right));
00114 child->height = 1 + maximum(height(child->left), height(child->right));
00115
00116 return parent;
00117 }
00118
00119
00120
00121
00122
00123 unsigned long avl_size(struct avltree *tree)
00124 {
00125 unsigned long i = 0;
00126 struct avlnode *list = avl_find_min(tree);
00127
00128 if (list == NULL)
00129 return i;
00130
00131 for (; list != NULL; list = list->next)
00132 i++;
00133
00134 return i;
00135 }
00136
00137
00138 struct avlnode *avl_find(unsigned long key, struct avltree *tree)
00139 {
00140 int i = 0;
00141 struct avlnode *node;
00142
00143 if (tree == NULL)
00144 return NULL;
00145 node = tree->root;
00146
00147 while (node != NULL) {
00148 if (key == node->key)
00149 break;
00150 if (key < node->key)
00151 node = node->left;
00152 else if (key > node->key)
00153 node = node->right;
00154 i++;
00155 }
00156 return node;
00157 }
00158
00159
00160 void *avl_retrieve(unsigned long key, struct avltree *tree)
00161 {
00162 struct avlnode *node;
00163 if ((node = avl_find(key, tree)) == NULL)
00164 return NULL;
00165 return node->element;
00166 }
00167
00168
00169 struct avlnode *avl_find_min(struct avltree *tree)
00170 {
00171 struct avlnode *node;
00172
00173 if (tree == NULL)
00174 return NULL;
00175
00176 node = tree->root;
00177 if (node == NULL)
00178 return NULL;
00179
00180 while (node->left != NULL)
00181 node = node->left;
00182
00183 return node;
00184 }
00185
00186
00187 struct avlnode *avl_find_max(struct avltree *tree)
00188 {
00189 struct avlnode *node;
00190
00191 if (tree == NULL)
00192 return NULL;
00193
00194 node = tree->root;
00195 if (node == NULL)
00196 return NULL;
00197
00198 while (node->right != NULL)
00199 node = node->right;
00200
00201 return node;
00202 }
00203
00204
00205
00206 static struct avlnode *__avl_ins(void *elt, unsigned long key,
00207 struct avlnode *tree, struct avlnode *parent,
00208 int direction, int *error)
00209 {
00210 if (tree == NULL) {
00211 tree = (struct avlnode *) OQ_ALLOCATE(sizeof(struct avlnode));
00212 if (tree == NULL) {
00213 *error = 1;
00214 return NULL;
00215 }
00216 tree->key = key;
00217 tree->element = elt;
00218 tree->left = tree->right = NULL;
00219
00220 if (direction == LEFT) {
00221 tree->next = parent;
00222 tree->prev = parent->prev;
00223 if (parent->prev != NULL)
00224 parent->prev->next = tree;
00225 parent->prev = tree;
00226 } else if (direction == RIGHT) {
00227 tree->next = parent->next;
00228 tree->prev = parent;
00229 if (parent->next != NULL)
00230 parent->next->prev = tree;
00231 parent->next = tree;
00232 } else {
00233 tree->next = tree->prev = NULL;
00234 }
00235 } else if (key < tree->key) {
00236 tree->left = __avl_ins(elt, key, tree->left, tree,
00237 LEFT, error);
00238
00239 if (height(tree->left) - height(tree->right) >= 2) {
00240 if (height(tree->left->left) -
00241 height(tree->left->right) >= 1)
00242 tree = rotate(tree, RIGHT);
00243 else if (height(tree->left->right) -
00244 height(tree->left->left) >= 1)
00245 tree = double_rotate(tree, RIGHT);
00246 }
00247 } else if (key > tree->key) {
00248 tree->right = __avl_ins(elt, key, tree->right, tree,
00249 RIGHT, error);
00250
00251 if (height(tree->right) - height(tree->left) >= 2) {
00252 if (height(tree->right->right) -
00253 height(tree->right->left) >= 1)
00254 tree = rotate(tree, LEFT);
00255 else if (height(tree->right->left) -
00256 height(tree->right->right) >= 1)
00257 tree = double_rotate(tree, LEFT);
00258 }
00259 } else if (key == tree->key) {
00260 *error = 1;
00261 }
00262
00263 tree->height = 1 + maximum(height(tree->left), height(tree->right));
00264 return tree;
00265 }
00266
00267
00268
00269 int avl_insert(void *elt, unsigned long key, struct avltree *tree)
00270 {
00271 int error = 0;
00272 if (tree == NULL || elt == NULL)
00273 return -1;
00274
00275 tree->root = __avl_ins(elt, key, tree->root, NULL, -1, &error);
00276 return error;
00277 }
00278
00279
00280
00281 static struct avlnode *__avl_del(void *elt, unsigned long key,
00282 struct avlnode *tree, struct avlnode *parent,
00283 int direction, int *error)
00284 {
00285 if (tree == NULL) {
00286 *error = 1;
00287 return NULL;
00288 } else if (key == tree->key) {
00289 if (tree->next != NULL)
00290 tree->next->prev = tree->prev;
00291 if (tree->prev != NULL)
00292 tree->prev->next = tree->next;
00293 if (direction == LEFT)
00294 parent->left = NULL;
00295 else if (direction == RIGHT)
00296 parent->right = NULL;
00297 OQ_FREE(tree);
00298 return NULL;
00299 } else if (key < tree->key) {
00300 tree->left = __avl_del(elt, key, tree->right, tree,
00301 LEFT, error);
00302
00303 if (height(tree->left) - height(tree->right) >= 2) {
00304 if (height(tree->left->left) -
00305 height(tree->left->right) >= 1)
00306 tree = rotate(tree, RIGHT);
00307 else if (height(tree->left->right) -
00308 height(tree->left->left) >= 1)
00309 tree = double_rotate(tree, RIGHT);
00310 }
00311 } else if (key > tree->key) {
00312 tree->right = __avl_del(elt, key, tree->right, tree,
00313 RIGHT, error);
00314
00315 if (height(tree->right) - height(tree->left) >= 2) {
00316 if (height(tree->right->right) -
00317 height(tree->right->left) >= 1)
00318 tree = rotate(tree, LEFT);
00319 else if (height(tree->right->left) -
00320 height(tree->right->right) >= 1)
00321 tree = double_rotate(tree, LEFT);
00322 }
00323 }
00324
00325 tree->height = 1 + maximum(height(tree->left), height(tree->right));
00326 return tree;
00327 }
00328
00329
00330 int avl_delete(void *elt, unsigned long key, struct avltree *tree)
00331 {
00332 int error = 0;
00333 if (tree == NULL)
00334 return -1;
00335
00336 tree->root = __avl_del(elt, key, tree->root, NULL, -1, &error);
00337 return error;
00338 }
00339
00340
00341
00342 void destroy_avltree(struct avlnode *root)
00343 {
00344 if (root != NULL) {
00345 destroy_avltree(root->left);
00346 destroy_avltree(root->right);
00347 OQ_FREE(root);
00348 }
00349 }
00350
00351
00352
00353
00354
00355 static void __avl_print(struct avlnode *tree, int direction, int indent)
00356 {
00357 int i;
00358 if (tree != NULL) {
00359 __avl_print(tree->right, RIGHT, indent + 1);
00360
00361 for (i = 0; i < indent - 1; i++)
00362 OQ_PRINT(" ");
00363 if (indent) {
00364 if (direction == LEFT)
00365 OQ_PRINT(" \\-- ");
00366 else
00367 OQ_PRINT(" /-- ");
00368 }
00369 OQ_PRINT("%ld\n", tree->key);
00370
00371 __avl_print(tree->left, LEFT, indent + 1);
00372 }
00373 }
00374
00375 void avl_print(struct avltree *tree)
00376 {
00377 if (tree == NULL)
00378 return;
00379
00380 OQ_PRINTLN("AVL tree: \n");
00381 __avl_print(tree->root, -1, 0);
00382 }
00383
00384
00385 void avl_print_list(struct avltree *tree)
00386 {
00387 int i;
00388 struct avlnode *list = avl_find_min(tree);
00389
00390 if (list == NULL)
00391 return;
00392
00393 OQ_PRINTLN("Linked list: %ld ", list->key);
00394 for (i = 1, list = list->next; list != NULL; list = list->next, i++)
00395 OQ_PRINT("-> %ld ", list->key);
00396 OQ_PRINT("\n\n");
00397 }