[Qemu-devel] [RFC 3/8] tiny_set: add module to test for membership in a tiny set of pointers

[Emilio G. Cota]

This will be used by the atomic instruction emulation code.

Signed-off-by: Emilio G. Cota <address@hidden>
---
 include/qemu/tiny_set.h | 90 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 90 insertions(+)
 create mode 100644 include/qemu/tiny_set.h

diff --git a/include/qemu/tiny_set.h b/include/qemu/tiny_set.h
new file mode 100644
index 0000000..b9aa049
--- /dev/null
+++ b/include/qemu/tiny_set.h
@@ -0,0 +1,90 @@
+/*
+ * tiny_set - simple data structure for fast lookups on tiny sets
+ *
+ * Assumptions:
+ * - Sets are tiny, i.e. of up to a few dozen items
+ * - All operations are serialised by some external lock
+ * - Only non-NULL pointers are supported
+ * - No values stored! This is a set, and thus key-only
+ * - No check for duplicates on insert
+ *
+ * Alternatives:
+ * - bitmap: if the number of items in the set is small and bounded
+ * - hash table: if the set is not tiny
+ *
+ * Complexity:
+ * - O(n) lookup/removal, O(1) insert
+ */
+#ifndef TINY_SET_H
+#define TINY_SET_H
+
+#include <stdbool.h>
+#include <assert.h>
+
+#include <glib.h>
+
+#include "qemu/osdep.h"
+#include "qemu/queue.h"
+
+typedef struct tiny_set TinySet;
+
+struct tiny_set {
+    const void **items;
+    int max_items;
+    int n_items;
+};
+
+static inline void tiny_set_init(TinySet *ts)
+{
+    memset(ts, 0, sizeof(*ts));
+}
+
+static inline void tiny_set_insert(TinySet *ts, const void *key)
+{
+    assert(key);
+
+    if (unlikely(ts->n_items == ts->max_items)) {
+        ts->max_items = ts->max_items ? ts->max_items * 2 : 1;
+        ts->items = g_realloc_n(ts->items, ts->max_items, sizeof(*ts->items));
+    }
+    ts->items[ts->n_items] = key;
+    ts->n_items++;
+}
+
+/* returns true if key was removed, false if it wasn't found */
+static inline bool tiny_set_remove(TinySet *ts, const void *key)
+{
+    bool ret = false;
+    int i;
+
+    assert(key);
+
+    for (i = 0; i < ts->n_items; i++) {
+        if (ts->items[i] == key) {
+            ts->items[i] = NULL;
+            ret = true;
+        }
+    }
+    return ret;
+}
+
+static inline void tiny_set_remove_all(TinySet *ts)
+{
+    ts->n_items = 0;
+}
+
+static inline bool tiny_set_contains(TinySet *ts, const void *key)
+{
+    int i;
+
+    assert(key);
+
+    for (i = 0; i < ts->n_items; i++) {
+        if (ts->items[i] == key) {
+            return true;
+        }
+    }
+    return false;
+}
+
+#endif /* TINY_SET_H */
-- 
1.8.3