common/uintmap.c

   1
   2 #include "config.h"
   3
   4 #include "uintmap.h"
   5
   6 #include <stdlib.h>
   7 #include <string.h>
   8
   9
  10 extern inline void LockUIntMapRead(UIntMap *map);
  11 extern inline void UnlockUIntMapRead(UIntMap *map);
  12 extern inline void LockUIntMapWrite(UIntMap *map);
  13 extern inline void UnlockUIntMapWrite(UIntMap *map);
  14
  15
  16 void InitUIntMap(UIntMap *map, ALsizei limit)
  17 {
  18     map->array = NULL;
  19     map->size = 0;
  20     map->maxsize = 0;
  21     map->limit = limit;
  22     RWLockInit(&map->lock);
  23 }
  24
  25 void ResetUIntMap(UIntMap *map)
  26 {
  27     WriteLock(&map->lock);
  28     free(map->array);
  29     map->array = NULL;
  30     map->size = 0;
  31     map->maxsize = 0;
  32     WriteUnlock(&map->lock);
  33 }
  34
  35 ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value)
  36 {
  37     ALsizei pos = 0;
  38
  39     WriteLock(&map->lock);
  40     if(map->size > 0)
  41     {
  42         ALsizei low = 0;
  43         ALsizei high = map->size - 1;
  44         while(low < high)
  45         {
  46             ALsizei mid = low + (high-low)/2;
  47             if(map->array[mid].key < key)
  48                 low = mid + 1;
  49             else
  50                 high = mid;
  51         }
  52         if(map->array[low].key < key)
  53             low++;
  54         pos = low;
  55     }
  56
  57     if(pos == map->size || map->array[pos].key != key)
  58     {
  59         if(map->size == map->limit)
  60         {
  61             WriteUnlock(&map->lock);
  62             return AL_OUT_OF_MEMORY;
  63         }
  64
  65         if(map->size == map->maxsize)
  66         {
  67             ALvoid *temp = NULL;
  68             ALsizei newsize;
  69
  70             newsize = (map->maxsize ? (map->maxsize<<1) : 4);
  71             if(newsize >= map->maxsize)
  72                 temp = realloc(map->array, newsize*sizeof(map->array[0]));
  73             if(!temp)
  74             {
  75                 WriteUnlock(&map->lock);
  76                 return AL_OUT_OF_MEMORY;
  77             }
  78             map->array = temp;
  79             map->maxsize = newsize;
  80         }
  81
  82         if(pos < map->size)
  83             memmove(&map->array[pos+1], &map->array[pos],
  84                     (map->size-pos)*sizeof(map->array[0]));
  85         map->size++;
  86     }
  87     map->array[pos].key = key;
  88     map->array[pos].value = value;
  89     WriteUnlock(&map->lock);
  90
  91     return AL_NO_ERROR;
  92 }
  93
  94 ALvoid *RemoveUIntMapKey(UIntMap *map, ALuint key)
  95 {
  96     ALvoid *ptr = NULL;
  97     WriteLock(&map->lock);
  98     if(map->size > 0)
  99     {
 100         ALsizei low = 0;
 101         ALsizei high = map->size - 1;
 102         while(low < high)
 103         {
 104             ALsizei mid = low + (high-low)/2;
 105             if(map->array[mid].key < key)
 106                 low = mid + 1;
 107             else
 108                 high = mid;
 109         }
 110         if(map->array[low].key == key)
 111         {
 112             ptr = map->array[low].value;
 113             if(low < map->size-1)
 114                 memmove(&map->array[low], &map->array[low+1],
 115                         (map->size-1-low)*sizeof(map->array[0]));
 116             map->size--;
 117         }
 118     }
 119     WriteUnlock(&map->lock);
 120     return ptr;
 121 }
 122
 123 ALvoid *LookupUIntMapKey(UIntMap *map, ALuint key)
 124 {
 125     ALvoid *ptr = NULL;
 126     ReadLock(&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->array[mid].key < key)
 135                 low = mid + 1;
 136             else
 137                 high = mid;
 138         }
 139         if(map->array[low].key == key)
 140             ptr = map->array[low].value;
 141     }
 142     ReadUnlock(&map->lock);
 143     return ptr;
 144 }