From b88b57868ab37453980170896070631714fdc1fa Mon Sep 17 00:00:00 2001
From: Chris Robinson <chris.kcat@gmail.com>
Date: Wed, 28 Jun 2017 19:09:38 -0700
Subject: [PATCH] Add a ptr-to-int map

---
 router/router.c | 150 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 router/router.h |  18 +++++++
 2 files changed, 168 insertions(+)

diff --git a/router/router.c b/router/router.c
index 21ab8a6a..7bbdfa8e 100644
--- a/router/router.c
+++ b/router/router.c
@@ -5,6 +5,7 @@
 
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 
 #include "AL/alc.h"
 #include "AL/al.h"
@@ -275,3 +276,152 @@ void LoadDriverList(void)
         path[len-1] = '\0';
     SearchDrivers(path);
 }
+
+
+void InitPtrIntMap(PtrIntMap *map)
+{
+    map->keys = NULL;
+    map->values = NULL;
+    map->size = 0;
+    map->capacity = 0;
+    RWLockInit(&map->lock);
+}
+
+void ResetPtrIntMap(PtrIntMap *map)
+{
+    WriteLock(&map->lock);
+    free(map->keys);
+    map->keys = NULL;
+    map->values = NULL;
+    map->size = 0;
+    map->capacity = 0;
+    WriteUnlock(&map->lock);
+}
+
+ALenum InsertPtrIntMapEntry(PtrIntMap *map, ALvoid *key, ALint value)
+{
+    ALsizei pos = 0;
+
+    WriteLock(&map->lock);
+    if(map->size > 0)
+    {
+        ALsizei count = map->size;
+        do {
+            ALsizei step = count>>1;
+            ALsizei i = pos+step;
+            if(!(map->keys[i] < key))
+                count = step;
+            else
+            {
+                pos = i+1;
+                count -= step+1;
+            }
+        } while(count > 0);
+    }
+
+    if(pos == map->size || map->keys[pos] != key)
+    {
+        if(map->size == map->capacity)
+        {
+            ALvoid **keys = NULL;
+            ALint *values;
+            ALsizei newcap;
+
+            newcap = (map->capacity ? (map->capacity<<1) : 4);
+            if(newcap > map->capacity)
+                keys = calloc(sizeof(map->keys[0])+sizeof(map->values[0]), newcap);
+            if(!keys)
+            {
+                WriteUnlock(&map->lock);
+                return AL_OUT_OF_MEMORY;
+            }
+            values = (ALint*)&keys[newcap];
+
+            if(map->keys)
+            {
+                memcpy(keys, map->keys, map->size*sizeof(map->keys[0]));
+                memcpy(values, map->values, map->size*sizeof(map->values[0]));
+            }
+            free(map->keys);
+            map->keys = keys;
+            map->values = values;
+            map->capacity = newcap;
+        }
+
+        if(pos < map->size)
+        {
+            memmove(&map->keys[pos+1], &map->keys[pos],
+                    (map->size-pos)*sizeof(map->keys[0]));
+            memmove(&map->values[pos+1], &map->values[pos],
+                    (map->size-pos)*sizeof(map->values[0]));
+        }
+        map->size++;
+    }
+    map->keys[pos] = key;
+    map->values[pos] = value;
+    WriteUnlock(&map->lock);
+
+    return AL_NO_ERROR;
+}
+
+ALint RemovePtrIntMapKey(PtrIntMap *map, ALvoid *key)
+{
+    ALint ret = -1;
+    WriteLock(&map->lock);
+    if(map->size > 0)
+    {
+        ALsizei pos = 0;
+        ALsizei count = map->size;
+        do {
+            ALsizei step = count>>1;
+            ALsizei i = pos+step;
+            if(!(map->keys[i] < key))
+                count = step;
+            else
+            {
+                pos = i+1;
+                count -= step+1;
+            }
+        } while(count > 0);
+        if(pos < map->size && map->keys[pos] == key)
+        {
+            ret = map->values[pos];
+            if(pos < map->size-1)
+            {
+                memmove(&map->keys[pos], &map->keys[pos+1],
+                        (map->size-1-pos)*sizeof(map->keys[0]));
+                memmove(&map->values[pos], &map->values[pos+1],
+                        (map->size-1-pos)*sizeof(map->values[0]));
+            }
+            map->size--;
+        }
+    }
+    WriteUnlock(&map->lock);
+    return ret;
+}
+
+ALint LookupPtrIntMapKey(PtrIntMap *map, ALvoid *key)
+{
+    ALint ret = -1;
+    ReadLock(&map->lock);
+    if(map->size > 0)
+    {
+        ALsizei pos = 0;
+        ALsizei count = map->size;
+        do {
+            ALsizei step = count>>1;
+            ALsizei i = pos+step;
+            if(!(map->keys[i] < key))
+                count = step;
+            else
+            {
+                pos = i+1;
+                count -= step+1;
+            }
+        } while(count > 0);
+        if(pos < map->size && map->keys[pos] == key)
+            ret = map->values[pos];
+    }
+    ReadUnlock(&map->lock);
+    return ret;
+}
diff --git a/router/router.h b/router/router.h
index 57a32d9a..7cd776f4 100644
--- a/router/router.h
+++ b/router/router.h
@@ -8,6 +8,7 @@
 #include "AL/alc.h"
 #include "AL/al.h"
 #include "atomic.h"
+#include "rwlock.h"
 
 
 typedef struct DriverIface {
@@ -116,4 +117,21 @@ extern int DriverListSize;
 extern ATOMIC(DriverIface*) CurrentCtxDriver;
 
 
+typedef struct PtrIntMap {
+    ALvoid **keys;
+    /* Shares memory with keys. */
+    ALint *values;
+
+    ALsizei size;
+    ALsizei capacity;
+    RWLock lock;
+} PtrIntMap;
+#define PTRINTMAP_STATIC_INITIALIZE { NULL, NULL, 0, 0, RWLOCK_STATIC_INITIALIZE }
+
+void InitPtrIntMap(PtrIntMap *map);
+void ResetPtrIntMap(PtrIntMap *map);
+ALenum InsertPtrIntMapEntry(PtrIntMap *map, ALvoid *key, ALint value);
+ALint RemovePtrIntMapKey(PtrIntMap *map, ALvoid *key);
+ALint LookupPtrIntMapKey(PtrIntMap *map, ALvoid *key);
+
 #endif /* ROUTER_ROUTER_H */
-- 
2.11.4.GIT