[libgee/coalesed-hash: 3/6] Temp
- From: Maciej Marcin Piechotka <mpiechotka src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [libgee/coalesed-hash: 3/6] Temp
- Date: Mon, 4 Mar 2013 17:09:01 +0000 (UTC)
commit ae0cf4b77c7d93a30a643c48d4a882cfa13ca0a8
Author: Maciej Piechotka <uzytkownik2 gmail com>
Date: Thu Jan 3 22:59:17 2013 +0100
Temp
gee/hash.vala | 852 ++++++++++++++++++++++++++++++++++-----------------------
1 files changed, 503 insertions(+), 349 deletions(-)
---
diff --git a/gee/hash.vala b/gee/hash.vala
index 48e2784..27997c9 100644
--- a/gee/hash.vala
+++ b/gee/hash.vala
@@ -19,8 +19,8 @@
* Author:
* Maciej Piechotka <uzytkownik2 gmail com>
*/
-[SimpleType]
-class Gee.Hash {
+[Compact]
+internal class Gee.Hash {
/*
* This code implements generalized coalesed hash implementation.
* For less then ARRAY_THRESHOLD it is just an array.
@@ -48,16 +48,16 @@ class Gee.Hash {
* 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);
+ data = GLib.Slice.alloc (_get_buckets_no (0) * BucketStructure.total_size (flags, 0));
}
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)) {
+ for (uint _curr = _get_first (flags, data, dummy_size, real_size, first); _curr != LINK_END;
_curr = _get_next (flags, data, dummy_size, real_size, _curr)) {
+ Bucket curr = Bucket (flags, dummy_size, data, _curr);
K key = (owned)curr.key;
K key2 = (owned)key;
key = (owned)key2;
- if ((flags & Flags.MAP) != 0) {
+ if (BucketStructure.value_present (flags, dummy_size)) {
V val = (owned)curr.value;
V val2 = (owned)val;
val = (owned)val2;
@@ -65,53 +65,42 @@ class Gee.Hash {
}
}
- 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;
- } else {
- return false;
- }
+ internal static inline bool lookup (Flags flags, char *data, int dummy_size, int real_size, void
*key, HashDataFunc hash, EqualDataFunc equal, out int id = null) {
+ uint _id = _lookup (flags, data, dummy_size, real_size, key, hash (key), equal);
+ id = _id != LINK_END ? id : -1;
+ return id != -1;
}
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;
+ _rehash (flags, ref data, ref dummy_size, ref real_size, new_size, hash, equal, ref first,
ref last, ref cellar_free, ref address_free);
}
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);
+ return _insert<K, V> (flags, 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 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);
+ return _delete<K, V> (flags, 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 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;
+ uint id = _get_first (flags, data, dummy_size, real_size, first);
+ return id != LINK_END ? (int)id : -1;
}
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;
+ uint id = _get_next (flags, data, dummy_size, real_size, curr);
+ return id != LINK_END ? (int)id : -1;
}
internal static inline unowned K get_key<K> (Flags flags, char *data, int size, int curr) {
- return Bucket (BucketStructure (flags, size), data, curr).key;
+ return Bucket (flags, size, data, curr).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 (BucketStructure.next_present (flags, dummy_size)) {
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)");
@@ -121,13 +110,13 @@ class Gee.Hash {
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++) {
- 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);
+ Bucket b = Bucket (flags, dummy_size, data, i);
+ if (b.next_id == LINK_END && !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);
+ 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_id,
digits_id, b.inext_id) : "", digits_id, b.next_id != LINK_END ? b.next_id : -1);
}
if (i + 1 == _get_primary_bucket_no (dummy_size)) {
stderr.printf("#
--------------------------------------------------------------------------\n");
@@ -138,7 +127,7 @@ class Gee.Hash {
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);
+ Bucket b = Bucket (flags, dummy_size, 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");
@@ -150,75 +139,86 @@ class Gee.Hash {
}
#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) {
+ private static inline uint _lookup (Flags flags, char *data, int dummy_size, int real_size, void
*key, uint hash, EqualDataFunc equal, out uint insert_prev = null, out uint delete_prev = null, out uint
first_deleted = null) {
+ insert_prev = LINK_END;
+ delete_prev = LINK_END;
+ first_deleted = LINK_END;
+ if (BucketStructure.next_present (flags, dummy_size)) {
+ uint _curr = _folded_hash (hash, dummy_size) % _get_primary_bucket_no (dummy_size);
+ while (_curr != LINK_END) {
+#if DEBUG
+ stderr.printf("Lookup considering %u\n", _curr);
+#endif
+ Bucket curr = Bucket (flags, dummy_size, data, _curr);
if (curr.present) {
- if ((bs.hash_offset == -1 || curr.hash == hash) && equal (curr.key,
key)) {
- return curr;
+ if ((!BucketStructure.hash_present (flags, dummy_size) || curr.hash
== hash) && equal (curr.key, key)) {
+ break;
}
- } else if (first_deleted.is_null) {
- first_deleted = curr;
+ } else if (first_deleted == LINK_END) {
+ first_deleted = curr.id;
}
- if (insert_prev.is_null || curr.id >= _get_primary_bucket_no (dummy_size)) {
- insert_prev = curr;
+ if (insert_prev == LINK_END || curr.id >= _get_primary_bucket_no
(dummy_size)) {
+ insert_prev = curr.id;
}
- assert (curr.id != curr.next.id);
- delete_prev = curr;
- curr = curr.next;
+ delete_prev = curr.id;
+ _curr = curr.next_id;
}
- return curr;
+#if DEBUG
+ stderr.printf("Lookup found %u\n", _curr);
+#endif
+ 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 (flags, dummy_size, data, i);
+ if ((!BucketStructure.hash_present (flags, dummy_size) || curr.hash == hash)
&& equal (curr.key, key)) {
+ return i;
}
}
- return Bucket.null (bs, data);
+ return LINK_END;
}
}
- 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);
+ private static inline uint _get_first (Flags flags, char *data, int dummy_size, int real_size, uint
first) {
+ if (BucketStructure.i_present (flags, dummy_size)) {
+ return first;
} else {
- return _get_next (Bucket (bs, data, -1), dummy_size, real_size);
+ return _get_next (flags, data, dummy_size, real_size, -1);
}
}
- 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 uint _get_next (Flags flags, char *data, int dummy_size, int real_size, uint
curr) {
+ if (BucketStructure.i_present (flags, dummy_size)) {
+ return Bucket (flags, dummy_size, data, curr).inext_id;
+ } else if (BucketStructure.next_present (flags, dummy_size)) {
+ for (uint _i = curr + 1; _i < _get_buckets_no(dummy_size); _i++) {
+ Bucket i = Bucket (flags, dummy_size, data, _i);
+ if (i.present) {
+ return _i;
}
}
- return Bucket.null (curr._bs, curr._data);
+ return LINK_END;
} else {
- return (curr._id + 1 < real_size) ? Bucket (curr._bs, curr._data, curr._id + 1):
Bucket.null (curr._bs, curr._data);
+ return (curr + 1 < real_size) ? curr + 1 : LINK_END;
}
}
- 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) {
+ private static inline InsertResult _insert<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 uint first, ref uint last, ref uint cellar_free, ref uint address_free, bool allow_rehash = true) {
+#if DEBUG
+ stderr.printf ("Before inserting %s\n", (string)key);
+ dump (flags, data, dummy_size, real_size, first, last, cellar_free, address_free);
+#endif
+ if (BucketStructure.next_present (flags, dummy_size)) {
// 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) {
+ uint _first_deleted;
+ uint _prev;
+ uint _curr = _lookup (flags, data, dummy_size, real_size, key, khash, equal, out
_prev, null, out _first_deleted);
+ if (_curr != LINK_END) {
if (replace) {
+ Bucket curr = Bucket (flags, dummy_size, data, _curr);
K k = (owned)curr.key;
k = key;
curr.key = (owned)k;
- if (bs.value_offset != -1) {
+ if (BucketStructure.value_present (flags, dummy_size)) {
V v = (owned)curr.value;
v = value;
curr.value = (owned)v;
@@ -229,258 +229,326 @@ class Gee.Hash {
}
}
// 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 {
- }
+ if (_first_deleted != LINK_END) {
+ _curr = _first_deleted;
+#if DEBUG
+ stderr.printf ("Insert allocating %u\n", _curr);
+#endif
+ _allocate (flags, data, dummy_size, _curr, ref cellar_free, ref address_free,
true);
} else {
- curr = _allocate_any (bs, data, ref cellar_free, ref address_free);
- if (GLib.unlikely(curr.is_null)) {
+ _curr = _allocate_any (flags, data, dummy_size, ref cellar_free, ref
address_free);
+#if ASSERT
+ assert (_curr != LINK_END || allow_rehash);
+#endif
+#if DEBUG
+ stderr.printf ("Insert allocating any -> %u\n", _curr);
+#endif
+ if (GLib.unlikely(_curr == LINK_END && allow_rehash)) {
// 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);
+ _rehash (flags, ref data, ref dummy_size, ref real_size, real_size +
1, hash, equal, ref first, ref last, ref cellar_free, ref address_free, true);
+ _curr = _lookup (flags, data, dummy_size, real_size, key, khash,
equal, out _prev);
+ assert (_curr == LINK_END);
+ _curr = _allocate_any (flags, data, dummy_size, ref cellar_free, ref
address_free);
+ assert (_curr != LINK_END);
allow_rehash = false;
}
- if (!prev.is_null) {
- curr.next = prev.next;
- prev.next = curr;
+#if DEBUG
+ stderr.printf ("Insert linking with %u\n", _prev);
+#endif
+ if (_prev != LINK_END) {
+ Bucket curr = Bucket (flags, dummy_size, data, _curr);
+ Bucket prev = Bucket (flags, dummy_size, data, _prev);
+ curr.next_id = prev.next_id;
+ prev.next_id = _curr;
} else {
- curr.next = Bucket.null (bs, data);
+ Bucket curr = Bucket (flags, dummy_size, data, _curr);
+ curr.next_id = LINK_END;
}
}
// STEP 3: Insert bucket
+ Bucket curr = Bucket (flags, dummy_size, data, _curr);
curr.present = true;
{
K k = key;
curr.key = (owned)k;
}
- {
+ if (BucketStructure.value_present (flags, dummy_size)) {
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 (BucketStructure.hash_present (flags, dummy_size)) {
+ curr.hash = khash;
+ }
+ if (BucketStructure.i_present (flags, dummy_size)) {
+ if (last == LINK_END) {
+ first = curr.id;
+ last = curr.id;
+ curr.iprev_id = LINK_END;
+ curr.inext_id = LINK_END;
+ } else {
+ Bucket _last = Bucket (flags, dummy_size, data, last);
+ _last.inext_id = _curr;
+ curr.inext_id = LINK_END;
+ curr.iprev_id = last;
+ last = curr.id;
+ }
}
+ real_size++;
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++;
+ _rehash (flags, ref data, ref dummy_size, ref real_size, real_size, hash,
equal, ref first, ref last, ref cellar_free, ref address_free);
}
+#if DEBUG
+ stderr.printf ("After inserting %s\n", (string)key);
+ dump (flags, data, dummy_size, real_size, first, last, cellar_free, address_free);
+#endif
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;
+ uint _curr = _lookup (flags, data, dummy_size, real_size, key, khash, equal);
+ if (_curr != LINK_END) {
+ if (replace) {
+ Bucket curr = Bucket (flags, dummy_size, data, _curr);
+ K k = (owned)curr.key;
+ k = key;
+ curr.key = (owned)k;
+ if (BucketStructure.value_present (flags, dummy_size)) {
+ 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);
+ Bucket curr = Bucket (flags, dummy_size, data, real_size);
{
K k = key;
curr.key = (owned)k;
}
- {
+ if (BucketStructure.value_present (flags, dummy_size)) {
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 (BucketStructure.hash_present (flags, dummy_size)) {
+ curr.hash = khash;
}
+ real_size++;
+ if (allow_rehash) {
+ _rehash (flags, ref data, ref dummy_size, ref real_size, real_size, hash,
equal, ref first, ref last, ref cellar_free, ref address_free);
+ }
+#if DEBUG
+ stderr.printf ("After inserting %s\n", (string)key);
+ dump (flags, data, dummy_size, real_size, first, last, cellar_free, address_free);
+#endif
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<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 uint first, ref
uint last, ref uint cellar_free, ref uint address_free, bool allow_rehash = true) {
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) {
+ uint _prev;
+ uint _curr = _lookup (flags, data, dummy_size, real_size, key, khash, equal, null, out _prev);
+ if (_curr == LINK_END) {
+ return false;
+ } else {
+ Bucket curr = Bucket (flags, dummy_size, data, _curr);
+ {
K *kp = curr.key;
K k = (owned)kp;
}
- if (bs.value_offset != -1) {
+ if (BucketStructure.value_present (flags, dummy_size)) {
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;
+ if (BucketStructure.i_present (flags, dummy_size)) {
+#if ASSERT
+ assert ((first == curr.id) == (curr.iprev_id == LINK_END));
+ assert ((last == curr.id) == (curr.inext_id == LINK_END));
+#endif
+ if (curr.iprev_id != LINK_END) {
+ Bucket iprev = Bucket (flags, dummy_size, data, curr.iprev_id);
+ iprev.inext_id = curr.inext_id;
} else {
- first = curr.inext._id;
+ first = curr.inext_id;
}
- if (!curr.iprev.is_null) {
- curr.inext.iprev = curr.iprev;
+ if (curr.inext_id != LINK_END) {
+ Bucket inext = Bucket (flags, dummy_size, data, curr.inext_id);
+ inext.iprev_id = curr.iprev_id;
} else {
last = curr.iprev_id;
}
}
- if (bs.next_offset != -1) {
- if (prev.is_null) {
+ if (BucketStructure.next_present (flags, dummy_size)) {
+ if (_prev == LINK_END) {
// CASE 1: head of chain
curr.present = false;
- if (curr.next.is_null) {
+ if (curr.next_id == LINK_END) {
_release (curr, dummy_size, ref cellar_free, ref
address_free);
}
} else if (curr._id >= _get_primary_bucket_no (dummy_size)) {
+ Bucket prev = Bucket (flags, dummy_size, data, _prev);
// CASE 2: in cellar region
- prev.next = curr.next;
+ prev.next_id = curr.next_id;
curr.present = false;
- curr.next = Bucket.null (bs, data);
+ curr.next_id = LINK_END;
_release (curr, dummy_size, ref cellar_free, ref address_free);
} else {
+ Bucket prev = Bucket (flags, dummy_size, data, _prev);
// 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;
+ uint _j = curr.next_id;
+ prev.next_id = LINK_END;
+ curr.next_id = LINK_END;
+ while (_j != LINK_END) {
+ Bucket j = Bucket (flags, dummy_size, data, _j);
+ uint _k = j._hash (hash) % _get_primary_bucket_no
(dummy_size);
+ while (true) {
+ Bucket k = Bucket (flags, dummy_size, data, _k);
+ if (!(k.next_id != LINK_END && k.next_id >=
_get_primary_bucket_no (dummy_size))) {
+ break;
+ }
+ _k = k.next_id;
}
- Bucket nj = j.next;
- j.next = k.next;
- k.next = j;
- j = nj;
+ Bucket k = Bucket (flags, dummy_size, data, _k);
+ uint _nj = j.next_id;
+ j.next_id = k.next_id;
+ k.next_id = _j;
+ _j = _nj;
}
- if (curr.next.is_null) {
+ if (curr.next_id == LINK_END) {
_release (curr, dummy_size, ref cellar_free, ref
address_free);
}
- if (!prev.present && prev.next.is_null) {
+ if (!prev.present && prev.next_id == LINK_END) {
_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--;
- }
- return true;
- } else {
- return false;
}
+ // Technically this is followup of previous if's but it needed to be separated for correct
blocking of restrict
+ if (!BucketStructure.next_present (flags, dummy_size)) {
+ uint ts = BucketStructure.total_size (flags, dummy_size);
+ GLib.Memory.move (data + ts * _curr, data + ts * (_curr + 1), ts * (real_size - _curr
- 1));
+ }
+ real_size--;
+ if (allow_rehash) {
+ _rehash (flags, ref data, ref dummy_size, ref real_size, real_size, hash, equal, ref
first, ref last, ref cellar_free, ref address_free);
+ }
+ return true;
}
- 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))
+ private static inline void _rehash (Flags flags, ref char *data, ref int old_dummy_size, ref 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)) {
+ old_dummy_size = new_size;
return;
- char *new_data = GLib.Slice.alloc0 (_get_buckets_no(new_size) * new_bs.total_size);
+ }
+ char *new_data = GLib.Slice.alloc0 (_get_buckets_no(new_size) * BucketStructure.total_size
(flags, new_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;
+ Bucket b = Bucket (flags, new_size, new_data, i);
+ if (BucketStructure.f_present (flags, new_size)) {
+ b.fprev_id = (i == 0 || i == _get_primary_bucket_no (new_size)) ? LINK_END :
i - 1;
+ b.fnext_id = (i == _get_primary_bucket_no (new_size) - 1 || i ==
_get_buckets_no(new_size) - 1) ? LINK_END : i + 1;
+ }
+ if (BucketStructure.next_present (flags, new_size)) {
+ b.present = false;
+ b.next_id = LINK_END;
+ }
}
+#if DEBUG
+ stderr.printf ("<<rehash start>>\n");
+#endif
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)) {
+ for (uint _b = _get_first (flags, data, old_dummy_size, old_real_size, first); _b !=
LINK_END; _b = _get_next (flags, data, old_dummy_size, old_real_size, _b)) {
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);
+ Bucket b = Bucket (flags, old_dummy_size, data, _b);
+ void *key = b.key;
+ void *value = BucketStructure.value_present (flags, old_dummy_size) ? b.value : null;
+ InsertResult ir = _insert<void *, void *> (flags, 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);
+#if ASSERT
assert (ir == InsertResult.INSERT);
assert (new_data == nnew_data);
assert (new_size == nnew_dummy_size);
assert (++new_real_size == nnew_real_size);
+#endif
}
- GLib.Slice.free (_get_buckets_no(old_dummy_size) * old_bs.total_size, data);
+#if DEBUG
+ stderr.printf ("<<rehash end>>\n");
+#endif
+ GLib.Slice.free (_get_buckets_no(old_dummy_size) * BucketStructure.total_size(flags,
old_dummy_size), data);
data = new_data;
+ old_dummy_size = new_size;
}
- private static inline Bucket _allocate_any (BucketStructure bs, char *data, ref uint cellar_free, ref
uint address_free) {
+ private static inline uint _allocate_any (Flags flags, char *data, int size, 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)
+ uint allocated = cellar_free;
+ Bucket bucket = Bucket (flags, size, data, allocated);
+ cellar_free = bucket.fnext_id;
+ if (cellar_free != LINK_END) {
+ Bucket next_free = Bucket (flags, size, data, cellar_free);
next_free.fprev_id = LINK_END;
- return bucket;
+ }
+ return allocated;
} 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)
+ uint allocated = address_free;
+ Bucket bucket = Bucket (flags, size, data, allocated);
+ address_free = bucket.fnext_id;
+ if (address_free != LINK_END) {
+ Bucket next_free = Bucket (flags, size, data, address_free);
next_free.fprev_id = LINK_END;
- return bucket;
+ }
+ return allocated;
} else {
- return Bucket.null (bs, data);
+ return LINK_END;
}
}
- 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 _allocate (Flags flags, char *data, int size, uint _bucket, ref uint
cellar_free, ref uint address_free, bool softfail) {
+ Bucket bucket = Bucket (flags, size, data, _bucket);
+#if ASSERT
+ assert (!bucket.present);
+#endif
+ if (softfail) {
+ if (bucket.next_id != LINK_END) {
+ return;
+ }
+#if ASSERT
+ } else {
+ assert (bucket.next_id != LINK_END);
+#endif
}
- if (!bucket.fprev.is_null) {
- bucket.fprev.fnext = bucket.fnext;
- } else if (bucket._id == cellar_free) {
- cellar_free = bucket.fnext._id;
+#if ASSERT
+ assert ((bucket.fprev_id == LINK_END) == (bucket.id == cellar_free || bucket.id ==
address_free));
+#endif
+ if (bucket.fnext_id != LINK_END) {
+ Bucket fnext = Bucket (flags, size, data, bucket.fnext_id);
+ fnext.fprev_id = bucket.fprev_id;
+ }
+ if (bucket.fprev_id != LINK_END) {
+ Bucket fprev = Bucket (flags, size, data, bucket.fprev_id);
+ fprev.fnext_id = bucket.fnext_id;
+ } else if (bucket.id == cellar_free) {
+ cellar_free = bucket.fnext_id;
} else {
- address_free = bucket.fnext._id;
+ address_free = bucket.fnext_id;
}
}
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);
+#if ASSERT
+ assert (!bucket.present && bucket.next_id == LINK_END);
+#endif
bucket.fprev_id = LINK_END;
- if (bucket._id < _get_primary_bucket_no (dummy_size)) {
+ if (bucket.id < _get_primary_bucket_no (dummy_size)) {
bucket.fnext_id = address_free;
- address_free = bucket._id;
+ address_free = bucket.id;
} else {
bucket.fnext_id = cellar_free;
- cellar_free = bucket._id;
+ cellar_free = bucket.id;
}
}
@@ -500,67 +568,108 @@ class Gee.Hash {
}
private struct BucketStructure {
- internal inline BucketStructure (Flags flags, int size) {
- total_size = 0;
- key_offset = total_size;
- total_size += (int8)sizeof(void *);
- if ((flags & Flags.MAP) != 0) {
- value_offset = total_size;
- total_size += (int8)sizeof(void *);
- } 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) {
- iprev_offset = total_size;
- total_size += (int8)sizeof(int);
- inext_offset = total_size;
- total_size += (int8)sizeof(int);
- } 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));
- next_offset = total_size;
- total_size += (int8)sizeof(int);
- } else {
- fprev_offset = -1;
- fnext_offset = -1;
- next_offset = -1;
- }
- int8 alignment = (int8)ulong.max (sizeof(int), sizeof(void *)); // FIXME: use
configure.ac
- total_size = ((total_size - 1)/alignment + 1)*alignment;
- }
-
- int8 key_offset;
- int8 value_offset;
- int8 hash_offset;
- int8 iprev_offset;
- int8 inext_offset;
- int8 fprev_offset;
- int8 fnext_offset;
- int8 next_offset;
- int8 total_size;
+ public static inline int8 key_offset (Flags flags, int size) {
+ return 0;
+ }
+
+ private static inline int8 key_end (Flags flags, int size) {
+ return key_offset (flags, size) + (int8)sizeof(void *);
+ }
+
+ public static inline bool value_present (Flags flags, int size) {
+ return (flags & Flags.MAP) != 0;
+ }
+
+ public static inline int8 value_offset (Flags flags, int size) {
+ assert (value_present (flags, size));
+ return key_end (flags, size);
+ }
+
+ private static inline int8 value_end (Flags flags, int size) {
+ return key_end (flags, size) + ((flags & Flags.MAP) != 0 ? (int8)sizeof(void *) : 0);
+ }
+
+ public static inline bool hash_present (Flags flags, int size) {
+ return (flags & Flags.CACHE_HASH) != 0 && ((flags & Flags.CACHE_HASH_ONLY_IN_ARRAY)
== 0 || size < ARRAY_THRESHOLD);
+ }
+
+ public static inline int8 hash_offset (Flags flags, int size) {
+ assert (hash_present (flags, size));
+ return value_end (flags, size);
+ }
+
+ private static inline int8 hash_end (Flags flags, int size) {
+ return value_end (flags, size) + (hash_present(flags, size) ? (int8)sizeof(uint) : 0);
+ }
+
+ public static inline bool i_present (Flags flags, int size) {
+ return (flags & Flags.LINKED_HASH) != 0 && size >= ARRAY_THRESHOLD;
+ }
+
+ public static inline int8 iprev_offset (Flags flags, int size) {
+ assert (i_present (flags, size));
+ return hash_end (flags, size);
+ }
+
+ public static inline int8 inext_offset (Flags flags, int size) {
+ assert (i_present (flags, size));
+ return hash_end (flags, size) + (int8)sizeof(uint);
+ }
+
+ private static inline int8 i_end (Flags flags, int size) {
+ return hash_end (flags, size) + (i_present (flags, size) ? 2*(int8)sizeof(uint) : 0);
+ }
+
+ public static inline bool f_present (Flags flags, int size) {
+ return (size >= ARRAY_THRESHOLD);
+ }
+
+ public static inline int8 fprev_offset (Flags flags, int size) {
+ assert (f_present (flags, size));
+ return 0;
+ }
+
+ public static inline int8 fnext_offset (Flags flags, int size) {
+ assert (f_present (flags, size));
+ return (int8)sizeof(uint);
+ }
+
+ private static inline int8 f_end (Flags flags, int size) {
+ return f_present (flags, size) ? 2*(int8)sizeof(uint) : 0;
+ }
+
+ public static inline bool next_present (Flags flags, int size) {
+ return (size >= ARRAY_THRESHOLD);
+ }
+
+ public static inline int8 next_offset (Flags flags, int size) {
+ assert (next_present (flags, size));
+ return int8.max (i_end (flags, size), f_end (flags, size));
+ }
+
+ private static inline int8 next_end (Flags flags, int size) {
+ return int8.max (i_end (flags, size), f_end (flags, size)) + (next_present (flags,
size) ? (int8)sizeof(uint) : 0);
+ }
+
+ public static inline int8 total_size (Flags flags, int size) {
+ return next_end (flags, size);
+ }
+
+ public int _dummy;
}
private struct Bucket {
- internal inline Bucket (BucketStructure bs, char *data, uint i) {
- _bs = bs;
- _data = data;
+ internal inline Bucket (Flags flags, int size, char *data, uint i) {
+ _flags = flags;
+ _size = size;
+ _data = data + BucketStructure.total_size (flags, size) * i;
_id = i;
}
- internal inline Bucket.null (BucketStructure bs, char *data) {
- _bs = bs;
- _data = data;
+ internal inline Bucket.null () {
+ _flags = 0;
+ _size = 0;
+ _data = null;
_id = LINK_END;
}
@@ -569,10 +678,9 @@ class Gee.Hash {
#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 *));
+ GLib.Memory.copy (&value, _data + BucketStructure.key_offset (_flags, _size),
sizeof (void *));
return value;
}
set {
@@ -580,9 +688,7 @@ class Gee.Hash {
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 *));
- }
+ GLib.Memory.copy (_data + BucketStructure.key_offset (_flags, _size), &value,
sizeof (void *));
}
}
@@ -591,19 +697,19 @@ class Gee.Hash {
#if ASSERT
assert (_data != null);
assert (_id != LINK_END);
- assert (_bs.value_offset != -1);
+ assert (BucketStructure.value_present (_flags, _size));
#endif
void *value = null;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.value_offset,
sizeof (void *));
+ GLib.Memory.copy (&value, _data + BucketStructure.value_offset (_flags,
_size), sizeof (void *));
return value;
}
set {
#if ASSERT
assert (_data != null);
assert (_id != LINK_END);
+ assert (BucketStructure.value_present (_flags, _size));
#endif
- if (_bs.value_offset != -1)
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.value_offset,
&value, sizeof (void *));
+ GLib.Memory.copy (_data + BucketStructure.value_offset (_flags, _size),
&value, sizeof (void *));
}
}
@@ -612,56 +718,66 @@ class Gee.Hash {
#if ASSERT
assert (_data != null);
assert (_id != LINK_END);
- assert (_bs.hash_offset != -1);
+ assert (BucketStructure.hash_present (_flags, _size));
#endif
uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.hash_offset,
sizeof (uint));
+ GLib.Memory.copy (&value, _data + BucketStructure.hash_offset (_flags,
_size), sizeof (uint));
return value;
}
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));
+ assert (BucketStructure.hash_present (_flags, _size));
+#endif
+ GLib.Memory.copy (_data + BucketStructure.hash_offset (_flags, _size),
&value, sizeof (uint));
}
}
+#if 0
internal Bucket iprev {
get {
- return Bucket (_bs, _data, iprev_id);
+ return Bucket (_flags, _size, _data, iprev_id);
}
set {
- assert (value._data == _data);
+#if ASSERT
+ assert (value.is_null || value._data == _data);
+ assert (value.is_null || value._flags == _flags);
+ assert (value.is_null || value._size == _size);
+#endif
iprev_id = value._id;
}
}
+ internal Bucket inext {
+ get {
+ return Bucket (_flags, _size, _data, inext_id);
+ }
+ set {
+ assert (value._data == _data);
+ inext_id = value._id;
+ }
+ }
+#endif
+
internal uint iprev_id {
get {
#if ASSERT
assert (_data != null);
assert (_id != LINK_END);
- assert (_bs.iprev_offset != -1);
+ assert (BucketStructure.i_present (_flags, _size));
#endif
uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.iprev_offset,
sizeof (uint));
+ GLib.Memory.copy (&value, _data + BucketStructure.iprev_offset (_flags,
_size), sizeof (uint));
return value;
}
set {
+#if ASSERT
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));
- }
- }
-
- internal Bucket inext {
- get {
- return Bucket (_bs, _data, inext_id);
- }
- set {
- assert (value._data == _data);
- inext_id = value._id;
+ assert (BucketStructure.i_present (_flags, _size));
+#endif
+ GLib.Memory.copy (_data + BucketStructure.iprev_offset (_flags, _size),
&value, sizeof (uint));
}
}
@@ -670,52 +786,70 @@ class Gee.Hash {
#if ASSERT
assert (_data != null);
assert (_id != LINK_END);
- assert (_bs.inext_offset != -1);
+ assert (BucketStructure.i_present (_flags, _size));
#endif
uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.inext_offset,
sizeof (uint));
+ GLib.Memory.copy (&value, _data + BucketStructure.inext_offset (_flags,
_size), sizeof (uint));
return value;
}
set {
- if (_bs.inext_offset != -1)
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.inext_offset,
&value, sizeof (uint));
+#if ASSERT
+ assert (_data != null);
+ assert (_id != LINK_END);
+ assert (BucketStructure.i_present (_flags, _size));
+#endif
+ GLib.Memory.copy (_data + BucketStructure.inext_offset (_flags, _size),
&value, sizeof (uint));
}
}
+#if 0
internal Bucket fprev {
get {
- return Bucket (_bs, _data, fprev_id);
+ return Bucket (_flags, _size, _data, fprev_id);
}
set {
- assert (value._data == _data);
+#if ASSERT
+ assert (value.is_null || value._data == _data);
+ assert (value.is_null || value._flags == _flags);
+ assert (value.is_null || value._size == _size);
+#endif
fprev_id = value._id;
}
}
+ internal Bucket fnext {
+ get {
+ return Bucket (_flags, _size, _data, fnext_id);
+ }
+ set {
+#if ASSERT
+ assert (value.is_null || value._data == _data);
+ assert (value.is_null || value._flags == _flags);
+ assert (value.is_null || value._size == _size);
+#endif
+ fnext_id = value._id;
+ }
+ }
+#endif
+
internal uint fprev_id {
get {
#if ASSERT
assert (_data != null);
assert (_id != LINK_END);
- assert (_bs.fprev_offset != -1);
+ assert (BucketStructure.f_present (_flags, _size));
#endif
uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.fprev_offset,
sizeof (uint));
+ GLib.Memory.copy (&value, _data + BucketStructure.fprev_offset (_flags,
_size), sizeof (uint));
return value;
}
set {
- if (_bs.fprev_offset != -1)
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.fprev_offset,
&value, sizeof (uint));
- }
- }
-
- internal Bucket fnext {
- get {
- return Bucket (_bs, _data, fnext_id);
- }
- set {
- assert (value._data == _data);
- fnext_id = value._id;
+#if ASSERT
+ assert (_data != null);
+ assert (_id != LINK_END);
+ assert (BucketStructure.f_present (_flags, _size));
+#endif
+ GLib.Memory.copy (_data + BucketStructure.fprev_offset (_flags, _size),
&value, sizeof (uint));
}
}
@@ -724,42 +858,57 @@ class Gee.Hash {
#if ASSERT
assert (_data != null);
assert (_id != LINK_END);
- assert (_bs.fnext_offset != -1);
+ assert (BucketStructure.f_present (_flags, _size));
#endif
uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.fnext_offset,
sizeof (uint));
+ GLib.Memory.copy (&value, _data + BucketStructure.fnext_offset (_flags,
_size), sizeof (uint));
return value;
}
set {
- if (_bs.fnext_offset != -1)
- GLib.Memory.copy (_data + _bs.total_size * _id + _bs.fnext_offset,
&value, sizeof (uint));
+#if ASSERT
+ assert (_data != null);
+ assert (_id != LINK_END);
+ assert (BucketStructure.f_present (_flags, _size));
+#endif
+ GLib.Memory.copy (_data + BucketStructure.fnext_offset (_flags, _size),
&value, sizeof (uint));
}
}
+#if 0
internal Bucket next {
get {
- return Bucket (_bs, _data, next_id);
+ return Bucket (_flags, _size, _data, next_id);
}
set {
- assert (value._data == _data);
+#if ASSERT
+ assert (value.is_null || value._data == _data);
+ assert (value.is_null || value._flags == _flags);
+ assert (value.is_null || value._size == _size);
+#endif
next_id = value._id;
}
}
+#endif
internal uint next_id {
get {
+#if ASSERT
assert (_data != null);
assert (_id != LINK_END);
- assert (_bs.next_offset != -1);
+ assert (BucketStructure.next_present (_flags, _size));
+#endif
uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.next_offset,
sizeof (uint));
+ GLib.Memory.copy (&value, _data + BucketStructure.next_offset (_flags,
_size), 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));
- }
+#if ASSERT
+ assert (_data != null);
+ assert (_id != LINK_END);
+ assert (BucketStructure.next_present (_flags, _size));
+#endif
+ value = (value << 1) | present;
+ GLib.Memory.copy (_data + BucketStructure.next_offset (_flags, _size),
&value, sizeof (uint));
}
}
@@ -768,49 +917,54 @@ class Gee.Hash {
#if ASSERT
assert (_data != null);
assert (_id != LINK_END);
- assert (_bs.next_offset != -1);
+ assert (BucketStructure.next_present (_flags, _size));
#endif
uint value = 0;
- GLib.Memory.copy (&value, _data + _bs.total_size * _id + _bs.next_offset,
sizeof (uint));
+ GLib.Memory.copy (&value, _data + BucketStructure.next_offset (_flags,
_size), sizeof (uint));
return 0 != (value & 1);
}
set {
#if ASSERT
assert (_data != null);
assert (_id != LINK_END);
+ assert (BucketStructure.next_present (_flags, _size));
#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));
- }
+ uint next = (next_id << 1) | value;
+ GLib.Memory.copy (_data + BucketStructure.next_offset (_flags, _size), &next,
sizeof (uint));
}
}
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) {
+ if (BucketStructure.hash_present (_flags, _size)) {
return hash;
} else {
return func (key);
}
}
+ internal uint _set_hash (uint hash) {
+ if (BucketStructure.hash_present (_flags, _size)) {
+ this.hash = hash;
+ }
+ return hash;
+ }
+
internal uint id {
get {
return _id;
}
}
+ //[CCode (type = "gchar * restrict")]
internal char *_data;
- internal BucketStructure _bs;
+ internal Flags _flags;
+ internal int _size;
internal uint _id;
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
