X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fhashset.c;h=811078742941fe61ec4c63d84fc548a98946437e;hb=0651be9698637d202db8d0acbda9597de4ca9a7c;hp=c2d8d7fa58e916949229140db1cbc55b4bc5fdbd;hpb=974215da1a935f250766874d0f7a7ddfa34bc4ef;p=libfirm
diff --git a/ir/adt/hashset.c b/ir/adt/hashset.c
index c2d8d7fa5..811078742 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.
*
@@ -47,7 +47,7 @@
*
GetKey(value) Extracts the key from a data value
* KeysEqual(hashset,key1,key2) Tests wether 2 keys are equal
* DO_REHASH Instead of storing the hash-values, recalculate
- * them on demand from the datavalues. (usefull if
+ * them on demand from the datavalues. (useful if
* calculating the hash-values takes less time than
* a memory access)
*
@@ -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 EntrySetHash(entry,new_hash) (void)0
+#define EntryGetHash(self,entry) Hash(self, GetKey(entry))
#define EntryGetValue(entry) (entry)
#else /* ! DO_REHASH */
#define EntryGetHash(self,entry) (entry).hash
@@ -95,16 +95,24 @@
#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
@@ -135,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); \
} \
@@ -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
@@ -205,26 +219,25 @@ size_t hashset_size(const HashSet *self)
* @note also see comments for hashset_insert()
* @internal
*/
-static INLINE
-InsertReturnValue insert_nogrow(HashSet *self, KeyType key)
+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);
- while(1) {
+ 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;
@@ -234,15 +247,15 @@ 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)
+ if (EntryIsDeleted(*entry)) {
+ if (insert_pos == ILLEGAL_POS)
insert_pos = bucknum;
- } else if(EntryGetHash(self, *entry) == hash) {
- if(KeysEqual(self, 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);
}
}
@@ -252,30 +265,41 @@ 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.
* @internal
*/
-static
-void insert_new(HashSet *self, unsigned hash, ValueType value)
+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) {
+ 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;
@@ -295,24 +319,11 @@ 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
*/
-static INLINE
-void resize(HashSet *self, size_t new_size)
+static inline void resize(HashSet *self, size_t new_size)
{
size_t num_buckets = self->num_buckets;
size_t i;
@@ -324,19 +335,19 @@ 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
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(self, EntryGetHash(self, *entry), EntryGetValue(*entry));
@@ -345,17 +356,22 @@ 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
* @internal
*/
-static INLINE
-void maybe_grow(HashSet *self)
+static inline void maybe_grow(HashSet *self)
{
size_t resize_to;
- if(LIKELY(self->num_elements + 1 <= self->enlarge_threshold))
+ if (LIKELY(self->num_elements + 1 <= self->enlarge_threshold))
return;
/* double table size */
@@ -367,32 +383,34 @@ void maybe_grow(HashSet *self)
* shrink the hashset if it is only sparsely filled
* @internal
*/
-static INLINE
-void maybe_shrink(HashSet *self)
+static inline void maybe_shrink(HashSet *self)
{
size_t size;
size_t resize_to;
- if(!self->consider_shrink)
+ if (!self->consider_shrink)
return;
self->consider_shrink = 0;
- size = hashset_size(self);
- if(LIKELY(size > self->shrink_threshold))
+ 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(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 self the hashset
@@ -411,32 +429,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) {
+ 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(self, *entry) == hash) {
- if(KeysEqual(self, 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);
}
}
@@ -455,26 +473,26 @@ 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++;
#endif
- while(1) {
+ 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(self, *entry) == hash) {
- if(KeysEqual(self, GetKey(EntryGetValue(*entry)), key)) {
+ } else if (EntryGetHash(self, *entry) == hash) {
+ if (KeysEqual(self, GetKey(EntryGetValue(*entry)), key)) {
EntrySetDeleted(*entry);
self->num_deleted++;
self->consider_shrink = 1;
@@ -492,27 +510,29 @@ void hashset_remove(HashSet *self, ConstKeyType key)
* Initializes hashset with a specific size
* @internal
*/
-static INLINE
-void init_size(HashSet *self, 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;
- 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 +546,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,22 +556,23 @@ 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)
{
size_t needed_size;
size_t po2size;
- if(expected_elements >= UINT_MAX/2) {
+ if (expected_elements >= UINT_MAX/2) {
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 +581,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 +596,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);
@@ -605,12 +624,13 @@ void hashset_remove_iterator(HashSet *self, const HashSetIterator *iter)
/* needs to be on a valid element */
assert(entry < self->entries + self->num_buckets);
- if(EntryIsDeleted(*entry))
+ if (EntryIsDeleted(*entry))
return;
EntrySetDeleted(*entry);
self->num_deleted++;
self->consider_shrink = 1;
}
+#endif /* NO_ITERATOR */
-#endif
+#endif /* HashSet */