bind9/lib/isc/ht.c

/*
 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
 *
 * SPDX-License-Identifier: MPL-2.0
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, you can obtain one at https://mozilla.org/MPL/2.0/.
 *
 * See the COPYRIGHT file distributed with this work for additional
 * information regarding copyright ownership.
 */

#include <inttypes.h>
#include <string.h>

#include <isc/ascii.h>
#include <isc/hash.h>
#include <isc/ht.h>
#include <isc/magic.h>
#include <isc/mem.h>
#include <isc/result.h>
#include <isc/types.h>
#include <isc/util.h>

typedef struct isc_ht_node isc_ht_node_t;

#define ISC_HT_MAGIC	 ISC_MAGIC('H', 'T', 'a', 'b')
#define ISC_HT_VALID(ht) ISC_MAGIC_VALID(ht, ISC_HT_MAGIC)

#define HT_NO_BITS    0
#define HT_MIN_BITS   1
#define HT_MAX_BITS   32
#define HT_OVERCOMMIT 3

#define HT_NEXTTABLE(idx)      ((idx == 0) ? 1 : 0)
#define TRY_NEXTTABLE(idx, ht) (idx == ht->hindex && rehashing_in_progress(ht))

#define GOLDEN_RATIO_32 0x61C88647

#define HASHSIZE(bits) (UINT64_C(1) << (bits))

struct isc_ht_node {
	void *value;
	isc_ht_node_t *next;
	uint32_t hashval;
	size_t keysize;
	unsigned char key[];
};

struct isc_ht {
	unsigned int magic;
	isc_mem_t *mctx;
	size_t count;
	bool case_sensitive;
	size_t size[2];
	uint8_t hashbits[2];
	isc_ht_node_t **table[2];
	uint8_t hindex;
	uint32_t hiter; /* rehashing iterator */
};

struct isc_ht_iter {
	isc_ht_t *ht;
	size_t i;
	uint8_t hindex;
	isc_ht_node_t *cur;
};

static isc_ht_node_t *
isc__ht_find(const isc_ht_t *ht, const unsigned char *key,
	     const uint32_t keysize, const uint32_t hashval, const uint8_t idx);
static void
isc__ht_add(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize,
	    const uint32_t hashval, const uint8_t idx, void *value);
static isc_result_t
isc__ht_delete(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize,
	       const uint32_t hashval, const uint8_t idx);

static uint32_t
rehash_bits(isc_ht_t *ht, size_t newcount);

static void
hashtable_new(isc_ht_t *ht, const uint8_t idx, const uint8_t bits);
static void
hashtable_free(isc_ht_t *ht, const uint8_t idx);
static void
hashtable_rehash(isc_ht_t *ht, uint32_t newbits);
static void
hashtable_rehash_one(isc_ht_t *ht);
static void
maybe_rehash(isc_ht_t *ht, size_t newcount);

static isc_result_t
isc__ht_iter_next(isc_ht_iter_t *it);

static bool
isc__ht_node_match(isc_ht_node_t *node, const uint32_t hashval,
		   const uint8_t *key, uint32_t keysize, bool case_sensitive) {
	return node->hashval == hashval && node->keysize == keysize &&
	       (case_sensitive
			? (memcmp(node->key, key, keysize) == 0)
			: (isc_ascii_lowerequal(node->key, key, keysize)));
}

static uint32_t
hash_32(uint32_t val, unsigned int bits) {
	REQUIRE(bits <= HT_MAX_BITS);
	/* High bits are more random. */
	return val * GOLDEN_RATIO_32 >> (32 - bits);
}

static bool
rehashing_in_progress(const isc_ht_t *ht) {
	return ht->table[HT_NEXTTABLE(ht->hindex)] != NULL;
}

static bool
hashtable_is_overcommited(isc_ht_t *ht) {
	return ht->count >= (ht->size[ht->hindex] * HT_OVERCOMMIT);
}

static uint32_t
rehash_bits(isc_ht_t *ht, size_t newcount) {
	uint32_t newbits = ht->hashbits[ht->hindex];

	while (newcount >= HASHSIZE(newbits) && newbits <= HT_MAX_BITS) {
		newbits += 1;
	}

	return newbits;
}

/*
 * Rebuild the hashtable to reduce the load factor
 */
