From 3e364fe27482c09b33c85b401f601ba7ba5c48bb Mon Sep 17 00:00:00 2001 From: "H. Peter Anvin" Date: Wed, 29 Oct 2008 23:29:23 -0700 Subject: [PATCH] Left-leaning red-black tree data structure Implement library functions for "left-leaning red-black trees" with uint64_t keys. This is meant for looking up symbols by address in the backends that need to do so, e.g. ELF. A good question is if there is a better way to do this, that recovers the original symbol, but that's a future issue. Signed-off-by: H. Peter Anvin --- Makefile.in | 3 +- Mkfiles/msvc.mak | 3 +- Mkfiles/netware.mak | 3 +- Mkfiles/openwcom.mak | 3 +- Mkfiles/owlinux.mak | 3 +- rbtree.c | 100 +++++++++++++++++++++++++++++++++++++++++++++++++++ rbtree.h | 18 ++++++++++ 7 files changed, 128 insertions(+), 5 deletions(-) create mode 100644 rbtree.c create mode 100644 rbtree.h diff --git a/Makefile.in b/Makefile.in index 06f51b8..efefe96 100644 --- a/Makefile.in +++ b/Makefile.in @@ -59,7 +59,7 @@ X = @EXEEXT@ $(NROFF) -man $< > $@ #-- Begin File Lists --# -NASM = nasm.$(O) nasmlib.$(O) raa.$(O) saa.$(O) \ +NASM = nasm.$(O) nasmlib.$(O) raa.$(O) saa.$(O) rbtree.$(O) \ float.$(O) insnsa.$(O) insnsb.$(O) \ assemble.$(O) labels.$(O) hashtbl.$(O) crc64.$(O) parser.$(O) \ outform.$(O) outlib.$(O) output/outbin.$(O) \ @@ -319,6 +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 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 45177fe..b509848 100644 --- a/Mkfiles/msvc.mak +++ b/Mkfiles/msvc.mak @@ -34,7 +34,7 @@ X = .exe #-- Begin File Lists --# # Edit in Makefile.in, not here! -NASM = nasm.$(O) nasmlib.$(O) raa.$(O) saa.$(O) \ +NASM = nasm.$(O) nasmlib.$(O) raa.$(O) saa.$(O) rbtree.$(O) \ float.$(O) insnsa.$(O) insnsb.$(O) \ assemble.$(O) labels.$(O) hashtbl.$(O) crc64.$(O) parser.$(O) \ outform.$(O) outlib.$(O) output/outbin.$(O) \ @@ -252,6 +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 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 5ef88bb..a64919b 100644 --- a/Mkfiles/netware.mak +++ b/Mkfiles/netware.mak @@ -30,7 +30,7 @@ O = o #-- Begin File Lists --# # Edit in Makefile.in, not here! -NASM = nasm.o nasmlib.o raa.o saa.o \ +NASM = nasm.o nasmlib.o raa.o saa.o rbtree.o \ float.o insnsa.o insnsb.o \ assemble.o labels.o hashtbl.o crc64.o parser.o \ outform.o outlib.o outbin.o \ @@ -194,6 +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 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 50ec1b8..001d6fe 100644 --- a/Mkfiles/openwcom.mak +++ b/Mkfiles/openwcom.mak @@ -46,7 +46,7 @@ X = .exe # Note: wcl386 is broken if forward slashes are used as path separators. #-- Begin File Lists --# # Edit in Makefile.in, not here! -NASM = nasm.$(O) nasmlib.$(O) raa.$(O) saa.$(O) & +NASM = nasm.$(O) nasmlib.$(O) raa.$(O) saa.$(O) rbtree.$(O) & float.$(O) insnsa.$(O) insnsb.$(O) & assemble.$(O) labels.$(O) hashtbl.$(O) crc64.$(O) parser.$(O) & outform.$(O) outlib.$(O) output\outbin.$(O) & @@ -281,6 +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 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 1bcc5bb..c423421 100644 --- a/Mkfiles/owlinux.mak +++ b/Mkfiles/owlinux.mak @@ -57,7 +57,7 @@ X = .exe #-- Begin File Lists --# # Edit in Makefile.in, not here! -NASM = nasm.$(O) nasmlib.$(O) raa.$(O) saa.$(O) \ +NASM = nasm.$(O) nasmlib.$(O) raa.$(O) saa.$(O) rbtree.$(O) \ float.$(O) insnsa.$(O) insnsb.$(O) \ assemble.$(O) labels.$(O) hashtbl.$(O) crc64.$(O) parser.$(O) \ outform.$(O) outlib.$(O) output/outbin.$(O) \ @@ -291,6 +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 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 new file mode 100644 index 0000000..adf2b8b --- /dev/null +++ b/rbtree.c @@ -0,0 +1,100 @@ +/* + * rbtree.c + * + * 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. + * + * 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) +{ + const struct rbtree *best = NULL; + + while (tree) { + if (tree->key == key) + return tree; + else if (tree->key > key) + tree = tree->left; + else { + best = tree; + tree = tree->right; + } + } + return best; +} + +static bool is_red(struct rbtree *h) +{ + return h && h->red; +} + +static struct rbtree *rotate_left(struct rbtree *h) +{ + struct rbtree *x = h->right; + h->right = x->left; + x->left = h; + x->red = x->left->red; + x->left->red = true; + return x; +} + +static struct rbtree *rotate_right(struct rbtree *h) +{ + struct rbtree *x = h->left; + h->left = x->right; + x->right = h; + x->red = x->right->red; + x->right->red = true; + return x; +} + +static void color_flip(struct rbtree *h) +{ + h->red = !h->red; + h->left->red = !h->left->red; + h->right->red = !h->right->red; +} + +struct rbtree *rb_insert(struct rbtree *tree, uint64_t key, void *data) +{ + if (!tree) { + struct rbtree *node = nasm_malloc(sizeof *node); + + node->key = key; + node->data = data; + 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); + else + tree->right = rb_insert(tree->right, key, data); + + if (is_red(tree->right)) + tree = rotate_left(tree); + + if (is_red(tree->left) && is_red(tree->left->left)) + tree = rotate_right(tree); + + 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 new file mode 100644 index 0000000..3b45428 --- /dev/null +++ b/rbtree.h @@ -0,0 +1,18 @@ +#ifndef NASM_RBTREE_H +#define NASM_RBTREE_H + +#include "compiler.h" +#include + +struct rbtree { + uint64_t key; + void *data; + struct rbtree *left, *right; + bool red; +}; + +struct rbtree *rb_insert(struct rbtree *, uint64_t, void *); +const struct rbtree *rb_search(const struct rbtree *, uint64_t); +void rb_free(struct rbtree *); + +#endif /* NASM_RBTREE_H */ -- 2.7.4