src/hashset.h

   1 /*      Copyright (c) 2015 Regents of the University of California
   2  *
   3  *      Author: Brian Demsky <bdemsky@uci.edu>
   4  *
   5  *      This program is free software; you can redistribute it and/or
   6  *      modify it under the terms of the GNU General Public License
   7  *      version 2 as published by the Free Software Foundation.
   8  */
   9
  10 #ifndef HASH_SET_H
  11 #define HASH_SET_H
  12 #include "hashtable.h"
  13
  14 #define HashSetDef(Name, _Key, _KeyInt, _Shift, hash_function, equals)  \
  15         struct LinkNode ## Name{                                                                                                                                                                                        \
  16         _Key key;                                                                                                                                                                                                                                                       \
  17         struct LinkNode ## Name *prev;                                                                                                                                                          \
  18         struct LinkNode ## Name *next;                                                                                                                                                          \
  19         };                                                                                                                                                                                                                                                                              \
  20         typedef struct LinkNode ## Name LinkNode ## Name;                                                                                       \
  21         struct HashSet ## Name;                                                                                                                                                                                         \
  22         typedef struct HashSet ## Name HashSet ## Name;                                                                                         \
  23         struct HSIterator ## Name {                                                                                                                                                                             \
  24                 LinkNode ## Name *curr;                                                                                                                                                                                 \
  25                 LinkNode ## Name *last;                                                                                                                                                                                 \
  26                 HashSet ## Name * set;                                                                                                                                                                                  \
  27         };                                                                                                                                                                                                                                                                              \
  28                                                                                                                                                                                                                                                                                                 \
  29         HSIterator ## Name * allocHSIterator ## Name(LinkNode ## Name *_curr, HashSet ## Name * _set); \
  30         void freeIter ## Name(HSIterator ## Name *hsit);                                                                                        \
  31         bool hasNext ## Name(HSIterator ## Name *hsit);                                                                                         \
  32         _Key next ## Name(HSIterator ## Name *hsit);                                                                                                    \
  33         _Key currKey ## Name(HSIterator ## Name *hsit);                                                                                         \
  34         void remove ## Name(HSIterator ## Name *hsit);                                                                                          \
  35         struct HashSet ## Name {                                                                                                                                                                                        \
  36                 HashTable ## Name * table;                                                                                                                                                                      \
  37                 LinkNode ## Name *list;                                                                                                                                                                                 \
  38                 LinkNode ## Name *tail;                                                                                                                                                                                 \
  39         };                                                                                                                                                                                                                                                                              \
  40         typedef struct HashSet ## Name HashSet ## Name;                                                                                         \
  41                                                                                                                                                                                                                                                                                                 \
  42         HashSet ## Name * allocHashSet ## Name (unsigned int initialcapacity, double factor);   \
  43         void freeHashSet ## Name(struct HashSet ## Name * set);                                                         \
  44         HashSet ## Name * copy ## Name(HashSet ## Name * set);                                                          \
  45         void reset ## Name(HashSet ## Name * set);                                                                                                              \
  46         bool add ## Name(HashSet ## Name * set,_Key key);                                                                                       \
  47         _Key get ## Name(HashSet ## Name * set,_Key key);                                                                                       \
  48         _Key getFirstKey ## Name(HashSet ## Name * set);                                                                                        \
  49         bool contains ## Name(HashSet ## Name * set,_Key key);                                                          \
  50         bool remove ## Name(HashSet ## Name * set,_Key key);                                                                    \
  51         unsigned int getSize ## Name(HashSet ## Name * set);                                                                    \
  52         bool isEmpty ## Name(HashSet ## Name * set);                                                                                                    \
  53         HSIterator ## Name * iterator ## Name(HashSet ## Name * set);
  54
  55
  56 #define HashSetDef(Name, _Key, _KeyInt, _Shift, hash_function, equals)  \
  57         HSIterator ## Name * allocHSIterator ## Name(LinkNode ## Name *_curr, HashSet ## Name * _set) { \
  58                 HSIterator ## Name * hsit = (HSIterator ## Name *) ouralloc(sizeof(HSIterator ## Name)); \
  59                 hsit->curr=_curr;                                                                                                                                                                                                               \
  60                 hsit->set=_set;                                                                                                                                                                                                                 \
  61         }                                                                                                                                                                                                                                                                                       \
  62                                                                                                                                                                                                                                                                                                 \
  63         void freeIter ## Name(HSIterator ## Name *hsit) {                                                                                       \
  64                 ourfree(hsit);                                                                                                                                                                                                                  \
  65         }                                                                                                                                                                                                                                                                                       \
  66                                                                                                                                                                                                                                                                                                 \
  67         bool hasNext ## Name(HSIterator ## Name *hsit) {                                                                                        \
  68                 return hsit->curr!=NULL;                                                                                                                                                                                \
  69         }                                                                                                                                                                                                                                                                                       \
  70                                                                                                                                                                                                                                                                                                 \
  71         _Key next ## Name(HSIterator ## Name *hsit) {                                                                                                   \
  72                 _Key k=hsit->curr->key;                                                                                                                                                                                 \
  73                 hsit->last=hsit->curr;                                                                                                                                                                                  \
  74                 hsit->curr=hsit->curr->next;                                                                                                                                                            \
  75                 return k;                                                                                                                                                                                                                                               \
  76         }                                                                                                                                                                                                                                                                                       \
  77                                                                                                                                                                                                                                                                                                 \
  78         _Key currKey ## Name(HSIterator ## Name *hsit) {                                                                                        \
  79                 return hsit->last->key;                                                                                                                                                                                 \
  80         }                                                                                                                                                                                                                                                                                       \
  81                                                                                                                                                                                                                                                                                                 \
  82         void remove ## Name(HSIterator ## Name *hsit) {                                                                                         \
  83                 _Key k=hsit->last->key;                                                                                                                                                                                 \
  84                 remove ## Name(hsit->set, k);                                                                                                                                                           \
  85         }                                                                                                                                                                                                                                                                                       \
  86                                                                                                                                                                                                                                                                                                 \
  87         HashSet ## Name * allocHashSet ## Name (unsigned int initialcapacity, double factor) { \
  88                 HashSet ## Name * set = (HashSet ## Name *) ouralloc(sizeof(struct HashSet ## Name));   \
  89                 set->table=allocHashTable ## Name(initialcapcity, factor);                                      \
  90                 set->list=NULL;                                                                                                                                                                                                                 \
  91                 set->tail=NULL;                                                                                                                                                                                                                 \
  92         }                                                                                                                                                                                                                                                                                       \
  93                                                                                                                                                                                                                                                                                                 \
  94         void freeHashSet ## Name(struct HashSet ## Name * set) {                                                        \
  95                 LinkNode ## Name *tmp=set->list;                                                                                                                                                \
  96                 while(tmp!=NULL) {                                                                                                                                                                                                      \
  97                         LinkNode ## Name *tmpnext=tmp->next;                                                                                                                    \
  98                         ourfree(tmp);                                                                                                                                                                                                                   \
  99                         tmp=tmpnext;                                                                                                                                                                                                                    \
 100                 }                                                                                                                                                                                                                                                                               \
 101                 freeHashTable ## Name(set->table);                                                                                                                                      \
 102                 ourfree(set);                                                                                                                                                                                                                           \
 103         }                                                                                                                                                                                                                                                                                       \
 104                                                                                                                                                                                                                                                                                                 \
 105         HashSet ## Name * copy ## Name(HashSet ## Name * set) {                                                         \
 106                 HashSet ## Name *copy=new HashSet ## Name(getCapacity ## Name(set->table), getLoadFactor ## Name(set->table)); \
 107                 HSIterator ## Name * it=iterator ## Name(set);                                                                                  \
 108                 while(hasNext ## Name(it))                                                                                                                                                                      \
 109                         add ## Name(copy, next ## Name(it));                                                                                                                    \
 110                 freeIt ## Name(it);                                                                                                                                                                                                     \
 111                 return copy;                                                                                                                                                                                                                            \
 112         }                                                                                                                                                                                                                                                                                       \
 113                                                                                                                                                                                                                                                                                                 \
 114         void reset ## Name(HashSet ## Name * set) {                                                                                                             \
 115                 LinkNode ## Name *tmp=set->list;                                                                                                                                                \
 116                 while(tmp!=NULL) {                                                                                                                                                                                                      \
 117                         LinkNode ## Name *tmpnext=tmp->next;                                                                                                                    \
 118                         ourfree(tmp);                                                                                                                                                                                                                   \
 119                         tmp=tmpnext;                                                                                                                                                                                                                    \
 120                 }                                                                                                                                                                                                                                                                               \
 121                 set->list=set->tail=NULL;                                                                                                                                                                               \
 122                 reset ## Name(set->table);                                                                                                                                                                      \
 123         }                                                                                                                                                                                                                                                                                       \
 124                                                                                                                                                                                                                                                                                                 \
 125         bool add ## Name(HashSet ## Name * set,_Key key) {                                                                              \
 126                 LinkNode ## Name * val=get ## Name(set->table, key);                                                            \
 127                 if (val==NULL) {                                                                                                                                                                                                                \
 128                         LinkNode ## Name * newnode=(LinkNode ## Name *)ourmalloc(sizeof(struct LinkNode ## Name)); \
 129                         newnode->prev=set->tail;                                                                                                                                                                        \
 130                         newnode->next=NULL;                                                                                                                                                                                             \
 131                         newnode->key=key;                                                                                                                                                                                                       \
 132                         if (set->tail!=NULL)                                                                                                                                                                                    \
 133                                 set->tail->next=newnode;                                                                                                                                                                \
 134                         else                                                                                                                                                                                                                                                    \
 135                                 set->list=newnode;                                                                                                                                                                                      \
 136                         set->tail=newnode;                                                                                                                                                                                              \
 137                         put ## Name(set->table, key, newnode);                                                                                                          \
 138                         return true;                                                                                                                                                                                                                    \
 139                 } else                                                                                                                                                                                                                                                  \
 140                         return false;                                                                                                                                                                                                                   \
 141         }                                                                                                                                                                                                                                                                                       \
 142                                                                                                                                                                                                                                                                                                 \
 143         _Key get ## Name(HashSet ## Name * set,_Key key) {                                                                              \
 144                 LinkNode ## Name * val=get ## Name(set->table, key);                                                            \
 145                 if (val!=NULL)                                                                                                                                                                                                                  \
 146                         return val->key;                                                                                                                                                                                                        \
 147                 else                                                                                                                                                                                                                                                            \
 148                         return NULL;                                                                                                                                                                                                                    \
 149         }                                                                                                                                                                                                                                                                                       \
 150                                                                                                                                                                                                                                                                                                 \
 151         _Key getFirstKey ## Name(HashSet ## Name * set) {                                                                                       \
 152                 return set->list->key;                                                                                                                                                                                  \
 153         }                                                                                                                                                                                                                                                                                       \
 154                                                                                                                                                                                                                                                                                                 \
 155         bool contains ## Name(HashSet ## Name * set,_Key key) {                                                         \
 156                 return get ## Name(set->table, key)!=NULL;                                                                                                      \
 157         }                                                                                                                                                                                                                                                                                       \
 158                                                                                                                                                                                                                                                                                                 \
 159         bool remove ## Name(HashSet ## Name * set,_Key key) {                                                                   \
 160                 LinkNode ## Name * oldlinknode;                                                                                                                                                 \
 161                 oldlinknode=get ## Name(set->table, key);                                                                                                               \
 162                 if (oldlinknode==NULL) {                                                                                                                                                                                \
 163                         return false;                                                                                                                                                                                                                   \
 164                 }                                                                                                                                                                                                                                                                               \
 165                 remove ## Name(set->table, key);                                                                                                                                                \
 166                                                                                                                                                                                                                                                                                                 \
 167                 if (oldlinknode->prev==NULL)                                                                                                                                                            \
 168                         set->list=oldlinknode->next;                                                                                                                                                    \
 169                 else                                                                                                                                                                                                                                                            \
 170                         oldlinknode->prev->next=oldlinknode->next;                                                                                              \
 171                 if (oldlinknode->next!=NULL)                                                                                                                                                            \
 172                         oldlinknode->next->prev=oldlinknode->prev;                                                                                              \
 173                 else                                                                                                                                                                                                                                                            \
 174                         set->tail=oldlinknode->prev;                                                                                                                                                    \
 175                 ourfree(oldlinknode);                                                                                                                                                                                           \
 176                 return true;                                                                                                                                                                                                                            \
 177         }                                                                                                                                                                                                                                                                                       \
 178                                                                                                                                                                                                                                                                                                 \
 179         unsigned int getSize ## Name(HashSet ## Name * set) {                                                                   \
 180                 return getSize ## Name (set->table);                                                                                                                            \
 181         }                                                                                                                                                                                                                                                                                       \
 182                                                                                                                                                                                                                                                                                                 \
 183         bool isEmpty ## Name(HashSet ## Name * set) {                                                                                                   \
 184                 return getSize ## Name(set)==0;                                                                                                                                                 \
 185         }                                                                                                                                                                                                                                                                                       \
 186                                                                                                                                                                                                                                                                                                 \
 187         HSIterator ## Name * iterator ## Name(HashSet ## Name * set) {                          \
 188                 return allocHSIterator ## Name(set->list, this);                                                                                \
 189         }
 190 #endif