From e8873121aadbbb465c0c48da3c56b47a6a5f1d68 Mon Sep 17 00:00:00 2001 From: "H. Peter Anvin" Date: Thu, 30 Oct 2008 10:58:28 -0700 Subject: [PATCH] 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 --- Makefile.in | 2 +- Mkfiles/msvc.mak | 2 +- Mkfiles/netware.mak | 2 +- Mkfiles/openwcom.mak | 2 +- Mkfiles/owlinux.mak | 2 +- rbtree.c | 28 +++++++--------------------- 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 diff --git a/rbtree.c b/rbtree.c index adf2b8b4..7e13bffb 100644 --- a/rbtree.c +++ b/rbtree.c @@ -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); - } -} diff --git a/rbtree.h b/rbtree.h index 3b45428f..d24daf35 100644 --- a/rbtree.h +++ b/rbtree.h @@ -4,15 +4,16 @@ #include "compiler.h" #include +/* 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 */ -- 2.11.4.GIT