From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:59353) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YqpP2-0004IE-6L for qemu-devel@nongnu.org; Fri, 08 May 2015 17:01:49 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1YqpOx-0003FZ-2I for qemu-devel@nongnu.org; Fri, 08 May 2015 17:01:48 -0400 Received: from out4-smtp.messagingengine.com ([66.111.4.28]:35088) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1YqpOw-0003Ey-Vk for qemu-devel@nongnu.org; Fri, 08 May 2015 17:01:43 -0400 Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailout.nyi.internal (Postfix) with ESMTP id C54D920BFA for ; Fri, 8 May 2015 17:01:42 -0400 (EDT) From: "Emilio G. Cota" Date: Fri, 8 May 2015 17:02:09 -0400 Message-Id: <1431118934-20900-4-git-send-email-cota@braap.org> In-Reply-To: <1431118934-20900-1-git-send-email-cota@braap.org> References: <1431118934-20900-1-git-send-email-cota@braap.org> Subject: [Qemu-devel] [RFC 3/8] tiny_set: add module to test for membership in a tiny set of pointers List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: mttcg@listserver.greensocs.com, Peter Maydell , Alvise Rigo , Paolo Bonzini , Frederic Konrad , alex.bennee@linaro.org, Richard Henderson This will be used by the atomic instruction emulation code. Signed-off-by: Emilio G. Cota --- 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 +#include + +#include + +#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