common/uintmap.c

   1
   2 #include "config.h"
   3
   4 #include "uintmap.h"
   5
   6 #include <stdlib.h>
   7 #include <string.h>
   8
   9 #include "almalloc.h"
  10
  11
  12 extern inline void LockUIntMapRead(UIntMap *map);
  13 extern inline void UnlockUIntMapRead(UIntMap *map);
  14 extern inline void LockUIntMapWrite(UIntMap *map);
  15 extern inline void UnlockUIntMapWrite(UIntMap *map);
  16
  17
  18 void InitUIntMap(UIntMap *map, ALsizei limit)
  19 {
  20     map->keys = NULL;
  21     map->values = NULL;
  22     map->size = 0;
  23     map->capacity = 0;
  24     map->limit = limit;
  25     RWLockInit(&map->lock);
  26 }
  27
  28 void ResetUIntMap(UIntMap *map)
  29 {
  30     WriteLock(&map->lock);
  31     al_free(map->keys);
  32     map->keys = NULL;
  33     map->values = NULL;
  34     map->size = 0;
  35     map->capacity = 0;
  36     WriteUnlock(&map->lock);
  37 }
  38
  39 ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value)
  40 {
  41     ALsizei pos = 0;
  42
  43     WriteLock(&map->lock);
  44     if(map->size > 0)
  45     {
  46         ALsizei count = map->size;
  47         do {
  48             ALsizei step = count>>1;
  49             ALsizei i = pos+step;
  50             if(!(map->keys[i] < key))
  51                 count = step;
  52             else
  53             {
  54                 pos = i+1;
  55                 count -= step+1;
  56             }
  57         } while(count > 0);
  58     }
  59
  60     if(pos == map->size || map->keys[pos] != key)
  61     {
  62         if(map->size == map->limit)
  63         {
  64             WriteUnlock(&map->lock);
  65             return AL_OUT_OF_MEMORY;
  66         }
  67
  68         if(map->size == map->capacity)
  69         {
  70             ALuint *keys = NULL;
  71             ALvoid **values;
  72             ALsizei newcap, keylen;
  73
  74             newcap = (map->capacity ? (map->capacity<<1) : 4);
  75             if(map->limit > 0 && newcap > map->limit)
  76                 newcap = map->limit;
  77             if(newcap > map->capacity)
  78             {
  79                 /* Round the memory size for keys up to a multiple of the
  80                  * pointer size.
  81                  */
  82                 keylen = newcap * sizeof(map->keys[0]);
  83                 keylen += sizeof(map->values[0]) - 1;
  84                 keylen -= keylen%sizeof(map->values[0]);
  85
  86                 keys = al_malloc(16, keylen + newcap*sizeof(map->values[0]));
  87             }
  88             if(!keys)
  89             {
  90                 WriteUnlock(&map->lock);
  91                 return AL_OUT_OF_MEMORY;
  92             }
  93             values = (ALvoid**)((ALbyte*)keys + keylen);
  94
  95             if(map->keys)
  96             {
  97                 memcpy(keys, map->keys, map->size*sizeof(map->keys[0]));
  98                 memcpy(values, map->values, map->size*sizeof(map->values[0]));
  99             }
 100             al_free(map->keys);
 101             map->keys = keys;
 102             map->values = values;
 103             map->capacity = newcap;
 104         }
 105
 106         if(pos < map->size)
 107         {
 108             memmove(&map->keys[pos+1], &map->keys[pos],
 109                     (map->size-pos)*sizeof(map->keys[0]));
 110             memmove(&map->values[pos+1], &map->values[pos],
 111                     (map->size-pos)*sizeof(map->values[0]));
 112         }
 113         map->size++;
 114     }
 115     map->keys[pos] = key;
 116     map->values[pos] = value;
 117     WriteUnlock(&map->lock);
 118
 119     return AL_NO_ERROR;
 120 }
 121
 122 ALvoid *RemoveUIntMapKey(UIntMap *map, ALuint key)
 123 {
 124     ALvoid *ptr = NULL;
 125     WriteLock(&map->lock);
 126     if(map->size > 0)
 127     {
 128         ALsizei pos = 0;
 129         ALsizei count = map->size;
 130         do {
 131             ALsizei step = count>>1;
 132             ALsizei i = pos+step;
 133             if(!(map->keys[i] < key))
 134                 count = step;
 135             else
 136             {
 137                 pos = i+1;
 138                 count -= step+1;
 139             }
 140         } while(count > 0);
 141         if(pos < map->size && map->keys[pos] == key)
 142         {
 143             ptr = map->values[pos];
 144             if(pos < map->size-1)
 145             {
 146                 memmove(&map->keys[pos], &map->keys[pos+1],
 147                         (map->size-1-pos)*sizeof(map->keys[0]));
 148                 memmove(&map->values[pos], &map->values[pos+1],
 149                         (map->size-1-pos)*sizeof(map->values[0]));
 150             }
 151             map->size--;
 152         }
 153     }
 154     WriteUnlock(&map->lock);
 155     return ptr;
 156 }
 157
 158 ALvoid *RemoveUIntMapKeyNoLock(UIntMap *map, ALuint key)
 159 {
 160     ALvoid *ptr = NULL;
 161     if(map->size > 0)
 162     {
 163         ALsizei pos = 0;
 164         ALsizei count = map->size;
 165         do {
 166             ALsizei step = count>>1;
 167             ALsizei i = pos+step;
 168             if(!(map->keys[i] < key))
 169                 count = step;
 170             else
 171             {
 172                 pos = i+1;
 173                 count -= step+1;
 174             }
 175         } while(count > 0);
 176         if(pos < map->size && map->keys[pos] == key)
 177         {
 178             ptr = map->values[pos];
 179             if(pos < map->size-1)
 180             {
 181                 memmove(&map->keys[pos], &map->keys[pos+1],
 182                         (map->size-1-pos)*sizeof(map->keys[0]));
 183                 memmove(&map->values[pos], &map->values[pos+1],
 184                         (map->size-1-pos)*sizeof(map->values[0]));
 185             }
 186             map->size--;
 187         }
 188     }
 189     return ptr;
 190 }
 191
 192 ALvoid *LookupUIntMapKey(UIntMap *map, ALuint key)
 193 {
 194     ALvoid *ptr = NULL;
 195     ReadLock(&map->lock);
 196     if(map->size > 0)
 197     {
 198         ALsizei pos = 0;
 199         ALsizei count = map->size;
 200         do {
 201             ALsizei step = count>>1;
 202             ALsizei i = pos+step;
 203             if(!(map->keys[i] < key))
 204                 count = step;
 205             else
 206             {
 207                 pos = i+1;
 208                 count -= step+1;
 209             }
 210         } while(count > 0);
 211         if(pos < map->size && map->keys[pos] == key)
 212             ptr = map->values[pos];
 213     }
 214     ReadUnlock(&map->lock);
 215     return ptr;
 216 }
 217
 218 ALvoid *LookupUIntMapKeyNoLock(UIntMap *map, ALuint key)
 219 {
 220     if(map->size > 0)
 221     {
 222         ALsizei pos = 0;
 223         ALsizei count = map->size;
 224         do {
 225             ALsizei step = count>>1;
 226             ALsizei i = pos+step;
 227             if(!(map->keys[i] < key))
 228                 count = step;
 229             else
 230             {
 231                 pos = i+1;
 232                 count -= step+1;
 233             }
 234         } while(count > 0);
 235         if(pos < map->size && map->keys[pos] == key)
 236             return map->values[pos];
 237     }
 238     return NULL;
 239 }