[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [RFC 3/8] tiny_set: add module to test for membership in a
From: |
Emilio G. Cota |
Subject: |
[Qemu-devel] [RFC 3/8] tiny_set: add module to test for membership in a tiny set of pointers |
Date: |
Fri, 8 May 2015 17:02:09 -0400 |
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
- [Qemu-devel] [RFC 0/8] Helper-based Atomic Instruction Emulation (AIE), Emilio G. Cota, 2015/05/08
- [Qemu-devel] [RFC 1/8] cputlb: add physical address to CPUTLBEntry, Emilio G. Cota, 2015/05/08
- [Qemu-devel] [RFC 3/8] tiny_set: add module to test for membership in a tiny set of pointers,
Emilio G. Cota <=
- [Qemu-devel] [RFC 2/8] softmmu: add helpers to get ld/st physical addresses, Emilio G. Cota, 2015/05/08
- [Qemu-devel] [RFC 4/8] radix-tree: add generic lockless radix tree module, Emilio G. Cota, 2015/05/08
- [Qemu-devel] [RFC 5/8] aie: add module for Atomic Instruction Emulation, Emilio G. Cota, 2015/05/08
- [Qemu-devel] [RFC 6/8] aie: add target helpers, Emilio G. Cota, 2015/05/08
- [Qemu-devel] [RFC 7/8] target-arm: emulate atomic instructions using AIE, Emilio G. Cota, 2015/05/08
- [Qemu-devel] [RFC 8/8] target-i386: emulate atomic instructions using AIE, Emilio G. Cota, 2015/05/08
- Re: [Qemu-devel] [RFC 0/8] Helper-based Atomic Instruction Emulation (AIE), Frederic Konrad, 2015/05/11