use the hashset and hashtable implementation from satcheck repo
authorweiyu <weiyuluo1232@gmail.com>
Mon, 15 Jul 2019 18:31:53 +0000 (11:31 -0700)
committerweiyu <weiyuluo1232@gmail.com>
Mon, 15 Jul 2019 18:31:53 +0000 (11:31 -0700)
hashset.h [new file with mode: 0644]
hashtable.h

diff --git a/hashset.h b/hashset.h
new file mode 100644 (file)
index 0000000..140b85f
--- /dev/null
+++ b/hashset.h
@@ -0,0 +1,221 @@
+/*      Copyright (c) 2015 Regents of the University of California
+ *
+ *      Author: Brian Demsky <bdemsky@uci.edu>
+ *
+ *      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<typename _Key>
+struct LinkNode {
+       _Key key;
+       LinkNode<_Key> *prev;
+       LinkNode<_Key> *next;
+};
+
+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)>
+class HashSet;
+
+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) = default_hash_function<_Key, _Shift, _KeyInt>, 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<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> >
+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
index 20fa56e..16744bb 100644 (file)
@@ -1,3 +1,12 @@
+/*      Copyright (c) 2015 Regents of the University of California
+ *
+ *      Author: Brian Demsky <bdemsky@uci.edu>
+ *
+ *      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 <stdlib.h>
 #include <stdio.h>
 #include <string.h>
-#include "stl-model.h"
 #include "mymemory.h"
 #include "common.h"
 
@@ -24,6 +32,16 @@ struct hashlistnode {
        _Val val;
 };
 
+template<typename _Key, int _Shift, typename _KeyInt>
+inline unsigned int default_hash_function(_Key hash) {
+       return (unsigned int)(((_KeyInt)hash) >> _Shift);
+}
+
+template<typename _Key>
+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<typename _Key, typename _Val, typename _KeyInt, int _Shift = 0, void * (*_malloc)(size_t) = snapshot_malloc, void * (*_calloc)(size_t, size_t) = snapshot_calloc, void (*_free)(void *) = snapshot_free>
+template<typename _Key, typename _Val, 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> >
 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<capacity;i++) {
+                       struct hashlistnode<_Key, _Val> *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<capacity;i++) {
+                       struct hashlistnode<_Key, _Val> *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__ */