1 /* Copyright (c) 2015 Regents of the University of California
3 * Author: Brian Demsky <bdemsky@uci.edu>
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.
12 #include "hashtable.h"
14 #define HashSetDef(Name, _Key) \
15 struct LinkNode ## Name { \
17 struct LinkNode ## Name *prev; \
18 struct LinkNode ## Name *next; \
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; \
28 typedef struct HSIterator ## Name HSIterator ## Name; \
29 HashTableDef(Name ## Set, _Key, LinkNode ## Name *); \
30 HSIterator ## Name * allocHSIterator ## Name(LinkNode ## Name *_curr, HashSet ## Name * _set); \
31 void deleteIter ## Name(HSIterator ## Name *hsit); \
32 bool hasNext ## Name(HSIterator ## Name *hsit); \
33 _Key next ## Name(HSIterator ## Name *hsit); \
34 _Key currKey ## Name(HSIterator ## Name *hsit); \
35 void removeIter ## Name(HSIterator ## Name *hsit); \
36 struct HashSet ## Name { \
37 HashTable ## Name ## Set * table; \
38 LinkNode ## Name *list; \
39 LinkNode ## Name *tail; \
41 typedef struct HashSet ## Name HashSet ## Name; \
43 HashSet ## Name * allocHashSet ## Name (unsigned int initialcapacity, double factor); \
44 void deleteHashSet ## Name(struct HashSet ## Name * set); \
45 HashSet ## Name * copyHashSet ## Name(HashSet ## Name * set); \
46 void resetHashSet ## Name(HashSet ## Name * set); \
47 bool addHashSet ## Name(HashSet ## Name * set,_Key key); \
48 _Key getHashSet ## Name(HashSet ## Name * set,_Key key); \
49 _Key getHashSetFirstKey ## Name(HashSet ## Name * set); \
50 bool containsHashSet ## Name(HashSet ## Name * set,_Key key); \
51 bool removeHashSet ## Name(HashSet ## Name * set,_Key key); \
52 unsigned int getSizeHashSet ## Name(HashSet ## Name * set); \
53 bool isEmptyHashSet ## Name(HashSet ## Name * set); \
54 HSIterator ## Name * iterator ## Name(HashSet ## Name * set);
57 #define HashSetImpl(Name, _Key, hash_function, equals) \
58 HashTableImpl(Name ## Set, _Key, LinkNode ## Name *, hash_function, equals, ourfree); \
59 HSIterator ## Name * allocHSIterator ## Name(LinkNode ## Name *_curr, HashSet ## Name * _set) { \
60 HSIterator ## Name * hsit = (HSIterator ## Name *)ourmalloc(sizeof(HSIterator ## Name)); \
66 void deleteIter ## Name(HSIterator ## Name *hsit) { \
70 bool hasNext ## Name(HSIterator ## Name *hsit) { \
71 return hsit->curr!=NULL; \
74 _Key next ## Name(HSIterator ## Name *hsit) { \
75 _Key k=hsit->curr->key; \
76 hsit->last=hsit->curr; \
77 hsit->curr=hsit->curr->next; \
81 _Key currKey ## Name(HSIterator ## Name *hsit) { \
82 return hsit->last->key; \
85 void removeIter ## Name(HSIterator ## Name *hsit) { \
86 _Key k=hsit->last->key; \
87 removeHashSet ## Name(hsit->set, k); \
90 HashSet ## Name * allocHashSet ## Name (unsigned int initialcapacity, double factor) { \
91 HashSet ## Name * set = (HashSet ## Name *)ourmalloc(sizeof(struct HashSet ## Name)); \
92 set->table=allocHashTable ## Name ## Set(initialcapacity, factor); \
98 void deleteHashSet ## Name(struct HashSet ## Name * set) { \
99 LinkNode ## Name *tmp=set->list; \
101 LinkNode ## Name *tmpnext=tmp->next; \
105 deleteHashTable ## Name ## Set(set->table); \
109 HashSet ## Name * copyHashSet ## Name(HashSet ## Name * set) { \
110 HashSet ## Name *copy=allocHashSet ## Name(getCapacity ## Name ## Set(set->table), getLoadFactor ## Name ## Set(set->table)); \
111 HSIterator ## Name * it=iterator ## Name(set); \
112 while(hasNext ## Name(it)) \
113 addHashSet ## Name(copy, next ## Name(it)); \
114 deleteIter ## Name(it); \
118 void resetHashSet ## Name(HashSet ## Name * set) { \
119 LinkNode ## Name *tmp=set->list; \
121 LinkNode ## Name *tmpnext=tmp->next; \
125 set->list=set->tail=NULL; \
126 reset ## Name ## Set(set->table); \
129 bool addHashSet ## Name(HashSet ## Name * set,_Key key) { \
130 LinkNode ## Name * val=get ## Name ## Set(set->table, key); \
132 LinkNode ## Name * newnode=(LinkNode ## Name *)ourmalloc(sizeof(struct LinkNode ## Name)); \
133 newnode->prev=set->tail; \
134 newnode->next=NULL; \
136 if (set->tail!=NULL) \
137 set->tail->next=newnode; \
141 put ## Name ## Set(set->table, key, newnode); \
147 _Key getHashSet ## Name(HashSet ## Name * set,_Key key) { \
148 LinkNode ## Name * val=get ## Name ## Set(set->table, key); \
155 _Key getHashSetFirstKey ## Name(HashSet ## Name * set) { \
156 return set->list->key; \
159 bool containsHashSet ## Name(HashSet ## Name * set,_Key key) { \
160 return get ## Name ## Set(set->table, key)!=NULL; \
163 bool removeHashSet ## Name(HashSet ## Name * set,_Key key) { \
164 LinkNode ## Name * oldlinknode; \
165 oldlinknode=get ## Name ## Set(set->table, key); \
166 if (oldlinknode==NULL) { \
169 remove ## Name ## Set(set->table, key); \
171 if (oldlinknode->prev==NULL) \
172 set->list=oldlinknode->next; \
174 oldlinknode->prev->next=oldlinknode->next; \
175 if (oldlinknode->next!=NULL) \
176 oldlinknode->next->prev=oldlinknode->prev; \
178 set->tail=oldlinknode->prev; \
179 ourfree(oldlinknode); \
183 unsigned int getSizeHashSet ## Name(HashSet ## Name * set) { \
184 return getSizeTable ## Name ## Set(set->table); \
187 bool isEmptyHashSet ## Name(HashSet ## Name * set) { \
188 return getSizeHashSet ## Name(set)==0; \
191 HSIterator ## Name * iterator ## Name(HashSet ## Name * set) { \
192 return allocHSIterator ## Name(set->list, set); \