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 void addAllHashSet ## Name(HashSet ## Name * set,HashSet ## Name * other); \
49 _Key getHashSet ## Name(HashSet ## Name * set,_Key key); \
50 _Key getHashSetFirstKey ## Name(HashSet ## Name * set); \
51 bool containsHashSet ## Name(HashSet ## Name * set,_Key key); \
52 bool removeHashSet ## Name(HashSet ## Name * set,_Key key); \
53 unsigned int getSizeHashSet ## Name(HashSet ## Name * set); \
54 bool isEmptyHashSet ## Name(HashSet ## Name * set); \
55 HSIterator ## Name * iterator ## Name(HashSet ## Name * set);
58 #define HashSetImpl(Name, _Key, hash_function, equals) \
59 HashTableImpl(Name ## Set, _Key, LinkNode ## Name *, hash_function, equals, ourfree); \
60 HSIterator ## Name * allocHSIterator ## Name(LinkNode ## Name * _curr, HashSet ## Name * _set) { \
61 HSIterator ## Name * hsit = (HSIterator ## Name *)ourmalloc(sizeof(HSIterator ## Name)); \
67 void deleteIter ## Name(HSIterator ## Name * hsit) { \
71 bool hasNext ## Name(HSIterator ## Name * hsit) { \
72 return hsit->curr != NULL; \
75 _Key next ## Name(HSIterator ## Name * hsit) { \
76 _Key k = hsit->curr->key; \
77 hsit->last = hsit->curr; \
78 hsit->curr = hsit->curr->next; \
82 _Key currKey ## Name(HSIterator ## Name * hsit) { \
83 return hsit->last->key; \
86 void removeIter ## Name(HSIterator ## Name * hsit) { \
87 _Key k = hsit->last->key; \
88 removeHashSet ## Name(hsit->set, k); \
91 HashSet ## Name * allocHashSet ## Name (unsigned int initialcapacity, double factor) { \
92 HashSet ## Name * set = (HashSet ## Name *)ourmalloc(sizeof(struct HashSet ## Name)); \
93 set->table = allocHashTable ## Name ## Set(initialcapacity, factor); \
99 void deleteHashSet ## Name(struct HashSet ## Name *set) { \
100 LinkNode ## Name *tmp = set->list; \
101 while (tmp != NULL) { \
102 LinkNode ## Name * tmpnext = tmp->next; \
106 deleteHashTable ## Name ## Set(set->table); \
110 HashSet ## Name * copyHashSet ## Name(HashSet ## Name * set) { \
111 HashSet ## Name * copy = allocHashSet ## Name(getCapacity ## Name ## Set(set->table), getLoadFactor ## Name ## Set(set->table)); \
112 HSIterator ## Name * it = iterator ## Name(set); \
113 while (hasNext ## Name(it)) \
114 addHashSet ## Name(copy, next ## Name(it)); \
115 deleteIter ## Name(it); \
119 void resetHashSet ## Name(HashSet ## Name * set) { \
120 LinkNode ## Name * tmp = set->list; \
121 while (tmp != NULL) { \
122 LinkNode ## Name * tmpnext = tmp->next; \
126 set->list = set->tail = NULL; \
127 reset ## Name ## Set(set->table); \
130 void addAllHashSet ## Name(HashSet ## Name * set, HashSet ## Name * other) { \
131 HSIterator ## Name * it = iterator ## Name(other); \
132 while (hasNext ## Name(it)) \
133 addHashSet ## Name(set, next ## Name(it)); \
134 deleteIter ## Name(it); \
137 bool addHashSet ## Name(HashSet ## Name * set,_Key key) { \
138 LinkNode ## Name * val = get ## Name ## Set(set->table, key); \
140 LinkNode ## Name * newnode = (LinkNode ## Name *)ourmalloc(sizeof(struct LinkNode ## Name)); \
141 newnode->prev = set->tail; \
142 newnode->next = NULL; \
143 newnode->key = key; \
144 if (set->tail != NULL) \
145 set->tail->next = newnode; \
147 set->list = newnode; \
148 set->tail = newnode; \
149 put ## Name ## Set(set->table, key, newnode); \
155 _Key getHashSet ## Name(HashSet ## Name * set,_Key key) { \
156 LinkNode ## Name * val = get ## Name ## Set(set->table, key); \
163 _Key getHashSetFirstKey ## Name(HashSet ## Name * set) { \
164 return set->list->key; \
167 bool containsHashSet ## Name(HashSet ## Name * set,_Key key) { \
168 return get ## Name ## Set(set->table, key) != NULL; \
171 bool removeHashSet ## Name(HashSet ## Name * set,_Key key) { \
172 LinkNode ## Name * oldlinknode; \
173 oldlinknode = get ## Name ## Set(set->table, key); \
174 if (oldlinknode == NULL) { \
177 remove ## Name ## Set(set->table, key); \
179 if (oldlinknode->prev == NULL) \
180 set->list = oldlinknode->next; \
182 oldlinknode->prev->next = oldlinknode->next; \
183 if (oldlinknode->next != NULL) \
184 oldlinknode->next->prev = oldlinknode->prev; \
186 set->tail = oldlinknode->prev; \
187 ourfree(oldlinknode); \
191 unsigned int getSizeHashSet ## Name(HashSet ## Name * set) { \
192 return getSizeTable ## Name ## Set(set->table); \
195 bool isEmptyHashSet ## Name(HashSet ## Name * set) { \
196 return getSizeHashSet ## Name(set) == 0; \
199 HSIterator ## Name * iterator ## Name(HashSet ## Name * set) { \
200 return allocHSIterator ## Name(set->list, set); \