X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fhashset.c;h=8741376d490cfd6a8a61d36429c6bd4d9c09a3b4;hb=f864dbddcf026827e85d49544abbb002841a5405;hp=c2d8d7fa58e916949229140db1cbc55b4bc5fdbd;hpb=974215da1a935f250766874d0f7a7ddfa34bc4ef;p=libfirm diff --git a/ir/adt/hashset.c b/ir/adt/hashset.c index c2d8d7fa5..8741376d4 100644 --- a/ir/adt/hashset.c +++ b/ir/adt/hashset.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -79,13 +79,13 @@ #ifndef Hash #define ID_HASH -#define Hash(self,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(self,entry) Hash(self,entry) +#define EntryGetHash(self,entry) Hash(self, GetKey(entry)) #define EntryGetValue(entry) (entry) #else /* ! DO_REHASH */ #define EntryGetHash(self,entry) (entry).hash @@ -100,11 +100,19 @@ #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 @@ -144,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 @@ -181,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 @@ -190,6 +203,7 @@ #ifndef hashset_remove_iterator #error You have to redefine hashset_remove_iterator #endif +#endif /** * Returns the number of elements in the hashset @@ -208,12 +222,12 @@ size_t hashset_size(const HashSet *self) static INLINE InsertReturnValue insert_nogrow(HashSet *self, KeyType key) { - 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; + 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); @@ -234,7 +248,7 @@ InsertReturnValue insert_nogrow(HashSet *self, KeyType key) InitData(self, EntryGetValue(*nentry), key); EntrySetHash(*nentry, hash); self->num_elements++; - return GetInsertReturnValue(*nentry, 1); + return GetInsertReturnValue(*nentry, 0); } if(EntryIsDeleted(*entry)) { if(insert_pos == ILLEGAL_POS) @@ -242,7 +256,7 @@ InsertReturnValue insert_nogrow(HashSet *self, KeyType 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); } } @@ -252,6 +266,19 @@ InsertReturnValue insert_nogrow(HashSet *self, 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. @@ -260,19 +287,19 @@ InsertReturnValue insert_nogrow(HashSet *self, KeyType key) static void insert_new(HashSet *self, unsigned hash, ValueType value) { - size_t num_probes = 0; + 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; + 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 = & self->entries[bucknum]; if(EntryIsEmpty(*entry)) { - size_t p; + size_t p; HashSetEntry *nentry; if(insert_pos != ILLEGAL_POS) { @@ -295,18 +322,6 @@ void insert_new(HashSet *self, unsigned hash, ValueType value) } } -/** - * calculate shrink and enlarge limits - * @internal - */ -static INLINE -void reset_thresholds(HashSet *self) -{ - self->enlarge_threshold = (size_t) (self->num_buckets * HT_OCCUPANCY_FLT); - self->shrink_threshold = (size_t) (self->num_buckets * HT_EMPTY_FLT); - self->consider_shrink = 0; -} - /** * Resize the hashset * @internal @@ -324,10 +339,10 @@ void resize(HashSet *self, size_t new_size) SetRangeEmpty(new_entries, new_size); /* use the new array */ - self->entries = new_entries; - self->num_buckets = new_size; + self->entries = new_entries; + self->num_buckets = new_size; self->num_elements = 0; - self->num_deleted = 0; + self->num_deleted = 0; #ifndef NDEBUG self->entries_version++; #endif @@ -345,6 +360,12 @@ void resize(HashSet *self, size_t new_size) /* 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 @@ -377,7 +398,10 @@ void maybe_shrink(HashSet *self) return; self->consider_shrink = 0; - size = hashset_size(self); + size = hashset_size(self); + if(size <= HT_MIN_BUCKETS) + return; + if(LIKELY(size > self->shrink_threshold)) return; @@ -390,9 +414,9 @@ void maybe_shrink(HashSet *self) } /** - * 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 self the hashset @@ -411,32 +435,32 @@ InsertReturnValue hashset_insert(HashSet *self, KeyType key) } /** - * Searchs for an element with key @p key. + * Searches for an element with key @p key. * * @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 *self, ConstKeyType key) +InsertReturnValue hashset_find(const HashSet *self, ConstKeyType key) { - 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 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 = & self->entries[bucknum]; if(EntryIsEmpty(*entry)) { - return NullValue; + return NullReturnValue; } if(EntryIsDeleted(*entry)) { // value is deleted } else if(EntryGetHash(self, *entry) == hash) { if(KeysEqual(self, GetKey(EntryGetValue(*entry)), key)) { // found the value - return EntryGetValue(*entry); + return GetInsertReturnValue(*entry, 1); } } @@ -455,11 +479,11 @@ ValueType hashset_find(const HashSet *self, ConstKeyType key) */ void hashset_remove(HashSet *self, ConstKeyType key) { - 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 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 self->entries_version++; @@ -498,21 +522,24 @@ void init_size(HashSet *self, size_t initial_size) if(initial_size < 4) initial_size = 4; - self->entries = Alloc(initial_size); + self->entries = Alloc(initial_size); SetRangeEmpty(self->entries, initial_size); - self->num_buckets = initial_size; + self->num_buckets = initial_size; self->consider_shrink = 0; - self->num_elements = 0; - self->num_deleted = 0; + self->num_elements = 0; + self->num_deleted = 0; #ifndef NDEBUG self->entries_version = 0; #endif +#ifdef ADDITIONAL_INIT + ADDITIONAL_INIT +#endif 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 *self) @@ -526,6 +553,9 @@ void hashset_init(HashSet *self) */ void hashset_destroy(HashSet *self) { +#ifdef ADDITIONAL_TERM + ADDITIONAL_TERM +#endif Free(self->entries); #ifndef NDEBUG self->entries = NULL; @@ -533,7 +563,7 @@ void hashset_destroy(HashSet *self) } /** - * Initializes a hashset expecting expected_element size + * Initializes a hashset expecting expected_element size. */ void hashset_init_size(HashSet *self, size_t expected_elements) { @@ -544,11 +574,12 @@ void hashset_init_size(HashSet *self, size_t expected_elements) abort(); } - needed_size = expected_elements * (int)(1.0 / HT_OCCUPANCY_FLT); - po2size = ceil_po2(needed_size); + 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. @@ -557,9 +588,9 @@ void hashset_init_size(HashSet *self, size_t expected_elements) void hashset_iterator_init(HashSetIterator *self, const HashSet *hashset) { self->current_bucket = hashset->entries - 1; - self->end = hashset->entries + hashset->num_buckets; + self->end = hashset->entries + hashset->num_buckets; #ifndef NDEBUG - self->set = hashset; + self->set = hashset; self->entries_version = hashset->entries_version; #endif } @@ -572,21 +603,16 @@ void hashset_iterator_init(HashSetIterator *self, const HashSet *hashset) ValueType hashset_iterator_next(HashSetIterator *self) { HashSetEntry *current_bucket = self->current_bucket; - HashSetEntry *end = self->end; - - if(current_bucket >= end) - return NullValue; + HashSetEntry *end = self->end; /* using hashset_insert or hashset_remove is not allowed while iterating */ 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)); self->current_bucket = current_bucket; return EntryGetValue(*current_bucket); @@ -612,5 +638,6 @@ void hashset_remove_iterator(HashSet *self, const HashSetIterator *iter) self->num_deleted++; self->consider_shrink = 1; } +#endif /* NO_ITERATOR */ -#endif +#endif /* HashSet */