d660620fe9cef6574ec15b18a2ad6e4d62f033d4
[c11tester.git] / 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 template<typename _Key>
15 struct LinkNode {
16         _Key key;
17         LinkNode<_Key> *prev;
18         LinkNode<_Key> *next;
19 };
20
21 template<typename _Key, typename _KeyInt, int _Shift, void * (* _malloc)(size_t), void * (* _calloc)(size_t, size_t), void (*_free)(void *), unsigned int (*hash_function)(_Key), bool (*equals)(_Key, _Key)>
22 class HashSet;
23
24 template<typename _Key, typename _KeyInt, int _Shift, void * (* _malloc)(size_t) = snapshot_malloc, void * (* _calloc)(size_t, size_t) = snapshot_calloc, void (*_free)(void *) = snapshot_free, unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
25 class HSIterator {
26 public:
27         HSIterator(LinkNode<_Key> *_curr, HashSet <_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * _set) :
28                 curr(_curr),
29                 set(_set)
30         {
31         }
32
33         /** Override: new operator */
34         void * operator new(size_t size) {
35                 return _malloc(size);
36         }
37
38         /** Override: delete operator */
39         void operator delete(void *p, size_t size) {
40                 _free(p);
41         }
42
43         /** Override: new[] operator */
44         void * operator new[](size_t size) {
45                 return _malloc(size);
46         }
47
48         /** Override: delete[] operator */
49         void operator delete[](void *p, size_t size) {
50                 _free(p);
51         }
52
53         bool hasNext() {
54                 return curr!=NULL;
55         }
56
57         _Key next() {
58                 _Key k=curr->key;
59                 last=curr;
60                 curr=curr->next;
61                 return k;
62         }
63
64         _Key currKey() {
65                 return last->key;
66         }
67
68         void remove() {
69                 _Key k=last->key;
70                 set->remove(k);
71         }
72
73 private:
74         LinkNode<_Key> *curr;
75         LinkNode<_Key> *last;
76         HashSet <_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * set;
77 };
78
79 template<typename _Key, typename _KeyInt, int _Shift = 0, void * (*_malloc)(size_t) = snapshot_malloc, void * (*_calloc)(size_t, size_t) = snapshot_calloc, void (*_free)(void *) = snapshot_free, unsigned int (*hash_function)(_Key) = default_hash_function<_Key, _Shift, _KeyInt>, bool (*equals)(_Key, _Key) = default_equals<_Key> >
80 class HashSet {
81 public:
82         HashSet(unsigned int initialcapacity = 16, double factor = 0.5) :
83                 table(new HashTable<_Key, LinkNode<_Key> *, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals>(initialcapacity, factor)),
84                 list(NULL),
85                 tail(NULL)
86         {
87         }
88
89         /** @brief Hashset destructor */
90         ~HashSet() {
91                 LinkNode<_Key> *tmp=list;
92                 while(tmp!=NULL) {
93                         LinkNode<_Key> *tmpnext=tmp->next;
94                         _free(tmp);
95                         tmp=tmpnext;
96                 }
97                 delete table;
98         }
99
100         HashSet<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * copy() {
101                 HashSet<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> *copy=new HashSet<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals>(table->getCapacity(), table->getLoadFactor());
102                 HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * it=iterator();
103                 while(it->hasNext())
104                         copy->add(it->next());
105                 delete it;
106                 return copy;
107         }
108
109         void reset() {
110                 LinkNode<_Key> *tmp=list;
111                 while(tmp!=NULL) {
112                         LinkNode<_Key> *tmpnext=tmp->next;
113                         _free(tmp);
114                         tmp=tmpnext;
115                 }
116                 list=tail=NULL;
117                 table->reset();
118         }
119
120         /** @brief Adds a new key to the hashset.  Returns false if the key
121          *  is already present. */
122
123         bool add(_Key key) {
124                 LinkNode<_Key> * val=table->get(key);
125                 if (val==NULL) {
126                         LinkNode<_Key> * newnode=(LinkNode<_Key> *)_malloc(sizeof(struct LinkNode<_Key>));
127                         newnode->prev=tail;
128                         newnode->next=NULL;
129                         newnode->key=key;
130                         if (tail!=NULL)
131                                 tail->next=newnode;
132                         else
133                                 list=newnode;
134                         tail=newnode;
135                         table->put(key, newnode);
136                         return true;
137                 } else
138                         return false;
139         }
140
141         /** @brief Gets the original key corresponding to this one from the
142          *  hashset.  Returns NULL if not present. */
143
144         _Key get(_Key key) {
145                 LinkNode<_Key> * val=table->get(key);
146                 if (val!=NULL)
147                         return val->key;
148                 else
149                         return NULL;
150         }
151
152         _Key getFirstKey() {
153                 return list->key;
154         }
155
156         bool contains(_Key key) {
157                 return table->get(key)!=NULL;
158         }
159
160         bool remove(_Key key) {
161                 LinkNode<_Key> * oldlinknode;
162                 oldlinknode=table->get(key);
163                 if (oldlinknode==NULL) {
164                         return false;
165                 }
166                 table->remove(key);
167
168                 //remove link node from the list
169                 if (oldlinknode->prev==NULL)
170                         list=oldlinknode->next;
171                 else
172                         oldlinknode->prev->next=oldlinknode->next;
173                 if (oldlinknode->next!=NULL)
174                         oldlinknode->next->prev=oldlinknode->prev;
175                 else
176                         tail=oldlinknode->prev;
177                 _free(oldlinknode);
178                 return true;
179         }
180
181         unsigned int getSize() {
182                 return table->getSize();
183         }
184
185         bool isEmpty() {
186                 return getSize()==0;
187         }
188
189
190
191         HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * iterator() {
192                 return new HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals>(list, this);
193         }
194
195         /** Override: new operator */
196         void * operator new(size_t size) {
197                 return _malloc(size);
198         }
199
200         /** Override: delete operator */
201         void operator delete(void *p, size_t size) {
202                 _free(p);
203         }
204
205         /** Override: new[] operator */
206         void * operator new[](size_t size) {
207                 return _malloc(size);
208         }
209
210         /** Override: delete[] operator */
211         void operator delete[](void *p, size_t size) {
212                 _free(p);
213         }
214 private:
215         HashTable<_Key, LinkNode<_Key>*, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * table;
216         LinkNode<_Key> *list;
217         LinkNode<_Key> *tail;
218 };
219 #endif