From 4c0f745dc80d392fddea23eb8d4d7d86425ce0c6 Mon Sep 17 00:00:00 2001
From: David 'Digit' Turner <digit@android.com>
Date: Wed, 17 Nov 2010 17:55:17 +0100
Subject: Update android/utils/ with misc. new features.

This introduces a few new features to android/utils/ that will
be used in later patches.

+ <android/utils/assert.h> to handle assertions
+ <android/utils/vector.h> to handle dynamic arrays
+ <android/utils/reflist.h> slightly updated (more docs)
+ <android/utils/refset.h> implements a set of pointers

Change-Id: Iebc14cfefd1c0e8aaecda9958a980d40f0be610a
---
 android/utils/refset.c | 146 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 146 insertions(+)
 create mode 100644 android/utils/refset.c

(limited to 'android/utils/refset.c')

diff --git a/android/utils/refset.c b/android/utils/refset.c
new file mode 100644
index 0000000..bb9a7f1
--- /dev/null
+++ b/android/utils/refset.c
@@ -0,0 +1,146 @@
+/* Copyright (C) 2009 The Android Open Source Project
+**
+** This software is licensed under the terms of the GNU General Public
+** License version 2, as published by the Free Software Foundation, and
+** may be copied, distributed, and modified under those terms.
+**
+** This program is distributed in the hope that it will be useful,
+** but WITHOUT ANY WARRANTY; without even the implied warranty of
+** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+** GNU General Public License for more details.
+*/
+#include <android/utils/refset.h>
+#include <stddef.h>
+
+#define  AREFSET_STEP    5
+
+AINLINED uint32_t
+_arefSet_hashItem( void*  item )
+{
+    uint32_t  hash;
+
+    hash = (uint32_t)(ptrdiff_t)item >> 2;
+    if (sizeof(item) > 4)
+        hash ^= ((uint64_t)(ptrdiff_t)item >> 32);
+
+    return hash;
+}
+
+static void**
+_arefSet_lookup( ARefSet*  s, void*  item)
+{
+    uint32_t  hash = _arefSet_hashItem(item);
+    unsigned  index = hash & (s->max_buckets-1);
+
+    for (;;) {
+        void**  pnode = &s->buckets[index];
+
+        if (*pnode == item || *pnode == NULL)
+            return pnode;
+
+        index += AREFSET_STEP;
+        if (index >= s->max_buckets)
+            index -= s->max_buckets;
+    }
+}
+
+static void**
+_arefSet_lookupInsert( ARefSet*  s, void*  item)
+{
+    uint32_t  hash = _arefSet_hashItem(item);
+    unsigned  index = hash & (s->max_buckets-1);
+    void**    insert = NULL;
+
+    for (;;) {
+        void**  pnode = &s->buckets[index];
+
+        if (*pnode == NULL) {
+            return insert ? insert : pnode;
+        } else if (*pnode == AREFSET_DELETED) {
+            if (!insert)
+                insert = pnode;
+        } else if (*pnode == item)
+            return pnode;
+
+        index += AREFSET_STEP;
+        if (index >= s->max_buckets)
+            index -= s->max_buckets;
+    }
+}
+
+extern ABool
+arefSet_has( ARefSet*  s, void*  item )
+{
+    void**  lookup;
+
+    if (item == NULL || s->max_buckets == 0)
+        return 0;
+
+    lookup = _arefSet_lookup(s, item);
+    return (*lookup == item);
+}
+
+/* the code below assumes, in the case of a down-size,
+ * that there aren't too many items in the set.
+ */
+static void
+_arefSet_resize( ARefSet*  s, unsigned  newSize )
+{
+    ARefSet   newSet;
+    unsigned  nn;
+
+    AVECTOR_INIT_ALLOC(&newSet,buckets, newSize);
+
+    for (nn = 0; nn < s->max_buckets; nn++) {
+        void*  item  = s->buckets[nn];
+        if (item != NULL && item != AREFSET_DELETED) {
+            void** lookup = _arefSet_lookup(&newSet, item);
+            *lookup = item;
+        }
+    }
+
+    AVECTOR_DONE(s,buckets);
+    s->buckets     = newSet.buckets;
+    s->max_buckets = newSet.max_buckets;
+}
+
+extern void
+arefSet_add( ARefSet*  s, void*  item )
+{
+    void**  lookup;
+
+    if (item == NULL)
+        return;
+
+    if (s->max_buckets == 0)
+        AVECTOR_INIT_ALLOC(s,buckets,4);
+
+    lookup = _arefSet_lookupInsert(s, item);
+    if (*lookup == item)
+        return;
+
+    *lookup = item;
+    s->num_buckets += 1;
+
+    if (s->num_buckets > s->max_buckets*0.85)
+        _arefSet_resize(s, s->max_buckets*2);
+}
+
+extern void
+arefSet_del( ARefSet*  s, void*  item )
+{
+    void**  lookup;
+
+    if (item == NULL || s->max_buckets == 0)
+        return;
+
+    lookup = _arefSet_lookup(s, item);
+    if (*lookup != item)
+        return;
+
+    *lookup = AREFSET_DELETED;
+    s->num_buckets -= 1;
+
+    if (s->num_buckets < s->max_buckets*0.25)
+        _arefSet_resize(s, s->max_buckets/2);
+}
-- 
cgit v1.1