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 void RelimitUIntMapNoLock(UIntMap *map, ALsizei limit)
  40 {
  41     map->limit = limit;
  42 }
  43
  44 ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value)
  45 {
  46     ALsizei pos = 0;
  47
  48     WriteLock(&map->lock);
  49     if(map->size > 0)
  50     {
  51         ALsizei count = map->size;
  52         do {
  53             ALsizei step = count>>1;
  54             ALsizei i = pos+step;
  55             if(!(map->keys[i] < key))
  56                 count = step;
  57             else
  58             {
  59                 pos = i+1;
  60                 count -= step+1;
  61             }
  62         } while(count > 0);
  63     }
  64
  65     if(pos == map->size || map->keys[pos] != key)
  66     {
  67         if(map->size >= map->limit)
  68         {
  69             WriteUnlock(&map->lock);
  70             return AL_OUT_OF_MEMORY;
  71         }
  72
  73         if(map->size == map->capacity)
  74         {
  75             ALuint *keys = NULL;
  76             ALvoid **values;
  77             ALsizei newcap, keylen;
  78
  79             newcap = (map->capacity ? (map->capacity<<1) : 4);
  80             if(map->limit > 0 && newcap > map->limit)
  81                 newcap = map->limit;
  82             if(newcap > map->capacity)
  83             {
  84                 /* Round the memory size for keys up to a multiple of the
  85                  * pointer size.
  86                  */
  87                 keylen = newcap * sizeof(map->keys[0]);
  88                 keylen += sizeof(map->values[0]) - 1;
  89                 keylen -= keylen%sizeof(map->values[0]);
  90
  91                 keys = al_malloc(16, keylen + newcap*sizeof(map->values[0]));
  92             }
  93             if(!keys)
  94             {
  95                 WriteUnlock(&map->lock);
  96                 return AL_OUT_OF_MEMORY;
  97             }
  98             values = (ALvoid**)((ALbyte*)keys + keylen);
  99
 100             if(map->keys)
 101             {
 102                 memcpy(keys, map->keys, map->size*sizeof(map->keys[0]));
 103                 memcpy(values, map->values, map->size*sizeof(map->values[0]));
 104             }
 105             al_free(map->keys);
 106             map->keys = keys;
 107             map->values = values;
 108             map->capacity = newcap;
 109         }
 110
 111         if(pos < map->size)
 112         {
 113             memmove(&map->keys[pos+1], &map->keys[pos],
 114                     (map->size-pos)*sizeof(map->keys[0]));
 115             memmove(&map->values[pos+1], &map->values[pos],
 116                     (map->size-pos)*sizeof(map->values[0]));
 117         }
 118         map->size++;
 119     }
 120     map->keys[pos] = key;
 121     map->values[pos] = value;
 122     WriteUnlock(&map->lock);
 123
 124     return AL_NO_ERROR;
 125 }
 126
 127 ALenum InsertUIntMapEntryNoLock(UIntMap *map, ALuint key, ALvoid *value)
 128 {
 129     ALsizei pos = 0;
 130
 131     if(map->size > 0)
 132     {
 133         ALsizei count = map->size;
 134         do {
 135             ALsizei step = count>>1;
 136             ALsizei i = pos+step;
 137             if(!(map->keys[i] < key))
 138                 count = step;
 139             else
 140             {
 141                 pos = i+1;
 142                 count -= step+1;
 143             }
 144         } while(count > 0);
 145     }
 146
 147     if(pos == map->size || map->keys[pos] != key)
 148     {
 149         if(map->size >= map->limit)
 150             return AL_OUT_OF_MEMORY;
 151
 152         if(map->size == map->capacity)
 153         {
 154             ALuint *keys = NULL;
 155             ALvoid **values;
 156             ALsizei newcap, keylen;
 157
 158             newcap = (map->capacity ? (map->capacity<<1) : 4);
 159             if(map->limit > 0 && newcap > map->limit)
 160                 newcap = map->limit;
 161             if(newcap > map->capacity)
 162             {
 163                 /* Round the memory size for keys up to a multiple of the
 164                  * pointer size.
 165                  */
 166                 keylen = newcap * sizeof(map->keys[0]);
 167                 keylen += sizeof(map->values[0]) - 1;
 168                 keylen -= keylen%sizeof(map->values[0]);
 169
 170                 keys = al_malloc(16, keylen + newcap*sizeof(map->values[0]));
 171             }
 172             if(!keys)
 173                 return AL_OUT_OF_MEMORY;
 174             values = (ALvoid**)((ALbyte*)keys + keylen);
 175
 176             if(map->keys)
 177             {
 178                 memcpy(keys, map->keys, map->size*sizeof(map->keys[0]));
 179                 memcpy(values, map->values, map->size*sizeof(map->values[0]));
 180             }
 181             al_free(map->keys);
 182             map->keys = keys;
 183             map->values = values;
 184             map->capacity = newcap;
 185         }
 186
 187         if(pos < map->size)
 188         {
 189             memmove(&map->keys[pos+1], &map->keys[pos],
 190                     (map->size-pos)*sizeof(map->keys[0]));
 191             memmove(&map->values[pos+1], &map->values[pos],
 192                     (map->size-pos)*sizeof(map->values[0]));
 193         }
 194         map->size++;
 195     }
 196     map->keys[pos] = key;
 197     map->values[pos] = value;
 198
 199     return AL_NO_ERROR;
 200 }
 201
 202 ALvoid *RemoveUIntMapKey(UIntMap *map, ALuint key)
 203 {
 204     ALvoid *ptr = NULL;
 205     WriteLock(&map->lock);
 206     if(map->size > 0)
 207     {
 208         ALsizei pos = 0;
 209         ALsizei count = map->size;
 210         do {
 211             ALsizei step = count>>1;
 212             ALsizei i = pos+step;
 213             if(!(map->keys[i] < key))
 214                 count = step;
 215             else
 216             {
 217                 pos = i+1;
 218                 count -= step+1;
 219             }
 220         } while(count > 0);
 221         if(pos < map->size && map->keys[pos] == key)
 222         {
 223             ptr = map->values[pos];
 224             if(pos < map->size-1)
 225             {
 226                 memmove(&map->keys[pos], &map->keys[pos+1],
 227                         (map->size-1-pos)*sizeof(map->keys[0]));
 228                 memmove(&map->values[pos], &map->values[pos+1],
 229                         (map->size-1-pos)*sizeof(map->values[0]));
 230             }
 231             map->size--;
 232         }
 233     }
 234     WriteUnlock(&map->lock);
 235     return ptr;
 236 }
 237
 238 ALvoid *RemoveUIntMapKeyNoLock(UIntMap *map, ALuint key)
 239 {
 240     ALvoid *ptr = NULL;
 241     if(map->size > 0)
 242     {
 243         ALsizei pos = 0;
 244         ALsizei count = map->size;
 245         do {
 246             ALsizei step = count>>1;
 247             ALsizei i = pos+step;
 248             if(!(map->keys[i] < key))
 249                 count = step;
 250             else
 251             {
 252                 pos = i+1;
 253                 count -= step+1;
 254             }
 255         } while(count > 0);
 256         if(pos < map->size && map->keys[pos] == key)
 257         {
 258             ptr = map->values[pos];
 259             if(pos < map->size-1)
 260             {
 261                 memmove(&map->keys[pos], &map->keys[pos+1],
 262                         (map->size-1-pos)*sizeof(map->keys[0]));
 263                 memmove(&map->values[pos], &map->values[pos+1],
 264                         (map->size-1-pos)*sizeof(map->values[0]));
 265             }
 266             map->size--;
 267         }
 268     }
 269     return ptr;
 270 }
 271
 272 ALvoid *LookupUIntMapKey(UIntMap *map, ALuint key)
 273 {
 274     ALvoid *ptr = NULL;
 275     ReadLock(&map->lock);
 276     if(map->size > 0)
 277     {
 278         ALsizei pos = 0;
 279         ALsizei count = map->size;
 280         do {
 281             ALsizei step = count>>1;
 282             ALsizei i = pos+step;
 283             if(!(map->keys[i] < key))
 284                 count = step;
 285             else
 286             {
 287                 pos = i+1;
 288                 count -= step+1;
 289             }
 290         } while(count > 0);
 291         if(pos < map->size && map->keys[pos] == key)
 292             ptr = map->values[pos];
 293     }
 294     ReadUnlock(&map->lock);
 295     return ptr;
 296 }
 297
 298 ALvoid *LookupUIntMapKeyNoLock(UIntMap *map, ALuint key)
 299 {
 300     if(map->size > 0)
 301     {
 302         ALsizei pos = 0;
 303         ALsizei count = map->size;
 304         do {
 305             ALsizei step = count>>1;
 306             ALsizei i = pos+step;
 307             if(!(map->keys[i] < key))
 308                 count = step;
 309             else
 310             {
 311                 pos = i+1;
 312                 count -= step+1;
 313             }
 314         } while(count > 0);
 315         if(pos < map->size && map->keys[pos] == key)
 316             return map->values[pos];
 317     }
 318     return NULL;
 319 }