diff options
Diffstat (limited to 'libc/stdlib/malloc/avlmacro.h')
| -rw-r--r-- | libc/stdlib/malloc/avlmacro.h | 214 |
1 files changed, 214 insertions, 0 deletions
diff --git a/libc/stdlib/malloc/avlmacro.h b/libc/stdlib/malloc/avlmacro.h new file mode 100644 index 000000000..8050172cc --- /dev/null +++ b/libc/stdlib/malloc/avlmacro.h @@ -0,0 +1,214 @@ +/* MACRO-CODED FAST FIXED AVL TREES IMPLEMENTATION IN C */ +/* COPYRIGHT (C) 1998 VALERY SHCHEDRIN */ +/* IT IS DISTRIBUTED UNDER GLPL (GNU GENERAL LIBRARY PUBLIC LICENSE) */ + +#define balance(objname, pr, root, ht_changed) \ + { \ + objname *p; \ + p = *root; \ + if (p->bal_##pr < -1) \ + { \ + if (p->l_##pr->bal_##pr == 1) \ + { \ + objname *pp; \ + pp=p->l_##pr; *root=p->l_##pr->r_##pr; p->l_##pr = (*root)->r_##pr; \ + (*root)->r_##pr = p; pp->r_##pr = (*root)->l_##pr; \ + p = *root; p->l_##pr = pp; \ + if (p->bal_##pr > 0) p->l_##pr ->bal_##pr = -p->bal_##pr ; \ + else p->l_##pr ->bal_##pr = 0; \ + if (p->bal_##pr < 0) p->r_##pr ->bal_##pr = -p->bal_##pr ; \ + else p->r_##pr ->bal_##pr = 0; \ + p->bal_##pr = 0; \ + ht_changed = 1; \ + } \ + else \ + { \ + ht_changed = (p->l_##pr ->bal_##pr)?1:0; \ + *root = p->l_##pr ; \ + p->l_##pr = (*root)->r_##pr ; (*root)->r_##pr = p; \ + p->bal_##pr = - (++((*root)->bal_##pr )); \ + } \ + } \ + else if (p->bal_##pr > 1) \ + { \ + if (p->r_##pr->bal_##pr == -1) \ + { \ + objname *pp; \ + pp=p->r_##pr ; *root=p->r_##pr ->l_##pr ; p->r_##pr =(*root)->l_##pr ; \ + (*root)->l_##pr = p; pp->l_##pr = (*root)->r_##pr ; \ + p = *root; p->r_##pr = pp; \ + if (p->bal_##pr > 0) p->l_##pr ->bal_##pr = -p->bal_##pr ; \ + else p->l_##pr ->bal_##pr = 0; \ + if (p->bal_##pr < 0) p->r_##pr ->bal_##pr = -p->bal_##pr ; \ + else p->r_##pr ->bal_##pr = 0; \ + p->bal_##pr = 0; \ + ht_changed = 1; \ + } \ + else \ + { \ + ht_changed = (p->r_##pr ->bal_##pr)?1:0; \ + *root = p->r_##pr ; \ + p->r_##pr = (*root)->l_##pr ; (*root)->l_##pr = p; \ + p->bal_##pr = - (--((*root)->bal_##pr )); \ + } \ + } else ht_changed = 0; \ + } + +#define Avl_r_insert_proto(objname, pr, COMPARE) \ + static int Avl_##objname##pr##_r_insert(objname **root) \ + { \ + int i; /* height increase */ \ + if (!*root) \ + { \ + *root = Avl_##objname##pr##_new_node; \ + Avl_##objname##pr##_new_node = NULL; \ + return 1; \ + } \ + COMPARE(i, Avl_##objname##pr##_new_node, *root); \ + \ + if (i < 0) \ + { /* insert into the left subtree */ \ + i = -Avl_##objname##pr##_r_insert(&((*root)->l_##pr)); \ + if (Avl_##objname##pr##_new_node != NULL) return 0; /* already there */ \ + } \ + else if (i > 0) \ + { /* insert into the right subtree */ \ + i = Avl_##objname##pr##_r_insert(&((*root)->r_##pr)); \ + if (Avl_##objname##pr##_new_node != NULL) return 0; /* already there */ \ + } \ + else \ + { /* found */ \ + Avl_##objname##pr##_new_node = *root; \ + return 0; \ + } \ + if (!i) return 0; \ + (*root)->bal_##pr += i; /* update balance factor */ \ + if ((*root)->bal_##pr) \ + { \ + balance(objname,pr,root,i); \ + return 1-i; \ + } \ + else return 0; \ + } + +#define Avl_r_delete_proto(objname,pr,COMPARE) \ + static int Avl_##objname##pr##_r_delete(objname **root) \ + { \ + int i; /* height decrease */ \ + \ + if (!*root) return 0; /* not found */ \ + \ + COMPARE(i, Avl_##objname##pr##_new_node, *root); \ + \ + if (i < 0) \ + i = -Avl_##objname##pr##_r_delete(&((*root)->l_##pr)); \ + else if (i > 0) \ + i = Avl_##objname##pr##_r_delete(&((*root)->r_##pr)); \ + else \ + { \ + if (!(*root)->l_##pr) \ + { \ + *root = (*root)->r_##pr; \ + return 1; \ + } \ + else if (!(*root)->r_##pr) \ + { \ + *root = (*root)->l_##pr; \ + return 1; \ + } \ + else \ + { \ + i = Avl_##objname##pr##_r_delfix(&((*root)->r_##pr)); \ + Avl_##objname##pr##_new_node->l_##pr = (*root)->l_##pr; \ + Avl_##objname##pr##_new_node->r_##pr = (*root)->r_##pr; \ + Avl_##objname##pr##_new_node->bal_##pr = (*root)->bal_##pr; \ + *root = Avl_##objname##pr##_new_node; \ + } \ + } \ + if (!i) return 0; \ + (*root)->bal_##pr -= i; \ + if ((*root)->bal_##pr) \ + { \ + balance(objname,pr,root,i); \ + return i; \ + } \ + return 1; \ + } + +#define Avl_r_delfix_proto(objname,pr) \ + static int Avl_##objname##pr##_r_delfix(objname **root) \ + { \ + int i; /* height decrease */ \ + \ + if (!(*root)->l_##pr) \ + { \ + Avl_##objname##pr##_new_node = *root; \ + *root = (*root)->r_##pr; \ + return 1; \ + } \ + i = -Avl_##objname##pr##_r_delfix(&((*root)->l_##pr)); \ + if (!i) return 0; \ + (*root)->bal_##pr -= i; \ + if ((*root)->bal_##pr) \ + { \ + balance(objname,pr,root,i); \ + return i; \ + } \ + return 1; \ + } + +#define Avl_ins_proto(alias,objname,pr) \ + static objname *##alias##_ins(objname *data) \ + { \ + Avl_##objname##pr##_new_node = data; \ + (data)->l_##pr = NULL; \ + (data)->r_##pr = NULL; \ + (data)->bal_##pr = 0; \ + Avl_##objname##pr##_r_insert(&Avl_##objname##pr##_tree); \ + if (Avl_##objname##pr##_new_node) \ + return Avl_##objname##pr##_new_node; \ + return NULL; \ + } + +#define Avl_del_proto(alias,objname,pr) \ + static void alias##_del(objname *data) \ + { \ + Avl_##objname##pr##_new_node = data; \ + Avl_##objname##pr##_r_delete(&Avl_##objname##pr##_tree); \ + } + +#define Avl_replace_proto(alias,objname,pr,COMPARE) \ + static void alias##_replace(objname *data) \ + { \ + objname **p = &Avl_##objname##pr##_tree; \ + int cmp; \ + while (*p) \ + { \ + COMPARE(cmp, data, *p); \ + if (cmp < 0) \ + p = &((*p)->l_##pr); \ + else if (cmp > 0) \ + p = &((*p)->r_##pr); \ + else \ + { \ + (data)->l_##pr = (*p)->l_##pr; \ + (data)->r_##pr = (*p)->r_##pr; \ + (data)->bal_##pr = (*p)->bal_##pr; \ + *p = data; \ + return; \ + } \ + } \ + } + +#define Avl_Root(objname,pr) Avl_##objname##pr##_tree + +#define Avl_Tree(alias,objname,pr,COMPARE) \ +static objname *Avl_##objname##pr##_tree = NULL; \ +static objname *Avl_##objname##pr##_new_node; \ +Avl_r_insert_proto(objname,pr,COMPARE) \ +Avl_r_delfix_proto(objname,pr) \ +Avl_r_delete_proto(objname,pr,COMPARE) \ +Avl_ins_proto(alias,objname,pr) \ +Avl_del_proto(alias,objname,pr) \ +Avl_replace_proto(alias,objname,pr,COMPARE) + |