From: bdemsky Date: Thu, 15 Jun 2017 03:30:03 +0000 (-0700) Subject: Finish rewriting Set/Table/Vector X-Git-Url: http://plrg.eecs.uci.edu/git/?p=satune.git;a=commitdiff_plain;h=5a24361bea3bece3f1a7c8aed2740b6ead119183;hp=27341bc75070b0eea154159c513c7751f1532121 Finish rewriting Set/Table/Vector --- diff --git a/src/element.c b/src/element.c index e9284f7..2513fe5 100644 --- a/src/element.c +++ b/src/element.c @@ -1,7 +1,7 @@ #include "element.h" Element *allocElement(Set * s) { - Element * tmp=(Element *)ouralloc(sizeof(Element)); + Element * tmp=(Element *)ourmalloc(sizeof(Element)); tmp->set=s; return tmp; } diff --git a/src/hashset.h b/src/hashset.h index adb3ce9..fe18631 100644 --- a/src/hashset.h +++ b/src/hashset.h @@ -11,11 +11,11 @@ #define HASH_SET_H #include "hashtable.h" -#define HashSetDef(Name, _Key, _KeyInt, _Shift, hash_function, equals) \ - struct LinkNode ## Name{ \ - _Key key; \ - struct LinkNode ## Name *prev; \ - struct LinkNode ## Name *next; \ +#define HashSetDef(Name, _Key, hash_function, equals) \ + struct LinkNode ## Name { \ + _Key key; \ + struct LinkNode ## Name *prev; \ + struct LinkNode ## Name *next; \ }; \ typedef struct LinkNode ## Name LinkNode ## Name; \ struct HashSet ## Name; \ @@ -25,15 +25,16 @@ LinkNode ## Name *last; \ HashSet ## Name * set; \ }; \ - \ + typedef struct HSIterator ## Name HSIterator ## Name; \ + HashTableDef(Name ## Set, _Key, LinkNode ## Name *, hash_function, equals); \ HSIterator ## Name * allocHSIterator ## Name(LinkNode ## Name *_curr, HashSet ## Name * _set); \ void freeIter ## Name(HSIterator ## Name *hsit); \ bool hasNext ## Name(HSIterator ## Name *hsit); \ _Key next ## Name(HSIterator ## Name *hsit); \ _Key currKey ## Name(HSIterator ## Name *hsit); \ - void remove ## Name(HSIterator ## Name *hsit); \ + void removeIter ## Name(HSIterator ## Name *hsit); \ struct HashSet ## Name { \ - HashTable ## Name * table; \ + HashTable ## Name ## Set * table; \ LinkNode ## Name *list; \ LinkNode ## Name *tail; \ }; \ @@ -42,22 +43,24 @@ HashSet ## Name * allocHashSet ## Name (unsigned int initialcapacity, double factor); \ void freeHashSet ## Name(struct HashSet ## Name * set); \ HashSet ## Name * copy ## Name(HashSet ## Name * set); \ - void reset ## Name(HashSet ## Name * set); \ + void resetSet ## Name(HashSet ## Name * set); \ bool add ## Name(HashSet ## Name * set,_Key key); \ - _Key get ## Name(HashSet ## Name * set,_Key key); \ + _Key getSet ## Name(HashSet ## Name * set,_Key key); \ _Key getFirstKey ## Name(HashSet ## Name * set); \ - bool contains ## Name(HashSet ## Name * set,_Key key); \ - bool remove ## Name(HashSet ## Name * set,_Key key); \ - unsigned int getSize ## Name(HashSet ## Name * set); \ + bool containsSet ## Name(HashSet ## Name * set,_Key key); \ + bool removeSet ## Name(HashSet ## Name * set,_Key key); \ + unsigned int getSizeSet ## Name(HashSet ## Name * set); \ bool isEmpty ## Name(HashSet ## Name * set); \ HSIterator ## Name * iterator ## Name(HashSet ## Name * set); -#define HashSetDef(Name, _Key, _KeyInt, _Shift, hash_function, equals) \ +#define HashSetImpl(Name, _Key, hash_function, equals) \ + HashTableImpl(Name ## Set, _Key, LinkNode ## Name *, hash_function, equals); \ HSIterator ## Name * allocHSIterator ## Name(LinkNode ## Name *_curr, HashSet ## Name * _set) { \ - HSIterator ## Name * hsit = (HSIterator ## Name *) ouralloc(sizeof(HSIterator ## Name)); \ + HSIterator ## Name * hsit = (HSIterator ## Name *) ourmalloc(sizeof(HSIterator ## Name)); \ hsit->curr=_curr; \ hsit->set=_set; \ + return hsit; \ } \ \ void freeIter ## Name(HSIterator ## Name *hsit) { \ @@ -79,17 +82,18 @@ return hsit->last->key; \ } \ \ - void remove ## Name(HSIterator ## Name *hsit) { \ + void removeIter ## Name(HSIterator ## Name *hsit) { \ _Key k=hsit->last->key; \ - remove ## Name(hsit->set, k); \ + removeSet ## Name(hsit->set, k); \ } \ \ HashSet ## Name * allocHashSet ## Name (unsigned int initialcapacity, double factor) { \ - HashSet ## Name * set = (HashSet ## Name *) ouralloc(sizeof(struct HashSet ## Name)); \ - set->table=allocHashTable ## Name(initialcapcity, factor); \ + HashSet ## Name * set = (HashSet ## Name *) ourmalloc(sizeof(struct HashSet ## Name)); \ + set->table=allocHashTable ## Name ## Set(initialcapacity, factor); \ set->list=NULL; \ set->tail=NULL; \ - } \ + return set; \ +} \ \ void freeHashSet ## Name(struct HashSet ## Name * set) { \ LinkNode ## Name *tmp=set->list; \ @@ -98,20 +102,20 @@ ourfree(tmp); \ tmp=tmpnext; \ } \ - freeHashTable ## Name(set->table); \ + freeHashTable ## Name ## Set(set->table); \ ourfree(set); \ } \ \ HashSet ## Name * copy ## Name(HashSet ## Name * set) { \ - HashSet ## Name *copy=new HashSet ## Name(getCapacity ## Name(set->table), getLoadFactor ## Name(set->table)); \ + HashSet ## Name *copy=allocHashSet ## Name(getCapacity ## Name ## Set(set->table), getLoadFactor ## Name ## Set(set->table)); \ HSIterator ## Name * it=iterator ## Name(set); \ while(hasNext ## Name(it)) \ add ## Name(copy, next ## Name(it)); \ - freeIt ## Name(it); \ + freeIter ## Name(it); \ return copy; \ } \ \ - void reset ## Name(HashSet ## Name * set) { \ + void resetSet ## Name(HashSet ## Name * set) { \ LinkNode ## Name *tmp=set->list; \ while(tmp!=NULL) { \ LinkNode ## Name *tmpnext=tmp->next; \ @@ -119,11 +123,11 @@ tmp=tmpnext; \ } \ set->list=set->tail=NULL; \ - reset ## Name(set->table); \ + reset ## Name ## Set(set->table); \ } \ \ bool add ## Name(HashSet ## Name * set,_Key key) { \ - LinkNode ## Name * val=get ## Name(set->table, key); \ + LinkNode ## Name * val=get ## Name ## Set(set->table, key); \ if (val==NULL) { \ LinkNode ## Name * newnode=(LinkNode ## Name *)ourmalloc(sizeof(struct LinkNode ## Name)); \ newnode->prev=set->tail; \ @@ -134,14 +138,14 @@ else \ set->list=newnode; \ set->tail=newnode; \ - put ## Name(set->table, key, newnode); \ + put ## Name ## Set(set->table, key, newnode); \ return true; \ } else \ return false; \ } \ \ - _Key get ## Name(HashSet ## Name * set,_Key key) { \ - LinkNode ## Name * val=get ## Name(set->table, key); \ + _Key getSet ## Name(HashSet ## Name * set,_Key key) { \ + LinkNode ## Name * val=get ## Name ## Set(set->table, key); \ if (val!=NULL) \ return val->key; \ else \ @@ -152,17 +156,17 @@ return set->list->key; \ } \ \ - bool contains ## Name(HashSet ## Name * set,_Key key) { \ - return get ## Name(set->table, key)!=NULL; \ + bool containsSet ## Name(HashSet ## Name * set,_Key key) { \ + return get ## Name ## Set(set->table, key)!=NULL; \ } \ \ - bool remove ## Name(HashSet ## Name * set,_Key key) { \ + bool removeSet ## Name(HashSet ## Name * set,_Key key) { \ LinkNode ## Name * oldlinknode; \ - oldlinknode=get ## Name(set->table, key); \ + oldlinknode=get ## Name ## Set(set->table, key); \ if (oldlinknode==NULL) { \ return false; \ } \ - remove ## Name(set->table, key); \ + remove ## Name ## Set(set->table, key); \ \ if (oldlinknode->prev==NULL) \ set->list=oldlinknode->next; \ @@ -176,15 +180,15 @@ return true; \ } \ \ - unsigned int getSize ## Name(HashSet ## Name * set) { \ - return getSize ## Name (set->table); \ + unsigned int getSizeSet ## Name(HashSet ## Name * set) { \ + return getSizeTable ## Name ## Set(set->table); \ } \ \ bool isEmpty ## Name(HashSet ## Name * set) { \ - return getSize ## Name(set)==0; \ + return getSizeSet ## Name(set)==0; \ } \ \ HSIterator ## Name * iterator ## Name(HashSet ## Name * set) { \ - return allocHSIterator ## Name(set->list, this); \ + return allocHSIterator ## Name(set->list, set); \ } #endif diff --git a/src/hashtable.h b/src/hashtable.h index 752e920..8a9ebb0 100644 --- a/src/hashtable.h +++ b/src/hashtable.h @@ -30,11 +30,8 @@ * * @tparam _Key Type name for the key * @tparam _Val Type name for the values to be stored - * @tparam _KeyInt Integer type that is at least as large as _Key. Used for key - * manipulation and storage. - * @tparam _Shift Logical shift to apply to all keys. Default 0. */ -#define HashTableDef(Name, _Key, _Val, _KeyInt, _Shift, hash_function, equals)\ +#define HashTableDef(Name, _Key, _Val, hash_function, equals)\ struct hashlistnode ## Name { \ _Key key; \ _Val val; \ @@ -56,15 +53,15 @@ void reset ## Name(HashTable ## Name * tab); \ void resetandfree ## Name(HashTable ## Name * tab); \ void put ## Name(HashTable ## Name * tab, _Key key, _Val val); \ - _Val get ## Name(HashTable ## Name * tab, _Key key) const; \ + _Val get ## Name(const HashTable ## Name * tab, _Key key); \ _Val remove ## Name(HashTable ## Name * tab, _Key key); \ - unsigned int getSize ## Name(HashTable ## Name * tab, ) const; \ - bool contains ## Name(HashTable ## Name * tab, _Key key) const; \ + unsigned int getSizeTable ## Name(const HashTable ## Name * tab); \ + bool contains ## Name(const HashTable ## Name * tab, _Key key); \ void resize ## Name(HashTable ## Name * tab, unsigned int newsize); \ double getLoadFactor ## Name(HashTable ## Name * tab); \ unsigned int getCapacity ## Name(HashTable ## Name * tab); -#define HashTableDef(Name, _Key, _Val, _KeyInt, _Shift, hash_function, equals) \ +#define HashTableImpl(Name, _Key, _Val, hash_function, equals) \ HashTable ## Name * allocHashTable ## Name(unsigned int initialcapacity, double factor) { \ HashTable ## Name * tab = (HashTable ## Name *) ourmalloc(sizeof(HashTable ## Name)); \ tab -> table = (struct hashlistnode ## Name *) ourcalloc(initialcapacity, sizeof(struct hashlistnode ## Name)); \ @@ -73,11 +70,12 @@ tab->capacity = initialcapacity; \ tab->capacitymask = initialcapacity - 1; \ \ - tab->threshold = (unsigned int)(initialcapacity * loadfactor); \ + tab->threshold = (unsigned int)(initialcapacity * factor); \ tab->size = 0; \ + return tab; \ } \ \ - void freeHashTable ## Name(HashTable ## Name * tab) { \ + void freeHashTable ## Name(HashTable ## Name * tab) { \ ourfree(tab->table); \ if (tab->zero) \ ourfree(tab->zero); \ @@ -85,7 +83,7 @@ } \ \ void reset ## Name(HashTable ## Name * tab) { \ - memset(tab->table, 0, capacity * sizeof(struct hashlistnode ## Name)); \ + memset(tab->table, 0, tab->capacity * sizeof(struct hashlistnode ## Name)); \ if (tab->zero) { \ ourfree(tab->zero); \ tab->zero = NULL; \ @@ -124,8 +122,8 @@ return; \ } \ \ - if (tab->size > tab->threshold) \ - resize(tab->capacity << 1); \ + if (tab->size > tab->threshold) \ + resize ## Name (tab, tab->capacity << 1); \ \ struct hashlistnode ## Name *search; \ \ @@ -148,7 +146,7 @@ tab->size++; \ } \ \ - _Val get ## Name(HashTable ## Name * tab, _Key key) const { \ + _Val get ## Name(const HashTable ## Name * tab, _Key key) { \ struct hashlistnode ## Name *search; \ \ if (!key) { \ @@ -211,12 +209,12 @@ return (_Val)0; \ } \ \ - unsigned int getSize ## Name(HashTable ## Name * tab, ) const { \ + unsigned int getSizeTable ## Name(const HashTable ## Name * tab) { \ return tab->size; \ } \ \ \ - bool contains ## Name(HashTable ## Name * tab, _Key key) const { \ + bool contains ## Name(const HashTable ## Name * tab, _Key key) { \ struct hashlistnode ## Name *search; \ if (!key) { \ return tab->zero!=NULL; \ @@ -250,7 +248,7 @@ tab->capacity = newsize; \ tab->capacitymask = newsize - 1; \ \ - tab->threshold = (unsigned int)(newsize * loadfactor); \ + tab->threshold = (unsigned int)(newsize * tab->loadfactor); \ \ struct hashlistnode ## Name *bin = &oldtable[0]; \ struct hashlistnode ## Name *lastbin = &oldtable[oldcapacity]; \ diff --git a/src/structs.c b/src/structs.c index 7eea923..058f628 100644 --- a/src/structs.c +++ b/src/structs.c @@ -3,3 +3,6 @@ VectorImpl(Int, uint64_t, 4); VectorImpl(Boolean, Boolean *, 4); +VectorImpl(Void, void *, 4); +HashTableImpl(Void, void *, void *, Ptr_hash_function, Ptr_equals); +HashSetImpl(Void, void *, Ptr_hash_function, Ptr_equals); diff --git a/src/structs.h b/src/structs.h index 4229f71..da5f863 100644 --- a/src/structs.h +++ b/src/structs.h @@ -1,8 +1,22 @@ #ifndef STRUCTS_H #define STRUCTS_H #include "vector.h" +#include "hashtable.h" +#include "hashset.h" #include "classlist.h" VectorDef(Int, uint64_t, 4); VectorDef(Boolean, Boolean *, 4); +VectorDef(Void, void *, 4); + +inline unsigned int Ptr_hash_function(void * hash) { + return (unsigned int)((uint64_t)hash >> 4); +} + +inline bool Ptr_equals(void * key1, void * key2) { + return key1 == key2; +} + +HashTableDef(Void, void *, void *, Ptr_hash_function, Ptr_equals); +HashSetDef(Void, void *, Ptr_hash_function, Ptr_equals); #endif diff --git a/src/vector.h b/src/vector.h index e9a3361..623c190 100644 --- a/src/vector.h +++ b/src/vector.h @@ -15,7 +15,7 @@ void pushVector ## name(Vector ## name *vector, type item); \ type getVector ## name(Vector ## name *vector, uint index); \ void setVector ## name(Vector ## name *vector, uint index, type item); \ - uint getSize ##name(Vector ##name *vector); \ + uint getSizeVector ##name(Vector ##name *vector); \ void freeVector ##name(Vector ##name *vector); #define VectorImpl(name, type, defcap) \ @@ -47,7 +47,7 @@ void setVector ## name(Vector ## name * vector, uint index, type item) { \ vector->array[index]=item; \ } \ - uint getSize ## name(Vector ## name *vector) { \ + uint getSizeVector ## name(Vector ## name *vector) { \ return vector->size; \ } \ void freeVector ##name(Vector ##name *vector) { \