dali-physics/third-party/chipmunk2d/src/cpHashSet.c

   1 /* Copyright (c) 2013 Scott Lembcke and Howling Moon Software
   2  *
   3  * Permission is hereby granted, free of charge, to any person obtaining a copy
   4  * of this software and associated documentation files (the "Software"), to deal
   5  * in the Software without restriction, including without limitation the rights
   6  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   7  * copies of the Software, and to permit persons to whom the Software is
   8  * furnished to do so, subject to the following conditions:
   9  *
  10  * The above copyright notice and this permission notice shall be included in
  11  * all copies or substantial portions of the Software.
  12  *
  13  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  14  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  15  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  16  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  17  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  18  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  19  * SOFTWARE.
  20  */
  21
  22 #include "chipmunk/chipmunk_private.h"
  23 #include "prime.h"
  24
  25 typedef struct cpHashSetBin {
  26         void *elt;
  27         cpHashValue hash;
  28         struct cpHashSetBin *next;
  29 } cpHashSetBin;
  30
  31 struct cpHashSet {
  32         unsigned int entries, size;
  33
  34         cpHashSetEqlFunc eql;
  35         void *default_value;
  36
  37         cpHashSetBin **table;
  38         cpHashSetBin *pooledBins;
  39
  40         cpArray *allocatedBuffers;
  41 };
  42
  43 void
  44 cpHashSetFree(cpHashSet *set)
  45 {
  46         if(set){
  47                 cpfree(set->table);
  48
  49                 cpArrayFreeEach(set->allocatedBuffers, cpfree);
  50                 cpArrayFree(set->allocatedBuffers);
  51
  52                 cpfree(set);
  53         }
  54 }
  55
  56 cpHashSet *
  57 cpHashSetNew(int size, cpHashSetEqlFunc eqlFunc)
  58 {
  59         cpHashSet *set = (cpHashSet *)cpcalloc(1, sizeof(cpHashSet));
  60
  61         set->size = next_prime(size);
  62         set->entries = 0;
  63
  64         set->eql = eqlFunc;
  65         set->default_value = NULL;
  66
  67         set->table = (cpHashSetBin **)cpcalloc(set->size, sizeof(cpHashSetBin *));
  68         set->pooledBins = NULL;
  69
  70         set->allocatedBuffers = cpArrayNew(0);
  71
  72         return set;
  73 }
  74
  75 void
  76 cpHashSetSetDefaultValue(cpHashSet *set, void *default_value)
  77 {
  78         set->default_value = default_value;
  79 }
  80
  81 static int
  82 setIsFull(cpHashSet *set)
  83 {
  84         return (set->entries >= set->size);
  85 }
  86
  87 static void
  88 cpHashSetResize(cpHashSet *set)
  89 {
  90         // Get the next approximate doubled prime.
  91         unsigned int newSize = next_prime(set->size + 1);
  92         // Allocate a new table.
  93         cpHashSetBin **newTable = (cpHashSetBin **)cpcalloc(newSize, sizeof(cpHashSetBin *));
  94
  95         // Iterate over the chains.
  96         for(unsigned int i=0; i<set->size; i++){
  97                 // Rehash the bins into the new table.
  98                 cpHashSetBin *bin = set->table[i];
  99                 while(bin){
 100                         cpHashSetBin *next = bin->next;
 101
 102                         cpHashValue idx = bin->hash%newSize;
 103                         bin->next = newTable[idx];
 104                         newTable[idx] = bin;
 105
 106                         bin = next;
 107                 }
 108         }
 109
 110         cpfree(set->table);
 111
 112         set->table = newTable;
 113         set->size = newSize;
 114 }
 115
 116 static inline void
 117 recycleBin(cpHashSet *set, cpHashSetBin *bin)
 118 {
 119         bin->next = set->pooledBins;
 120         set->pooledBins = bin;
 121         bin->elt = NULL;
 122 }
 123
 124 static cpHashSetBin *
 125 getUnusedBin(cpHashSet *set)
 126 {
 127         cpHashSetBin *bin = set->pooledBins;
 128
 129         if(bin){
 130                 set->pooledBins = bin->next;
 131                 return bin;
 132         } else {
 133                 // Pool is exhausted, make more
 134                 int count = CP_BUFFER_BYTES/sizeof(cpHashSetBin);
 135                 cpAssertHard(count, "Internal Error: Buffer size is too small.");
 136
 137                 cpHashSetBin *buffer = (cpHashSetBin *)cpcalloc(1, CP_BUFFER_BYTES);
 138                 cpArrayPush(set->allocatedBuffers, buffer);
 139
 140                 // push all but the first one, return it instead
 141                 for(int i=1; i<count; i++) recycleBin(set, buffer + i);
 142                 return buffer;
 143         }
 144 }
 145
 146 int
 147 cpHashSetCount(cpHashSet *set)
 148 {
 149         return set->entries;
 150 }
 151
 152 const void *
 153 cpHashSetInsert(cpHashSet *set, cpHashValue hash, const void *ptr, cpHashSetTransFunc trans, void *data)
 154 {
 155         cpHashValue idx = hash%set->size;
 156
 157         // Find the bin with the matching element.
 158         cpHashSetBin *bin = set->table[idx];
 159         while(bin && !set->eql(ptr, bin->elt))
 160                 bin = bin->next;
 161
 162         // Create it if necessary.
 163         if(!bin){
 164                 bin = getUnusedBin(set);
 165                 bin->hash = hash;
 166                 bin->elt = (trans ? trans(ptr, data) : data);
 167
 168                 bin->next = set->table[idx];
 169                 set->table[idx] = bin;
 170
 171                 set->entries++;
 172                 if(setIsFull(set)) cpHashSetResize(set);
 173         }
 174
 175         return bin->elt;
 176 }
 177
 178 const void *
 179 cpHashSetRemove(cpHashSet *set, cpHashValue hash, const void *ptr)
 180 {
 181         cpHashValue idx = hash%set->size;
 182
 183         cpHashSetBin **prev_ptr = &set->table[idx];
 184         cpHashSetBin *bin = set->table[idx];
 185
 186         // Find the bin
 187         while(bin && !set->eql(ptr, bin->elt)){
 188                 prev_ptr = &bin->next;
 189                 bin = bin->next;
 190         }
 191
 192         // Remove it if it exists.
 193         if(bin){
 194                 // Update the previous linked list pointer
 195                 (*prev_ptr) = bin->next;
 196                 set->entries--;
 197
 198                 const void *elt = bin->elt;
 199                 recycleBin(set, bin);
 200
 201                 return elt;
 202         }
 203
 204         return NULL;
 205 }
 206
 207 const void *
 208 cpHashSetFind(cpHashSet *set, cpHashValue hash, const void *ptr)
 209 {
 210         cpHashValue idx = hash%set->size;
 211         cpHashSetBin *bin = set->table[idx];
 212         while(bin && !set->eql(ptr, bin->elt))
 213                 bin = bin->next;
 214
 215         return (bin ? bin->elt : set->default_value);
 216 }
 217
 218 void
 219 cpHashSetEach(cpHashSet *set, cpHashSetIteratorFunc func, void *data)
 220 {
 221         for(unsigned int i=0; i<set->size; i++){
 222                 cpHashSetBin *bin = set->table[i];
 223                 while(bin){
 224                         cpHashSetBin *next = bin->next;
 225                         func(bin->elt, data);
 226                         bin = next;
 227                 }
 228         }
 229 }
 230
 231 void
 232 cpHashSetFilter(cpHashSet *set, cpHashSetFilterFunc func, void *data)
 233 {
 234         for(unsigned int i=0; i<set->size; i++){
 235                 // The rest works similarly to cpHashSetRemove() above.
 236                 cpHashSetBin **prev_ptr = &set->table[i];
 237                 cpHashSetBin *bin = set->table[i];
 238                 while(bin){
 239                         cpHashSetBin *next = bin->next;
 240
 241                         if(func(bin->elt, data)){
 242                                 prev_ptr = &bin->next;
 243                         } else {
 244                                 (*prev_ptr) = next;
 245
 246                                 set->entries--;
 247                                 recycleBin(set, bin);
 248                         }
 249
 250                         bin = next;
 251                 }
 252         }
 253 }