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 <hpa@zytor.com>

1 files changed, 18 insertions, 0 deletions

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 */