diff options
author | H. Peter Anvin <hpa@zytor.com> | 2008-10-30 10:58:28 -0700 |
---|---|---|
committer | H. Peter Anvin <hpa@zytor.com> | 2008-10-30 10:58:28 -0700 |
commit | e8873121aadbbb465c0c48da3c56b47a6a5f1d68 (patch) | |
tree | 9333fb01193d78f0f02050359f8acfeb7cfc672a | |
parent | 9656a581cdb6f505c9adc6b5158b395c21b5c43a (diff) | |
download | nasm-e8873121aadbbb465c0c48da3c56b47a6a5f1d68.tar.gz |
rbtree: drop the data pointer; instead rely on being embedded
Drop the data pointer, and instead assume the struct rbtree will be
embedded in a bigger data structure (to be extracted via
container_of()).
Signed-off-by: H. Peter Anvin <hpa@zytor.com>
-rw-r--r-- | Makefile.in | 2 | ||||
-rw-r--r-- | Mkfiles/msvc.mak | 2 | ||||
-rw-r--r-- | Mkfiles/netware.mak | 2 | ||||
-rw-r--r-- | Mkfiles/openwcom.mak | 2 | ||||
-rw-r--r-- | Mkfiles/owlinux.mak | 2 | ||||
-rw-r--r-- | rbtree.c | 28 | ||||
-rw-r--r-- | rbtree.h | 7 |
7 files changed, 16 insertions, 29 deletions
diff --git a/Makefile.in b/Makefile.in index efefe966..e4fe5177 100644 --- a/Makefile.in +++ b/Makefile.in @@ -319,7 +319,7 @@ preproc.$(O): preproc.c compiler.h config.h hashtbl.h insnsi.h nasm.h \ version.h quote.$(O): quote.c compiler.h config.h nasmlib.h quote.h raa.$(O): raa.c compiler.h config.h nasmlib.h raa.h -rbtree.$(O): rbtree.c compiler.h config.h nasmlib.h rbtree.h +rbtree.$(O): rbtree.c compiler.h config.h rbtree.h regdis.$(O): regdis.c regdis.h regs.h regflags.$(O): regflags.c compiler.h config.h insnsi.h nasm.h nasmlib.h \ pptok.h preproc.h regs.h tables.h version.h diff --git a/Mkfiles/msvc.mak b/Mkfiles/msvc.mak index b509848f..4604be87 100644 --- a/Mkfiles/msvc.mak +++ b/Mkfiles/msvc.mak @@ -252,7 +252,7 @@ preproc.$(O): preproc.c compiler.h hashtbl.h insnsi.h nasm.h nasmlib.h \ pptok.h preproc.h quote.h regs.h stdscan.h tables.h tokens.h version.h quote.$(O): quote.c compiler.h nasmlib.h quote.h raa.$(O): raa.c compiler.h nasmlib.h raa.h -rbtree.$(O): rbtree.c compiler.h nasmlib.h rbtree.h +rbtree.$(O): rbtree.c compiler.h rbtree.h regdis.$(O): regdis.c regdis.h regs.h regflags.$(O): regflags.c compiler.h insnsi.h nasm.h nasmlib.h pptok.h \ preproc.h regs.h tables.h version.h diff --git a/Mkfiles/netware.mak b/Mkfiles/netware.mak index a64919bb..715106a6 100644 --- a/Mkfiles/netware.mak +++ b/Mkfiles/netware.mak @@ -194,7 +194,7 @@ preproc.o: preproc.c compiler.h config.h hashtbl.h insnsi.h nasm.h nasmlib.h \ pptok.h preproc.h quote.h regs.h stdscan.h tables.h tokens.h version.h quote.o: quote.c compiler.h config.h nasmlib.h quote.h raa.o: raa.c compiler.h config.h nasmlib.h raa.h -rbtree.o: rbtree.c compiler.h config.h nasmlib.h rbtree.h +rbtree.o: rbtree.c compiler.h config.h rbtree.h regdis.o: regdis.c regdis.h regs.h regflags.o: regflags.c compiler.h config.h insnsi.h nasm.h nasmlib.h pptok.h \ preproc.h regs.h tables.h version.h diff --git a/Mkfiles/openwcom.mak b/Mkfiles/openwcom.mak index 001d6fe9..72d72e30 100644 --- a/Mkfiles/openwcom.mak +++ b/Mkfiles/openwcom.mak @@ -281,7 +281,7 @@ preproc.$(O): preproc.c compiler.h hashtbl.h insnsi.h nasm.h nasmlib.h & pptok.h preproc.h quote.h regs.h stdscan.h tables.h tokens.h version.h quote.$(O): quote.c compiler.h nasmlib.h quote.h raa.$(O): raa.c compiler.h nasmlib.h raa.h -rbtree.$(O): rbtree.c compiler.h nasmlib.h rbtree.h +rbtree.$(O): rbtree.c compiler.h rbtree.h regdis.$(O): regdis.c regdis.h regs.h regflags.$(O): regflags.c compiler.h insnsi.h nasm.h nasmlib.h pptok.h & preproc.h regs.h tables.h version.h diff --git a/Mkfiles/owlinux.mak b/Mkfiles/owlinux.mak index c4234216..8a8ac902 100644 --- a/Mkfiles/owlinux.mak +++ b/Mkfiles/owlinux.mak @@ -291,7 +291,7 @@ preproc.$(O): preproc.c compiler.h hashtbl.h insnsi.h nasm.h nasmlib.h \ pptok.h preproc.h quote.h regs.h stdscan.h tables.h tokens.h version.h quote.$(O): quote.c compiler.h nasmlib.h quote.h raa.$(O): raa.c compiler.h nasmlib.h raa.h -rbtree.$(O): rbtree.c compiler.h nasmlib.h rbtree.h +rbtree.$(O): rbtree.c compiler.h rbtree.h regdis.$(O): regdis.c regdis.h regs.h regflags.$(O): regflags.c compiler.h insnsi.h nasm.h nasmlib.h pptok.h \ preproc.h regs.h tables.h version.h @@ -3,15 +3,14 @@ * * Simple implementation of a left-leaning red-black tree with 64-bit * integer keys. The search operation will return the highest node <= - * the key; only search, insert, and full-tree deletion is supported, - * but additional standard llrbtree operations can be coded up at will. + * the key; only search and insert are supported, but additional + * standard llrbtree operations can be coded up at will. * * See http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf for * information about left-leaning red-black trees. */ #include "rbtree.h" -#include "nasmlib.h" const struct rbtree *rb_search(const struct rbtree *tree, uint64_t key) { @@ -62,24 +61,20 @@ static void color_flip(struct rbtree *h) h->right->red = !h->right->red; } -struct rbtree *rb_insert(struct rbtree *tree, uint64_t key, void *data) +struct rbtree *rb_insert(struct rbtree *tree, struct rbtree *node) { if (!tree) { - struct rbtree *node = nasm_malloc(sizeof *node); - - node->key = key; - node->data = data; - node->red = true; + node->red = true; return node; } if (is_red(tree->left) && is_red(tree->right)) color_flip(tree); - if (key < tree->key) - tree->left = rb_insert(tree->left, key, data); + if (node->key < tree->key) + tree->left = rb_insert(tree->left, node); else - tree->right = rb_insert(tree->right, key, data); + tree->right = rb_insert(tree->right, node); if (is_red(tree->right)) tree = rotate_left(tree); @@ -89,12 +84,3 @@ struct rbtree *rb_insert(struct rbtree *tree, uint64_t key, void *data) return tree; } - -void rb_free(struct rbtree *tree) -{ - if (tree) { - rb_free(tree->left); - rb_free(tree->right); - nasm_free(tree); - } -} @@ -4,15 +4,16 @@ #include "compiler.h" #include <inttypes.h> +/* This structure should be embedded in a larger data structure; + the final output from rb_search() can then be converted back + to the larger data structure via container_of(). */ struct rbtree { uint64_t key; - void *data; struct rbtree *left, *right; bool red; }; -struct rbtree *rb_insert(struct rbtree *, uint64_t, void *); +struct rbtree *rb_insert(struct rbtree *, struct rbtree *); const struct rbtree *rb_search(const struct rbtree *, uint64_t); -void rb_free(struct rbtree *); #endif /* NASM_RBTREE_H */ |