projects
/
libfirm
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
- add missing include
[libfirm]
/
ir
/
adt
/
hashset.c
diff --git
a/ir/adt/hashset.c
b/ir/adt/hashset.c
index
8741376
..
92b5911
100644
(file)
--- a/
ir/adt/hashset.c
+++ b/
ir/adt/hashset.c
@@
-95,7
+95,7
@@
#ifndef Alloc
#include "xmalloc.h"
#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 */
#define Free(ptr) free(ptr)
#endif /* Alloc */
@@
-143,7
+143,7
@@
size_t _i; \
size_t _size = (size); \
HashSetEntry *entries = (ptr); \
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); \
} \
HashSetEntry *entry = & entries[_i]; \
EntrySetEmpty(*entry); \
} \
@@
-219,8
+219,7
@@
size_t hashset_size(const HashSet *self)
* @note also see comments for hashset_insert()
* @internal
*/
* @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 num_probes = 0;
size_t num_buckets = self->num_buckets;
@@
-231,14
+230,14
@@
InsertReturnValue insert_nogrow(HashSet *self, KeyType key)
assert((num_buckets & (num_buckets - 1)) == 0);
assert((num_buckets & (num_buckets - 1)) == 0);
-
while(1
) {
+
for (;;
) {
HashSetEntry *entry = & self->entries[bucknum];
HashSetEntry *entry = & self->entries[bucknum];
- if(EntryIsEmpty(*entry)) {
+ if
(EntryIsEmpty(*entry)) {
size_t p;
HashSetEntry *nentry;
size_t p;
HashSetEntry *nentry;
- if(insert_pos != ILLEGAL_POS) {
+ if
(insert_pos != ILLEGAL_POS) {
p = insert_pos;
} else {
p = bucknum;
p = insert_pos;
} else {
p = bucknum;
@@
-250,11
+249,11
@@
InsertReturnValue insert_nogrow(HashSet *self, KeyType key)
self->num_elements++;
return GetInsertReturnValue(*nentry, 0);
}
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;
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, 1);
}
// Value already in the set, return it
return GetInsertReturnValue(*entry, 1);
}
@@
-270,8
+269,7
@@
InsertReturnValue insert_nogrow(HashSet *self, KeyType key)
* calculate shrink and enlarge limits
* @internal
*/
* calculate shrink and enlarge limits
* @internal
*/
-static INLINE
-void reset_thresholds(HashSet *self)
+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->enlarge_threshold = (size_t) HT_OCCUPANCY_FLT(self->num_buckets);
self->shrink_threshold = (size_t) HT_EMPTY_FLT(self->num_buckets);
@@
-284,8
+282,7
@@
void reset_thresholds(HashSet *self)
* contains no deleted entries and the element doesn't exist in the hashset yet.
* @internal
*/
* 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_buckets = self->num_buckets;
{
size_t num_probes = 0;
size_t num_buckets = self->num_buckets;
@@
-295,14
+292,14
@@
void insert_new(HashSet *self, unsigned hash, ValueType value)
//assert(value != NullValue);
//assert(value != NullValue);
-
while(1
) {
+
for (;;
) {
HashSetEntry *entry = & self->entries[bucknum];
HashSetEntry *entry = & self->entries[bucknum];
- if(EntryIsEmpty(*entry)) {
+ if
(EntryIsEmpty(*entry)) {
size_t p;
HashSetEntry *nentry;
size_t p;
HashSetEntry *nentry;
- if(insert_pos != ILLEGAL_POS) {
+ if
(insert_pos != ILLEGAL_POS) {
p = insert_pos;
} else {
p = bucknum;
p = insert_pos;
} else {
p = bucknum;
@@
-326,8
+323,7
@@
void insert_new(HashSet *self, unsigned hash, ValueType value)
* Resize the hashset
* @internal
*/
* 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;
{
size_t num_buckets = self->num_buckets;
size_t i;
@@
-349,9
+345,9
@@
void resize(HashSet *self, size_t new_size)
reset_thresholds(self);
/* reinsert all elements */
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];
HashSetEntry *entry = & old_entries[i];
- if(EntryIsEmpty(*entry) || EntryIsDeleted(*entry))
+ if
(EntryIsEmpty(*entry) || EntryIsDeleted(*entry))
continue;
insert_new(self, EntryGetHash(self, *entry), EntryGetValue(*entry));
continue;
insert_new(self, EntryGetHash(self, *entry), EntryGetValue(*entry));
@@
-363,7
+359,7
@@
void resize(HashSet *self, size_t new_size)
#else
/* resize must be defined outside */
#else
/* resize must be defined outside */
-static
INLINE
void resize(HashSet *self, size_t new_size);
+static
inline
void resize(HashSet *self, size_t new_size);
#endif
#endif
@@
-371,12
+367,11
@@
static INLINE void resize(HashSet *self, size_t new_size);
* grow the hashset if adding 1 more elements would make it too crowded
* @internal
*/
* 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;
{
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 */
return;
/* double table size */
@@
-388,26
+383,25
@@
void maybe_grow(HashSet *self)
* shrink the hashset if it is only sparsely filled
* @internal
*/
* 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;
{
size_t size;
size_t resize_to;
- if(!self->consider_shrink)
+ if
(!self->consider_shrink)
return;
self->consider_shrink = 0;
size = hashset_size(self);
return;
self->consider_shrink = 0;
size = hashset_size(self);
- if(size <= HT_MIN_BUCKETS)
+ if
(size <= HT_MIN_BUCKETS)
return;
return;
- if(LIKELY(size > self->shrink_threshold))
+ if
(LIKELY(size > self->shrink_threshold))
return;
resize_to = ceil_po2(size);
return;
resize_to = ceil_po2(size);
- if(resize_to < 4)
+ if
(resize_to < 4)
resize_to = 4;
resize(self, resize_to);
resize_to = 4;
resize(self, resize_to);
@@
-449,16
+443,16
@@
InsertReturnValue hashset_find(const HashSet *self, ConstKeyType key)
unsigned hash = Hash(self, key);
size_t bucknum = hash & hashmask;
unsigned hash = Hash(self, key);
size_t bucknum = hash & hashmask;
-
while(1
) {
+
for (;;
) {
HashSetEntry *entry = & self->entries[bucknum];
HashSetEntry *entry = & self->entries[bucknum];
- if(EntryIsEmpty(*entry)) {
+ if
(EntryIsEmpty(*entry)) {
return NullReturnValue;
}
return NullReturnValue;
}
- if(EntryIsDeleted(*entry)) {
+ if
(EntryIsDeleted(*entry)) {
// value is deleted
// 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 GetInsertReturnValue(*entry, 1);
}
// found the value
return GetInsertReturnValue(*entry, 1);
}
@@
-489,16
+483,16
@@
void hashset_remove(HashSet *self, ConstKeyType key)
self->entries_version++;
#endif
self->entries_version++;
#endif
-
while(1
) {
+
for (;;
) {
HashSetEntry *entry = & self->entries[bucknum];
HashSetEntry *entry = & self->entries[bucknum];
- if(EntryIsEmpty(*entry)) {
+ if
(EntryIsEmpty(*entry)) {
return;
}
return;
}
- if(EntryIsDeleted(*entry)) {
+ if
(EntryIsDeleted(*entry)) {
// entry is deleted
// 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;
EntrySetDeleted(*entry);
self->num_deleted++;
self->consider_shrink = 1;
@@
-516,10
+510,9
@@
void hashset_remove(HashSet *self, ConstKeyType key)
* Initializes hashset with a specific size
* @internal
*/
* 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);
initial_size = 4;
self->entries = Alloc(initial_size);
@@
-570,7
+563,7
@@
void hashset_init_size(HashSet *self, size_t expected_elements)
size_t needed_size;
size_t po2size;
size_t needed_size;
size_t po2size;
- if(expected_elements >= UINT_MAX/2) {
+ if
(expected_elements >= UINT_MAX/2) {
abort();
}
abort();
}
@@
-610,9
+603,9
@@
ValueType hashset_iterator_next(HashSetIterator *self)
do {
current_bucket++;
do {
current_bucket++;
- if(current_bucket >= end)
+ if
(current_bucket >= end)
return NullValue;
return NullValue;
- } while(EntryIsEmpty(*current_bucket) || EntryIsDeleted(*current_bucket));
+ } while
(EntryIsEmpty(*current_bucket) || EntryIsDeleted(*current_bucket));
self->current_bucket = current_bucket;
return EntryGetValue(*current_bucket);
self->current_bucket = current_bucket;
return EntryGetValue(*current_bucket);
@@
-631,7
+624,7
@@
void hashset_remove_iterator(HashSet *self, const HashSetIterator *iter)
/* needs to be on a valid element */
assert(entry < self->entries + self->num_buckets);
/* needs to be on a valid element */
assert(entry < self->entries + self->num_buckets);
- if(EntryIsDeleted(*entry))
+ if
(EntryIsDeleted(*entry))
return;
EntrySetDeleted(*entry);
return;
EntrySetDeleted(*entry);