summaryrefslogtreecommitdiff
path: root/lib/ntdb/test/helprun-layout.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/ntdb/test/helprun-layout.c')
-rw-r--r--lib/ntdb/test/helprun-layout.c102
1 files changed, 31 insertions, 71 deletions
diff --git a/lib/ntdb/test/helprun-layout.c b/lib/ntdb/test/helprun-layout.c
index 7f1f9f9d8e..fa6fa29fce 100644
--- a/lib/ntdb/test/helprun-layout.c
+++ b/lib/ntdb/test/helprun-layout.c
@@ -94,13 +94,6 @@ static ntdb_len_t data_record_len(struct tle_used *used)
return len;
}
-static ntdb_len_t hashtable_len(struct tle_hashtable *htable)
-{
- return sizeof(struct ntdb_used_record)
- + (sizeof(ntdb_off_t) << NTDB_SUBLEVEL_HASH_BITS)
- + htable->extra;
-}
-
static ntdb_len_t capability_len(struct tle_capability *cap)
{
return sizeof(struct ntdb_capability) + cap->extra;
@@ -128,25 +121,13 @@ static void set_data_record(void *mem, struct ntdb_context *ntdb,
struct ntdb_used_record *u = mem;
set_header(ntdb, u, NTDB_USED_MAGIC, used->key.dsize, used->data.dsize,
- used->key.dsize + used->data.dsize + used->extra,
- ntdb_hash(ntdb, used->key.dptr, used->key.dsize));
+ used->key.dsize + used->data.dsize + used->extra);
memcpy(u + 1, used->key.dptr, used->key.dsize);
memcpy((char *)(u + 1) + used->key.dsize,
used->data.dptr, used->data.dsize);
add_zero_pad(u, used->key.dsize + used->data.dsize, used->extra);
}
-static void set_hashtable(void *mem, struct ntdb_context *ntdb,
- struct tle_hashtable *htable)
-{
- struct ntdb_used_record *u = mem;
- ntdb_len_t len = sizeof(ntdb_off_t) << NTDB_SUBLEVEL_HASH_BITS;
-
- set_header(ntdb, u, NTDB_HTABLE_MAGIC, 0, len, len + htable->extra, 0);
- memset(u + 1, 0, len);
- add_zero_pad(u, len, htable->extra);
-}
-
static void set_capability(void *mem, struct ntdb_context *ntdb,
struct tle_capability *cap, struct ntdb_header *hdr,
ntdb_off_t last_cap)
@@ -156,7 +137,7 @@ static void set_capability(void *mem, struct ntdb_context *ntdb,
c->type = cap->type;
c->next = 0;
- set_header(ntdb, &c->hdr, NTDB_CAP_MAGIC, 0, len, len, 0);
+ set_header(ntdb, &c->hdr, NTDB_CAP_MAGIC, 0, len, len);
/* Append to capability list. */
if (!last_cap) {
@@ -175,7 +156,7 @@ static void set_freetable(void *mem, struct ntdb_context *ntdb,
memset(ftable, 0, sizeof(*ftable));
set_header(ntdb, &ftable->hdr, NTDB_FTABLE_MAGIC, 0,
sizeof(*ftable) - sizeof(ftable->hdr),
- sizeof(*ftable) - sizeof(ftable->hdr), 0);
+ sizeof(*ftable) - sizeof(ftable->hdr));
if (last_ftable) {
ftable = (struct ntdb_freetable *)((char *)hdr + last_ftable);
@@ -197,12 +178,6 @@ static void add_to_freetable(struct ntdb_context *ntdb,
NTDB_LOCK_WAIT, false);
}
-static ntdb_off_t hbucket_off(ntdb_off_t group_start, unsigned ingroup)
-{
- return group_start
- + (ingroup % (1 << NTDB_HASH_GROUP_BITS)) * sizeof(ntdb_off_t);
-}
-
/* Get bits from a value. */
static uint32_t bits(uint64_t val, unsigned start, unsigned num)
{
@@ -210,22 +185,24 @@ static uint32_t bits(uint64_t val, unsigned start, unsigned num)
return (val >> start) & ((1U << num) - 1);
}
-/* We take bits from the top: that way we can lock whole sections of the hash
- * by using lock ranges. */
-static uint32_t use_bits(uint64_t h, unsigned num, unsigned *used)
+static ntdb_off_t encode_offset(const struct ntdb_context *ntdb,
+ ntdb_off_t new_off, uint32_t hash)
{
- *used += num;
- return bits(h, 64 - *used, num);
+ ntdb_off_t extra;
+
+ assert((new_off & (1ULL << NTDB_OFF_CHAIN_BIT)) == 0);
+ assert((new_off >> (64 - NTDB_OFF_UPPER_STEAL)) == 0);
+ /* We pack extra hash bits into the upper bits of the offset. */
+ extra = bits(hash, ntdb->hash_bits, NTDB_OFF_UPPER_STEAL);
+ extra <<= (64 - NTDB_OFF_UPPER_STEAL);
+
+ return new_off | extra;
}
-static ntdb_off_t encode_offset(ntdb_off_t new_off, unsigned bucket,
- uint64_t h)
+static ntdb_off_t hbucket_off(ntdb_len_t idx)
{
- return bucket
- | new_off
- | ((uint64_t)bits(h, 64 - NTDB_OFF_UPPER_STEAL_EXTRA,
- NTDB_OFF_UPPER_STEAL_EXTRA)
- << NTDB_OFF_HASH_EXTRA_BIT);
+ return sizeof(struct ntdb_header) + sizeof(struct ntdb_used_record)
+ + idx * sizeof(ntdb_off_t);
}
/* FIXME: Our hash table handling here is primitive: we don't expand! */
@@ -233,28 +210,14 @@ static void add_to_hashtable(struct ntdb_context *ntdb,
ntdb_off_t eoff,
NTDB_DATA key)
{
- uint64_t h = ntdb_hash(ntdb, key.dptr, key.dsize);
- ntdb_off_t b_off, group_start;
- unsigned i, group, in_group;
- unsigned used = 0;
+ ntdb_off_t b_off;
+ uint32_t h = ntdb_hash(ntdb, key.dptr, key.dsize);
- group = use_bits(h, NTDB_TOPLEVEL_HASH_BITS-NTDB_HASH_GROUP_BITS, &used);
- in_group = use_bits(h, NTDB_HASH_GROUP_BITS, &used);
+ b_off = hbucket_off(h & ((1 << ntdb->hash_bits)-1));
+ if (ntdb_read_off(ntdb, b_off) != 0)
+ abort();
- group_start = offsetof(struct ntdb_header, hashtable)
- + group * (sizeof(ntdb_off_t) << NTDB_HASH_GROUP_BITS);
-
- for (i = 0; i < (1 << NTDB_HASH_GROUP_BITS); i++) {
- unsigned bucket = (in_group + i) % (1 << NTDB_HASH_GROUP_BITS);
-
- b_off = hbucket_off(group_start, bucket);
- if (ntdb_read_off(ntdb, b_off) == 0) {
- ntdb_write_off(ntdb, b_off,
- encode_offset(eoff, in_group, h));
- return;
- }
- }
- abort();
+ ntdb_write_off(ntdb, b_off, encode_offset(ntdb, eoff, h));
}
static struct tle_freetable *find_ftable(struct ntdb_layout *layout, unsigned num)
@@ -277,11 +240,16 @@ struct ntdb_context *ntdb_layout_get(struct ntdb_layout *layout,
union ntdb_attribute *attr)
{
unsigned int i;
- ntdb_off_t off, len, last_ftable, last_cap;
+ ntdb_off_t off, hdrlen, len, last_ftable, last_cap;
char *mem;
struct ntdb_context *ntdb;
- off = sizeof(struct ntdb_header);
+ /* Now populate our header, cribbing from a real NTDB header. */
+ ntdb = ntdb_open("layout", NTDB_INTERNAL, O_RDWR, 0, attr);
+
+ off = sizeof(struct ntdb_header) + sizeof(struct ntdb_used_record)
+ + (sizeof(ntdb_off_t) << ntdb->hash_bits);
+ hdrlen = off;
/* First pass of layout: calc lengths */
for (i = 0; i < layout->num_elems; i++) {
@@ -297,9 +265,6 @@ struct ntdb_context *ntdb_layout_get(struct ntdb_layout *layout,
case DATA:
len = data_record_len(&e->used);
break;
- case HASHTABLE:
- len = hashtable_len(&e->hashtable);
- break;
case CAPABILITY:
len = capability_len(&e->capability);
break;
@@ -312,9 +277,7 @@ struct ntdb_context *ntdb_layout_get(struct ntdb_layout *layout,
mem = malloc(off);
/* Fill with some weird pattern. */
memset(mem, 0x99, off);
- /* Now populate our header, cribbing from a real NTDB header. */
- ntdb = ntdb_open("layout", NTDB_INTERNAL, O_RDWR, 0, attr);
- memcpy(mem, ntdb->file->map_ptr, sizeof(struct ntdb_header));
+ memcpy(mem, ntdb->file->map_ptr, hdrlen);
/* Mug the ntdb we have to make it use this. */
freefn(ntdb->file->map_ptr);
@@ -337,9 +300,6 @@ struct ntdb_context *ntdb_layout_get(struct ntdb_layout *layout,
case DATA:
set_data_record(mem + e->base.off, ntdb, &e->used);
break;
- case HASHTABLE:
- set_hashtable(mem + e->base.off, ntdb, &e->hashtable);
- break;
case CAPABILITY:
set_capability(mem + e->base.off, ntdb, &e->capability,
(struct ntdb_header *)mem, last_cap);
generated by cgit (git 2.34.1) at 2024-06-02 12:34:03 +0000