From 110873aa95a98a28561165f803d21a9b050205ed Mon Sep 17 00:00:00 2001 From: weiyu Date: Mon, 15 Jul 2019 11:31:53 -0700 Subject: [PATCH] use the hashset and hashtable implementation from satcheck repo --- hashset.h | 221 +++++++++++++++++++++++++++++++++++++++++++++++++++ hashtable.h | 222 +++++++++++++++++++++++++++++++++++++++------------- 2 files changed, 390 insertions(+), 53 deletions(-) create mode 100644 hashset.h diff --git a/hashset.h b/hashset.h new file mode 100644 index 00000000..140b85fb --- /dev/null +++ b/hashset.h @@ -0,0 +1,221 @@ +/* Copyright (c) 2015 Regents of the University of California + * + * Author: Brian Demsky + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * version 2 as published by the Free Software Foundation. + */ + +#ifndef HASH_SET_H +#define HASH_SET_H +#include "hashtable.h" + +template +struct LinkNode { + _Key key; + LinkNode<_Key> *prev; + LinkNode<_Key> *next; +}; + +template +class HashSet; + +template, bool (*equals)(_Key, _Key) = default_equals<_Key> > +class HSIterator { +public: + HSIterator(LinkNode<_Key> *_curr, HashSet <_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * _set) : + curr(_curr), + set(_set) + { + } + + /** Override: new operator */ + void * operator new(size_t size) { + return _malloc(size); + } + + /** Override: delete operator */ + void operator delete(void *p, size_t size) { + _free(p); + } + + /** Override: new[] operator */ + void * operator new[](size_t size) { + return _malloc(size); + } + + /** Override: delete[] operator */ + void operator delete[](void *p, size_t size) { + _free(p); + } + + bool hasNext() { + return curr!=NULL; + } + + _Key next() { + _Key k=curr->key; + last=curr; + curr=curr->next; + return k; + } + + _Key currKey() { + return last->key; + } + + void remove() { + _Key k=last->key; + set->remove(k); + } + +private: + LinkNode<_Key> *curr; + LinkNode<_Key> *last; + HashSet <_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * set; +}; + +template, bool (*equals)(_Key, _Key) = default_equals<_Key> > +class HashSet { +public: + HashSet(unsigned int initialcapacity = 16, double factor = 0.5) : + table(new HashTable<_Key, LinkNode<_Key> *, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals>(initialcapacity, factor)), + list(NULL), + tail(NULL) + { + } + + /** @brief Hashset destructor */ + ~HashSet() { + LinkNode<_Key> *tmp=list; + while(tmp!=NULL) { + LinkNode<_Key> *tmpnext=tmp->next; + _free(tmp); + tmp=tmpnext; + } + delete table; + } + + HashSet<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * copy() { + 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()); + HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * it=iterator(); + while(it->hasNext()) + copy->add(it->next()); + delete it; + return copy; + } + + void reset() { + LinkNode<_Key> *tmp=list; + while(tmp!=NULL) { + LinkNode<_Key> *tmpnext=tmp->next; + _free(tmp); + tmp=tmpnext; + } + list=tail=NULL; + table->reset(); + } + + /** @brief Adds a new key to the hashset. Returns false if the key + * is already present. */ + + bool add(_Key key) { + LinkNode<_Key> * val=table->get(key); + if (val==NULL) { + LinkNode<_Key> * newnode=(LinkNode<_Key> *)_malloc(sizeof(struct LinkNode<_Key>)); + newnode->prev=tail; + newnode->next=NULL; + newnode->key=key; + if (tail!=NULL) + tail->next=newnode; + else + list=newnode; + tail=newnode; + table->put(key, newnode); + return true; + } else + return false; + } + + /** @brief Gets the original key corresponding to this one from the + * hashset. Returns NULL if not present. */ + + _Key get(_Key key) { + LinkNode<_Key> * val=table->get(key); + if (val!=NULL) + return val->key; + else + return NULL; + } + + _Key getFirstKey() { + return list->key; + } + + bool contains(_Key key) { + return table->get(key)!=NULL; + } + + bool remove(_Key key) { + LinkNode<_Key> * oldlinknode; + oldlinknode=table->get(key); + if (oldlinknode==NULL) { + return false; + } + table->remove(key); + + //remove link node from the list + if (oldlinknode->prev==NULL) + list=oldlinknode->next; + else + oldlinknode->prev->next=oldlinknode->next; + if (oldlinknode->next!=NULL) + oldlinknode->next->prev=oldlinknode->prev; + else + tail=oldlinknode->prev; + _free(oldlinknode); + return true; + } + + unsigned int getSize() { + return table->getSize(); + } + + bool isEmpty() { + return getSize()==0; + } + + + + HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * iterator() { + return new HSIterator<_Key, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals>(list, this); + } + + /** Override: new operator */ + void * operator new(size_t size) { + return _malloc(size); + } + + /** Override: delete operator */ + void operator delete(void *p, size_t size) { + _free(p); + } + + /** Override: new[] operator */ + void * operator new[](size_t size) { + return _malloc(size); + } + + /** Override: delete[] operator */ + void operator delete[](void *p, size_t size) { + _free(p); + } +private: + HashTable<_Key, LinkNode<_Key>*, _KeyInt, _Shift, _malloc, _calloc, _free, hash_function, equals> * table; + LinkNode<_Key> *list; + LinkNode<_Key> *tail; +}; +#endif diff --git a/hashtable.h b/hashtable.h index 20fa56e7..16744bb4 100644 --- a/hashtable.h +++ b/hashtable.h @@ -1,3 +1,12 @@ +/* Copyright (c) 2015 Regents of the University of California + * + * Author: Brian Demsky + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * version 2 as published by the Free Software Foundation. + */ + /** @file hashtable.h * @brief Hashtable. Standard chained bucket variety. */ @@ -8,7 +17,6 @@ #include #include #include -#include "stl-model.h" #include "mymemory.h" #include "common.h" @@ -24,6 +32,16 @@ struct hashlistnode { _Val val; }; +template +inline unsigned int default_hash_function(_Key hash) { + return (unsigned int)(((_KeyInt)hash) >> _Shift); +} + +template +inline bool default_equals(_Key key1, _Key key2) { + return key1 == key2; +} + /** * @brief A simple, custom hash table * @@ -44,7 +62,7 @@ struct hashlistnode { * @tparam _free Provide your own 'free' for the table, or default to * snapshotting. */ -template +template, bool (*equals)(_Key, _Key) = default_equals<_Key> > class HashTable { public: /** @@ -57,20 +75,20 @@ public: HashTable(unsigned int initialcapacity = 1024, double factor = 0.5) { // Allocate space for the hash table table = (struct hashlistnode<_Key, _Val> *)_calloc(initialcapacity, sizeof(struct hashlistnode<_Key, _Val>)); - keyset = (_Key *)_calloc(initialcapacity, sizeof(_Key)); - keyset_end = keyset; + zero = NULL; loadfactor = factor; capacity = initialcapacity; capacitymask = initialcapacity - 1; threshold = (unsigned int)(initialcapacity * loadfactor); - size = 0; // Initial number of elements in the hash + size = 0; // Initial number of elements in the hash } /** @brief Hash table destructor */ ~HashTable() { _free(table); - _free(keyset); + if (zero) + _free(zero); } /** Override: new operator */ @@ -96,7 +114,50 @@ public: /** @brief Reset the table to its initial state. */ void reset() { memset(table, 0, capacity * sizeof(struct hashlistnode<_Key, _Val>)); - memset(keyset, 0, capacity * sizeof(_Key)); + if (zero) { + _free(zero); + zero = NULL; + } + size = 0; + } + + void resetanddelete() { + for(unsigned int i=0;i *bin = &table[i]; + if (bin->key != NULL) { + bin->key = NULL; + if (bin->val != NULL) { + delete bin->val; + bin->val = NULL; + } + } + } + if (zero) { + if (zero->val != NULL) + delete zero->val; + _free(zero); + zero = NULL; + } + size = 0; + } + + void resetandfree() { + for(unsigned int i=0;i *bin = &table[i]; + if (bin->key != NULL) { + bin->key = NULL; + if (bin->val != NULL) { + _free(bin->val); + bin->val = NULL; + } + } + } + if (zero) { + if (zero->val != NULL) + _free(zero->val); + _free(zero); + zero = NULL; + } size = 0; } @@ -107,28 +168,38 @@ public: */ void put(_Key key, _Val val) { /* HashTable cannot handle 0 as a key */ - ASSERT(key); + if (!key) { + if (!zero) { + zero=(struct hashlistnode<_Key, _Val> *)_malloc(sizeof(struct hashlistnode<_Key, _Val>)); + size++; + } + zero->key=key; + zero->val=val; + return; + } if (size > threshold) resize(capacity << 1); struct hashlistnode<_Key, _Val> *search; - unsigned int index = ((_KeyInt)key) >> _Shift; + unsigned int index = hash_function(key); do { index &= capacitymask; search = &table[index]; - if (search->key == key) { + if (!search->key) { + //key is null, probably done + break; + } + if (equals(search->key, key)) { search->val = val; return; } index++; - } while (search->key); + } while (true); search->key = key; search->val = val; - *keyset_end = key; - keyset_end++; size++; } @@ -141,19 +212,79 @@ public: struct hashlistnode<_Key, _Val> *search; /* HashTable cannot handle 0 as a key */ - ASSERT(key); + if (!key) { + if (zero) + return zero->val; + else + return (_Val) 0; + } - unsigned int index = ((_KeyInt)key) >> _Shift; + unsigned int oindex = hash_function(key) & capacitymask; + unsigned int index=oindex; do { - index &= capacitymask; search = &table[index]; - if (search->key == key) + if (!search->key) { + if (!search->val) + break; + } else + if (equals(search->key, key)) return search->val; index++; - } while (search->key); + index &= capacitymask; + if (index==oindex) + break; + } while (true); + return (_Val)0; + } + + /** + * @brief Remove the given key and return the corresponding value + * @param key The key for finding the value; must not be 0 or NULL + * @return The value in the table, if the key is found; otherwise 0 + */ + _Val remove(_Key key) { + struct hashlistnode<_Key, _Val> *search; + + /* HashTable cannot handle 0 as a key */ + if (!key) { + if (!zero) { + return (_Val)0; + } else { + _Val v=zero->val; + _free(zero); + zero=NULL; + size--; + return v; + } + } + + + unsigned int index = hash_function(key); + do { + index &= capacitymask; + search = &table[index]; + if (!search->key) { + if (!search->val) + break; + } else + if (equals(search->key, key)) { + _Val v=search->val; + //empty out this bin + search->val=(_Val) 1; + search->key=0; + size--; + return v; + } + index++; + } while (true); return (_Val)0; } + unsigned int getSize() const { + return size; + } + + /** * @brief Check whether the table contains a value for the given key * @param key The key for finding the value; must not be 0 or NULL @@ -163,16 +294,22 @@ public: struct hashlistnode<_Key, _Val> *search; /* HashTable cannot handle 0 as a key */ - ASSERT(key); + if (!key) { + return zero!=NULL; + } - unsigned int index = ((_KeyInt)key) >> _Shift; + unsigned int index = hash_function(key); do { index &= capacitymask; search = &table[index]; - if (search->key == key) + if (!search->key) { + if (!search->val) + break; + } else + if (equals(search->key, key)) return true; index++; - } while (search->key); + } while (true); return false; } @@ -183,9 +320,6 @@ public: void resize(unsigned int newsize) { struct hashlistnode<_Key, _Val> *oldtable = table; struct hashlistnode<_Key, _Val> *newtable; - _Key *oldkeyset = keyset; - _Key *newkeyset; - unsigned int oldcapacity = capacity; if ((newtable = (struct hashlistnode<_Key, _Val> *)_calloc(newsize, sizeof(struct hashlistnode<_Key, _Val>))) == NULL) { @@ -193,15 +327,7 @@ public: exit(EXIT_FAILURE); } - if ((newkeyset = (_Key *)_calloc(newsize, sizeof(_Key))) == NULL ) { - model_print("calloc error %s %d\n", __FILE__, __LINE__); - exit(EXIT_FAILURE); - } - - table = newtable; // Update the global hashtable upon resize() - keyset = newkeyset; - keyset_end = newkeyset; - + table = newtable; // Update the global hashtable upon resize() capacity = newsize; capacitymask = newsize - 1; @@ -213,8 +339,10 @@ public: _Key key = bin->key; struct hashlistnode<_Key, _Val> *search; + if (!key) + continue; - unsigned int index = ((_KeyInt)key) >> _Shift; + unsigned int index = hash_function(key); do { index &= capacitymask; search = &table[index]; @@ -225,30 +353,18 @@ public: search->val = bin->val; } - memcpy(keyset, oldkeyset, size * sizeof(_Key)); // copy keyset - keyset_end = keyset + size; // pointer arithmetic - - _free(oldtable); // Free the memory of the old hash table - _free(oldkeyset); + _free(oldtable); // Free the memory of the old hash table } - - _Key * getKeySet() { - return keyset; - } - - unsigned int getSize() { - return size; - } - -private: + double getLoadFactor() {return loadfactor;} + unsigned int getCapacity() {return capacity;} struct hashlistnode<_Key, _Val> *table; - _Key *keyset; - _Key *keyset_end; + struct hashlistnode<_Key, _Val> *zero; unsigned int capacity; unsigned int size; +private: unsigned int capacitymask; unsigned int threshold; double loadfactor; }; -#endif /* __HASHTABLE_H__ */ +#endif/* __HASHTABLE_H__ */ -- 2.34.1