static void
hashtable_rehash(isc_ht_t *ht, uint32_t newbits) {
	uint8_t oldindex = ht->hindex;
	uint32_t oldbits = ht->hashbits[oldindex];
	uint8_t newindex = HT_NEXTTABLE(oldindex);

	REQUIRE(ht->hashbits[oldindex] >= HT_MIN_BITS);
	REQUIRE(ht->hashbits[oldindex] <= HT_MAX_BITS);
	REQUIRE(ht->table[oldindex] != NULL);

	REQUIRE(newbits <= HT_MAX_BITS);
	REQUIRE(ht->hashbits[newindex] == HT_NO_BITS);
	REQUIRE(ht->table[newindex] == NULL);

	REQUIRE(newbits > oldbits);

	hashtable_new(ht, newindex, newbits);

	ht->hindex = newindex;

	hashtable_rehash_one(ht);
}

static void
hashtable_rehash_one(isc_ht_t *ht) {
	isc_ht_node_t **newtable = ht->table[ht->hindex];
	uint32_t oldsize = ht->size[HT_NEXTTABLE(ht->hindex)];
	isc_ht_node_t **oldtable = ht->table[HT_NEXTTABLE(ht->hindex)];
	isc_ht_node_t *node = NULL;
	isc_ht_node_t *nextnode;

	/* Find first non-empty node */
	while (ht->hiter < oldsize && oldtable[ht->hiter] == NULL) {
		ht->hiter++;
	}

	/* Rehashing complete */
	if (ht->hiter == oldsize) {
		hashtable_free(ht, HT_NEXTTABLE(ht->hindex));
		ht->hiter = 0;
		return;
	}

	/* Move the first non-empty node from old hashtable to new hashtable */
	for (node = oldtable[ht->hiter]; node != NULL; node = nextnode) {
		uint32_t hash = hash_32(node->hashval,
					ht->hashbits[ht->hindex]);
		nextnode = node->next;
		node->next = newtable[hash];
		newtable[hash] = node;
	}

	oldtable[ht->hiter] = NULL;

	ht->hiter++;
}

static void
maybe_rehash(isc_ht_t *ht, size_t newcount) {
	uint32_t newbits = rehash_bits(ht, newcount);

	if (ht->hashbits[ht->hindex] < newbits && newbits <= HT_MAX_BITS) {
		hashtable_rehash(ht, newbits);
	}
}

static void
hashtable_new(isc_ht_t *ht, const uint8_t idx, const uint8_t bits) {
	REQUIRE(ht->hashbits[idx] == HT_NO_BITS);
	REQUIRE(ht->table[idx] == NULL);
	REQUIRE(bits >= HT_MIN_BITS);
	REQUIRE(bits <= HT_MAX_BITS);

	ht->hashbits[idx] = bits;
	ht->size[idx] = HASHSIZE(ht->hashbits[idx]);

	ht->table[idx] = isc_mem_cget(ht->mctx, ht->size[idx],
				      sizeof(isc_ht_node_t *));
}

static void
hashtable_free(isc_ht_t *ht, const uint8_t idx) {
	for (size_t i = 0; i < ht->size[idx]; i++) {
		isc_ht_node_t *node = ht->table[idx][i];
		while (node != NULL) {
			isc_ht_node_t *next = node->next;
			ht->count--;
			isc_mem_put(ht->mctx, node,
				    sizeof(*node) + node->keysize);
			node = next;
		}
	}

	isc_mem_cput(ht->mctx, ht->table[idx], ht->size[idx],
		     sizeof(isc_ht_node_t *));

	ht->hashbits[idx] = HT_NO_BITS;
	ht->table[idx] = NULL;
}

void
isc_ht_init(isc_ht_t **htp, isc_mem_t *mctx, uint8_t bits,
	    unsigned int options) {
	isc_ht_t *ht = NULL;
	bool case_sensitive = ((options & ISC_HT_CASE_INSENSITIVE) == 0);

	REQUIRE(htp != NULL && *htp == NULL);
	REQUIRE(mctx != NULL);
	REQUIRE(bits >= 1 && bits <= HT_MAX_BITS);

	ht = isc_mem_get(mctx, sizeof(*ht));
	*ht = (isc_ht_t){
		.case_sensitive = case_sensitive,
	};

	isc_mem_attach(mctx, &ht->mctx);

	hashtable_new(ht, 0, bits);

	ht->magic = ISC_HT_MAGIC;

	*htp = ht;
}

