X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fhashset.c;h=92b59117cc34268e233ed05c68583234cbe94568;hb=c496fb7a06926c15967ea635fd95a9c78e74d6bc;hp=936f6c9785978110daf83352bd905217dc887ebb;hpb=863d31d7a5c8210432fef88b30fc3e8353131538;p=libfirm diff --git a/ir/adt/hashset.c b/ir/adt/hashset.c index 936f6c978..92b59117c 100644 --- a/ir/adt/hashset.c +++ b/ir/adt/hashset.c @@ -1,9 +1,28 @@ +/* + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + /** * @file - * @date 17.03.2007 - * @brief Geberic hashset implementation + * @brief Generic hashset implementation * @author Matthias Braun, inspiration from densehash from google sparsehash * package + * @date 17.03.2007 * @version $Id$ * * @@ -60,38 +79,46 @@ #ifndef Hash #define ID_HASH -#define Hash(this,value) ((unsigned)(value)) +#define Hash(self,key) ((unsigned)(((char *)key) - (char *)0)) #endif /* Hash */ #ifdef DO_REHASH #define HashSetEntry ValueType #define EntrySetHash(entry,new_hash) -#define EntryGetHash(this,entry) Hash(this,entry) +#define EntryGetHash(self,entry) Hash(self, GetKey(entry)) #define EntryGetValue(entry) (entry) #else /* ! DO_REHASH */ -#define EntryGetHash(this,entry) (entry).hash +#define EntryGetHash(self,entry) (entry).hash #define EntrySetHash(entry,new_hash) (entry).hash = (new_hash) #define EntryGetValue(entry) (entry).data #endif /* DO_REHASH */ #ifndef Alloc #include "xmalloc.h" -#define Alloc(size) (HashSetEntry*) xmalloc((size) * sizeof(HashSetEntry)) +#define Alloc(size) XMALLOCN(HashSetEntry, (size)) #define Free(ptr) free(ptr) #endif /* Alloc */ #ifdef ID_HASH -#define InsertReturnValue int -#define GetInsertReturnValue(entry,new) (new) +#define InsertReturnValue int +#define GetInsertReturnValue(entry,found) (found) +#define NullReturnValue 0 #else /* ! ID_HASH */ -#define InsertReturnValue ValueType -#define GetInsertReturnValue(entry,new) EntryGetValue(entry) +#ifdef SCALAR_RETURN +#define InsertReturnValue ValueType +#define GetInsertReturnValue(entry,found) EntryGetValue(entry) +#define NullReturnValue NullValue +#else +#define InsertReturnValue ValueType* +#define GetInsertReturnValue(entry,found) & EntryGetValue(entry) +#define NullReturnValue & NullValue +#endif #endif /* ID_HASH */ #ifndef KeyType #define KeyType ValueType #define GetKey(value) (value) -#define InitData(this,value,key) (value) = (key) +#define InitData(self,value,key) (value) = (key) #endif /* KeyType */ #ifndef ConstKeyType @@ -116,7 +143,7 @@ size_t _i; \ size_t _size = (size); \ HashSetEntry *entries = (ptr); \ - for(_i = 0; _i < _size; ++_i) { \ + for (_i = 0; _i < _size; ++_i) { \ HashSetEntry *entry = & entries[_i]; \ EntrySetEmpty(*entry); \ } \ @@ -125,12 +152,15 @@ #ifndef HT_OCCUPANCY_FLT /** how full before we double size */ -#define HT_OCCUPANCY_FLT 0.5f +#define HT_OCCUPANCY_FLT(x) ((x)/2) #endif /* HT_OCCUPANCY_FLT */ +#ifndef HT_1_DIV_OCCUPANCY_FLT +#define HT_1_DIV_OCCUPANCY_FLT 2 +#endif #ifndef HT_EMPTY_FLT /** how empty before we half size */ -#define HT_EMPTY_FLT (0.4f * (HT_OCCUPANCY_FLT)) +#define HT_EMPTY_FLT(x) ((x)/5) #endif /* HT_EMPTY_FLT */ #ifndef HT_MIN_BUCKETS @@ -162,6 +192,8 @@ #ifndef hashset_size #error You have to redefine hashset_size #endif + +#ifndef NO_ITERATOR #ifndef hashset_iterator_init #error You have to redefine hashset_iterator_init #endif @@ -171,13 +203,14 @@ #ifndef hashset_remove_iterator #error You have to redefine hashset_remove_iterator #endif +#endif /** * Returns the number of elements in the hashset */ -size_t hashset_size(const HashSet *this) +size_t hashset_size(const HashSet *self) { - return this->num_elements - this->num_deleted; + return self->num_elements - self->num_deleted; } /** @@ -186,44 +219,43 @@ size_t hashset_size(const HashSet *this) * @note also see comments for hashset_insert() * @internal */ -static inline -InsertReturnValue insert_nogrow(HashSet *this, KeyType key) +static inline InsertReturnValue insert_nogrow(HashSet *self, KeyType key) { - size_t num_probes = 0; - size_t num_buckets = this->num_buckets; - size_t hashmask = num_buckets - 1; - unsigned hash = Hash(this, key); - size_t bucknum = hash & hashmask; - size_t insert_pos = ILLEGAL_POS; + size_t num_probes = 0; + size_t num_buckets = self->num_buckets; + size_t hashmask = num_buckets - 1; + unsigned hash = Hash(self, key); + size_t bucknum = hash & hashmask; + size_t insert_pos = ILLEGAL_POS; assert((num_buckets & (num_buckets - 1)) == 0); - while(1) { - HashSetEntry *entry = & this->entries[bucknum]; + for (;;) { + HashSetEntry *entry = & self->entries[bucknum]; - if(EntryIsEmpty(*entry)) { + if (EntryIsEmpty(*entry)) { size_t p; HashSetEntry *nentry; - if(insert_pos != ILLEGAL_POS) { + if (insert_pos != ILLEGAL_POS) { p = insert_pos; } else { p = bucknum; } - nentry = &this->entries[p]; - InitData(this, EntryGetValue(*nentry), key); + nentry = &self->entries[p]; + InitData(self, EntryGetValue(*nentry), key); EntrySetHash(*nentry, hash); - this->num_elements++; - return GetInsertReturnValue(*nentry, 1); + self->num_elements++; + return GetInsertReturnValue(*nentry, 0); } - if(EntryIsDeleted(*entry)) { - if(insert_pos == ILLEGAL_POS) + if (EntryIsDeleted(*entry)) { + if (insert_pos == ILLEGAL_POS) insert_pos = bucknum; - } else if(EntryGetHash(this, *entry) == hash) { - if(KeysEqual(this, GetKey(EntryGetValue(*entry)), key)) { + } else if (EntryGetHash(self, *entry) == hash) { + if (KeysEqual(self, GetKey(EntryGetValue(*entry)), key)) { // Value already in the set, return it - return GetInsertReturnValue(*entry, 0); + return GetInsertReturnValue(*entry, 1); } } @@ -233,39 +265,50 @@ InsertReturnValue insert_nogrow(HashSet *this, KeyType key) } } +/** + * calculate shrink and enlarge limits + * @internal + */ +static inline void reset_thresholds(HashSet *self) +{ + self->enlarge_threshold = (size_t) HT_OCCUPANCY_FLT(self->num_buckets); + self->shrink_threshold = (size_t) HT_EMPTY_FLT(self->num_buckets); + self->consider_shrink = 0; +} + +#ifndef HAVE_OWN_RESIZE /** * Inserts an element into a hashset under the assumption that the hashset * contains no deleted entries and the element doesn't exist in the hashset yet. * @internal */ -static -void insert_new(HashSet *this, unsigned hash, ValueType value) +static void insert_new(HashSet *self, unsigned hash, ValueType value) { - size_t num_probes = 0; - size_t num_buckets = this->num_buckets; - size_t hashmask = num_buckets - 1; - size_t bucknum = hash & hashmask; - size_t insert_pos = ILLEGAL_POS; + size_t num_probes = 0; + size_t num_buckets = self->num_buckets; + size_t hashmask = num_buckets - 1; + size_t bucknum = hash & hashmask; + size_t insert_pos = ILLEGAL_POS; - assert(value != NullValue); + //assert(value != NullValue); - while(1) { - HashSetEntry *entry = & this->entries[bucknum]; + for (;;) { + HashSetEntry *entry = & self->entries[bucknum]; - if(EntryIsEmpty(*entry)) { - size_t p; + if (EntryIsEmpty(*entry)) { + size_t p; HashSetEntry *nentry; - if(insert_pos != ILLEGAL_POS) { + if (insert_pos != ILLEGAL_POS) { p = insert_pos; } else { p = bucknum; } - nentry = &this->entries[p]; + nentry = &self->entries[p]; EntryGetValue(*nentry) = value; EntrySetHash(*nentry, hash); - this->num_elements++; + self->num_elements++; return; } assert(!EntryIsDeleted(*entry)); @@ -276,28 +319,15 @@ void insert_new(HashSet *this, unsigned hash, ValueType value) } } -/** - * calculate shrink and enlarge limits - * @internal - */ -static inline -void reset_thresholds(HashSet *this) -{ - this->enlarge_threshold = (size_t) (this->num_buckets * HT_OCCUPANCY_FLT); - this->shrink_threshold = (size_t) (this->num_buckets * HT_EMPTY_FLT); - this->consider_shrink = 0; -} - /** * Resize the hashset * @internal */ -static inline -void resize(HashSet *this, size_t new_size) +static inline void resize(HashSet *self, size_t new_size) { - size_t num_buckets = this->num_buckets; + size_t num_buckets = self->num_buckets; size_t i; - HashSetEntry *old_entries = this->entries; + HashSetEntry *old_entries = self->entries; HashSetEntry *new_entries; /* allocate a new array with double size */ @@ -305,119 +335,126 @@ void resize(HashSet *this, size_t new_size) SetRangeEmpty(new_entries, new_size); /* use the new array */ - this->entries = new_entries; - this->num_buckets = new_size; - this->num_elements = 0; - this->num_deleted = 0; + self->entries = new_entries; + self->num_buckets = new_size; + self->num_elements = 0; + self->num_deleted = 0; #ifndef NDEBUG - this->entries_version++; + self->entries_version++; #endif - reset_thresholds(this); + reset_thresholds(self); /* reinsert all elements */ - for(i = 0; i < num_buckets; ++i) { + for (i = 0; i < num_buckets; ++i) { HashSetEntry *entry = & old_entries[i]; - if(EntryIsEmpty(*entry) || EntryIsDeleted(*entry)) + if (EntryIsEmpty(*entry) || EntryIsDeleted(*entry)) continue; - insert_new(this, EntryGetHash(this, *entry), EntryGetValue(*entry)); + insert_new(self, EntryGetHash(self, *entry), EntryGetValue(*entry)); } /* now we can free the old array */ Free(old_entries); } +#else + +/* resize must be defined outside */ +static inline void resize(HashSet *self, size_t new_size); + +#endif /** * grow the hashset if adding 1 more elements would make it too crowded * @internal */ -static inline -void maybe_grow(HashSet *this) +static inline void maybe_grow(HashSet *self) { size_t resize_to; - if(LIKELY(this->num_elements + 1 <= this->enlarge_threshold)) + if (LIKELY(self->num_elements + 1 <= self->enlarge_threshold)) return; /* double table size */ - resize_to = this->num_buckets * 2; - resize(this, resize_to); + resize_to = self->num_buckets * 2; + resize(self, resize_to); } /** * shrink the hashset if it is only sparsely filled * @internal */ -static inline -void maybe_shrink(HashSet *this) +static inline void maybe_shrink(HashSet *self) { size_t size; size_t resize_to; - if(!this->consider_shrink) + if (!self->consider_shrink) return; - this->consider_shrink = 0; - size = hashset_size(this); - if(LIKELY(size > this->shrink_threshold)) + self->consider_shrink = 0; + size = hashset_size(self); + if (size <= HT_MIN_BUCKETS) + return; + + if (LIKELY(size > self->shrink_threshold)) return; resize_to = ceil_po2(size); - if(resize_to < 4) + if (resize_to < 4) resize_to = 4; - resize(this, resize_to); + resize(self, resize_to); } /** - * Insert an element into the hashset. If no element with key key exists yet, + * Insert an element into the hashset. If no element with the given key exists yet, * then a new one is created and initialized with the InitData function. - * Otherwise the exisiting element is returned (for hashs where key is equal to + * Otherwise the existing element is returned (for hashs where key is equal to * value, nothing is returned.) * - * @param this the hashset + * @param self the hashset * @param key the key that identifies the data * @returns the existing or newly created data element (or nothing in case of hashs where keys are the while value) */ -InsertReturnValue hashset_insert(HashSet *this, KeyType key) +InsertReturnValue hashset_insert(HashSet *self, KeyType key) { #ifndef NDEBUG - this->entries_version++; + self->entries_version++; #endif - maybe_shrink(this); - maybe_grow(this); - return insert_nogrow(this, key); + maybe_shrink(self); + maybe_grow(self); + return insert_nogrow(self, key); } /** - * Searchs for an element with key @p key. + * Searches for an element with key @p key. * - * @param this the hashset + * @param self the hashset * @param key the key to search for * @returns the found value or NullValue if nothing was found */ -ValueType hashset_find(const HashSet *this, ConstKeyType key) +InsertReturnValue hashset_find(const HashSet *self, ConstKeyType key) { - size_t num_probes = 0; - size_t num_buckets = this->num_buckets; - size_t hashmask = num_buckets - 1; - unsigned hash = Hash(this, key); - size_t bucknum = hash & hashmask; + size_t num_probes = 0; + size_t num_buckets = self->num_buckets; + size_t hashmask = num_buckets - 1; + unsigned hash = Hash(self, key); + size_t bucknum = hash & hashmask; - while(1) { - HashSetEntry *entry = & this->entries[bucknum]; + for (;;) { + HashSetEntry *entry = & self->entries[bucknum]; - if(EntryIsEmpty(*entry)) { - return NullValue; + if (EntryIsEmpty(*entry)) { + return NullReturnValue; } - if(EntryIsDeleted(*entry)) { + if (EntryIsDeleted(*entry)) { // value is deleted - } else if(EntryGetHash(this, *entry) == hash) { - if(KeysEqual(this, GetKey(EntryGetValue(*entry)), key)) { + } else if (EntryGetHash(self, *entry) == hash) { + if (KeysEqual(self, GetKey(EntryGetValue(*entry)), key)) { // found the value - return EntryGetValue(*entry); + return GetInsertReturnValue(*entry, 1); } } @@ -431,34 +468,34 @@ ValueType hashset_find(const HashSet *this, ConstKeyType key) * Removes an element from a hashset. Does nothing if the set doesn't contain * the element. * - * @param this the hashset + * @param self the hashset * @param key key that identifies the data to remove */ -void hashset_remove(HashSet *this, ConstKeyType key) +void hashset_remove(HashSet *self, ConstKeyType key) { - size_t num_probes = 0; - size_t num_buckets = this->num_buckets; - size_t hashmask = num_buckets - 1; - unsigned hash = Hash(this, key); - size_t bucknum = hash & hashmask; + size_t num_probes = 0; + size_t num_buckets = self->num_buckets; + size_t hashmask = num_buckets - 1; + unsigned hash = Hash(self, key); + size_t bucknum = hash & hashmask; #ifndef NDEBUG - this->entries_version++; + self->entries_version++; #endif - while(1) { - HashSetEntry *entry = & this->entries[bucknum]; + for (;;) { + HashSetEntry *entry = & self->entries[bucknum]; - if(EntryIsEmpty(*entry)) { + if (EntryIsEmpty(*entry)) { return; } - if(EntryIsDeleted(*entry)) { + if (EntryIsDeleted(*entry)) { // entry is deleted - } else if(EntryGetHash(this, *entry) == hash) { - if(KeysEqual(this, GetKey(EntryGetValue(*entry)), key)) { + } else if (EntryGetHash(self, *entry) == hash) { + if (KeysEqual(self, GetKey(EntryGetValue(*entry)), key)) { EntrySetDeleted(*entry); - this->num_deleted++; - this->consider_shrink = 1; + self->num_deleted++; + self->consider_shrink = 1; return; } } @@ -473,75 +510,81 @@ void hashset_remove(HashSet *this, ConstKeyType key) * Initializes hashset with a specific size * @internal */ -static inline -void init_size(HashSet *this, size_t initial_size) +static inline void init_size(HashSet *self, size_t initial_size) { - if(initial_size < 4) + if (initial_size < 4) initial_size = 4; - this->entries = Alloc(initial_size); - SetRangeEmpty(this->entries, initial_size); - this->num_buckets = initial_size; - this->consider_shrink = 0; - this->num_elements = 0; - this->num_deleted = 0; + self->entries = Alloc(initial_size); + SetRangeEmpty(self->entries, initial_size); + self->num_buckets = initial_size; + self->consider_shrink = 0; + self->num_elements = 0; + self->num_deleted = 0; #ifndef NDEBUG - this->entries_version = 0; + self->entries_version = 0; +#endif +#ifdef ADDITIONAL_INIT + ADDITIONAL_INIT #endif - reset_thresholds(this); + reset_thresholds(self); } /** - * Initialializes a hashset with the default size. The memory for the set has to + * Initializes a hashset with the default size. The memory for the set has to * already allocated. */ -void hashset_init(HashSet *this) +void hashset_init(HashSet *self) { - init_size(this, HT_MIN_BUCKETS); + init_size(self, HT_MIN_BUCKETS); } /** * Destroys a hashset, freeing all used memory (except the memory for the * HashSet struct itself). */ -void hashset_destroy(HashSet *this) +void hashset_destroy(HashSet *self) { - Free(this->entries); +#ifdef ADDITIONAL_TERM + ADDITIONAL_TERM +#endif + Free(self->entries); #ifndef NDEBUG - this->entries = NULL; + self->entries = NULL; #endif } /** - * Initializes a hashset expecting expected_element size + * Initializes a hashset expecting expected_element size. */ -void hashset_init_size(HashSet *this, size_t expected_elements) +void hashset_init_size(HashSet *self, size_t expected_elements) { size_t needed_size; size_t po2size; - if(expected_elements >= UINT_MAX/2) { + if (expected_elements >= UINT_MAX/2) { abort(); } - needed_size = expected_elements * (1.0 / HT_OCCUPANCY_FLT); - po2size = ceil_po2(needed_size); - init_size(this, po2size); + needed_size = expected_elements * HT_1_DIV_OCCUPANCY_FLT; + po2size = ceil_po2(needed_size); + init_size(self, po2size); } +#ifndef NO_ITERATOR /** * Initializes a hashset iterator. The memory for the allocator has to be * already allocated. * @note it is not allowed to remove or insert elements while iterating */ -void hashset_iterator_init(HashSetIterator *this, const HashSet *hashset) +void hashset_iterator_init(HashSetIterator *self, const HashSet *hashset) { - this->current_bucket = hashset->entries - 1; - this->end = hashset->entries + hashset->num_buckets; + self->current_bucket = hashset->entries - 1; + self->end = hashset->entries + hashset->num_buckets; #ifndef NDEBUG - this->set = hashset; - this->entries_version = hashset->entries_version; + self->set = hashset; + self->entries_version = hashset->entries_version; #endif } @@ -550,26 +593,21 @@ void hashset_iterator_init(HashSetIterator *this, const HashSet *hashset) * in the hashset. * @note it is not allowed to remove or insert elements while iterating */ -ValueType hashset_iterator_next(HashSetIterator *this) +ValueType hashset_iterator_next(HashSetIterator *self) { - HashSetEntry *current_bucket = this->current_bucket; - HashSetEntry *end = this->end; - - if(current_bucket >= end) - return NullValue; + HashSetEntry *current_bucket = self->current_bucket; + HashSetEntry *end = self->end; /* using hashset_insert or hashset_remove is not allowed while iterating */ - assert(this->entries_version == this->set->entries_version); + assert(self->entries_version == self->set->entries_version); do { current_bucket++; - } while(current_bucket < end && - (EntryIsEmpty(*current_bucket) || EntryIsDeleted(*current_bucket))); - - if(current_bucket >= end) - return NullValue; + if (current_bucket >= end) + return NullValue; + } while (EntryIsEmpty(*current_bucket) || EntryIsDeleted(*current_bucket)); - this->current_bucket = current_bucket; + self->current_bucket = current_bucket; return EntryGetValue(*current_bucket); } @@ -577,21 +615,22 @@ ValueType hashset_iterator_next(HashSetIterator *this) * Removes the element the iterator points to. Removing an element a second time * has no result. */ -void hashset_remove_iterator(HashSet *this, const HashSetIterator *iter) +void hashset_remove_iterator(HashSet *self, const HashSetIterator *iter) { HashSetEntry *entry = iter->current_bucket; /* iterator_next needs to have been called at least once */ - assert(entry >= this->entries); + assert(entry >= self->entries); /* needs to be on a valid element */ - assert(entry < this->entries + this->num_buckets); + assert(entry < self->entries + self->num_buckets); - if(EntryIsDeleted(*entry)) + if (EntryIsDeleted(*entry)) return; EntrySetDeleted(*entry); - this->num_deleted++; - this->consider_shrink = 1; + self->num_deleted++; + self->consider_shrink = 1; } +#endif /* NO_ITERATOR */ -#endif +#endif /* HashSet */