[libgee/coalesed-hash: 5/6] Temp
- From: Maciej Marcin Piechotka <mpiechotka src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [libgee/coalesed-hash: 5/6] Temp
- Date: Mon, 4 Mar 2013 17:09:11 +0000 (UTC)
commit 66bc6d59326d835e3b84e14da6c41a6aa26a2599
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date: Sat Jan 5 01:36:21 2013 +0100
Temp
gee/hash.vala | 1127 ++++++++++++++++++++++++++-------------------------
gee/hashset.vala | 99 +++---
tests/testdata.vala | 2 +-
3 files changed, 620 insertions(+), 608 deletions(-)
---
diff --git a/gee/hash.vala b/gee/hash.vala
index 48e2784..f195828 100644
--- a/gee/hash.vala
+++ b/gee/hash.vala
@@ -47,460 +47,623 @@ class Gee.Hash {
* This code contains relativy low level operations.
* Before modifing please read about strict aliasing.
*/
- internal static inline void init (Flags flags, out char *data) {
- data = GLib.Slice.alloc (_get_buckets_no (0) * BucketStructure (flags, 0).total_size);
+ internal static inline void init (Flags flags, out void *data) {
+ data = GLib.Slice.alloc0 (11 * BucketStructure (flags, true).total_size);
}
- internal static inline void cleanup<K, V> (Flags flags, char *data, int dummy_size, int real_size,
int first) {
- BucketStructure bs = BucketStructure (flags, dummy_size);
- for (Bucket curr = _get_first (bs, data, first, dummy_size, real_size); !curr.is_null; curr =
_get_next (curr, dummy_size, real_size)) {
- K key = (owned)curr.key;
- K key2 = (owned)key;
- key = (owned)key2;
- if ((flags & Flags.MAP) != 0) {
- V val = (owned)curr.value;
- V val2 = (owned)val;
- val = (owned)val2;
- }
+ internal static inline void cleanup<K, V> (Flags flags, void *data, int dummy_size, int real_size,
int first) {
+ if (dummy_size < ARRAY_THRESHOLD) {
+ _cleanup_array<K, V> (flags, data, dummy_size, real_size);
+ } else {
+ _cleanup_linked<K, V> (flags, data, dummy_size);
}
}
- internal static inline bool lookup (Flags flags, char *data, int dummy_size, int real_size, void
*key, HashDataFunc hash, EqualDataFunc equal, out uint id = null) {
- id = 0;
- Bucket bucket = _lookup (BucketStructure (flags, dummy_size), data, dummy_size, real_size,
key, hash (key), equal);
- if (!bucket.is_null) {
- id = bucket.id;
- return true;
+ internal static inline bool lookup (Flags flags, void *data, int dummy_size, int real_size, void
*key, HashDataFunc hash, EqualDataFunc equal, out void *ptr) {
+ if (dummy_size < ARRAY_THRESHOLD) {
+ return _lookup_array (flags, data, dummy_size, real_size, key, hash (key), equal, out
ptr);
} else {
- return false;
+ ptr = *_lookup_linked (flags, data, dummy_size, key, hash (key), equal);
+ return ptr != null;
}
}
- internal static inline void rehash (Flags flags, ref char *data, ref int dummy_size, ref int
real_size, int new_size, HashDataFunc hash, EqualDataFunc equal, ref uint first, ref uint last, ref uint
cellar_free, ref uint address_free) {
- BucketStructure old_bs = BucketStructure (flags, dummy_size);
- BucketStructure new_bs = BucketStructure (flags, new_size);
- _rehash (flags, old_bs, new_bs, ref data, dummy_size, real_size, new_size, hash, equal, ref
first, ref last, ref cellar_free, ref address_free);
- dummy_size = real_size = new_size;
+ internal static inline InsertResult insert<K, V> (Flags flags, ref void *data, ref int dummy_size,
ref int real_size, K key, V? value, HashDataFunc<K> hash, EqualDataFunc<K> equal, bool replace, ref void
*first, ref void *last) {
+ if (dummy_size < ARRAY_THRESHOLD) {
+ return _insert_array<K, V> (flags, ref data, ref dummy_size, ref real_size, key,
value, hash (key), hash, equal, replace, ref first, ref last, true);
+ } else {
+ return _insert_linked<K, V> (flags, ref data, ref dummy_size, ref real_size, key,
value, hash (key), hash, equal, replace, ref first, ref last, true);
+ }
}
- internal static inline InsertResult insert<K, V> (Flags flags, ref char *data, ref int dummy_size,
ref int real_size, K key, V? value, HashDataFunc<K> hash, EqualDataFunc<K> equal, bool replace, ref uint
first, ref uint last, ref uint cellar_free, ref uint address_free) {
- BucketStructure bs = BucketStructure (flags, dummy_size);
- return _insert<K, V> (flags, bs, ref data, ref dummy_size, ref real_size, key, value, hash
(key), hash, equal, replace, ref first, ref last, ref cellar_free, ref address_free);
+ internal static inline bool delete<K, V> (Flags flags, ref void *data, ref int dummy_size, ref int
real_size, K key, out V? value, HashDataFunc<K> hash, EqualDataFunc<K> equal, ref void *first, ref void
*last) {
+ if (dummy_size < ARRAY_THRESHOLD) {
+ return _delete_array<K, V> (flags, ref data, ref dummy_size, ref real_size, key, out
value, hash (key), hash, equal, ref first, ref last);
+ } else {
+ return _delete_linked<K, V> (flags, ref data, ref dummy_size, ref real_size, key, out
value, hash (key), hash, equal, ref first, ref last);
+ }
}
- internal static inline bool delete<K, V> (Flags flags, ref char *data, ref int dummy_size, ref int
real_size, K key, out V? value, HashDataFunc<K> hash, EqualDataFunc<K> equal, ref uint first, ref uint last,
ref uint cellar_free, ref uint address_free, bool allow_rehash = true) {
- BucketStructure bs = BucketStructure (flags, dummy_size);
- return _delete<K, V> (flags, bs, ref data, ref dummy_size, ref real_size, key, out value,
hash (key), hash, equal, ref first, ref last, ref cellar_free, ref address_free, allow_rehash);
+ internal static inline void *delete_iter<K, V> (Flags flags, ref char *data, ref int dummy_size, ref
int real_size, ref void **iter_base, void *iter_ptr, out V value, HashDataFunc<K> hash, EqualDataFunc<K>
equal, ref void *first, ref void *last) {
+ if (dummy_size < ARRAY_THRESHOLD) {
+ return _delete_iter_array<K, V> (flags, ref data, ref dummy_size, ref real_size,ref
iter_base, iter_ptr, out value, hash, equal, ref first, ref last);
+ } else {
+ return _delete_iter_linked<K, V> (flags, ref data, ref dummy_size, ref real_size,ref
iter_base, iter_ptr, out value, hash, equal, ref first, ref last);
+ }
}
- internal static inline int get_first (Flags flags, char *data, int dummy_size, int real_size, int
first) {
- Bucket b = _get_first (BucketStructure (flags, dummy_size), data, first, dummy_size,
real_size);
- return b.is_null ? -1 : (int)b.id;
+ internal static inline void *get_first (Flags flags, void *data, int dummy_size, int real_size, void
*first, out void *iter_base) {
+ if (dummy_size < ARRAY_THRESHOLD) {
+ return (iter_base = _get_first_array (flags, data, dummy_size, real_size));
+ } else {
+ return _get_first_linked (flags, data, dummy_size, real_size, first, out iter_base);
+ }
}
- internal static inline int get_next (Flags flags, char *data, int dummy_size, int real_size, int
curr) {
- Bucket b = _get_next (Bucket (BucketStructure (flags, dummy_size), data, curr), dummy_size,
real_size);
- return b.is_null ? -1 : (int)b.id;
+ internal static inline void get_next (Flags flags, void *data, int dummy_size, int real_size, ref
void *curr_base, ref void *curr_ptr) {
+ if (dummy_size < ARRAY_THRESHOLD) {
+ curr_ptr = _get_next_array (flags, data, dummy_size, real_size, curr_ptr);
+ } else {
+ curr_ptr = _get_next_linked (flags, data, dummy_size, real_size, ref curr_base,
curr_ptr);
+ }
}
- internal static inline unowned K get_key<K> (Flags flags, char *data, int size, int curr) {
- return Bucket (BucketStructure (flags, size), data, curr).key;
+ internal static inline unowned K get_key<K> (Flags flags, void *data, int size, void *curr_ptr) {
+ return Bucket (BucketStructure (flags, size < ARRAY_THRESHOLD), curr_ptr).key;
}
-#if DEBUG
- internal static inline void dump (Flags flags, char *data, int dummy_size, int real_size, uint first,
uint last, uint cellar_free, uint address_free) {
- BucketStructure bs = BucketStructure (flags, dummy_size);
- stderr.printf ("# Dumping hashtable...\n");
- if (bs.next_offset != -1) {
- if ((flags & Flags.LINKED_HASH) != 0) {
- stderr.printf ("# First element: %s\n", first != LINK_END ?
first.to_string () : "(null)");
- stderr.printf ("# Last element: %s\n", last != LINK_END ? last.to_string
() : "(null)");
+ /**********************************************************************
+ * Linked section *
+ **********************************************************************/
+
+ private static inline void **_lookup_linked (Flags flags, void *data, int dummy_size, void *key, uint
hash, EqualDataFunc equal) {
+ BucketStructure bs = BucketStructure (flags, dummy_size < ARRAY_THRESHOLD);
+#if ASSERT
+ assert (bs.next_offset != -1);
+#endif
+ void **curr_ptr = (void **)((char *)data + sizeof(void *) * (_folded_hash (hash, dummy_size)
% _get_buckets_no (dummy_size)));
+ bool skip_hash = !((flags & Flags.CACHE_HASH) != 0 && (flags &
Flags.CACHE_HASH_ONLY_IN_ARRAY) == 0);
+ while (*curr_ptr != null) {
+ Bucket curr = Bucket (bs, *curr_ptr);
+ if ((skip_hash || curr.hash == hash) && equal (curr.key, key)) {
+ return curr_ptr;
}
- stderr.printf ("# First free element in cellar region: %s\n", cellar_free !=
LINK_END ? cellar_free.to_string () : "(null)");
- stderr.printf ("# First free element in address region: %s\n", address_free !=
LINK_END ? address_free.to_string () : "(null)");
- stderr.printf("#
==========================================================================\n");
- int digits_id = (int)GLib.Math.log10(_get_buckets_no (dummy_size));
+ curr_ptr = curr.next_ptr;
+ }
+ return curr_ptr;
+ }
+
+ private static inline void *_get_first_linked (Flags flags, void *data, int dummy_size, int
real_size, void *first, out void *curr_base) {
+#if ASSERT
+ BucketStructure bs = BucketStructure (flags, false);
+ assert (bs.next_offset != -1);
+#endif
+ if ((Flags.LINKED_HASH & flags) != 0) {
+ return first;
+ } else {
for (int i = 0; i < _get_buckets_no (dummy_size); i++) {
- Bucket b = Bucket (bs, data, i);
- if (b.next.is_null && !b.present) {
- stderr.printf ("# %*d FREE: prev. free = %*d, next free = %*d\n",
digits_id, i, digits_id, b.fprev_id != LINK_END ? b.fprev_id : -1, digits_id, b.fnext_id != LINK_END ?
b.fnext_id : -1);
- } else if (!b.present) {
- stderr.printf ("# %*d DELETED: next = %*d\n", digits_id, i,
digits_id, b.next_id);
- } else {
- stderr.printf ("# %*d OCCUPIED: key = \"%s\"%s%s, next = %*d\n",
digits_id, i, (string)b.key, (flags & Flags.MAP) != 0 ? ", value = \"%s\"".printf((string)b.value) : "",
(flags & Flags.LINKED_HASH) != 0 ? ", iter. prev. = %*d, iter. next = %*d".printf (digits_id, b.iprev,
digits_id, b.inext) : "", digits_id, b.next_id != LINK_END ? b.next_id : -1);
- }
- if (i + 1 == _get_primary_bucket_no (dummy_size)) {
- stderr.printf("#
--------------------------------------------------------------------------\n");
+ void **curr_base_ = (void **)((char *)data + sizeof(void *) * i);
+ if (*curr_base_ != null) {
+ curr_base = curr_base_;
+ return *curr_base_;
}
}
- stderr.printf("#
==========================================================================\n");
+ return null;
+ }
+ }
+
+ private static inline void *_get_next_linked (Flags flags, void *data, int dummy_size, int real_size,
ref void *curr_base, void *curr_ptr) {
+ BucketStructure bs = BucketStructure (flags, false);
+#if ASSERT
+ assert (bs.next_offset != -1);
+#endif
+ if ((Flags.LINKED_HASH & flags) != 0) {
+ return *Bucket (bs, curr_ptr).inext_ptr;
} else {
- stderr.printf("#
==========================================================================\n");
- int digits_id = (int)GLib.Math.log10(ARRAY_THRESHOLD);
- for (int i = 0; i < real_size; i++) {
- Bucket b = Bucket (bs, data, i);
- stderr.printf ("# %*d OCCUPIED: key = \"%s\"%s\n", digits_id, i,
(string)b.key, (flags & Flags.MAP) != 0 ? ", value = \"%s\"".printf((string)b.value) : "");
- }
- stderr.printf("#
--------------------------------------------------------------------------\n");
- for (int i = real_size; i < ARRAY_THRESHOLD; i++) {
- stderr.printf ("# %*d FREE\n", digits_id, i);
+ Bucket curr = Bucket (bs, curr_ptr);
+ if (*curr.next_ptr != null) {
+ return *curr.next_ptr;
+ }
+ for (int i = (int)(((char *)curr_base - (char *)data)/sizeof(void *) + 1); i <
_get_buckets_no (dummy_size); i++) {
+ void **_curr_base = (void **)((char *)data + sizeof(void *) * i);
+ if (*_curr_base != null) {
+ curr_base = _curr_base;
+ return *_curr_base;
+ }
}
- stderr.printf("#
==========================================================================\n");
+ curr_base = null;
+ return null;
}
}
-#endif
- private static inline Bucket _lookup (BucketStructure bs, char *data, int dummy_size, int real_size,
void *key, uint hash, EqualDataFunc equal, out Bucket insert_prev = null, out Bucket delete_prev = null, out
Bucket first_deleted = null) {
- insert_prev = Bucket.null (bs, data);
- delete_prev = Bucket.null (bs, data);
- first_deleted = Bucket.null (bs, data);
- if (bs.next_offset != -1) {
- Bucket curr = Bucket (bs, data, _folded_hash (hash, dummy_size) %
_get_primary_bucket_no (dummy_size));
- while (!curr.is_null) {
- if (curr.present) {
- if ((bs.hash_offset == -1 || curr.hash == hash) && equal (curr.key,
key)) {
- return curr;
- }
- } else if (first_deleted.is_null) {
- first_deleted = curr;
- }
- if (insert_prev.is_null || curr.id >= _get_primary_bucket_no (dummy_size)) {
- insert_prev = curr;
+ private static inline InsertResult _insert_linked<K, V> (Flags flags, ref char *data, ref int
dummy_size, ref int real_size, K key, V? value, uint khash, HashDataFunc<K> hash, EqualDataFunc<K> equal,
bool replace, ref void *first, ref void *last, bool allow_rehash = true) {
+ BucketStructure bs = BucketStructure (flags, false);
+#if ASSERT
+ assert (bs.next_offset != -1);
+#endif
+ void **bucket = _lookup_linked (flags, data, dummy_size, key, khash, equal);
+ if (*bucket != null) {
+ if (replace) {
+ Bucket curr = Bucket (bs, *bucket);
+ K k = (owned)curr.key;
+ k = key;
+ curr.key = (owned)k;
+ if ((flags & Flags.MAP) != 0) {
+ V v = (owned)curr.value;
+ v = value;
+ curr.value = (owned)v;
}
- assert (curr.id != curr.next.id);
- delete_prev = curr;
- curr = curr.next;
+ return InsertResult.REPLACE;
+ } else {
+ return InsertResult.FAIL;
}
- return curr;
} else {
- for (int i = 0; i < real_size; i++) {
- Bucket curr = Bucket (bs, data, i);
- if ((bs.hash_offset == -1 || curr.hash == hash) && equal (curr.key, key)) {
- return curr;
+ Bucket curr = Bucket (bs, GLib.Slice.alloc (bs.total_size));
+ K k = key;
+ curr.key = (owned)k;
+ if ((flags & Flags.MAP) != 0) {
+ V v = value;
+ curr.value = (owned)v;
+ }
+ if ((flags & Flags.CACHE_HASH) != 0 && (flags & Flags.CACHE_HASH_ONLY_IN_ARRAY) == 0)
{
+ curr.hash = khash;
+ }
+ if ((flags & Flags.LINKED_HASH) != 0) {
+ if (first == null) {
+#if ASSERT
+ assert (last == null)
+#endif
+ first = curr._data;
+ last = curr._data;
+ *curr.iprev_ptr = null;
+ } else {
+ Bucket last_bucket = Bucket (bs, last);
+#if ASSERT
+ assert (*last_bucket.inext_ptr == null)
+#endif
+ *last_bucket.inext_ptr = curr._data;
}
+ *curr.inext_ptr = null;
+ }
+ *curr.next_ptr = null;
+ *bucket = curr._data;
+ real_size++;
+ if (allow_rehash && 3 * _get_buckets_no (dummy_size) < _get_buckets_no (real_size)
|| 3 * _get_buckets_no (real_size) < _get_buckets_no (dummy_size)) {
+ _rehash_linked<K, V> (flags, ref data, ref dummy_size, ref real_size,
real_size, hash, equal, ref first, ref last, false);
}
- return Bucket.null (bs, data);
+ return InsertResult.INSERT;
}
}
- private static inline Bucket _get_first (BucketStructure bs, char *data, uint first, int dummy_size,
int real_size) {
- if (bs.inext_offset != -1) {
- return Bucket (bs, data, first);
- } else {
- return _get_next (Bucket (bs, data, -1), dummy_size, real_size);
+ private static inline bool _delete_linked<K, V> (Flags flags, ref char *data, ref int dummy_size, ref
int real_size, K key, out V? value, uint khash, HashDataFunc<K> hash, EqualDataFunc<K> equal, ref void
*first, ref void *last, bool allow_rehash = true) {
+ BucketStructure bs = BucketStructure (flags, false);
+#if ASSERT
+ assert (bs.next_offset != -1);
+#endif
+ value = null;
+ void **location = _lookup_linked (flags, data, dummy_size, key, khash, equal);
+ if (*location == null) {
+ return false;
+ }
+ Bucket curr = Bucket (bs, *location);
+ K k = (owned)curr.key;
+ _delete_helper<K> ((owned)k);
+ if ((flags & Flags.MAP) != 0) {
+ V v = (owned)curr.value;
+ _delete_helper<V> ((owned)v);
}
+ if ((flags & Flags.LINKED_HASH) != 0) {
+#if ASSERT
+ assert ((first == *location) == (*curr.iprev_ptr == null));
+ assert ((last == *location) == (*curr.inext_ptr == null));
+#endif
+ if (first == *location) {
+ first = *curr.inext_ptr;
+ } else {
+ *curr.iprev.inext_ptr = *curr.inext_ptr;
+ }
+ if (last == *location) {
+ last = *curr.iprev_ptr;
+ } else {
+ *curr.inext.iprev_ptr = *curr.iprev_ptr;
+ }
+ }
+ *location = *curr.next_ptr;
+ GLib.Slice.free (bs.total_size, curr._data);
+ real_size--;
+ if (allow_rehash) {
+ if (real_size < ARRAY_THRESHOLD) {
+ _rehash_linked_to_array<K, V> (flags, ref data, ref dummy_size, ref
real_size, real_size, hash, equal, ref first, ref last);
+ } else if (3 * _get_buckets_no (dummy_size) < _get_buckets_no (real_size) || 3 *
_get_buckets_no (real_size) < _get_buckets_no (dummy_size)) {
+ _rehash_linked<K, V> (flags, ref data, ref dummy_size, ref real_size,
real_size, hash, equal, ref first, ref last);
+ }
+ }
+ return true;
}
- private static inline Bucket _get_next (Bucket curr, int dummy_size, int real_size) {
- if (curr._bs.inext_offset != -1) {
- return curr.inext;
- } else if (curr._bs.next_offset != -1) {
- for (uint i = curr._id + 1; i < _get_buckets_no(dummy_size); i++) {
- curr = Bucket (curr._bs, curr._data, i);
- if (curr.present) {
- return curr;
+ private static inline void *_delete_iter_linked<K, V> (Flags flags, ref char *data, ref int
dummy_size, ref int real_size, ref void **iter_base, void *iter_ptr, out V value, HashDataFunc<K> hash,
EqualDataFunc<K> equal, ref void *first, ref void *last) {
+ BucketStructure bs = BucketStructure (flags, false);
+ void **curr_base = iter_base;
+ void *curr_ptr = iter_ptr;
+ iter_ptr = _get_next_linked (flags, data, dummy_size, real_size, ref iter_base, iter_ptr);
+ while (true) {
+#if ASSERT
+ assert (*curr_base != null);
+#endif
+ if (*curr_base == curr_ptr) {
+ Bucket curr = Bucket (bs, curr_ptr);
+ *curr_base = *curr.next_ptr;
+ K k = (owned)curr.key;
+ _delete_helper<K> ((owned)k);
+ if ((flags & Flags.MAP) != 0) {
+ V v = (owned)curr.value;
+ _delete_helper<V> ((owned)v);
+ }
+ real_size--;
+ if ((flags & Flags.LINKED_HASH) != 0) {
+#if ASSERT
+ assert ((first == curr_ptr) == (*curr.iprev_ptr == null));
+ assert ((last == curr_ptr) == (*curr.inext_ptr == null));
+#endif
+ if (first == curr_ptr) {
+ first = *curr.inext_ptr;
+ } else {
+ *curr.iprev.inext_ptr = *curr.inext_ptr;
+ }
+ if (last == curr_ptr) {
+ last = *curr.iprev_ptr;
+ } else {
+ *curr.inext.iprev_ptr = *curr.iprev_ptr;
+ }
+
+ if (dummy_size < ARRAY_THRESHOLD) {
+ if (iter_ptr != null) {
+ Bucket next = Bucket (bs, iter_ptr);
+ K nk = next.key;
+ uint khash = ((flags & Flags.CACHE_HASH) != 0 &&
(flags & Flags.CACHE_HASH_ONLY_IN_ARRAY) == 0) ? next.hash : hash (nk);
+ _rehash_linked_to_array<K, V> (flags, ref data, ref
dummy_size, ref real_size, real_size, hash, equal, ref first, ref last);
+ bool b = _lookup_array (flags, data, dummy_size,
real_size, nk, khash, equal, out iter_ptr);
+ assert (b);
+ } else {
+ _rehash_linked_to_array<K, V> (flags, ref data, ref
dummy_size, ref real_size, real_size, hash, equal, ref first, ref last);
+ }
+ } else if (3 * _get_buckets_no (dummy_size) < _get_buckets_no
(real_size) || 3 * _get_buckets_no (real_size) < _get_buckets_no (dummy_size)) {
+ _rehash_linked<K, V> (flags, ref data, ref dummy_size, ref
real_size, real_size, hash, equal, ref first, ref last);
+ }
}
+ return iter_ptr;
+ } else {
+ Bucket curr = Bucket (bs, *curr_base);
+ curr_base = curr.next_ptr;
}
- return Bucket.null (curr._bs, curr._data);
- } else {
- return (curr._id + 1 < real_size) ? Bucket (curr._bs, curr._data, curr._id + 1):
Bucket.null (curr._bs, curr._data);
}
}
- private static inline InsertResult _insert<K, V> (Flags flags, BucketStructure bs, ref char *data,
ref int dummy_size, ref int real_size, K key, V? value, uint khash, HashDataFunc<K> hash, EqualDataFunc<K>
equal, bool replace, ref uint first, ref uint last, ref uint cellar_free, ref uint address_free, bool
allow_rehash = true) {
- if (bs.next_offset != -1) {
- // STEP 1: Lookup bucket
- Bucket first_deleted;
- Bucket prev;
- Bucket curr = _lookup (bs, data, dummy_size, real_size, key, khash, equal, out prev,
null, out first_deleted);
- if (!curr.is_null) {
- if (replace) {
+ private static inline void _rehash_linked_to_array<K, V> (Flags flags, ref char *data, ref int
dummy_size, ref int real_size, int new_size, HashDataFunc hash, EqualDataFunc equal, ref void *first, ref
void *last) {
+ BucketStructure bs = BucketStructure (flags, false);
+ BucketStructure new_bs = BucketStructure (flags, true);
+#if ASSERT
+ assert (bs.next_offset != -1);
+ assert (new_bs.next_offset != -1);
+ assert (new_size < ARRAY_THRESHOLD);
+#endif
+ char *old_data = data;
+ int old_dummy_size = dummy_size;
+ int old_real_size = real_size;
+ data = GLib.Slice.alloc (ARRAY_THRESHOLD * new_bs.total_size);
+ first = null;
+ last = null;
+ dummy_size = new_size;
+ real_size = 0;
+ void *iter_base, iter_ptr;
+ for (iter_ptr = _get_first_linked (flags, old_data, old_dummy_size, real_size, first, out
iter_base); iter_ptr != null; iter_ptr = _get_next_linked (flags, old_data, old_dummy_size, old_real_size,
ref iter_base, iter_ptr)) {
+ Bucket bucket = Bucket (bs, iter_ptr);
+#if ASSERT
+ char *data_save = data;
+ int real_size_save = real_size;
+ int dummy_size_save = dummy_size;
+#endif
+ K key = (owned)bucket.key;
+ V? value = ((flags & Flags.MAP) != 0) ? (owned)bucket.value : null;
+ uint khash = ((flags & Flags.CACHE_HASH) != 0 && (flags &
Flags.CACHE_HASH_ONLY_IN_ARRAY) == 0) ? bucket.hash : hash (key);
+ InsertResult it = _insert_array<K, V> (flags, ref data, ref dummy_size, ref
real_size, key, value, khash, hash, equal, false, ref first, ref last, false);
+#if ASSERT
+ assert (it == InsertResult.INSERT);
+ assert (data_save == data);
+ assert (real_size_save + 1 == real_size);
+ assert (dummy_size_save == dummy_size);
+#endif
+ }
+ _cleanup_linked<K, V> (flags, old_data, old_dummy_size, true);
+ }
+
+ private static inline void _rehash_linked<K, V> (Flags flags, ref char *data, ref int dummy_size, ref
int real_size, int new_size, HashDataFunc hash, EqualDataFunc equal, ref void *first, ref void *last, bool
to_array = false) {
+ BucketStructure bs = BucketStructure (flags, false);
+#if ASSERT
+ assert (bs.next_offset != -1);
+ assert (new_size >= ARRAY_THRESHOLD);
+#endif
+ void *old_data = data;
+ int old_dummy_size = dummy_size;
+ int old_real_size = real_size;
+ data = GLib.Slice.alloc0 (sizeof(void *) * _get_buckets_no (new_size));
+ first = null;
+ last = null;
+ dummy_size = new_size;
+ real_size = 0;
+ bool skip_hash = !((flags & Flags.CACHE_HASH) != 0 && (flags &
Flags.CACHE_HASH_ONLY_IN_ARRAY) == 0);
+ for (void **iter_base = (void **)old_data; iter_base < (void **)old_data + _get_buckets_no
(old_dummy_size); iter_base++) {
+ void *iter_ptr = *iter_base;
+ while (iter_ptr != null) {
+ Bucket bucket = Bucket (bs, iter_ptr);
+ void *next_ptr = *bucket.next_ptr;
+ *bucket.next_ptr = null;
+ uint khash = skip_hash ? hash (bucket.key) : bucket.hash;
+ void **new_base = (void **)((char *)data + sizeof (void *) * (khash %
_get_buckets_no (new_size)));
+ *bucket.next_ptr = *new_base;
+ *new_base = iter_ptr;
+ real_size++;
+ iter_ptr = next_ptr;
+ }
+ }
+ GLib.Slice.free (sizeof(void *) * _get_buckets_no (old_dummy_size), old_data);
+ }
+
+ private static inline void _cleanup_linked<K, V> (Flags flags, void *data, int dummy_size, bool
skip_destroy = false) {
+ BucketStructure bs = BucketStructure (flags, false);
+ for (void **base_ptr = (void **)data; base_ptr < (void **)((char *)data + sizeof(void *) *
_get_buckets_no (dummy_size)); base_ptr++) {
+ void *iter_ptr = *base_ptr;
+ while (iter_ptr != null) {
+ Bucket curr = Bucket (bs, iter_ptr);
+ if (!skip_destroy) {
K k = (owned)curr.key;
- k = key;
- curr.key = (owned)k;
- if (bs.value_offset != -1) {
+ _delete_helper<K> ((owned)k);
+ if ((flags & Flags.MAP) != 0) {
V v = (owned)curr.value;
- v = value;
- curr.value = (owned)v;
+ _delete_helper<V> ((owned)v);
}
- return InsertResult.REPLACE;
- } else {
- return InsertResult.FAIL;
}
+ void *new_iter_ptr = *curr.next_ptr;
+ GLib.Slice.free (bs.total_size, iter_ptr);
+ iter_ptr = new_iter_ptr;
}
- // STEP 2: Allocate new bucket
- if (!first_deleted.is_null) {
- curr = first_deleted;
- if (curr.next.is_null) {
- _allocate (curr, ref cellar_free, ref address_free);
- } else {
- }
- } else {
- curr = _allocate_any (bs, data, ref cellar_free, ref address_free);
- if (GLib.unlikely(curr.is_null)) {
- // This should be rare
- assert (allow_rehash);
- BucketStructure new_bs = BucketStructure (flags, real_size + 1);
- _rehash (flags, bs, new_bs, ref data, dummy_size, real_size,
real_size + 1, hash, equal, ref first, ref last, ref cellar_free, ref address_free, true);
- dummy_size = real_size = real_size + 1;
- bs = new_bs;
- curr = _lookup (bs, data, dummy_size, real_size, key, khash, equal,
out prev);
- assert (curr.is_null);
- curr = _allocate_any (bs, data, ref cellar_free, ref address_free);
- assert (!curr.is_null);
- allow_rehash = false;
- }
- if (!prev.is_null) {
- curr.next = prev.next;
- prev.next = curr;
- } else {
- curr.next = Bucket.null (bs, data);
- }
+ }
+ GLib.Slice.free (sizeof(void *) * _get_buckets_no (dummy_size), data);
+ }
+
+ /**********************************************************************
+ * Array section *
+ **********************************************************************/
+ private static inline bool _lookup_array (Flags flags, void *data, int dummy_size, int real_size,
void *key, uint hash, EqualDataFunc equal, out void *location) {
+ assert (real_size < ARRAY_THRESHOLD);
+ BucketStructure bs = BucketStructure (flags, true);
+#if ARRAY
+ assert (bs.next_offset == -1);
+#endif
+ bool skip_hash = !((flags & Flags.CACHE_HASH) != 0);
+ for (int i = 0; i < real_size; i++) {
+ Bucket curr = Bucket (bs, (void *)((char *)data + bs.total_size * i));
+ if ((skip_hash || curr.hash == hash) && equal (curr.key, key)) {
+ location = (void *)((char *)data + bs.total_size * i);
+ return true;
}
- // STEP 3: Insert bucket
- curr.present = true;
- {
- K k = key;
+ }
+ location = (void *)((char *)data + bs.total_size * real_size);
+ return false;
+ }
+
+ private static inline void *_get_first_array (Flags flags, void *data, int dummy_size, int real_size)
{
+ return real_size != 0 ? data : null;
+ }
+
+ private static inline void *_get_next_array (Flags flags, void *data, int dummy_size, int real_size,
void *curr_ptr) {
+ BucketStructure bs = BucketStructure (flags, true);
+#if ARRAY
+ assert (bs.next_offset == -1);
+#endif
+ if ((int)(((char *)curr_ptr - (char *)data)/bs.total_size + 1) < real_size) {
+ return (void *)((char *)curr_ptr + bs.total_size);
+ } else {
+ return null;
+ }
+ }
+
+ private static inline InsertResult _insert_array<K, V> (Flags flags, ref char *data, ref int
dummy_size, ref int real_size, K key, V? value, uint khash, HashDataFunc<K> hash, EqualDataFunc<K> equal,
bool replace, ref void *first, ref void *last, bool allow_rehash = true) {
+ BucketStructure bs = BucketStructure (flags, true);
+#if ASSERT
+ assert (bs.next_offset == -1);
+#endif
+ void *location;
+ if (_lookup_array (flags, data, dummy_size, real_size, key, khash, equal, out location)) {
+ if (replace) {
+ Bucket curr = Bucket (bs, location);
+ K k = (owned)curr.key;
+ k = key;
curr.key = (owned)k;
- }
- {
- V v = value;
- curr.value = (owned)v;
- }
- curr.hash = khash;
- if (last == LINK_END) {
- first = curr._id;
- last = curr._id;
- curr.iprev_id = LINK_END;
- curr.inext_id = LINK_END;
- } else {
- Bucket lastb = Bucket (bs, data, last);
- lastb.inext = curr;
- curr.inext_id = LINK_END;
- curr.iprev_id = last;
- last = curr._id;
- }
- if (allow_rehash) {
- BucketStructure new_bs = BucketStructure (flags, real_size + 1);
- _rehash (flags, bs, new_bs, ref data, dummy_size, real_size + 1, real_size +
1, hash, equal, ref first, ref last, ref cellar_free, ref address_free);
- real_size = dummy_size = real_size + 1;
+ if ((flags & Flags.MAP) != 0) {
+ V v = (owned)curr.value;
+ v = value;
+ curr.value = (owned)v;
+ }
+ return InsertResult.REPLACE;
} else {
- real_size++;
+ return InsertResult.FAIL;
}
- return InsertResult.INSERT;
} else {
- for (int i = 0; i < real_size; i++) {
- Bucket curr = Bucket (bs, data, i);
- if ((bs.hash_offset == -1 || curr.hash == khash) && equal (curr.key, key)) {
- if (replace) {
- K k = (owned)curr.key;
- k = key;
- curr.key = (owned)k;
- if (bs.value_offset != -1) {
- V v = (owned)curr.value;
- v = value;
- curr.value = (owned)v;
- }
- return InsertResult.REPLACE;
- } else {
- return InsertResult.FAIL;
- }
- }
- }
- assert (real_size <= ARRAY_THRESHOLD);
- Bucket curr = Bucket (bs, data, real_size);
- {
- K k = key;
- curr.key = (owned)k;
- }
- {
+ Bucket curr = Bucket (bs, location);
+ K k = key;
+ curr.key = (owned)k;
+ if ((flags & Flags.MAP) != 0) {
V v = value;
curr.value = (owned)v;
}
- curr.hash = khash;
- if (allow_rehash) {
- BucketStructure new_bs = BucketStructure (flags, real_size + 1);
- _rehash (flags, bs, new_bs, ref data, dummy_size, real_size + 1, real_size +
1, hash, equal, ref first, ref last, ref cellar_free, ref address_free);
- real_size = dummy_size = real_size + 1;
- } else {
- real_size++;
+ if ((flags & Flags.CACHE_HASH) != 0) {
+ curr.hash = khash;
+ }
+ real_size++;
+#if ASSERT
+ assert (real_size != ARRAY_THRESHOLD || allow_rehash);
+#endif
+ if (allow_rehash && real_size == ARRAY_THRESHOLD) {
+ _rehash_array<K, V> (flags, ref data, ref dummy_size, ref real_size,
real_size, hash, equal, ref first, ref last);
}
return InsertResult.INSERT;
}
}
- private static inline bool _delete<K, V> (Flags flags, BucketStructure bs, ref char *data, ref int
dummy_size, ref int real_size, K key, out V? value, uint khash, HashDataFunc<K> hash, EqualDataFunc<K> equal,
ref uint first, ref uint last, ref uint cellar_free, ref uint address_free, bool allow_rehash = true) {
+ private static inline bool _delete_array<K, V> (Flags flags, ref char *data, ref int dummy_size, ref
int real_size, K key, out V? value, uint khash, HashDataFunc<K> hash, EqualDataFunc<K> equal, ref void
*first, ref void *last) {
+ BucketStructure bs = BucketStructure (flags, true);
+#if ASSERT
+ assert (bs.next_offset == -1);
+#endif
value = null;
- Bucket prev;
- Bucket curr = _lookup (bs, data, dummy_size, real_size, key, khash, equal, null, out prev);
- if (!curr.is_null) {
- if (bs.key_offset != -1) {
- K *kp = curr.key;
- K k = (owned)kp;
- }
- if (bs.value_offset != -1) {
- V *vp = curr.value;
- value = (owned)vp;
- }
- if (bs.inext_offset != -1) {
- assert ((first == curr._id) == curr.iprev.is_null);
- assert ((last == curr._id) == curr.inext.is_null);
- if (!curr.iprev.is_null) {
- curr.iprev.inext = curr.inext;
- } else {
- first = curr.inext._id;
- }
- if (!curr.iprev.is_null) {
- curr.inext.iprev = curr.iprev;
- } else {
- last = curr.iprev_id;
- }
- }
- if (bs.next_offset != -1) {
- if (prev.is_null) {
- // CASE 1: head of chain
- curr.present = false;
- if (curr.next.is_null) {
- _release (curr, dummy_size, ref cellar_free, ref
address_free);
- }
- } else if (curr._id >= _get_primary_bucket_no (dummy_size)) {
- // CASE 2: in cellar region
- prev.next = curr.next;
- curr.present = false;
- curr.next = Bucket.null (bs, data);
- _release (curr, dummy_size, ref cellar_free, ref address_free);
- } else {
- // CASE 3: in address region
- curr.present = false;
- Bucket j = curr.next;
- prev.next = Bucket.null (bs, data);
- curr.next = Bucket.null (bs, data);
- while (!j.is_null) {
- Bucket k = Bucket (bs, data, j._hash (hash) %
_get_primary_bucket_no (dummy_size));
- while (!k.next.is_null && k.next._id >=
_get_primary_bucket_no (dummy_size)) {
- k = k.next;
- }
- Bucket nj = j.next;
- j.next = k.next;
- k.next = j;
- j = nj;
- }
- if (curr.next.is_null) {
- _release (curr, dummy_size, ref cellar_free, ref
address_free);
- }
- if (!prev.present && prev.next.is_null) {
- _release (prev, dummy_size, ref cellar_free, ref
address_free);
- }
- }
- } else {
- GLib.Memory.move (data + bs.total_size * curr._id, data + bs.total_size *
(curr._id + 1), bs.total_size * (real_size - curr._id - 1));
- }
- if (allow_rehash) {
- BucketStructure new_bs = BucketStructure (flags, real_size - 1);
- _rehash (flags, bs, new_bs, ref data, dummy_size, real_size - 1, real_size -
1, hash, equal, ref first, ref last, ref cellar_free, ref address_free);
- dummy_size = real_size = real_size - 1;
- } else {
- real_size--;
+ void *location;
+ if (_lookup_array (flags, data, dummy_size, real_size, key, khash, equal, out location)) {
+ Bucket curr = Bucket (bs, location);
+ K k = (owned)curr.key;
+ _delete_helper<K> ((owned)k);
+ if ((flags & Flags.MAP) != 0) {
+ V v = (owned)curr.value;
+ _delete_helper<V> ((owned)v);
}
+ char *next = (char *)location + bs.total_size;
+ char *end = (char *)data + bs.total_size * real_size;
+ GLib.Memory.move (location, next, end - next);
+ dummy_size = --real_size;
return true;
} else {
return false;
}
}
- private static inline void _rehash (Flags flags, BucketStructure old_bs, BucketStructure new_bs, ref
char *data, int old_dummy_size, int old_real_size, int new_size, HashDataFunc hash, EqualDataFunc equal, ref
uint first, ref uint last, ref uint cellar_free, ref uint address_free, bool force = false) {
- if (!force && _get_buckets_no(old_dummy_size) == _get_buckets_no(new_size))
- return;
- char *new_data = GLib.Slice.alloc0 (_get_buckets_no(new_size) * new_bs.total_size);
- cellar_free = (_get_primary_bucket_no (new_size) != _get_buckets_no(new_size)) ?
_get_primary_bucket_no (new_size) : LINK_END;
- address_free = 0;
- for (uint i = 0; i < _get_buckets_no(new_size); i++) {
- Bucket b = Bucket (new_bs, new_data, i);
- b.fprev = (i == 0 || i == _get_primary_bucket_no (new_size)) ? Bucket.null (new_bs,
new_data) : Bucket (new_bs, new_data, i - 1);
- b.fnext = (i == _get_primary_bucket_no (new_size) - 1 || i ==
_get_buckets_no(new_size) - 1) ? Bucket.null (new_bs, new_data) : Bucket (new_bs, new_data, i + 1);
- b.present = false;
- b.next_id = LINK_END;
- }
- int new_real_size = 0;
- for (Bucket b = _get_first (old_bs, data, first, old_dummy_size, old_real_size); !b.is_null;
b = _get_next (b, old_dummy_size, old_real_size)) {
- char *nnew_data = new_data;
- int nnew_dummy_size = new_size;
- int nnew_real_size = new_real_size;
- void *key = old_bs.key_offset != -1 ? b.key : null;
- void *value = old_bs.value_offset != -1 ? b.value : null;
- InsertResult ir = _insert<void *, void *> (flags, new_bs, ref nnew_data, ref
nnew_dummy_size, ref nnew_real_size, key, value, b._hash(hash), hash, equal, false, ref first, ref last, ref
cellar_free, ref address_free, false);
- assert (ir == InsertResult.INSERT);
- assert (new_data == nnew_data);
- assert (new_size == nnew_dummy_size);
- assert (++new_real_size == nnew_real_size);
- }
- GLib.Slice.free (_get_buckets_no(old_dummy_size) * old_bs.total_size, data);
- data = new_data;
- }
-
- private static inline Bucket _allocate_any (BucketStructure bs, char *data, ref uint cellar_free, ref
uint address_free) {
- if (cellar_free != LINK_END) {
- Bucket bucket = Bucket (bs, data, cellar_free);
- cellar_free = bucket.fnext._id;
- Bucket next_free = Bucket (bs, data, cellar_free);
- if (!next_free.is_null)
- next_free.fprev_id = LINK_END;
- return bucket;
- } else if (address_free != LINK_END) {
- Bucket bucket = Bucket (bs, data, address_free);
- address_free = bucket.fnext._id;
- Bucket next_free = Bucket (bs, data, address_free);
- if (!next_free.is_null)
- next_free.fprev_id = LINK_END;
- return bucket;
- } else {
- return Bucket.null (bs, data);
+ private static inline void *_delete_iter_array<K, V> (Flags flags, ref char *data, ref int
dummy_size, ref int real_size, ref void **iter_base, void *iter_ptr, out V value, HashDataFunc<K> hash,
EqualDataFunc<K> equal, ref void *first, ref void *last) {
+ BucketStructure bs = BucketStructure (flags, true);
+ Bucket curr = Bucket (bs, iter_ptr);
+ K k = (owned)curr.key;
+ _delete_helper<K> ((owned)k);
+ if ((flags & Flags.MAP) != 0) {
+ V v = (owned)curr.value;
+ _delete_helper<V> ((owned)v);
+ }
+ void *end = (void *)((char *)data + bs.total_size * real_size);
+ void *next = (void *)((char *)iter_ptr + bs.total_size);
+ real_size--;
+ if (end == next) {
+ return null;
+ }
+ GLib.Memory.move (iter_ptr, next, (char *)end - (char *)next);
+ return iter_ptr;
+ }
+
+ private static inline void _rehash_array<K, V> (Flags flags, ref char *data, ref int dummy_size, ref
int real_size, int new_size, HashDataFunc hash, EqualDataFunc equal, ref void *first, ref void *last) {
+ BucketStructure bs = BucketStructure (flags, true);
+#if ASSERT
+ BucketStructure new_bs = BucketStructure (flags, false);
+ assert (bs.next_offset == -1);
+ assert (new_bs.next_offset != -1);
+#endif
+ char *old_data = data;
+ int old_dummy_size = dummy_size;
+ int old_real_size = real_size;
+ data = GLib.Slice.alloc0 (sizeof(void *) * _get_buckets_no (new_size));
+ first = null;
+ last = null;
+ dummy_size = new_size;
+ real_size = 0;
+ for (int i = 0; i < new_size; i++) {
+ Bucket bucket = Bucket (bs, (char *)old_data + bs.total_size * i);
+#if ASSERT
+ char *data_save = data;
+ int real_size_save = real_size;
+ int dummy_size_save = dummy_size;
+#endif
+ K key = bucket.key;
+ V? value = ((flags & Flags.MAP) != 0) ? bucket.value : null;
+ uint khash = ((flags & Flags.CACHE_HASH) != 0 && (flags &
Flags.CACHE_HASH_ONLY_IN_ARRAY) == 0) ? bucket.hash : hash (key);
+ InsertResult it = _insert_linked<K, V> (flags, ref data, ref dummy_size, ref
real_size, key, value, khash, hash, equal, false, ref first, ref last, false);
+#if ASSERT
+ assert (it == InsertResult.INSERT);
+ assert (data_save == data);
+ assert (real_size_save + 1 == real_size);
+ assert (dummy_size_save == dummy_size);
+#endif
}
+ _cleanup_array<K, V> (flags, old_data, old_dummy_size, old_real_size, true);
}
- private static inline void _allocate (Bucket bucket, ref uint cellar_free, ref uint address_free) {
- assert (bucket.fprev.is_null == (bucket._id == cellar_free || bucket._id == address_free));
- if (!bucket.fnext.is_null) {
- bucket.fnext.fprev = bucket.fprev;
+ private static inline void _cleanup_array<K, V> (Flags flags, void *data, int dummy_size, int
real_size, bool skip_destroy = false) {
+ BucketStructure bs = BucketStructure (flags, true);
+ if (!skip_destroy) {
+ for (void *iter_ptr = (void *)data; iter_ptr < (void *)((char *)data + bs.total_size
* real_size); iter_ptr = (void *)((char *)iter_ptr + bs.total_size)) {
+ Bucket curr = Bucket (bs, iter_ptr);
+ K k = (owned)curr.key;
+ _delete_helper<K> ((owned)k);
+ if ((flags & Flags.MAP) != 0) {
+ V v = (owned)curr.value;
+ _delete_helper<V> ((owned)v);
+ }
+ }
}
- if (!bucket.fprev.is_null) {
- bucket.fprev.fnext = bucket.fnext;
- } else if (bucket._id == cellar_free) {
- cellar_free = bucket.fnext._id;
- } else {
- address_free = bucket.fnext._id;
- }
+ GLib.Slice.free (bs.total_size * ARRAY_THRESHOLD, data);
}
- private static inline void _release (Bucket bucket, int dummy_size, ref uint cellar_free, ref uint
address_free) {
- assert (!bucket.present && bucket.next.is_null);
- bucket.fprev_id = LINK_END;
- if (bucket._id < _get_primary_bucket_no (dummy_size)) {
- bucket.fnext_id = address_free;
- address_free = bucket._id;
+ /**********************************************************************
+ * Helpers *
+ **********************************************************************/
+ private static inline void _delete_helper<G> (owned G g) {}
+
+#if DEBUG
+ internal static inline void _dump (Flags flags, char *data, int dummy_size, int real_size, void
*first, void *last) {
+ BucketStructure bs = BucketStructure (flags, dummy_size < ARRAY_THRESHOLD);
+ stderr.printf ("# Dumping hashtable...\n");
+ if (dummy_size >= ARRAY_THRESHOLD) {
+ if ((flags & Flags.LINKED_HASH) != 0) {
+ stderr.printf ("# First element: %p\n", first);
+ stderr.printf ("# Last element: %p\n", last);
+ }
+ stderr.printf("#
==========================================================================\n");
+ int digits_id = (int)GLib.Math.log10(_get_buckets_no (dummy_size));
+ for (int i = 0; i < _get_buckets_no (dummy_size); i++) {
+ void *iter = *(void **)((char *)data + sizeof (void *) * i);
+ stderr.printf ("# Bucket chain %*d:\n", digits_id, i);
+ while (iter != null) {
+ Bucket curr = Bucket (bs, iter);
+ stderr.printf ("# Bucket %p: key = \"%s\"", iter,
(string)curr.key);
+ if ((flags & Flags.MAP) != 0) {
+ stderr.printf(", value = \"%s\"\n", (string)curr.value);
+ }
+ if ((flags & Flags.LINKED_HASH) != 0) {
+ stderr.printf (", prev = %p, next = %p\n", *curr.iprev_ptr,
*curr.inext_ptr);
+ }
+ stderr.printf ("\n");
+ iter = *curr.next_ptr;
+ }
+ }
+ stderr.printf("#
==========================================================================\n");
} else {
- bucket.fnext_id = cellar_free;
- cellar_free = bucket._id;
+ stderr.printf("#
==========================================================================\n");
+ int digits_id = (int)GLib.Math.log10(ARRAY_THRESHOLD);
+ for (int i = 0; i < real_size; i++) {
+ Bucket b = Bucket (bs, (char *)data + i * bs.total_size);
+ stderr.printf ("# %*d Bucket: key = \"%s\"%s\n", digits_id, i,
(string)b.key, (flags & Flags.MAP) != 0 ? ", value = \"%s\"".printf((string)b.value) : "");
+ }
+ stderr.printf("#
==========================================================================\n");
}
}
+#endif
private static inline uint _folded_hash (uint hash, int size) {
return hash;
}
- private static inline int _get_primary_bucket_no (int dummy_size) {
- return 1 << (int)GLib.Math.ceil(GLib.Math.log2((dummy_size/ALPHA)*BETA));
- }
-
private static inline int _get_buckets_no (int dummy_size) {
- if (dummy_size < ARRAY_THRESHOLD) {
- return ARRAY_THRESHOLD;
- }
- return (int)GLib.Math.ceil(_get_primary_bucket_no (dummy_size)/BETA);
+ int i = (int)GLib.SpacedPrimes.closest (dummy_size);
+ return i < 11 ? 11 : i;
+ //return (int)(_get_primary_bucket_no (dummy_size)/BETA) + 1;
}
private struct BucketStructure {
- internal inline BucketStructure (Flags flags, int size) {
+ internal inline BucketStructure (Flags flags, bool array) {
total_size = 0;
key_offset = total_size;
total_size += (int8)sizeof(void *);
@@ -510,32 +673,27 @@ class Gee.Hash {
} else {
value_offset = -1;
}
- if ((flags & Flags.CACHE_HASH) != 0 && ((flags & Flags.CACHE_HASH_ONLY_IN_ARRAY) == 0
|| size < ARRAY_THRESHOLD)) {
- hash_offset = total_size;
- total_size += (int8)sizeof(int);
- } else {
- hash_offset = -1;
- }
- if ((flags & Flags.LINKED_HASH) != 0 && size >= ARRAY_THRESHOLD) {
+ if ((flags & Flags.LINKED_HASH) != 0 && !array) {
iprev_offset = total_size;
- total_size += (int8)sizeof(int);
+ total_size += (int8)sizeof(void *);
inext_offset = total_size;
- total_size += (int8)sizeof(int);
+ total_size += (int8)sizeof(void *);
} else {
iprev_offset = -1;
inext_offset = -1;
}
- if (size >= ARRAY_THRESHOLD) {
- fprev_offset = 0;
- fnext_offset = (int8)sizeof(int);
- total_size = int8.max (total_size, 2*(int8)sizeof(int));
+ if (!array) {
next_offset = total_size;
- total_size += (int8)sizeof(int);
+ total_size += (int8)sizeof(void *);
} else {
- fprev_offset = -1;
- fnext_offset = -1;
next_offset = -1;
}
+ if ((flags & Flags.CACHE_HASH) != 0 && ((flags & Flags.CACHE_HASH_ONLY_IN_ARRAY) == 0
|| array)) {
+ hash_offset = total_size;
+ total_size += (int8)sizeof(int);
+ } else {
+ hash_offset = -1;
+ }
int8 alignment = (int8)ulong.max (sizeof(int), sizeof(void *)); // FIXME: use
configure.ac
total_size = ((total_size - 1)/alignment + 1)*alignment;
}
@@ -545,44 +703,25 @@ class Gee.Hash {
int8 hash_offset;
int8 iprev_offset;
int8 inext_offset;
- int8 fprev_offset;
- int8 fnext_offset;
int8 next_offset;
int8 total_size;
}
private struct Bucket {
- internal inline Bucket (BucketStructure bs, char *data, uint i) {
- _bs = bs;
- _data = data;
- _id = i;
- }
-
- internal inline Bucket.null (BucketStructure bs, char *data) {
+ internal inline Bucket (BucketStructure bs, void *data) {
_bs = bs;
_data = data;
- _id = LINK_END;
}
- internal void *key {
+ internal inline void *key {
get {
-#if ASSERT
- assert (_data != null);
- assert (_id != LINK_END);
- assert (_bs.key_offset != -1);
-#endif
- void *value = null;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.key_offset,
sizeof (void *));
- return value;
+ return *(void **)((char *)_data + _bs.key_offset);
}
set {
#if ASSERT
assert (_data != null);
- assert (_id != LINK_END);
#endif
- if (_bs.key_offset != -1) {
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.key_offset,
&value, sizeof (void *));
- }
+ *(void **)((char *)_data + _bs.key_offset) = value;
}
}
@@ -590,20 +729,16 @@ class Gee.Hash {
get {
#if ASSERT
assert (_data != null);
- assert (_id != LINK_END);
assert (_bs.value_offset != -1);
#endif
- void *value = null;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.value_offset,
sizeof (void *));
- return value;
+ return *(void **)((char *)_data + _bs.value_offset);
}
set {
#if ASSERT
assert (_data != null);
assert (_id != LINK_END);
#endif
- if (_bs.value_offset != -1)
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.value_offset,
&value, sizeof (void *));
+ *(void **)((char *)_data + _bs.value_offset) = value;
}
}
@@ -611,207 +746,92 @@ class Gee.Hash {
get {
#if ASSERT
assert (_data != null);
- assert (_id != LINK_END);
assert (_bs.hash_offset != -1);
#endif
- uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.hash_offset,
sizeof (uint));
- return value;
+ return *(uint *)((char *)_data + _bs.hash_offset);
}
set {
+#if ASSERT
assert (_data != null);
- assert (_id != LINK_END);
- if (_bs.hash_offset != -1)
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.hash_offset,
&value, sizeof (uint));
+#endif
+ *(uint *)((char *)_data + _bs.hash_offset) = value;
}
}
internal Bucket iprev {
get {
- return Bucket (_bs, _data, iprev_id);
+ return Bucket (_bs, *iprev_ptr);
}
set {
- assert (value._data == _data);
- iprev_id = value._id;
+#if ASSERT
+ assert (_data != null || _data == value._data);
+#endif
+ *iprev_ptr = value._data;
}
}
- internal uint iprev_id {
+ internal void **iprev_ptr {
get {
#if ASSERT
assert (_data != null);
- assert (_id != LINK_END);
assert (_bs.iprev_offset != -1);
#endif
- uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.iprev_offset,
sizeof (uint));
- return value;
- }
- set {
- assert (_data != null);
- assert (_id != LINK_END);
- if (_bs.iprev_offset != -1)
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.iprev_offset,
&value, sizeof (uint));
+ return (void **)((char *)_data + _bs.iprev_offset);
}
}
internal Bucket inext {
get {
- return Bucket (_bs, _data, inext_id);
+ return Bucket (_bs, *inext_ptr);
}
set {
- assert (value._data == _data);
- inext_id = value._id;
- }
- }
-
- internal uint inext_id {
- get {
#if ASSERT
- assert (_data != null);
- assert (_id != LINK_END);
- assert (_bs.inext_offset != -1);
+ assert (_data != null || _data == value._data);
#endif
- uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.inext_offset,
sizeof (uint));
- return value;
- }
- set {
- if (_bs.inext_offset != -1)
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.inext_offset,
&value, sizeof (uint));
- }
- }
-
- internal Bucket fprev {
- get {
- return Bucket (_bs, _data, fprev_id);
- }
- set {
- assert (value._data == _data);
- fprev_id = value._id;
+ *inext_ptr = value._data;
}
}
- internal uint fprev_id {
+ internal void **inext_ptr {
get {
#if ASSERT
assert (_data != null);
- assert (_id != LINK_END);
- assert (_bs.fprev_offset != -1);
+ assert (_bs.inext_offset != -1);
#endif
- uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.fprev_offset,
sizeof (uint));
- return value;
- }
- set {
- if (_bs.fprev_offset != -1)
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.fprev_offset,
&value, sizeof (uint));
+ return (void **)((char *)_data + _bs.inext_offset);
}
}
- internal Bucket fnext {
+ internal Bucket next {
get {
- return Bucket (_bs, _data, fnext_id);
+ return Bucket (_bs, *next_ptr);
}
set {
- assert (value._data == _data);
- fnext_id = value._id;
- }
- }
-
- internal uint fnext_id {
- get {
#if ASSERT
- assert (_data != null);
- assert (_id != LINK_END);
- assert (_bs.fnext_offset != -1);
+ assert (_data != null || _data == value._data);
#endif
- uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.fnext_offset,
sizeof (uint));
- return value;
- }
- set {
- if (_bs.fnext_offset != -1)
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.fnext_offset,
&value, sizeof (uint));
- }
- }
-
- internal Bucket next {
- get {
- return Bucket (_bs, _data, next_id);
- }
- set {
- assert (value._data == _data);
- next_id = value._id;
- }
- }
-
- internal uint next_id {
- get {
- assert (_data != null);
- assert (_id != LINK_END);
- assert (_bs.next_offset != -1);
- uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.next_offset,
sizeof (uint));
- return value >> 1;
- }
- set {
- if (_bs.next_offset != -1) {
- value = (value << 1) | present;
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.next_offset,
&value, sizeof (uint));
- }
+ *next_ptr = value._data;
}
}
- internal bool present {
+ internal void **next_ptr {
get {
#if ASSERT
assert (_data != null);
- assert (_id != LINK_END);
assert (_bs.next_offset != -1);
#endif
- uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.next_offset,
sizeof (uint));
- return 0 != (value & 1);
- }
- set {
-#if ASSERT
- assert (_data != null);
- assert (_id != LINK_END);
-#endif
- if (_bs.next_offset != -1) {
- uint next = (next_id << 1) | value;
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.next_offset,
&next, sizeof (uint));
- }
+ return (void **)((char *)_data + _bs.next_offset);
}
}
internal bool is_null {
get {
-#if ASSERT
- assert (_data != null);
-#endif
- return _id == LINK_END;
- }
- }
-
- internal uint _hash (HashDataFunc func) {
- if (_bs.hash_offset == -1) {
- return hash;
- } else {
- return func (key);
- }
- }
-
- internal uint id {
- get {
- return _id;
+ return _data != null;
}
}
- internal char *_data;
+ internal void *_data;
internal BucketStructure _bs;
- internal uint _id;
}
[Flags]
@@ -819,8 +839,7 @@ class Gee.Hash {
MAP,
CACHE_HASH,
CACHE_HASH_ONLY_IN_ARRAY,
- LINKED_HASH,
- FOLD_HASHES
+ LINKED_HASH
}
public enum InsertResult {
@@ -829,9 +848,7 @@ class Gee.Hash {
REPLACE
}
- internal static const int ARRAY_THRESHOLD = 9;
- private static const double ALPHA = 0.7;
- private static const double BETA = 0.86;
- private static const uint LINK_END = 0x7fffffff; //uint.MAX >> 1;
+ internal static const int ARRAY_THRESHOLD = (int)0x80000000; //int.MIN;
+ private static const double ALPHA = 0.9;
}
diff --git a/gee/hashset.vala b/gee/hashset.vala
index 1498823..9f24023 100644
--- a/gee/hashset.vala
+++ b/gee/hashset.vala
@@ -68,8 +68,6 @@ public class Gee.HashSet<G> : AbstractSet<G> {
private int _dummy_size;
private int _real_size;
private char *_data;
- private uint _cellar_free;
- private uint _address_free;
// concurrent modification protection
private int _stamp = 0;
@@ -107,7 +105,7 @@ public class Gee.HashSet<G> : AbstractSet<G> {
* { inheritDoc}
*/
public override bool contains (G key) {
- return Hash.lookup (Hash.Flags.CACHE_HASH, _data, _dummy_size, _real_size, key, hash_func,
equal_func);
+ return Hash.lookup (Hash.Flags.CACHE_HASH, _data, _dummy_size, _real_size, key, hash_func,
equal_func, null);
}
/**
@@ -121,11 +119,8 @@ public class Gee.HashSet<G> : AbstractSet<G> {
* { inheritDoc}
*/
public override bool add (G key) {
- uint first = 0, last = 0;
- if (_dummy_size != _real_size) {
- Hash.rehash (Hash.Flags.CACHE_HASH, ref _data, ref _dummy_size, ref _real_size,
_real_size, hash_func, equal_func, ref first, ref last, ref _cellar_free, ref _address_free);
- }
- Hash.InsertResult ir = Hash.insert<G, void *> (Hash.Flags.CACHE_HASH, ref _data, ref
_dummy_size, ref _real_size, key, null, hash_func, equal_func, false, ref first, ref last, ref _cellar_free,
ref _address_free);
+ void *first = null, last = null;
+ Hash.InsertResult ir = Hash.insert<G, void *> (Hash.Flags.CACHE_HASH, ref _data, ref
_dummy_size, ref _real_size, key, null, hash_func, equal_func, false, ref first, ref last);
_stamp++;
switch (ir) {
case Hash.InsertResult.FAIL:
@@ -141,11 +136,8 @@ public class Gee.HashSet<G> : AbstractSet<G> {
* { inheritDoc}
*/
public override bool remove (G key) {
- uint first = 0, last = 0;
- if (_dummy_size != _real_size) {
- Hash.rehash (Hash.Flags.CACHE_HASH, ref _data, ref _dummy_size, ref _real_size,
_real_size, hash_func, equal_func, ref first, ref last, ref _cellar_free, ref _address_free);
- }
- bool result = Hash.delete<G, void *> (Hash.Flags.CACHE_HASH, ref _data, ref _dummy_size, ref
_real_size, key, null, hash_func, equal_func, ref first, ref last, ref _cellar_free, ref _address_free);
+ void *first = null, last = null;
+ bool result = Hash.delete<G, void *> (Hash.Flags.CACHE_HASH, ref _data, ref _dummy_size, ref
_real_size, key, null, hash_func, equal_func, ref first, ref last);
_stamp++;
return result;
}
@@ -167,7 +159,8 @@ public class Gee.HashSet<G> : AbstractSet<G> {
private class Iterator<G> : Object, Traversable<G>, Gee.Iterator<G> {
private HashSet<G> _set;
- private int _index = -1;
+ private void *_iter_base = null;
+ private void *_iter_ptr = null;
private bool _removed = false;
private int _stamp;
@@ -179,49 +172,49 @@ public class Gee.HashSet<G> : AbstractSet<G> {
public bool next () {
assert (_set._stamp == _stamp);
if (_removed) {
- if (_index != -1)
+ if (_iter_ptr != null)
_removed = false;
- return _index != -1;
- } else if (_index == -1) {
- _index = Hash.get_first (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size,
_set._real_size, 0);
- return _index != -1;
+ return _iter_ptr != null;
+ } else if (_iter_ptr == null) {
+ _iter_ptr = Hash.get_first (Hash.Flags.CACHE_HASH, _set._data,
_set._dummy_size, _set._real_size, null, out _iter_base);
+ return _iter_ptr != null;
} else {
- int new_index = Hash.get_next (Hash.Flags.CACHE_HASH, _set._data,
_set._dummy_size, _set._real_size, _index);
- if (new_index != -1) {
- _index = new_index;
+ void *iter_base = _iter_base;
+ void *iter_ptr = _iter_ptr;
+ Hash.get_next (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size,
_set._real_size, ref iter_base, ref iter_ptr);
+ if (iter_ptr != null) {
+ _iter_base = iter_base;
+ _iter_ptr = iter_ptr;
+ return true;
+ } else {
+ return false;
}
- return new_index != -1;
}
}
public bool has_next () {
assert (_set._stamp == _stamp);
- int new_index;
- if (_removed) {
- new_index = _index;
- } else if (_index == -1) {
- new_index = Hash.get_first (Hash.Flags.CACHE_HASH, _set._data,
_set._dummy_size, _set._real_size, 0);
- } else {
- new_index = Hash.get_next (Hash.Flags.CACHE_HASH, _set._data,
_set._dummy_size, _set._real_size, _index);
+ void *iter_ptr = _iter_ptr;
+ if (!_removed) {
+ if (_iter_ptr == null) {
+ iter_ptr = Hash.get_first (Hash.Flags.CACHE_HASH, _set._data,
_set._dummy_size, _set._real_size, null, null);
+ } else {
+ void *iter_base = _iter_base;
+ Hash.get_next (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size,
_set._real_size, ref iter_base, ref iter_ptr);
+ }
}
- return new_index != -1;
+ return iter_ptr != null;
}
public new G get () {
assert (valid);
- return Hash.get_key<G> (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size, _index);
+ return Hash.get_key<G> (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size,
_iter_ptr);
}
public void remove () {
assert (valid);
- uint first = 0, last = 0;
- unowned G element = Hash.get_key<G> (Hash.Flags.CACHE_HASH, _set._data,
_set._dummy_size, _index);
- if (_set._dummy_size >= Hash.ARRAY_THRESHOLD)
- _index = Hash.get_next (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size,
_set._real_size, _index);
- else if (_index == _set._real_size - 1)
- _index = -1;
- bool res = Hash.delete<G, void *> (Hash.Flags.CACHE_HASH, ref _set._data, ref
_set._dummy_size, ref _set._real_size, element, null, _set.hash_func, _set.equal_func, ref first, ref last,
ref _set._cellar_free, ref _set._address_free, false);
- assert (res);
+ void *first = null, last = null;
+ _iter_ptr = Hash.delete_iter<G, void *> (Hash.Flags.CACHE_HASH, ref _set._data, ref
_set._dummy_size, ref _set._real_size, ref _iter_base, _iter_ptr, null, _set._hash_func, _set._equal_func,
ref first, ref last);
_set._stamp = ++_stamp;
_removed = true;
}
@@ -235,35 +228,37 @@ public class Gee.HashSet<G> : AbstractSet<G> {
public bool valid {
get {
assert (_set._stamp == _stamp);
- return _index != -1 && !_removed;
+ return _iter_ptr != null && !_removed;
}
}
public bool foreach (ForallFunc<G> f) {
assert (_set._stamp == _stamp);
- if (!_removed && _index != -1) {
- if (!f (Hash.get_key<G> (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size,
_index))) {
+ if (!_removed && _iter_ptr != null) {
+ if (!f (Hash.get_key<G> (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size,
_iter_ptr))) {
return false;
}
}
- if (_removed && _index == -1) {
+ if (_removed && _iter_ptr == null) {
return true;
}
if (_removed) {
_removed = false;
}
- int new_index;
- if (_index == -1) {
- new_index = Hash.get_first (Hash.Flags.CACHE_HASH, _set._data,
_set._dummy_size, _set._real_size, 0);
+ void *iter_ptr = _iter_ptr;
+ void *iter_base = _iter_base;
+ if (_iter_ptr == null) {
+ iter_ptr = Hash.get_first (Hash.Flags.CACHE_HASH, _set._data,
_set._dummy_size, _set._real_size, null, out iter_base);
} else {
- new_index = Hash.get_next (Hash.Flags.CACHE_HASH, _set._data,
_set._dummy_size, _set._dummy_size, _index);
+ Hash.get_next (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size,
_set._real_size, ref iter_base, ref iter_ptr);
}
- while (new_index != -1) {
- _index = new_index;
- if (!f (Hash.get_key<G> (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size,
_index))) {
+ while (iter_ptr != null) {
+ _iter_ptr = iter_ptr;
+ _iter_base = iter_base;
+ if (!f (Hash.get_key<G> (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size,
_iter_ptr))) {
return false;
}
- new_index = Hash.get_next (Hash.Flags.CACHE_HASH, _set._data,
_set._dummy_size, _set._dummy_size, _index);
+ Hash.get_next (Hash.Flags.CACHE_HASH, _set._data, _set._dummy_size,
_set._real_size, ref iter_base, ref iter_ptr);
}
return true;
}
diff --git a/tests/testdata.vala b/tests/testdata.vala
index 5f00c97..ee93afe 100644
--- a/tests/testdata.vala
+++ b/tests/testdata.vala
@@ -26,7 +26,7 @@ public class TestData {
private static string?[] thousands = {null, "thousand", "million", "billion", "trillion"};
private static uint data_size () {
- return Test.quick() ? 128 : 1024;
+ return 1024; //Test.quick() ? 128 : 1024;
}
private static uint DATA_SIZE = data_size ();
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