void
isc_ht_destroy(isc_ht_t **htp) {
	isc_ht_t *ht;

	REQUIRE(htp != NULL);
	REQUIRE(ISC_HT_VALID(*htp));

	ht = *htp;
	*htp = NULL;
	ht->magic = 0;

	for (size_t i = 0; i <= 1; i++) {
		if (ht->table[i] != NULL) {
			hashtable_free(ht, i);
		}
	}

	INSIST(ht->count == 0);

	isc_mem_putanddetach(&ht->mctx, ht, sizeof(*ht));
}

static void
isc__ht_add(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize,
	    const uint32_t hashval, const uint8_t idx, void *value) {
	isc_ht_node_t *node;
	uint32_t hash;

	hash = hash_32(hashval, ht->hashbits[idx]);

	node = isc_mem_get(ht->mctx, STRUCT_FLEX_SIZE(node, key, keysize));
	*node = (isc_ht_node_t){
		.keysize = keysize,
		.hashval = hashval,
		.next = ht->table[idx][hash],
		.value = value,
	};

	memmove(node->key, key, keysize);

	ht->count++;
	ht->table[idx][hash] = node;
}

isc_result_t
isc_ht_add(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize,
	   void *value) {
	uint32_t hashval;

	REQUIRE(ISC_HT_VALID(ht));
	REQUIRE(key != NULL && keysize > 0);

	if (rehashing_in_progress(ht)) {
		/* Rehash in progress */
		hashtable_rehash_one(ht);
	} else if (hashtable_is_overcommited(ht)) {
		/* Rehash requested */
		maybe_rehash(ht, ht->count);
	}

	hashval = isc_hash32(key, keysize, ht->case_sensitive);

	if (isc__ht_find(ht, key, keysize, hashval, ht->hindex) != NULL) {
		return ISC_R_EXISTS;
	}

	isc__ht_add(ht, key, keysize, hashval, ht->hindex, value);

	return ISC_R_SUCCESS;
}

static isc_ht_node_t *
isc__ht_find(const isc_ht_t *ht, const unsigned char *key,
	     const uint32_t keysize, const uint32_t hashval,
	     const uint8_t idx) {
	uint32_t hash;
	uint8_t findex = idx;

nexttable:
	hash = hash_32(hashval, ht->hashbits[findex]);
	for (isc_ht_node_t *node = ht->table[findex][hash]; node != NULL;
	     node = node->next)
	{
		if (isc__ht_node_match(node, hashval, key, keysize,
				       ht->case_sensitive))
		{
			return node;
		}
	}
	if (TRY_NEXTTABLE(findex, ht)) {
		/*
		 * Rehashing in progress, check the other table
		 */
		findex = HT_NEXTTABLE(findex);
		goto nexttable;
	}

	return NULL;
}

isc_result_t
isc_ht_find(const isc_ht_t *ht, const unsigned char *key,
	    const uint32_t keysize, void **valuep) {
	uint32_t hashval;
	isc_ht_node_t *node;

	REQUIRE(ISC_HT_VALID(ht));
	REQUIRE(key != NULL && keysize > 0);
	REQUIRE(valuep == NULL || *valuep == NULL);

	hashval = isc_hash32(key, keysize, ht->case_sensitive);

	node = isc__ht_find(ht, key, keysize, hashval, ht->hindex);
	if (node == NULL) {
		return ISC_R_NOTFOUND;
	}

	SET_IF_NOT_NULL(valuep, node->value);
	return ISC_R_SUCCESS;
}

static isc_result_t
isc__ht_delete(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize,
	       const uint32_t hashval, const uint8_t idx) {
	isc_ht_node_t *prev = NULL;
	uint32_t hash;

	hash = hash_32(hashval, ht->hashbits[idx]);

	for (isc_ht_node_t *node = ht->table[idx][hash]; node != NULL;
	     prev = node, node = node->next)
	{
		if (isc__ht_node_match(node, hashval, key, keysize,
				       ht->case_sensitive))
		{
			if (prev == NULL) {
				ht->table[idx][hash] = node->next;
			} else {
				prev->next = node->next;
			}
			isc_mem_put(ht->mctx, node,
				    STRUCT_FLEX_SIZE(node, key, node->keysize));
			ht->count--;

			return ISC_R_SUCCESS;
		}
	}

	return ISC_R_NOTFOUND;
}

