- BSF/BSR cannot do 16 bit AM in our model, because they only set the lower 16 bits...

[libfirm] / ir / adt / hashset.c

diff --git a/ir/adt/hashset.c b/ir/adt/hashset.c
index 08869b7..44cd1a7 100644 (file)
--- 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,7 +79,7 @@
 
 #ifndef Hash
 #define ID_HASH
-#define Hash(self,key)        ((unsigned)(key))
+#define Hash(self,key)        ((unsigned)(((char *)key) - (char *)0))
 #endif /* Hash */
 
 #ifdef DO_REHASH
@@ -95,7 +95,7 @@
 
 #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 */
 
@@ -192,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
@@ -201,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
@@ -216,7 +219,7 @@ size_t hashset_size(const HashSet *self)
  * @note also see comments for hashset_insert()
  * @internal
  */
-static INLINE
+static inline
 InsertReturnValue insert_nogrow(HashSet *self, KeyType key)
 {
        size_t   num_probes  = 0;
@@ -263,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.
@@ -283,7 +299,7 @@ void insert_new(HashSet *self, unsigned hash, ValueType value)
                HashSetEntry *entry = & self->entries[bucknum];
 
                if(EntryIsEmpty(*entry)) {
-                       size_t p;
+                       size_t        p;
                        HashSetEntry *nentry;
 
                        if(insert_pos != ILLEGAL_POS) {
@@ -306,23 +322,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) HT_OCCUPANCY_FLT(self->num_buckets);
-       self->shrink_threshold  = (size_t) HT_EMPTY_FLT(self->num_buckets);
-       self->consider_shrink   = 0;
-}
-
 /**
  * Resize the hashset
  * @internal
  */
-static INLINE
+static inline
 void resize(HashSet *self, size_t new_size)
 {
        size_t num_buckets = self->num_buckets;
@@ -356,12 +360,18 @@ 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
+static inline
 void maybe_grow(HashSet *self)
 {
        size_t resize_to;
@@ -378,7 +388,7 @@ void maybe_grow(HashSet *self)
  * shrink the hashset if it is only sparsely filled
  * @internal
  */
-static INLINE
+static inline
 void maybe_shrink(HashSet *self)
 {
        size_t size;
@@ -388,7 +398,7 @@ void maybe_shrink(HashSet *self)
                return;
 
        self->consider_shrink = 0;
-       size = hashset_size(self);
+       size                  = hashset_size(self);
        if(size <= HT_MIN_BUCKETS)
                return;
 
@@ -404,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
@@ -425,7 +435,7 @@ 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
@@ -506,7 +516,7 @@ void hashset_remove(HashSet *self, ConstKeyType key)
  * Initializes hashset with a specific size
  * @internal
  */
-static INLINE
+static inline
 void init_size(HashSet *self, size_t initial_size)
 {
        if(initial_size < 4)
@@ -521,12 +531,15 @@ void init_size(HashSet *self, size_t initial_size)
 #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)
@@ -540,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;
@@ -547,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)
 {
@@ -563,6 +579,7 @@ void hashset_init_size(HashSet *self, size_t expected_elements)
        init_size(self, po2size);
 }
 
+#ifndef NO_ITERATOR
 /**
  * Initializes a hashset iterator. The memory for the allocator has to be
  * already allocated.
@@ -621,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 */