diff options
| -rw-r--r-- | Makefile.in | 3 | ||||
| -rw-r--r-- | Mkfiles/msvc.mak | 3 | ||||
| -rw-r--r-- | Mkfiles/netware.mak | 3 | ||||
| -rw-r--r-- | Mkfiles/openwcom.mak | 3 | ||||
| -rw-r--r-- | Mkfiles/owlinux.mak | 3 | ||||
| -rw-r--r-- | rbtree.c | 100 | ||||
| -rw-r--r-- | rbtree.h | 18 |
7 files changed, 128 insertions, 5 deletions
diff --git a/Makefile.in b/Makefile.in index 06f51b8b..efefe966 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 45177fe2..b509848f 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 5ef88bb9..a64919bb 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 50ec1b89..001d6fe9 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 1bcc5bbd..c4234216 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 00000000..adf2b8b4 --- /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 00000000..3b45428f --- /dev/null +++ b/rbtree.h @@ -0,0 +1,18 @@ +#ifndef NASM_RBTREE_H +#define NASM_RBTREE_H + +#include "compiler.h" +#include <inttypes.h> + +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 */ |