isc_result_t
isc_ht_delete(isc_ht_t *ht, const unsigned char *key, const uint32_t keysize) {
	uint32_t hashval;
	uint8_t hindex;
	isc_result_t result;

	REQUIRE(ISC_HT_VALID(ht));
	REQUIRE(key != NULL && keysize > 0);

	if (rehashing_in_progress(ht)) {
		/* Rehash in progress */
		hashtable_rehash_one(ht);
	}

	hindex = ht->hindex;
	hashval = isc_hash32(key, keysize, ht->case_sensitive);
nexttable:
	result = isc__ht_delete(ht, key, keysize, hashval, hindex);

	if (result == ISC_R_NOTFOUND && TRY_NEXTTABLE(hindex, ht)) {
		/*
		 * Rehashing in progress, check the other table
		 */
		hindex = HT_NEXTTABLE(hindex);
		goto nexttable;
	}

	return result;
}

void
isc_ht_iter_create(isc_ht_t *ht, isc_ht_iter_t **itp) {
	isc_ht_iter_t *it;

	REQUIRE(ISC_HT_VALID(ht));
	REQUIRE(itp != NULL && *itp == NULL);

	it = isc_mem_get(ht->mctx, sizeof(isc_ht_iter_t));
	*it = (isc_ht_iter_t){
		.ht = ht,
		.hindex = ht->hindex,
	};

	*itp = it;
}

void
isc_ht_iter_destroy(isc_ht_iter_t **itp) {
	isc_ht_iter_t *it;
	isc_ht_t *ht;

	REQUIRE(itp != NULL && *itp != NULL);

	it = *itp;
	*itp = NULL;
	ht = it->ht;
	isc_mem_put(ht->mctx, it, sizeof(*it));
}

isc_result_t
isc_ht_iter_first(isc_ht_iter_t *it) {
	isc_ht_t *ht;

	REQUIRE(it != NULL);

	ht = it->ht;

	it->hindex = ht->hindex;
	it->i = 0;

	return isc__ht_iter_next(it);
}

static isc_result_t
isc__ht_iter_next(isc_ht_iter_t *it) {
	isc_ht_t *ht = it->ht;

	while (it->i < ht->size[it->hindex] &&
	       ht->table[it->hindex][it->i] == NULL)
	{
		it->i++;
	}

	if (it->i < ht->size[it->hindex]) {
		it->cur = ht->table[it->hindex][it->i];

		return ISC_R_SUCCESS;
	}

	if (TRY_NEXTTABLE(it->hindex, ht)) {
		it->hindex = HT_NEXTTABLE(it->hindex);
		it->i = 0;
		return isc__ht_iter_next(it);
	}

	return ISC_R_NOMORE;
}

isc_result_t
isc_ht_iter_next(isc_ht_iter_t *it) {
	REQUIRE(it != NULL);
	REQUIRE(it->cur != NULL);

	it->cur = it->cur->next;

	if (it->cur != NULL) {
		return ISC_R_SUCCESS;
	}

	it->i++;

	return isc__ht_iter_next(it);
}

isc_result_t
isc_ht_iter_delcurrent_next(isc_ht_iter_t *it) {
	isc_result_t result = ISC_R_SUCCESS;
	isc_ht_node_t *dnode = NULL;
	uint8_t dindex;
	isc_ht_t *ht;
	isc_result_t dresult;

	REQUIRE(it != NULL);
	REQUIRE(it->cur != NULL);

	ht = it->ht;
	dnode = it->cur;
	dindex = it->hindex;

	result = isc_ht_iter_next(it);

	dresult = isc__ht_delete(ht, dnode->key, dnode->keysize, dnode->hashval,
				 dindex);
	INSIST(dresult == ISC_R_SUCCESS);

	return result;
}

void
isc_ht_iter_current(isc_ht_iter_t *it, void **valuep) {
	REQUIRE(it != NULL);
	REQUIRE(it->cur != NULL);
	REQUIRE(valuep != NULL && *valuep == NULL);

	*valuep = it->cur->value;
}

void
isc_ht_iter_currentkey(isc_ht_iter_t *it, unsigned char **key,
		       size_t *keysize) {
	REQUIRE(it != NULL);
	REQUIRE(it->cur != NULL);
	REQUIRE(key != NULL && *key == NULL);

	*key = it->cur->key;
	*keysize = it->cur->keysize;
}

size_t
isc_ht_count(const isc_ht_t *ht) {
	REQUIRE(ISC_HT_VALID(ht));

	return ht->count;
}