From 7415018e055da96e94fa61c43a5227555e8e6ba5 Mon Sep 17 00:00:00 2001 From: Eric Andersen Date: Fri, 12 Jan 2001 09:42:21 +0000 Subject: Manuel Novoa III modified malloc.c and avlmacro.h to reduce code size by using functions instead on Inlining (size vas speed tradeoff). I ran the results through indent. Looking pretty good IMHO. --- libc/stdlib/malloc/avlmacro.h | 132 +++++++++++++++++++++++------------------- 1 file changed, 72 insertions(+), 60 deletions(-) (limited to 'libc/stdlib/malloc/avlmacro.h') diff --git a/libc/stdlib/malloc/avlmacro.h b/libc/stdlib/malloc/avlmacro.h index 8050172cc..cce2c38f3 100644 --- a/libc/stdlib/malloc/avlmacro.h +++ b/libc/stdlib/malloc/avlmacro.h @@ -2,9 +2,21 @@ /* COPYRIGHT (C) 1998 VALERY SHCHEDRIN */ /* IT IS DISTRIBUTED UNDER GLPL (GNU GENERAL LIBRARY PUBLIC LICENSE) */ -#define balance(objname, pr, root, ht_changed) \ +/* + * Manuel Novoa III Jan 2001 + * + * Modified to decrease object size. + * Tree balancing is now done in a fuction rather than inline. + * Removed common code in balance by use of a goto. + * Added macro Avl_Tree_no_replace since ptrs_replace was not used. + * Prepended may symbols with "__" for possible conversion to extern. + */ + +#define __Avl_balance_proto(objname, pr, root) \ + static int __Avl_##objname##pr##balance(objname **root) \ { \ objname *p; \ + int ht_changed; \ p = *root; \ if (p->bal_##pr < -1) \ { \ @@ -14,12 +26,7 @@ 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; \ + goto pr_common_ht_changed; \ } \ else \ { \ @@ -37,6 +44,7 @@ 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; \ + pr_common_ht_changed: \ 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 ; \ @@ -52,58 +60,61 @@ p->bal_##pr = - (--((*root)->bal_##pr )); \ } \ } else ht_changed = 0; \ + return ht_changed; \ } -#define Avl_r_insert_proto(objname, pr, COMPARE) \ - static int Avl_##objname##pr##_r_insert(objname **root) \ +#define balance(objname, pr, root) \ + __Avl_##objname##pr##balance(root) + +#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; \ + *root = __Avl_##objname##pr##_new_node; \ + __Avl_##objname##pr##_new_node = NULL; \ return 1; \ } \ - COMPARE(i, Avl_##objname##pr##_new_node, *root); \ + 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 */ \ + 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 */ \ + 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; \ + __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; \ + return 1 - balance(objname,pr,root); \ } \ else return 0; \ } -#define Avl_r_delete_proto(objname,pr,COMPARE) \ - static int Avl_##objname##pr##_r_delete(objname **root) \ +#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); \ + COMPARE(i, __Avl_##objname##pr##_new_node, *root); \ \ if (i < 0) \ - i = -Avl_##objname##pr##_r_delete(&((*root)->l_##pr)); \ + i = -__Avl_##objname##pr##_r_delete(&((*root)->l_##pr)); \ else if (i > 0) \ - i = Avl_##objname##pr##_r_delete(&((*root)->r_##pr)); \ + i = __Avl_##objname##pr##_r_delete(&((*root)->r_##pr)); \ else \ { \ if (!(*root)->l_##pr) \ @@ -118,69 +129,67 @@ } \ 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; \ + 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 balance(objname,pr,root); \ } \ return 1; \ } -#define Avl_r_delfix_proto(objname,pr) \ - static int Avl_##objname##pr##_r_delfix(objname **root) \ +#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; \ + __Avl_##objname##pr##_new_node = *root; \ *root = (*root)->r_##pr; \ return 1; \ } \ - i = -Avl_##objname##pr##_r_delfix(&((*root)->l_##pr)); \ + 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 balance(objname,pr,root); \ } \ return 1; \ } -#define Avl_ins_proto(alias,objname,pr) \ - static objname *##alias##_ins(objname *data) \ +#define __Avl_ins_proto(alias,objname,pr) \ + objname *__##alias##_ins(objname *data) \ { \ - Avl_##objname##pr##_new_node = 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; \ + __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) \ +#define __Avl_del_proto(alias,objname,pr) \ + void __##alias##_del(objname *data) \ { \ - Avl_##objname##pr##_new_node = data; \ - Avl_##objname##pr##_r_delete(&Avl_##objname##pr##_tree); \ + __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) \ +#define __Avl_replace_proto(alias,objname,pr,COMPARE) \ + void __##alias##_replace(objname *data) \ { \ - objname **p = &Avl_##objname##pr##_tree; \ + objname **p = &__Avl_##objname##pr##_tree; \ int cmp; \ while (*p) \ { \ @@ -200,15 +209,18 @@ } \ } -#define Avl_Root(objname,pr) Avl_##objname##pr##_tree +#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) +#define Avl_Tree_no_replace(alias,objname,pr,COMPARE) \ +objname *__Avl_##objname##pr##_tree = NULL; \ +static objname *__Avl_##objname##pr##_new_node; \ +__Avl_balance_proto(objname, pr, root) \ +__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) +#define Avl_Tree(alias,objname,pr,COMPARE) \ +Avl_Tree_no_replace(alias,objname,pr,COMPARE) \ +__Avl_replace_proto(alias,objname,pr,COMPARE) -- cgit v1.2.3