This will be used by the atomic instruction emulation code.
Signed-off-by: Emilio G. Cota <c...@braap.org>
---
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
