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: Add a ptr-to-int map --- router/router.c | 150 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ router/router.h | 18 +++++++ 2 files changed, 168 insertions(+) (limited to 'router') 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 */ -- cgit v1.2.3