This will be used by atomic instruction emulation code.
Signed-off-by: Emilio G. Cota <[email protected]>
---
include/qemu/radix-tree.h | 29 ++++++++++++++++++
util/Makefile.objs | 2 +-
util/radix-tree.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 105 insertions(+), 1 deletion(-)
create mode 100644 include/qemu/radix-tree.h
create mode 100644 util/radix-tree.c
diff --git a/include/qemu/radix-tree.h b/include/qemu/radix-tree.h
new file mode 100644
index 0000000..a4e1f97
--- /dev/null
+++ b/include/qemu/radix-tree.h
@@ -0,0 +1,29 @@
+#ifndef RADIX_TREE_H
+#define RADIX_TREE_H
+
+#include <stddef.h>
+
+typedef struct QemuRadixNode QemuRadixNode;
+typedef struct QemuRadixTree QemuRadixTree;
+
+struct QemuRadixNode {
+ void *slots[0];
+};
+
+struct QemuRadixTree {
+ QemuRadixNode *root;
+ int radix;
+ int max_height;
+};
+
+void qemu_radix_tree_init(QemuRadixTree *tree, int bits, int radix);
+void *qemu_radix_tree_find_alloc(QemuRadixTree *tree, unsigned long index,
+ void *(*create)(unsigned long),
+ void (*delete)(void *));
+
+static inline void *qemu_radix_tree_find(QemuRadixTree *t, unsigned long index)
+{
+ return qemu_radix_tree_find_alloc(t, index, NULL, NULL);
+}
+
+#endif /* RADIX_TREE_H */
diff --git a/util/Makefile.objs b/util/Makefile.objs
index 114d657..6b18d3d 100644
--- a/util/Makefile.objs
+++ b/util/Makefile.objs
@@ -1,4 +1,4 @@
-util-obj-y = osdep.o cutils.o unicode.o qemu-timer-common.o
+util-obj-y = osdep.o cutils.o unicode.o qemu-timer-common.o radix-tree.o
util-obj-$(CONFIG_WIN32) += oslib-win32.o qemu-thread-win32.o
event_notifier-win32.o
util-obj-$(CONFIG_POSIX) += oslib-posix.o qemu-thread-posix.o
event_notifier-posix.o qemu-openpty.o
util-obj-y += envlist.o path.o module.o
diff --git a/util/radix-tree.c b/util/radix-tree.c
new file mode 100644
index 0000000..69eff29
--- /dev/null
+++ b/util/radix-tree.c
@@ -0,0 +1,75 @@
+/*
+ * radix-tree.c
+ * Non-blocking radix tree.
+ *
+ * Features:
+ * - Concurrent lookups and inserts.
+ * - No support for deletions.
+ *
+ * Conventions:
+ * - Height is counted starting from 0 at the bottom.
+ * - The index is used from left to right, i.e. MSBs are used first. This way
+ * nearby addresses land in nearby slots, minimising cache/TLB misses.
+ */
+#include <glib.h>
+
+#include "qemu/radix-tree.h"
+#include "qemu/atomic.h"
+#include "qemu/bitops.h"
+#include "qemu/osdep.h"
+
+typedef struct QemuRadixNode QemuRadixNode;
+
+void *qemu_radix_tree_find_alloc(QemuRadixTree *tree, unsigned long index,
+ void *(*create)(unsigned long),
+ void (*delete)(void *))
+{
+ QemuRadixNode *parent;
+ QemuRadixNode *node = tree->root;
+ void **slot;
+ int n_slots = BIT(tree->radix);
+ int level = tree->max_height - 1;
+ int shift = (level - 1) * tree->radix;
+
+ do {
+ parent = node;
+ slot = parent->slots + ((index >> shift) & (n_slots - 1));
+ node = atomic_read(slot);
+ smp_read_barrier_depends();
+ if (node == NULL) {
+ void *old;
+ void *new;
+
+ if (!create) {
+ return NULL;
+ }
+
+ if (level == 1) {
+ node = create(index);
+ } else {
+ node = g_malloc0(sizeof(*node) + sizeof(void *) * n_slots);
+ }
+ new = node;
+ /* atomic_cmpxchg is type-safe so we cannot use 'node' here */
+ old = atomic_cmpxchg(slot, NULL, new);
+ if (old) {
+ if (level == 1) {
+ delete(node);
+ } else {
+ g_free(node);
+ }
+ node = old;
+ }
+ }
+ shift -= tree->radix;
+ level--;
+ } while (level > 0);
+ return node;
+}
+
+void qemu_radix_tree_init(QemuRadixTree *tree, int bits, int radix)
+{
+ tree->radix = radix;
+ tree->max_height = 1 + DIV_ROUND_UP(bits, radix);
+ tree->root = g_malloc0(sizeof(*tree->root) + sizeof(void *) * BIT(radix));
+}
--
1.9.1
