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 HashSet ## Name * allocDefHashSet ## Name (); \
45 void deleteHashSet ## Name(struct HashSet ## Name *set); \
46 HashSet ## Name * copyHashSet ## Name(HashSet ## Name * set); \
47 void resetHashSet ## Name(HashSet ## Name * set); \
48 bool addHashSet ## Name(HashSet ## Name * set,_Key key); \
49 void addAllHashSet ## Name(HashSet ## Name * set,HashSet ## Name * other); \
50 _Key getHashSet ## Name(HashSet ## Name * set,_Key key); \
51 _Key getHashSetFirstKey ## Name(HashSet ## Name * set); \
52 bool containsHashSet ## Name(HashSet ## Name * set,_Key key); \
53 bool removeHashSet ## Name(HashSet ## Name * set,_Key key); \
54 unsigned int getSizeHashSet ## Name(HashSet ## Name * set); \
55 bool isEmptyHashSet ## Name(HashSet ## Name * set); \
56 HSIterator ## Name * iterator ## Name(HashSet ## Name * set);
59 #define HashSetImpl(Name, _Key, hash_function, equals) \
60 HashTableImpl(Name ## Set, _Key, LinkNode ## Name *, hash_function, equals, ourfree); \
61 HSIterator ## Name * allocHSIterator ## Name(LinkNode ## Name * _curr, HashSet ## Name * _set) { \
62 HSIterator ## Name * hsit = (HSIterator ## Name *)ourmalloc(sizeof(HSIterator ## Name)); \
68 void deleteIter ## Name(HSIterator ## Name * hsit) { \
72 bool hasNext ## Name(HSIterator ## Name * hsit) { \
73 return hsit->curr != NULL; \
76 _Key next ## Name(HSIterator ## Name * hsit) { \
77 _Key k = hsit->curr->key; \
78 hsit->last = hsit->curr; \
79 hsit->curr = hsit->curr->next; \
83 _Key currKey ## Name(HSIterator ## Name * hsit) { \
84 return hsit->last->key; \
87 void removeIter ## Name(HSIterator ## Name * hsit) { \
88 _Key k = hsit->last->key; \
89 removeHashSet ## Name(hsit->set, k); \
92 HashSet ## Name * allocDefHashSet ## Name () { \
93 return allocHashSet ## Name(16, 0.25); \
96 HashSet ## Name * allocHashSet ## Name (unsigned int initialcapacity, double factor) { \
97 HashSet ## Name * set = (HashSet ## Name *)ourmalloc(sizeof(struct HashSet ## Name)); \
98 set->table = allocHashTable ## Name ## Set(initialcapacity, factor); \
104 void deleteHashSet ## Name(struct HashSet ## Name *set) { \
105 LinkNode ## Name *tmp = set->list; \
106 while (tmp != NULL) { \
107 LinkNode ## Name * tmpnext = tmp->next; \
111 deleteHashTable ## Name ## Set(set->table); \
115 HashSet ## Name * copyHashSet ## Name(HashSet ## Name * set) { \
116 HashSet ## Name * copy = allocHashSet ## Name(getCapacity ## Name ## Set(set->table), getLoadFactor ## Name ## Set(set->table)); \
117 HSIterator ## Name * it = iterator ## Name(set); \
118 while (hasNext ## Name(it)) \
119 addHashSet ## Name(copy, next ## Name(it)); \
120 deleteIter ## Name(it); \
124 void resetHashSet ## Name(HashSet ## Name * set) { \
125 LinkNode ## Name * tmp = set->list; \
126 while (tmp != NULL) { \
127 LinkNode ## Name * tmpnext = tmp->next; \
131 set->list = set->tail = NULL; \
132 reset ## Name ## Set(set->table); \
135 void addAllHashSet ## Name(HashSet ## Name * set, HashSet ## Name * other) { \
136 HSIterator ## Name * it = iterator ## Name(other); \
137 while (hasNext ## Name(it)) \
138 addHashSet ## Name(set, next ## Name(it)); \
139 deleteIter ## Name(it); \
142 bool addHashSet ## Name(HashSet ## Name * set,_Key key) { \
143 LinkNode ## Name * val = get ## Name ## Set(set->table, key); \
145 LinkNode ## Name * newnode = (LinkNode ## Name *)ourmalloc(sizeof(struct LinkNode ## Name)); \
146 newnode->prev = set->tail; \
147 newnode->next = NULL; \
148 newnode->key = key; \
149 if (set->tail != NULL) \
150 set->tail->next = newnode; \
152 set->list = newnode; \
153 set->tail = newnode; \
154 put ## Name ## Set(set->table, key, newnode); \
160 _Key getHashSet ## Name(HashSet ## Name * set,_Key key) { \
161 LinkNode ## Name * val = get ## Name ## Set(set->table, key); \
168 _Key getHashSetFirstKey ## Name(HashSet ## Name * set) { \
169 return set->list->key; \
172 bool containsHashSet ## Name(HashSet ## Name * set,_Key key) { \
173 return get ## Name ## Set(set->table, key) != NULL; \
176 bool removeHashSet ## Name(HashSet ## Name * set,_Key key) { \
177 LinkNode ## Name * oldlinknode; \
178 oldlinknode = get ## Name ## Set(set->table, key); \
179 if (oldlinknode == NULL) { \
182 remove ## Name ## Set(set->table, key); \
184 if (oldlinknode->prev == NULL) \
185 set->list = oldlinknode->next; \
187 oldlinknode->prev->next = oldlinknode->next; \
188 if (oldlinknode->next != NULL) \
189 oldlinknode->next->prev = oldlinknode->prev; \
191 set->tail = oldlinknode->prev; \
192 ourfree(oldlinknode); \
196 unsigned int getSizeHashSet ## Name(HashSet ## Name * set) { \
197 return getSizeTable ## Name ## Set(set->table); \
200 bool isEmptyHashSet ## Name(HashSet ## Name * set) { \
201 return getSizeHashSet ## Name(set) == 0; \
204 HSIterator ## Name * iterator ## Name(HashSet ## Name * set) { \
205 return allocHSIterator ## Name(set->list, set); \