X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fadt%2Fhashset.c;h=44cd1a770a0a1b0d5c1d9178ce93196de2862978;hb=6571b31236f780199ba476adc33ee23518200497;hp=08869b75b779135cb279f64ea705282835acf4cd;hpb=aef4d3b28b21856e05c0bd91552b51b69ed5ac50;p=libfirm diff --git a/ir/adt/hashset.c b/ir/adt/hashset.c index 08869b75b..44cd1a770 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,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 */