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 low = 0;
  47         ALsizei high = map->size - 1;
  48         while(low < high)
  49         {
  50             ALsizei mid = low + (high-low)/2;
  51             if(map->keys[mid] < key)
  52                 low = mid + 1;
  53             else
  54                 high = mid;
  55         }
  56         if(map->keys[low] < key)
  57             low++;
  58         pos = low;
  59     }
  60
  61     if(pos == map->size || map->keys[pos] != key)
  62     {
  63         if(map->size == map->limit)
  64         {
  65             WriteUnlock(&map->lock);
  66             return AL_OUT_OF_MEMORY;
  67         }
  68
  69         if(map->size == map->capacity)
  70         {
  71             ALuint *keys = NULL;
  72             ALvoid **values;
  73             ALsizei newcap, keylen;
  74
  75             newcap = (map->capacity ? (map->capacity<<1) : 4);
  76             if(map->limit > 0 && newcap > map->limit)
  77                 newcap = map->limit;
  78             if(newcap > map->capacity)
  79             {
  80                 /* Round the memory size for keys up to a multiple of the
  81                  * pointer size.
  82                  */
  83                 keylen = newcap * sizeof(map->keys[0]);
  84                 keylen += sizeof(map->values[0]) - 1;
  85                 keylen -= keylen%sizeof(map->values[0]);
  86
  87                 keys = al_malloc(16, keylen + newcap*sizeof(map->values[0]));
  88             }
  89             if(!keys)
  90             {
  91                 WriteUnlock(&map->lock);
  92                 return AL_OUT_OF_MEMORY;
  93             }
  94             values = (ALvoid**)((ALbyte*)keys + keylen);
  95
  96             if(map->keys)
  97             {
  98                 memcpy(keys, map->keys, map->size*sizeof(map->keys[0]));
  99                 memcpy(values, map->values, map->size*sizeof(map->values[0]));
 100             }
 101             al_free(map->keys);
 102             map->keys = keys;
 103             map->values = values;
 104             map->capacity = newcap;
 105         }
 106
 107         if(pos < map->size)
 108         {
 109             memmove(&map->keys[pos+1], &map->keys[pos],
 110                     (map->size-pos)*sizeof(map->keys[0]));
 111             memmove(&map->values[pos+1], &map->values[pos],
 112                     (map->size-pos)*sizeof(map->values[0]));
 113         }
 114         map->size++;
 115     }
 116     map->keys[pos] = key;
 117     map->values[pos] = value;
 118     WriteUnlock(&map->lock);
 119
 120     return AL_NO_ERROR;
 121 }
 122
 123 ALvoid *RemoveUIntMapKey(UIntMap *map, ALuint key)
 124 {
 125     ALvoid *ptr = NULL;
 126     WriteLock(&map->lock);
 127     if(map->size > 0)
 128     {
 129         ALsizei low = 0;
 130         ALsizei high = map->size - 1;
 131         while(low < high)
 132         {
 133             ALsizei mid = low + (high-low)/2;
 134             if(map->keys[mid] < key)
 135                 low = mid + 1;
 136             else
 137                 high = mid;
 138         }
 139         if(map->keys[low] == key)
 140         {
 141             ptr = map->values[low];
 142             if(low < map->size-1)
 143             {
 144                 memmove(&map->keys[low], &map->keys[low+1],
 145                         (map->size-1-low)*sizeof(map->keys[0]));
 146                 memmove(&map->values[low], &map->values[low+1],
 147                         (map->size-1-low)*sizeof(map->values[0]));
 148             }
 149             map->size--;
 150         }
 151     }
 152     WriteUnlock(&map->lock);
 153     return ptr;
 154 }
 155
 156 ALvoid *RemoveUIntMapKeyNoLock(UIntMap *map, ALuint key)
 157 {
 158     if(map->size > 0)
 159     {
 160         ALsizei low = 0;
 161         ALsizei high = map->size - 1;
 162         while(low < high)
 163         {
 164             ALsizei mid = low + (high-low)/2;
 165             if(map->keys[mid] < key)
 166                 low = mid + 1;
 167             else
 168                 high = mid;
 169         }
 170         if(map->keys[low] == key)
 171         {
 172             ALvoid *ptr = map->values[low];
 173             if(low < map->size-1)
 174             {
 175                 memmove(&map->keys[low], &map->keys[low+1],
 176                         (map->size-1-low)*sizeof(map->keys[0]));
 177                 memmove(&map->values[low], &map->values[low+1],
 178                         (map->size-1-low)*sizeof(map->values[0]));
 179             }
 180             map->size--;
 181             return ptr;
 182         }
 183     }
 184     return NULL;
 185 }
 186
 187 ALvoid *LookupUIntMapKey(UIntMap *map, ALuint key)
 188 {
 189     ALvoid *ptr = NULL;
 190     ReadLock(&map->lock);
 191     if(map->size > 0)
 192     {
 193         ALsizei low = 0;
 194         ALsizei high = map->size - 1;
 195         while(low < high)
 196         {
 197             ALsizei mid = low + (high-low)/2;
 198             if(map->keys[mid] < key)
 199                 low = mid + 1;
 200             else
 201                 high = mid;
 202         }
 203         if(map->keys[low] == key)
 204             ptr = map->values[low];
 205     }
 206     ReadUnlock(&map->lock);
 207     return ptr;
 208 }
 209
 210 ALvoid *LookupUIntMapKeyNoLock(UIntMap *map, ALuint key)
 211 {
 212     if(map->size > 0)
 213     {
 214         ALsizei low = 0;
 215         ALsizei high = map->size - 1;
 216         while(low < high)
 217         {
 218             ALsizei mid = low + (high-low)/2;
 219             if(map->keys[mid] < key)
 220                 low = mid + 1;
 221             else
 222                 high = mid;
 223         }
 224         if(map->keys[low] == key)
 225             return map->values[low];
 226     }
 227     return NULL;
 228 }