src/Set.c

   1 /**
   2  * @file Set.c
   3  */
   4
   5 #include "cgds/Set.h"
   6
   7 void _set_init(Set* set, size_t dataSize, size_t hashSize,
   8                UInt (*getHash)(void*, size_t))
   9 {
  10   set->hashSize = hashSize;
  11   set->dataSize = dataSize;
  12   set->head = safe_malloc(hashSize * sizeof(SetCell*));
  13   for (UInt i = 0; i < hashSize; i++)
  14     set->head[i] = NULL;
  15   set->size = 0;
  16   set->getHash = getHash; //may be NULL
  17 }
  18
  19 Set* _set_new(size_t dataSize, size_t hashSize, UInt (*getHash)(void*, size_t))
  20 {
  21   Set* set = (Set*) safe_malloc(sizeof(Set));
  22   _set_init(set, dataSize, hashSize, getHash);
  23   return set;
  24 }
  25
  26 Set* set_copy(Set* set)
  27 {
  28   Set* setCopy = _set_new(set->dataSize, set->hashSize, set->getHash);
  29   setCopy->size = set->size;
  30   for (UInt i = 0; i < set->hashSize; i++)
  31   {
  32     SetCell *cell = set->head[i],
  33              *cellCopy = setCopy->head[i],
  34              *prev = NULL;
  35     while (cell != NULL)
  36     {
  37       // cellCopy == NULL (from empty list)
  38       cellCopy = (SetCell*) safe_malloc(sizeof(SetCell));
  39       cellCopy->item = safe_malloc(set->dataSize);
  40       memcpy(cellCopy->item, cell->item, set->dataSize);
  41       if (prev == NULL) setCopy->head[i] = cellCopy;
  42       else prev->next = cellCopy;
  43       prev = cellCopy;
  44       cell = cell->next;
  45     }
  46     if (cellCopy != NULL) cellCopy->next = NULL;
  47   }
  48   return setCopy;
  49 }
  50
  51 bool set_empty(Set* set)
  52 {
  53   return (set->size == 0);
  54 }
  55
  56 UInt set_size(Set* set)
  57 {
  58   return set->size;
  59 }
  60
  61 // Function (string) key --> (integer) hash [internal usage]
  62 // Default function. Can be changed (see hashtable_new())
  63 UInt _set_compute_hash(void* key, size_t dataSize, size_t hashSize)
  64 {
  65   UInt res = 0;
  66   // Interpret the bytes in key as a piece of string
  67   unsigned char* keyStr = (unsigned char*)key;
  68   for (size_t i = 0; i < dataSize; i++)
  69     // NOTE: '31' from here https://stackoverflow.com/a/4384446
  70     res = (*(keyStr+i) + 31 * res) % hashSize;
  71   return res;
  72 }
  73
  74 // Get hash index from key [internal usage]
  75 UInt _set_get_hindex(Set* set, void* key)
  76 {
  77   if (set->getHash == NULL)
  78     return _set_compute_hash(key, set->dataSize, set->hashSize);
  79   return set->getHash(key, set->hashSize);
  80 }
  81
  82 bool set_has(Set* set, void* item)
  83 {
  84   UInt hashIdx = _set_get_hindex(set, item);
  85   SetCell* cell = set->head[hashIdx];
  86   while (cell != NULL)
  87   {
  88     if (memcmp(cell->item, item, set->dataSize) == 0)
  89       return true;
  90     cell = cell->next;
  91   }
  92   return false;
  93 }
  94
  95 void _set_add(Set* set, void* item)
  96 {
  97   UInt hashIdx = _set_get_hindex(set, item);
  98   SetCell *cell = set->head[hashIdx],
  99           *prev = NULL;
 100   while (cell != NULL)
 101   {
 102     if (memcmp(cell->item, item, set->dataSize) == 0)
 103       // Already here: nothing to do
 104       return;
 105     prev = cell;
 106     cell = cell->next;
 107   }
 108   // New element: insert after prev (which may be NULL)
 109   SetCell* newCell = (SetCell*) safe_malloc(sizeof(SetCell));
 110   newCell->item = safe_malloc(set->dataSize);
 111   memcpy(newCell->item, item, set->dataSize);
 112   newCell->next = NULL;
 113   if (prev == NULL)
 114     set->head[hashIdx] = newCell;
 115   else
 116     prev->next = newCell;
 117   set->size++;
 118 }
 119
 120 void _set_delete(Set* set, void* item)
 121 {
 122   UInt hashIdx = _set_get_hindex(set, item);
 123   SetCell *cell = set->head[hashIdx],
 124           *prev = NULL;
 125   while (cell != NULL)
 126   {
 127     if (memcmp(cell->item, item, set->dataSize) == 0)
 128     {
 129       if (prev == NULL)
 130         set->head[hashIdx] = cell->next;
 131       else
 132         prev->next = cell->next;
 133       safe_free(cell->item);
 134       safe_free(cell);
 135       set->size--;
 136       break;
 137     }
 138     prev = cell;
 139     cell = cell->next;
 140   }
 141 }
 142
 143 Vector* set_to_vector(Set* set) {
 144   Vector* v = _vector_new(set->dataSize);
 145   for (UInt i = 0; i < set->hashSize; i++) {
 146     SetCell* cell = set->head[i];
 147     while (cell != NULL) {
 148       _vector_push(v, cell->item);
 149       cell = cell->next;
 150     }
 151   }
 152   return v;
 153 }
 154
 155 void set_clear(Set* set)
 156 {
 157   for (UInt i = 0; i < set->hashSize; i++)
 158   {
 159     SetCell* cell = set->head[i];
 160     while (cell != NULL)
 161     {
 162       SetCell* next = cell->next;
 163       safe_free(cell->item);
 164       safe_free(cell);
 165       cell = next;
 166     }
 167     set->head[i] = NULL;
 168   }
 169   set->size = 0;
 170 }
 171
 172 void set_destroy(Set* set)
 173 {
 174   set_clear(set);
 175   safe_free(set->head);
 176   safe_free(set);
 177 }