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