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->array = NULL;
  21     map->size = 0;
  22     map->capacity = 0;
  23     map->limit = limit;
  24     RWLockInit(&map->lock);
  25 }
  26
  27 void ResetUIntMap(UIntMap *map)
  28 {
  29     WriteLock(&map->lock);
  30     al_free(map->array);
  31     map->array = NULL;
  32     map->size = 0;
  33     map->capacity = 0;
  34     WriteUnlock(&map->lock);
  35 }
  36
  37 ALenum InsertUIntMapEntry(UIntMap *map, ALuint key, ALvoid *value)
  38 {
  39     ALsizei pos = 0;
  40
  41     WriteLock(&map->lock);
  42     if(map->size > 0)
  43     {
  44         ALsizei low = 0;
  45         ALsizei high = map->size - 1;
  46         while(low < high)
  47         {
  48             ALsizei mid = low + (high-low)/2;
  49             if(map->array[mid].key < key)
  50                 low = mid + 1;
  51             else
  52                 high = mid;
  53         }
  54         if(map->array[low].key < key)
  55             low++;
  56         pos = low;
  57     }
  58
  59     if(pos == map->size || map->array[pos].key != key)
  60     {
  61         if(map->size == map->limit)
  62         {
  63             WriteUnlock(&map->lock);
  64             return AL_OUT_OF_MEMORY;
  65         }
  66
  67         if(map->size == map->capacity)
  68         {
  69             ALvoid *temp = NULL;
  70             ALsizei newsize;
  71
  72             newsize = (map->capacity ? (map->capacity<<1) : 4);
  73             if(map->limit > 0 && newsize > map->limit)
  74                 newsize = map->limit;
  75             if(newsize > map->capacity)
  76                 temp = al_malloc(16, newsize * sizeof(map->array[0]));
  77             if(!temp)
  78             {
  79                 WriteUnlock(&map->lock);
  80                 return AL_OUT_OF_MEMORY;
  81             }
  82
  83             if(map->array)
  84                 memcpy(temp, map->array, map->size*sizeof(map->array[0]));
  85             al_free(map->array);
  86             map->array = temp;
  87             map->capacity = newsize;
  88         }
  89
  90         if(pos < map->size)
  91             memmove(&map->array[pos+1], &map->array[pos],
  92                     (map->size-pos)*sizeof(map->array[0]));
  93         map->size++;
  94     }
  95     map->array[pos].key = key;
  96     map->array[pos].value = value;
  97     WriteUnlock(&map->lock);
  98
  99     return AL_NO_ERROR;
 100 }
 101
 102 ALvoid *RemoveUIntMapKey(UIntMap *map, ALuint key)
 103 {
 104     ALvoid *ptr = NULL;
 105     WriteLock(&map->lock);
 106     if(map->size > 0)
 107     {
 108         ALsizei low = 0;
 109         ALsizei high = map->size - 1;
 110         while(low < high)
 111         {
 112             ALsizei mid = low + (high-low)/2;
 113             if(map->array[mid].key < key)
 114                 low = mid + 1;
 115             else
 116                 high = mid;
 117         }
 118         if(map->array[low].key == key)
 119         {
 120             ptr = map->array[low].value;
 121             if(low < map->size-1)
 122                 memmove(&map->array[low], &map->array[low+1],
 123                         (map->size-1-low)*sizeof(map->array[0]));
 124             map->size--;
 125         }
 126     }
 127     WriteUnlock(&map->lock);
 128     return ptr;
 129 }
 130
 131 ALvoid *RemoveUIntMapKeyNoLock(UIntMap *map, ALuint key)
 132 {
 133     if(map->size > 0)
 134     {
 135         ALsizei low = 0;
 136         ALsizei high = map->size - 1;
 137         while(low < high)
 138         {
 139             ALsizei mid = low + (high-low)/2;
 140             if(map->array[mid].key < key)
 141                 low = mid + 1;
 142             else
 143                 high = mid;
 144         }
 145         if(map->array[low].key == key)
 146         {
 147             ALvoid *ptr = map->array[low].value;
 148             if(low < map->size-1)
 149                 memmove(&map->array[low], &map->array[low+1],
 150                         (map->size-1-low)*sizeof(map->array[0]));
 151             map->size--;
 152             return ptr;
 153         }
 154     }
 155     return NULL;
 156 }
 157
 158 ALvoid *LookupUIntMapKey(UIntMap *map, ALuint key)
 159 {
 160     ALvoid *ptr = NULL;
 161     ReadLock(&map->lock);
 162     if(map->size > 0)
 163     {
 164         ALsizei low = 0;
 165         ALsizei high = map->size - 1;
 166         while(low < high)
 167         {
 168             ALsizei mid = low + (high-low)/2;
 169             if(map->array[mid].key < key)
 170                 low = mid + 1;
 171             else
 172                 high = mid;
 173         }
 174         if(map->array[low].key == key)
 175             ptr = map->array[low].value;
 176     }
 177     ReadUnlock(&map->lock);
 178     return ptr;
 179 }
 180
 181 ALvoid *LookupUIntMapKeyNoLock(UIntMap *map, ALuint key)
 182 {
 183     if(map->size > 0)
 184     {
 185         ALsizei low = 0;
 186         ALsizei high = map->size - 1;
 187         while(low < high)
 188         {
 189             ALsizei mid = low + (high-low)/2;
 190             if(map->array[mid].key < key)
 191                 low = mid + 1;
 192             else
 193                 high = mid;
 194         }
 195         if(map->array[low].key == key)
 196             return map->array[low].value;
 197     }
 198     return NULL;
 199 }