Use size_t for Hash indices
Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/5e798aea Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/5e798aea Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/5e798aea Branch: refs/heads/master Commit: 5e798aea6d48f6f2412cb8132b617952e1f5607c Parents: b93a882 Author: Nick Wellnhofer <[email protected]> Authored: Fri Apr 24 12:27:06 2015 +0200 Committer: Nick Wellnhofer <[email protected]> Committed: Fri Apr 24 12:27:06 2015 +0200 ---------------------------------------------------------------------- runtime/core/Clownfish/Hash.c | 50 ++++++++++---------- runtime/core/Clownfish/Hash.cfh | 18 +++---- runtime/core/Clownfish/HashIterator.c | 18 +++---- runtime/core/Clownfish/HashIterator.cfh | 6 +-- runtime/core/Clownfish/String.c | 6 +-- runtime/core/Clownfish/String.cfh | 2 +- .../core/Clownfish/Test/TestLockFreeRegistry.c | 2 +- .../Clownfish/Test/TestLockFreeRegistry.cfh | 2 +- 8 files changed, 51 insertions(+), 53 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5e798aea/runtime/core/Clownfish/Hash.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Hash.c b/runtime/core/Clownfish/Hash.c index d0553a7..e23d3b6 100644 --- a/runtime/core/Clownfish/Hash.c +++ b/runtime/core/Clownfish/Hash.c @@ -35,14 +35,14 @@ static String *TOMBSTONE; #define HashEntry cfish_HashEntry typedef struct HashEntry { - String *key; - Obj *value; - int32_t hash_sum; + String *key; + Obj *value; + size_t hash_sum; } HashEntry; // Return the entry associated with the key, if any. static CFISH_INLINE HashEntry* -SI_fetch_entry(Hash *self, String *key, int32_t hash_sum); +SI_fetch_entry(Hash *self, String *key, size_t hash_sum); // Double the number of buckets and redistribute all entries. static CFISH_INLINE HashEntry* @@ -54,31 +54,30 @@ Hash_init_class() { } Hash* -Hash_new(uint32_t capacity) { +Hash_new(size_t capacity) { Hash *self = (Hash*)Class_Make_Obj(HASH); return Hash_init(self, capacity); } Hash* -Hash_init(Hash *self, uint32_t capacity) { +Hash_init(Hash *self, size_t min_threshold) { // Allocate enough space to hold the requested number of elements without // triggering a rebuild. - uint32_t requested_capacity = capacity < INT32_MAX ? capacity : INT32_MAX; - uint32_t threshold; - capacity = 16; - while (1) { + size_t threshold; + size_t capacity = 16; + do { threshold = (capacity / 3) * 2; - if (threshold > requested_capacity) { break; } + if (threshold > min_threshold) { break; } capacity *= 2; - } + } while (capacity <= SIZE_MAX / 2); // Init. - self->size = 0; + self->size = 0; // Derive. - self->capacity = capacity; - self->entries = (HashEntry*)CALLOCATE(capacity, sizeof(HashEntry)); - self->threshold = threshold; + self->capacity = capacity; + self->entries = (HashEntry*)CALLOCATE(capacity, sizeof(HashEntry)); + self->threshold = threshold; return self; } @@ -117,7 +116,7 @@ Hash_Clear_IMP(Hash *self) { } static void -S_do_store(Hash *self, String *key, Obj *value, int32_t hash_sum, +S_do_store(Hash *self, String *key, Obj *value, size_t hash_sum, bool incref_key) { HashEntry *entry = SI_fetch_entry(self, key, hash_sum); if (entry) { @@ -129,8 +128,8 @@ S_do_store(Hash *self, String *key, Obj *value, int32_t hash_sum, HashEntry *entries = self->size >= self->threshold ? SI_rebuild_hash(self) : (HashEntry*)self->entries; - uint32_t tick = hash_sum; - const uint32_t mask = self->capacity - 1; + size_t tick = hash_sum; + const size_t mask = self->capacity - 1; while (1) { tick &= mask; @@ -170,8 +169,8 @@ Hash_Fetch_Utf8_IMP(Hash *self, const char *key, size_t key_len) { } static CFISH_INLINE HashEntry* -SI_fetch_entry(Hash *self, String *key, int32_t hash_sum) { - uint32_t tick = hash_sum; +SI_fetch_entry(Hash *self, String *key, size_t hash_sum) { + size_t tick = hash_sum; HashEntry *const entries = (HashEntry*)self->entries; HashEntry *entry; @@ -223,7 +222,7 @@ Hash_Delete_Utf8_IMP(Hash *self, const char *key, size_t key_len) { } String* -Hash_Find_Key_IMP(Hash *self, String *key, int32_t hash_sum) { +Hash_Find_Key_IMP(Hash *self, String *key, size_t hash_sum) { HashEntry *entry = SI_fetch_entry(self, key, hash_sum); return entry ? entry->key : NULL; } @@ -281,20 +280,19 @@ Hash_Equals_IMP(Hash *self, Obj *other) { return true; } -uint32_t +size_t Hash_Get_Capacity_IMP(Hash *self) { return self->capacity; } -uint32_t +size_t Hash_Get_Size_IMP(Hash *self) { return self->size; } static CFISH_INLINE HashEntry* SI_rebuild_hash(Hash *self) { - // HashIterator ticks are int32_t. - if (self->capacity > INT32_MAX / 2) { + if (self->capacity > SIZE_MAX / 2) { THROW(ERR, "Hash grew too large"); } http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5e798aea/runtime/core/Clownfish/Hash.cfh ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Hash.cfh b/runtime/core/Clownfish/Hash.cfh index 54a7456..2960f2a 100644 --- a/runtime/core/Clownfish/Hash.cfh +++ b/runtime/core/Clownfish/Hash.cfh @@ -23,23 +23,23 @@ parcel Clownfish; */ public class Clownfish::Hash inherits Clownfish::Obj { - void *entries; - uint32_t capacity; - uint32_t size; - uint32_t threshold; /* rehashing trigger point */ + void *entries; + size_t capacity; + size_t size; + size_t threshold; /* rehashing trigger point */ inert void init_class(); public inert incremented Hash* - new(uint32_t capacity = 0); + new(size_t capacity = 0); /** * @param capacity The number of elements that the hash will be asked to * hold initially. */ public inert Hash* - init(Hash *self, uint32_t capacity = 0); + init(Hash *self, size_t capacity = 0); inert String* get_tombstone(); @@ -83,7 +83,7 @@ public class Clownfish::Hash inherits Clownfish::Obj { * rather than its value. */ nullable String* - Find_Key(Hash *self, String *key, int32_t hash_sum); + Find_Key(Hash *self, String *key, size_t hash_sum); /** Return an VArray of pointers to the hash's keys. */ @@ -95,14 +95,14 @@ public class Clownfish::Hash inherits Clownfish::Obj { public incremented VArray* Values(Hash *self); - uint32_t + size_t Get_Capacity(Hash *self); /** Accessor for Hash's "size" member. * * @return the number of key-value pairs. */ - public uint32_t + public size_t Get_Size(Hash *self); public bool http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5e798aea/runtime/core/Clownfish/HashIterator.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/HashIterator.c b/runtime/core/Clownfish/HashIterator.c index ee31066..806c325 100644 --- a/runtime/core/Clownfish/HashIterator.c +++ b/runtime/core/Clownfish/HashIterator.c @@ -28,9 +28,9 @@ static String *TOMBSTONE; typedef struct HashEntry { - String *key; - Obj *value; - int32_t hash_sum; + String *key; + Obj *value; + size_t hash_sum; } HashEntry; void @@ -50,7 +50,7 @@ HashIter_new(Hash *hash) { HashIterator* HashIter_init(HashIterator *self, Hash *hash) { self->hash = (Hash*)INCREF(hash); - self->tick = -1; + self->tick = (size_t)-1; self->capacity = hash->capacity; return self; } @@ -61,7 +61,7 @@ HashIter_Next_IMP(HashIterator *self) { THROW(ERR, "Hash modified during iteration."); } while (1) { - if (++self->tick >= (int32_t)self->capacity) { + if (++self->tick >= self->capacity) { // Iteration complete. Pin tick at capacity. self->tick = self->capacity; return false; @@ -82,10 +82,10 @@ HashIter_Get_Key_IMP(HashIterator *self) { if (self->capacity != self->hash->capacity) { THROW(ERR, "Hash modified during iteration."); } - if (self->tick >= (int32_t)self->capacity) { + if (self->tick >= self->capacity) { THROW(ERR, "Invalid call to Get_Key after end of iteration."); } - else if (self->tick == -1) { + else if (self->tick == (size_t)-1) { THROW(ERR, "Invalid call to Get_Key before iteration."); } @@ -102,10 +102,10 @@ HashIter_Get_Value_IMP(HashIterator *self) { if (self->capacity != self->hash->capacity) { THROW(ERR, "Hash modified during iteration."); } - if (self->tick >= (int32_t)self->capacity) { + if (self->tick >= self->capacity) { THROW(ERR, "Invalid call to Get_Value after end of iteration."); } - else if (self->tick == -1) { + else if (self->tick == (size_t)-1) { THROW(ERR, "Invalid call to Get_Value before iteration."); } http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5e798aea/runtime/core/Clownfish/HashIterator.cfh ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/HashIterator.cfh b/runtime/core/Clownfish/HashIterator.cfh index 0e51273..f4dea3e 100644 --- a/runtime/core/Clownfish/HashIterator.cfh +++ b/runtime/core/Clownfish/HashIterator.cfh @@ -21,9 +21,9 @@ parcel Clownfish; */ class Clownfish::HashIterator nickname HashIter inherits Clownfish::Obj { - Hash *hash; - int32_t tick; - uint32_t capacity; + Hash *hash; + size_t tick; + size_t capacity; inert void init_class(); http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5e798aea/runtime/core/Clownfish/String.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/String.c b/runtime/core/Clownfish/String.c index 2a4bbfe..067a0b2 100644 --- a/runtime/core/Clownfish/String.c +++ b/runtime/core/Clownfish/String.c @@ -185,9 +185,9 @@ Str_Destroy_IMP(String *self) { SUPER_DESTROY(self, STRING); } -int32_t +size_t Str_Hash_Sum_IMP(String *self) { - uint32_t hashvalue = 5381; + size_t hashvalue = 5381; StackStringIterator *iter = STR_STACKTOP(self); const SStrIter_Next_t next @@ -197,7 +197,7 @@ Str_Hash_Sum_IMP(String *self) { hashvalue = ((hashvalue << 5) + hashvalue) ^ code_point; } - return (int32_t) hashvalue; + return hashvalue; } static void http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5e798aea/runtime/core/Clownfish/String.cfh ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/String.cfh b/runtime/core/Clownfish/String.cfh index 6ca7285..5ad84c9 100644 --- a/runtime/core/Clownfish/String.cfh +++ b/runtime/core/Clownfish/String.cfh @@ -217,7 +217,7 @@ class Clownfish::String nickname Str /** Return a hash code for the string. */ - int32_t + size_t Hash_Sum(String *self); public incremented String* http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5e798aea/runtime/core/Clownfish/Test/TestLockFreeRegistry.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Test/TestLockFreeRegistry.c b/runtime/core/Clownfish/Test/TestLockFreeRegistry.c index 1acc1ed..5bc4d30 100644 --- a/runtime/core/Clownfish/Test/TestLockFreeRegistry.c +++ b/runtime/core/Clownfish/Test/TestLockFreeRegistry.c @@ -39,7 +39,7 @@ StupidHashString_new(const char *text) { strlen(text)); } -int32_t +size_t StupidHashString_Hash_Sum_IMP(StupidHashString *self) { UNUSED_VAR(self); return 1; http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/5e798aea/runtime/core/Clownfish/Test/TestLockFreeRegistry.cfh ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Test/TestLockFreeRegistry.cfh b/runtime/core/Clownfish/Test/TestLockFreeRegistry.cfh index a54f00b..c2cca6e 100644 --- a/runtime/core/Clownfish/Test/TestLockFreeRegistry.cfh +++ b/runtime/core/Clownfish/Test/TestLockFreeRegistry.cfh @@ -33,7 +33,7 @@ class Clownfish::Test::StupidHashString inherits Clownfish::String { new(const char *text); /** Always returns 1, guaranteeing collisions. */ - int32_t + size_t Hash_Sum(StupidHashString *self); }
