/src/bind9/lib/isc/hashmap.c

Source
/*
 * 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.
 */

/*
 * This is an implementation of the Robin Hood hash table algorithm as
 * described in [a] with simple linear searching, and backwards shift
 * deletion algorithm as described in [b] and [c].
 *
 * Further work:
 * 1. Implement 4.1 Speeding up Searches - 4.4 Smart Search [a]
 * 2. Implement A Fast Concurrent and Resizable Robin Hood Hash Table [b]
 *
 * a. https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf paper.
 * b. https://dspace.mit.edu/bitstream/handle/1721.1/130693/1251799942-MIT.pdf
 * c.
 * https://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
 */

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

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

#define APPROX_99_PERCENT(x) (((x) * 1013) >> 10)
#define APPROX_95_PERCENT(x) (((x) * 972) >> 10)
#define APPROX_90_PERCENT(x) (((x) * 921) >> 10)
#define APPROX_85_PERCENT(x) (((x) * 870) >> 10)
#define APPROX_40_PERCENT(x) (((x) * 409) >> 10)
#define APPROX_35_PERCENT(x) (((x) * 359) >> 10)
#define APPROX_30_PERCENT(x) (((x) * 308) >> 10)
#define APPROX_25_PERCENT(x) (((x) * 256) >> 10)
#define APPROX_20_PERCENT(x) (((x) * 205) >> 10)
#define APPROX_15_PERCENT(x) (((x) * 154) >> 10)
#define APPROX_10_PERCENT(x) (((x) * 103) >> 10)
#define APPROX_05_PERCENT(x) (((x) * 52) >> 10)
#define APPROX_01_PERCENT(x) (((x) * 11) >> 10)

#define ISC_HASHMAP_MAGIC    ISC_MAGIC('H', 'M', 'a', 'p')
#define ISC_HASHMAP_VALID(hashmap) ISC_MAGIC_VALID(hashmap, ISC_HASHMAP_MAGIC)

/* We have two tables for incremental rehashing */
#define HASHMAP_NUM_TABLES 2

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

#define HASHMAP_NO_BITS  0U
#define HASHMAP_MIN_BITS 1U
#define HASHMAP_MAX_BITS 32U

typedef struct hashmap_node {
  const void *key;
  void *value;
  uint32_t hashval;
  uint32_t psl;
} hashmap_node_t;

typedef struct hashmap_table {
  size_t size;
  uint8_t hashbits;
  uint32_t hashmask;
  hashmap_node_t *table;
} hashmap_table_t;

struct isc_hashmap {
  unsigned int magic;
  uint8_t hindex;
  uint32_t hiter; /* rehashing iterator */
  isc_mem_t *mctx;
  size_t count;
  hashmap_table_t tables[HASHMAP_NUM_TABLES];
  atomic_uint_fast32_t iterators;
};

struct isc_hashmap_iter {
  isc_hashmap_t *hashmap;
  size_t i;
  size_t size;
  uint8_t hindex;
  hashmap_node_t *cur;
};

static isc_result_t
hashmap_add(isc_hashmap_t *hashmap, const uint32_t hashval,
      isc_hashmap_match_fn match, const uint8_t *key, void *value,
      void **foundp, uint8_t idx);

static void
hashmap_rehash_one(isc_hashmap_t *hashmap);
static void
hashmap_rehash_start_grow(isc_hashmap_t *hashmap);
static void
hashmap_rehash_start_shrink(isc_hashmap_t *hashmap);
static bool
over_threshold(isc_hashmap_t *hashmap);
static bool
under_threshold(isc_hashmap_t *hashmap);

static uint8_t
hashmap_nexttable(uint8_t idx) {
  return (idx == 0) ? 1 : 0;
}

static bool
rehashing_in_progress(const isc_hashmap_t *hashmap) {
  return hashmap->tables[hashmap_nexttable(hashmap->hindex)].table !=
         NULL;
}

static bool
try_nexttable(const isc_hashmap_t *hashmap, uint8_t idx) {
  return idx == hashmap->hindex && rehashing_in_progress(hashmap);
}

static void
hashmap_node_init(hashmap_node_t *node, const uint32_t hashval,
      const uint8_t *key, void *value) {
  *node = (hashmap_node_t){
    .value = value,
    .hashval = hashval,
    .key = key,
    .psl = 0,
  };
}

ISC_ATTR_UNUSED static void
hashmap_dump_table(const isc_hashmap_t *hashmap, const uint8_t idx) {
  fprintf(stderr,
    "====== %" PRIu8 " (bits = %" PRIu8 ", size = %zu =====\n", idx,
    hashmap->tables[idx].hashbits, hashmap->tables[idx].size);
  for (size_t i = 0; i < hashmap->tables[idx].size; i++) {
    hashmap_node_t *node = &hashmap->tables[idx].table[i];
    if (node->key != NULL) {
      uint32_t hash = isc_hash_bits32(
        node->hashval, hashmap->tables[idx].hashbits);
      fprintf(stderr,
        "%p: %zu -> %p"
        ", value = %p"
        ", hash = %" PRIu32 ", hashval = %" PRIu32
        ", psl = %" PRIu32 ", key = %s\n",
        hashmap, i, node, node->value, hash,
        node->hashval, node->psl, (char *)node->key);
    }
  }
  fprintf(stderr, "================\n\n");
}

static void
hashmap_create_table(isc_hashmap_t *hashmap, const uint8_t idx,
         const uint8_t bits) {
  REQUIRE(hashmap->tables[idx].hashbits == HASHMAP_NO_BITS);
  REQUIRE(hashmap->tables[idx].table == NULL);
  REQUIRE(bits >= HASHMAP_MIN_BITS);
  REQUIRE(bits <= HASHMAP_MAX_BITS);

  hashmap->tables[idx] = (hashmap_table_t){
    .hashbits = bits,
    .hashmask = HASHSIZE(bits) - 1,
    .size = HASHSIZE(bits),
  };

  hashmap->tables[idx].table =
    isc_mem_cget(hashmap->mctx, hashmap->tables[idx].size,
           sizeof(hashmap->tables[idx].table[0]));
}

static void
hashmap_free_table(isc_hashmap_t *hashmap, const uint8_t idx, bool cleanup) {
  size_t size;

  if (cleanup) {
    for (size_t i = 0; i < hashmap->tables[idx].size; i++) {
      hashmap_node_t *node = &hashmap->tables[idx].table[i];
      if (node->key != NULL) {
        *node = (hashmap_node_t){ 0 };
        hashmap->count--;
      }
    }
  }

  size = hashmap->tables[idx].size *
         sizeof(hashmap->tables[idx].table[0]);
  isc_mem_put(hashmap->mctx, hashmap->tables[idx].table, size);

  hashmap->tables[idx] = (hashmap_table_t){
    .hashbits = HASHMAP_NO_BITS,
  };
}

void
isc_hashmap_create(isc_mem_t *mctx, uint8_t bits, isc_hashmap_t **hashmapp) {
  isc_hashmap_t *hashmap = isc_mem_get(mctx, sizeof(*hashmap));

  REQUIRE(hashmapp != NULL && *hashmapp == NULL);
  REQUIRE(mctx != NULL);
  REQUIRE(bits >= HASHMAP_MIN_BITS && bits <= HASHMAP_MAX_BITS);

  *hashmap = (isc_hashmap_t){
    .magic = ISC_HASHMAP_MAGIC,
  };
  isc_mem_attach(mctx, &hashmap->mctx);

  hashmap_create_table(hashmap, 0, bits);

  hashmap->magic = ISC_HASHMAP_MAGIC;

  *hashmapp = hashmap;
}

void
isc_hashmap_destroy(isc_hashmap_t **hashmapp) {
  isc_hashmap_t *hashmap;

  REQUIRE(hashmapp != NULL && *hashmapp != NULL);
  REQUIRE(ISC_HASHMAP_VALID(*hashmapp));

  hashmap = *hashmapp;
  *hashmapp = NULL;

  hashmap->magic = 0;

  for (size_t i = 0; i < HASHMAP_NUM_TABLES; i++) {
    if (hashmap->tables[i].table != NULL) {
      hashmap_free_table(hashmap, i, true);
    }
  }
  INSIST(hashmap->count == 0);

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

static hashmap_node_t *
hashmap_find(const isc_hashmap_t *hashmap, const uint32_t hashval,
       isc_hashmap_match_fn match, const uint8_t *key, uint32_t *pslp,
       uint8_t *idxp) {
  uint32_t hash;
  uint32_t psl;
  uint8_t idx = *idxp;
  uint32_t pos;

nexttable:
  psl = 0;
  hash = isc_hash_bits32(hashval, hashmap->tables[idx].hashbits);

  while (true) {
    hashmap_node_t *node = NULL;

    pos = (hash + psl) & hashmap->tables[idx].hashmask;

    node = &hashmap->tables[idx].table[pos];

    if (node->key == NULL || psl > node->psl) {
      break;
    }

    if (node->hashval == hashval) {
      if (match(node->value, key)) {
        *pslp = psl;
        *idxp = idx;
        return node;
      }
    }

    psl++;
  }
  if (try_nexttable(hashmap, idx)) {
    idx = hashmap_nexttable(idx);
    goto nexttable;
  }

  return NULL;
}

isc_result_t
isc_hashmap_find(const isc_hashmap_t *hashmap, const uint32_t hashval,
     isc_hashmap_match_fn match, const void *key, void **valuep) {
  REQUIRE(ISC_HASHMAP_VALID(hashmap));
  REQUIRE(valuep == NULL || *valuep == NULL);

  uint8_t idx = hashmap->hindex;
  hashmap_node_t *node = hashmap_find(hashmap, hashval, match, key,
              &(uint32_t){ 0 }, &idx);
  if (node == NULL) {
    return ISC_R_NOTFOUND;
  }

  INSIST(node->key != NULL);
  SET_IF_NOT_NULL(valuep, node->value);
  return ISC_R_SUCCESS;
}

static bool
hashmap_delete_node(isc_hashmap_t *hashmap, hashmap_node_t *entry,
        uint32_t hashval, uint32_t psl, const uint8_t idx,
        size_t size) {
  uint32_t pos;
  uint32_t hash;
  bool last = false;

  hashmap->count--;

  hash = isc_hash_bits32(hashval, hashmap->tables[idx].hashbits);
  pos = (hash + psl) & hashmap->tables[idx].hashmask;

  while (true) {
    hashmap_node_t *node = NULL;

    pos = (pos + 1) & hashmap->tables[idx].hashmask;
    INSIST(pos < hashmap->tables[idx].size);

    node = &hashmap->tables[idx].table[pos];

    if (node->key == NULL || node->psl == 0) {
      break;
    }

    if ((pos % size) == 0) {
      last = true;
    }

    node->psl--;
    *entry = *node;
    entry = &hashmap->tables[idx].table[pos];
  }

  *entry = (hashmap_node_t){ 0 };
  return last;
}

static void
hashmap_rehash_one(isc_hashmap_t *hashmap) {
  uint8_t oldidx = hashmap_nexttable(hashmap->hindex);
  uint32_t oldsize = hashmap->tables[oldidx].size;
  hashmap_node_t *oldtable = hashmap->tables[oldidx].table;
  hashmap_node_t node;

  /* Don't rehash when iterating */
  INSIST(atomic_load_acquire(&hashmap->iterators) == 0);

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

  /* Rehashing complete */
  if (hashmap->hiter == oldsize) {
    hashmap_free_table(hashmap, hashmap_nexttable(hashmap->hindex),
           false);
    hashmap->hiter = 0;
    return;
  }

  /* Move the first non-empty node from old table to new table */
  node = oldtable[hashmap->hiter];

  (void)hashmap_delete_node(hashmap, &oldtable[hashmap->hiter],
          node.hashval, node.psl, oldidx, UINT32_MAX);

  isc_result_t result = hashmap_add(hashmap, node.hashval, NULL, node.key,
            node.value, NULL, hashmap->hindex);
  INSIST(result == ISC_R_SUCCESS);

  /*
   * we don't increase the hiter here because the table has been reordered
   * when we deleted the old node
   */
}

static uint32_t
grow_bits(isc_hashmap_t *hashmap) {
  uint32_t newbits = hashmap->tables[hashmap->hindex].hashbits + 1;
  size_t newsize = HASHSIZE(newbits);

  while (hashmap->count > APPROX_40_PERCENT(newsize)) {
    newbits += 1;
    newsize = HASHSIZE(newbits);
  }
  if (newbits > HASHMAP_MAX_BITS) {
    newbits = HASHMAP_MAX_BITS;
  }

  return newbits;
}

static uint32_t
shrink_bits(isc_hashmap_t *hashmap) {
  uint32_t newbits = hashmap->tables[hashmap->hindex].hashbits - 1;

  if (newbits <= HASHMAP_MIN_BITS) {
    newbits = HASHMAP_MIN_BITS;
  }

  return newbits;
}

static void
hashmap_rehash_start_grow(isc_hashmap_t *hashmap) {
  uint32_t newbits;
  uint8_t oldindex = hashmap->hindex;
  uint32_t oldbits = hashmap->tables[oldindex].hashbits;
  uint8_t newindex = hashmap_nexttable(oldindex);

  REQUIRE(!rehashing_in_progress(hashmap));

  newbits = grow_bits(hashmap);

  if (newbits > oldbits) {
    hashmap_create_table(hashmap, newindex, newbits);
    hashmap->hindex = newindex;
  }
}

static void
hashmap_rehash_start_shrink(isc_hashmap_t *hashmap) {
  uint32_t newbits;
  uint8_t oldindex = hashmap->hindex;
  uint32_t oldbits = hashmap->tables[oldindex].hashbits;
  uint8_t newindex = hashmap_nexttable(oldindex);

  REQUIRE(!rehashing_in_progress(hashmap));

  newbits = shrink_bits(hashmap);

  if (newbits < oldbits) {
    hashmap_create_table(hashmap, newindex, newbits);
    hashmap->hindex = newindex;
  }
}

isc_result_t
isc_hashmap_delete(isc_hashmap_t *hashmap, const uint32_t hashval,
       isc_hashmap_match_fn match, const void *key) {
  REQUIRE(ISC_HASHMAP_VALID(hashmap));
  REQUIRE(key != NULL);

  hashmap_node_t *node;
  isc_result_t result = ISC_R_NOTFOUND;
  uint32_t psl = 0;
  uint8_t idx;

  if (rehashing_in_progress(hashmap)) {
    hashmap_rehash_one(hashmap);
  } else if (under_threshold(hashmap)) {
    hashmap_rehash_start_shrink(hashmap);
    hashmap_rehash_one(hashmap);
  }

  /* Initialize idx after possible shrink start */
  idx = hashmap->hindex;

  node = hashmap_find(hashmap, hashval, match, key, &psl, &idx);
  if (node != NULL) {
    INSIST(node->key != NULL);
    (void)hashmap_delete_node(hashmap, node, hashval, psl, idx,
            UINT32_MAX);
    result = ISC_R_SUCCESS;
  }

  return result;
}

static bool
over_threshold(isc_hashmap_t *hashmap) {
  uint32_t bits = hashmap->tables[hashmap->hindex].hashbits;
  if (bits == HASHMAP_MAX_BITS) {
    return false;
  }
  size_t threshold = APPROX_90_PERCENT(HASHSIZE(bits));
  return hashmap->count > threshold;
}

static bool
under_threshold(isc_hashmap_t *hashmap) {
  uint32_t bits = hashmap->tables[hashmap->hindex].hashbits;
  if (bits == HASHMAP_MIN_BITS) {
    return false;
  }
  size_t threshold = APPROX_20_PERCENT(HASHSIZE(bits));
  return hashmap->count < threshold;
}

static isc_result_t
hashmap_add(isc_hashmap_t *hashmap, const uint32_t hashval,
      isc_hashmap_match_fn match, const uint8_t *key, void *value,
      void **foundp, uint8_t idx) {
  uint32_t hash;
  uint32_t psl = 0;
  hashmap_node_t node;
  hashmap_node_t *current = NULL;
  uint32_t pos;

  INSIST(atomic_load_acquire(&hashmap->iterators) == 0);

  hash = isc_hash_bits32(hashval, hashmap->tables[idx].hashbits);

  /* Initialize the node to be store to 'node' */
  hashmap_node_init(&node, hashval, key, value);

  psl = 0;
  while (true) {
    pos = (hash + psl) & hashmap->tables[idx].hashmask;

    current = &hashmap->tables[idx].table[pos];

    /* Found an empty node */
    if (current->key == NULL) {
      break;
    }

    if (current->hashval == hashval) {
      if (match != NULL && match(current->value, key)) {
        SET_IF_NOT_NULL(foundp, current->value);
        return ISC_R_EXISTS;
      }
    }

    /* Found rich node */
    if (node.psl > current->psl) {
      /* Swap the poor with the rich node */
      ISC_SWAP(*current, node);
    }

    node.psl++;
    psl++;
  }

  /*
   * Possible optimalization - start growing when the poor node is too far
   */
#if ISC_HASHMAP_GROW_FAST
  if (psl > hashmap->hashbits[idx]) {
    if (!rehashing_in_progress(hashmap)) {
      hashmap_rehash_start_grow(hashmap);
    }
  }
#endif

  hashmap->count++;

  /* We found an empty place, store entry into current node */
  *current = node;

  return ISC_R_SUCCESS;
}

isc_result_t
isc_hashmap_add(isc_hashmap_t *hashmap, const uint32_t hashval,
    isc_hashmap_match_fn match, const void *key, void *value,
    void **foundp) {
  REQUIRE(ISC_HASHMAP_VALID(hashmap));
  REQUIRE(key != NULL);

  if (rehashing_in_progress(hashmap)) {
    hashmap_rehash_one(hashmap);
  } else if (over_threshold(hashmap)) {
    hashmap_rehash_start_grow(hashmap);
    hashmap_rehash_one(hashmap);
  }

  if (rehashing_in_progress(hashmap)) {
    uint8_t fidx = hashmap_nexttable(hashmap->hindex);
    uint32_t psl;

    /* Look for the value in the old table */
    hashmap_node_t *found = hashmap_find(hashmap, hashval, match,
                 key, &psl, &fidx);
    if (found != NULL) {
      INSIST(found->key != NULL);
      SET_IF_NOT_NULL(foundp, found->value);
      return ISC_R_EXISTS;
    }
  }

  return hashmap_add(hashmap, hashval, match, key, value, foundp,
         hashmap->hindex);
}

void
isc_hashmap_iter_create(isc_hashmap_t *hashmap, isc_hashmap_iter_t **iterp) {
  isc_hashmap_iter_t *iter;

  REQUIRE(ISC_HASHMAP_VALID(hashmap));
  REQUIRE(iterp != NULL && *iterp == NULL);

  iter = isc_mem_get(hashmap->mctx, sizeof(*iter));
  *iter = (isc_hashmap_iter_t){
    .hashmap = hashmap,
    .hindex = hashmap->hindex,
  };

  (void)atomic_fetch_add_release(&hashmap->iterators, 1);

  *iterp = iter;
}

void
isc_hashmap_iter_destroy(isc_hashmap_iter_t **iterp) {
  isc_hashmap_iter_t *iter;
  isc_hashmap_t *hashmap;

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

  iter = *iterp;
  *iterp = NULL;
  hashmap = iter->hashmap;
  isc_mem_put(hashmap->mctx, iter, sizeof(*iter));

  INSIST(atomic_fetch_sub_release(&hashmap->iterators, 1) > 0);
}

static isc_result_t
isc__hashmap_iter_next(isc_hashmap_iter_t *iter) {
  isc_hashmap_t *hashmap = iter->hashmap;

  while (iter->i < iter->size &&
         hashmap->tables[iter->hindex].table[iter->i].key == NULL)
  {
    iter->i++;
  }

  if (iter->i < iter->size) {
    iter->cur = &hashmap->tables[iter->hindex].table[iter->i];

    return ISC_R_SUCCESS;
  }

  if (try_nexttable(hashmap, iter->hindex)) {
    iter->hindex = hashmap_nexttable(iter->hindex);
    iter->i = hashmap->hiter;
    iter->size = hashmap->tables[iter->hindex].size;
    return isc__hashmap_iter_next(iter);
  }

  return ISC_R_NOMORE;
}

isc_result_t
isc_hashmap_iter_first(isc_hashmap_iter_t *iter) {
  REQUIRE(iter != NULL);

  iter->hindex = iter->hashmap->hindex;
  iter->i = 0;
  iter->size = iter->hashmap->tables[iter->hashmap->hindex].size;

  return isc__hashmap_iter_next(iter);
}

isc_result_t
isc_hashmap_iter_next(isc_hashmap_iter_t *iter) {
  REQUIRE(iter != NULL);
  REQUIRE(iter->cur != NULL);

  iter->i++;

  return isc__hashmap_iter_next(iter);
}

isc_result_t
isc_hashmap_iter_delcurrent_next(isc_hashmap_iter_t *iter) {
  REQUIRE(iter != NULL);
  REQUIRE(iter->cur != NULL);

  hashmap_node_t *node =
    &iter->hashmap->tables[iter->hindex].table[iter->i];

  if (hashmap_delete_node(iter->hashmap, node, node->hashval, node->psl,
        iter->hindex, iter->size))
  {
    /*
     * We have seen the new last element so reduce the size
     * so we don't iterate over it twice.
     */
    INSIST(iter->size != 0);
    iter->size--;
  }

  return isc__hashmap_iter_next(iter);
}

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

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

void
isc_hashmap_iter_currentkey(isc_hashmap_iter_t *it, const unsigned char **key) {
  REQUIRE(it != NULL);
  REQUIRE(it->cur != NULL);
  REQUIRE(key != NULL && *key == NULL);

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

unsigned int
isc_hashmap_count(isc_hashmap_t *hashmap) {
  REQUIRE(ISC_HASHMAP_VALID(hashmap));

  return hashmap->count;
}

Coverage Report

Created: 2025-12-14 06:30

Line	Count	Source
1		/*
2		* Copyright (C) Internet Systems Consortium, Inc. ("ISC")
3		*
4		* SPDX-License-Identifier: MPL-2.0
5		*
6		* This Source Code Form is subject to the terms of the Mozilla Public
7		* License, v. 2.0. If a copy of the MPL was not distributed with this
8		* file, you can obtain one at https://mozilla.org/MPL/2.0/.
9		*
10		* See the COPYRIGHT file distributed with this work for additional
11		* information regarding copyright ownership.
12		*/
13
14		/*
15		* This is an implementation of the Robin Hood hash table algorithm as
16		* described in [a] with simple linear searching, and backwards shift
17		* deletion algorithm as described in [b] and [c].
18		*
19		* Further work:
20		* 1. Implement 4.1 Speeding up Searches - 4.4 Smart Search [a]
21		* 2. Implement A Fast Concurrent and Resizable Robin Hood Hash Table [b]
22		*
23		* a. https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf paper.
24		* b. https://dspace.mit.edu/bitstream/handle/1721.1/130693/1251799942-MIT.pdf
25		* c.
26		* https://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/
27		*/
28
29		#include <ctype.h>
30		#include <inttypes.h>
31		#include <string.h>
32
33		#include <isc/ascii.h>
34		#include <isc/atomic.h>
35		#include <isc/hash.h>
36		#include <isc/hashmap.h>
37		#include <isc/magic.h>
38		#include <isc/mem.h>
39		#include <isc/result.h>
40		#include <isc/types.h>
41		#include <isc/util.h>
42
43		#define APPROX_99_PERCENT(x) (((x) * 1013) >> 10)
44		#define APPROX_95_PERCENT(x) (((x) * 972) >> 10)
45	0	#define APPROX_90_PERCENT(x) (((x) * 921) >> 10)
46		#define APPROX_85_PERCENT(x) (((x) * 870) >> 10)
47	0	#define APPROX_40_PERCENT(x) (((x) * 409) >> 10)
48		#define APPROX_35_PERCENT(x) (((x) * 359) >> 10)
49		#define APPROX_30_PERCENT(x) (((x) * 308) >> 10)
50		#define APPROX_25_PERCENT(x) (((x) * 256) >> 10)
51	0	#define APPROX_20_PERCENT(x) (((x) * 205) >> 10)
52		#define APPROX_15_PERCENT(x) (((x) * 154) >> 10)
53		#define APPROX_10_PERCENT(x) (((x) * 103) >> 10)
54		#define APPROX_05_PERCENT(x) (((x) * 52) >> 10)
55		#define APPROX_01_PERCENT(x) (((x) * 11) >> 10)
56
57	0	#define ISC_HASHMAP_MAGIC ISC_MAGIC('H', 'M', 'a', 'p')
58		#define ISC_HASHMAP_VALID(hashmap) ISC_MAGIC_VALID(hashmap, ISC_HASHMAP_MAGIC)
59
60		/* We have two tables for incremental rehashing */
61	0	#define HASHMAP_NUM_TABLES 2
62
63	0	#define HASHSIZE(bits) (UINT64_C(1) << (bits))
64
65	0	#define HASHMAP_NO_BITS 0U
66	0	#define HASHMAP_MIN_BITS 1U
67	0	#define HASHMAP_MAX_BITS 32U
68
69		typedef struct hashmap_node {
70		const void *key;
71		void *value;
72		uint32_t hashval;
73		uint32_t psl;
74		} hashmap_node_t;
75
76		typedef struct hashmap_table {
77		size_t size;
78		uint8_t hashbits;
79		uint32_t hashmask;
80		hashmap_node_t *table;
81		} hashmap_table_t;
82
83		struct isc_hashmap {
84		unsigned int magic;
85		uint8_t hindex;
86		uint32_t hiter; /* rehashing iterator */
87		isc_mem_t *mctx;
88		size_t count;
89		hashmap_table_t tables[HASHMAP_NUM_TABLES];
90		atomic_uint_fast32_t iterators;
91		};
92
93		struct isc_hashmap_iter {
94		isc_hashmap_t *hashmap;
95		size_t i;
96		size_t size;
97		uint8_t hindex;
98		hashmap_node_t *cur;
99		};
100
101		static isc_result_t
102		hashmap_add(isc_hashmap_t *hashmap, const uint32_t hashval,
103		isc_hashmap_match_fn match, const uint8_t key, void value,
104		void **foundp, uint8_t idx);
105
106		static void
107		hashmap_rehash_one(isc_hashmap_t *hashmap);
108		static void
109		hashmap_rehash_start_grow(isc_hashmap_t *hashmap);
110		static void
111		hashmap_rehash_start_shrink(isc_hashmap_t *hashmap);
112		static bool
113		over_threshold(isc_hashmap_t *hashmap);
114		static bool
115		under_threshold(isc_hashmap_t *hashmap);
116
117		static uint8_t
118	0	hashmap_nexttable(uint8_t idx) {
119	0	return (idx == 0) ? 1 : 0;
120	0	}
121
122		static bool
123	0	rehashing_in_progress(const isc_hashmap_t *hashmap) {
124	0	return hashmap->tables[hashmap_nexttable(hashmap->hindex)].table !=
125	0	NULL;
126	0	}
127
128		static bool
129	0	try_nexttable(const isc_hashmap_t *hashmap, uint8_t idx) {
130	0	return idx == hashmap->hindex && rehashing_in_progress(hashmap);
131	0	}
132
133		static void
134		hashmap_node_init(hashmap_node_t *node, const uint32_t hashval,
135	0	const uint8_t key, void value) {
136	0	*node = (hashmap_node_t){
137	0	.value = value,
138	0	.hashval = hashval,
139	0	.key = key,
140	0	.psl = 0,
141	0	};
142	0	}
143
144		ISC_ATTR_UNUSED static void
145	0	hashmap_dump_table(const isc_hashmap_t *hashmap, const uint8_t idx) {
146	0	fprintf(stderr,
147	0	"====== %" PRIu8 " (bits = %" PRIu8 ", size = %zu =====\n", idx,
148	0	hashmap->tables[idx].hashbits, hashmap->tables[idx].size);
149	0	for (size_t i = 0; i < hashmap->tables[idx].size; i++) {
150	0	hashmap_node_t *node = &hashmap->tables[idx].table[i];
151	0	if (node->key != NULL) {
152	0	uint32_t hash = isc_hash_bits32(
153	0	node->hashval, hashmap->tables[idx].hashbits);
154	0	fprintf(stderr,
155	0	"%p: %zu -> %p"
156	0	", value = %p"
157	0	", hash = %" PRIu32 ", hashval = %" PRIu32
158	0	", psl = %" PRIu32 ", key = %s\n",
159	0	hashmap, i, node, node->value, hash,
160	0	node->hashval, node->psl, (char *)node->key);
161	0	}
162	0	}
163	0	fprintf(stderr, "================\n\n");
164	0	}
165
166		static void
167		hashmap_create_table(isc_hashmap_t *hashmap, const uint8_t idx,
168	0	const uint8_t bits) {
169	0	REQUIRE(hashmap->tables[idx].hashbits == HASHMAP_NO_BITS);
170	0	REQUIRE(hashmap->tables[idx].table == NULL);
171	0	REQUIRE(bits >= HASHMAP_MIN_BITS);
172	0	REQUIRE(bits <= HASHMAP_MAX_BITS);
173
174	0	hashmap->tables[idx] = (hashmap_table_t){
175	0	.hashbits = bits,
176	0	.hashmask = HASHSIZE(bits) - 1,
177	0	.size = HASHSIZE(bits),
178	0	};
179
180	0	hashmap->tables[idx].table =
181	0	isc_mem_cget(hashmap->mctx, hashmap->tables[idx].size,
182	0	sizeof(hashmap->tables[idx].table[0]));
183	0	}
184
185		static void
186	0	hashmap_free_table(isc_hashmap_t *hashmap, const uint8_t idx, bool cleanup) {
187	0	size_t size;
188
189	0	if (cleanup) {
190	0	for (size_t i = 0; i < hashmap->tables[idx].size; i++) {
191	0	hashmap_node_t *node = &hashmap->tables[idx].table[i];
192	0	if (node->key != NULL) {
193	0	*node = (hashmap_node_t){ 0 };
194	0	hashmap->count--;
195	0	}
196	0	}
197	0	}
198
199	0	size = hashmap->tables[idx].size *
200	0	sizeof(hashmap->tables[idx].table[0]);
201	0	isc_mem_put(hashmap->mctx, hashmap->tables[idx].table, size);
202
203	0	hashmap->tables[idx] = (hashmap_table_t){
204	0	.hashbits = HASHMAP_NO_BITS,
205	0	};
206	0	}
207
208		void
209	0	isc_hashmap_create(isc_mem_t mctx, uint8_t bits, isc_hashmap_t *hashmapp) {
210	0	isc_hashmap_t hashmap = isc_mem_get(mctx, sizeof(hashmap));
211
212	0	REQUIRE(hashmapp != NULL && *hashmapp == NULL);
213	0	REQUIRE(mctx != NULL);
214	0	REQUIRE(bits >= HASHMAP_MIN_BITS && bits <= HASHMAP_MAX_BITS);
215
216	0	*hashmap = (isc_hashmap_t){
217	0	.magic = ISC_HASHMAP_MAGIC,
218	0	};
219	0	isc_mem_attach(mctx, &hashmap->mctx);
220
221	0	hashmap_create_table(hashmap, 0, bits);
222
223	0	hashmap->magic = ISC_HASHMAP_MAGIC;
224
225	0	*hashmapp = hashmap;
226	0	}
227
228		void
229	0	isc_hashmap_destroy(isc_hashmap_t **hashmapp) {
230	0	isc_hashmap_t *hashmap;
231
232	0	REQUIRE(hashmapp != NULL && *hashmapp != NULL);
233	0	REQUIRE(ISC_HASHMAP_VALID(*hashmapp));
234
235	0	hashmap = *hashmapp;
236	0	*hashmapp = NULL;
237
238	0	hashmap->magic = 0;
239
240	0	for (size_t i = 0; i < HASHMAP_NUM_TABLES; i++) {
241	0	if (hashmap->tables[i].table != NULL) {
242	0	hashmap_free_table(hashmap, i, true);
243	0	}
244	0	}
245	0	INSIST(hashmap->count == 0);
246
247	0	isc_mem_putanddetach(&hashmap->mctx, hashmap, sizeof(*hashmap));
248	0	}
249
250		static hashmap_node_t *
251		hashmap_find(const isc_hashmap_t *hashmap, const uint32_t hashval,
252		isc_hashmap_match_fn match, const uint8_t key, uint32_t pslp,
253	0	uint8_t *idxp) {
254	0	uint32_t hash;
255	0	uint32_t psl;
256	0	uint8_t idx = *idxp;
257	0	uint32_t pos;
258
259	0	nexttable:
260	0	psl = 0;
261	0	hash = isc_hash_bits32(hashval, hashmap->tables[idx].hashbits);
262
263	0	while (true) {
264	0	hashmap_node_t *node = NULL;
265
266	0	pos = (hash + psl) & hashmap->tables[idx].hashmask;
267
268	0	node = &hashmap->tables[idx].table[pos];
269
270	0	if (node->key == NULL \|\| psl > node->psl) {
271	0	break;
272	0	}
273
274	0	if (node->hashval == hashval) {
275	0	if (match(node->value, key)) {
276	0	*pslp = psl;
277	0	*idxp = idx;
278	0	return node;
279	0	}
280	0	}
281
282	0	psl++;
283	0	}
284	0	if (try_nexttable(hashmap, idx)) {
285	0	idx = hashmap_nexttable(idx);
286	0	goto nexttable;
287	0	}
288
289	0	return NULL;
290	0	}
291
292		isc_result_t
293		isc_hashmap_find(const isc_hashmap_t *hashmap, const uint32_t hashval,
294	0	isc_hashmap_match_fn match, const void key, void *valuep) {
295	0	REQUIRE(ISC_HASHMAP_VALID(hashmap));
296	0	REQUIRE(valuep == NULL \|\| *valuep == NULL);
297
298	0	uint8_t idx = hashmap->hindex;
299	0	hashmap_node_t *node = hashmap_find(hashmap, hashval, match, key,
300	0	&(uint32_t){ 0 }, &idx);
301	0	if (node == NULL) {
302	0	return ISC_R_NOTFOUND;
303	0	}
304
305	0	INSIST(node->key != NULL);
306	0	SET_IF_NOT_NULL(valuep, node->value);
307	0	return ISC_R_SUCCESS;
308	0	}
309
310		static bool
311		hashmap_delete_node(isc_hashmap_t hashmap, hashmap_node_t entry,
312		uint32_t hashval, uint32_t psl, const uint8_t idx,
313	0	size_t size) {
314	0	uint32_t pos;
315	0	uint32_t hash;
316	0	bool last = false;
317
318	0	hashmap->count--;
319
320	0	hash = isc_hash_bits32(hashval, hashmap->tables[idx].hashbits);
321	0	pos = (hash + psl) & hashmap->tables[idx].hashmask;
322
323	0	while (true) {
324	0	hashmap_node_t *node = NULL;
325
326	0	pos = (pos + 1) & hashmap->tables[idx].hashmask;
327	0	INSIST(pos < hashmap->tables[idx].size);
328
329	0	node = &hashmap->tables[idx].table[pos];
330
331	0	if (node->key == NULL \|\| node->psl == 0) {
332	0	break;
333	0	}
334
335	0	if ((pos % size) == 0) {
336	0	last = true;
337	0	}
338
339	0	node->psl--;
340	0	entry = node;
341	0	entry = &hashmap->tables[idx].table[pos];
342	0	}
343
344	0	*entry = (hashmap_node_t){ 0 };
345	0	return last;
346	0	}
347
348		static void
349	0	hashmap_rehash_one(isc_hashmap_t *hashmap) {
350	0	uint8_t oldidx = hashmap_nexttable(hashmap->hindex);
351	0	uint32_t oldsize = hashmap->tables[oldidx].size;
352	0	hashmap_node_t *oldtable = hashmap->tables[oldidx].table;
353	0	hashmap_node_t node;
354
355		/* Don't rehash when iterating */
356	0	INSIST(atomic_load_acquire(&hashmap->iterators) == 0);
357
358		/* Find first non-empty node */
359	0	while (hashmap->hiter < oldsize && oldtable[hashmap->hiter].key == NULL)
360	0	{
361	0	hashmap->hiter++;
362	0	}
363
364		/* Rehashing complete */
365	0	if (hashmap->hiter == oldsize) {
366	0	hashmap_free_table(hashmap, hashmap_nexttable(hashmap->hindex),
367	0	false);
368	0	hashmap->hiter = 0;
369	0	return;
370	0	}
371
372		/* Move the first non-empty node from old table to new table */
373	0	node = oldtable[hashmap->hiter];
374
375	0	(void)hashmap_delete_node(hashmap, &oldtable[hashmap->hiter],
376	0	node.hashval, node.psl, oldidx, UINT32_MAX);
377
378	0	isc_result_t result = hashmap_add(hashmap, node.hashval, NULL, node.key,
379	0	node.value, NULL, hashmap->hindex);
380	0	INSIST(result == ISC_R_SUCCESS);
381
382		/*
383		* we don't increase the hiter here because the table has been reordered
384		* when we deleted the old node
385		*/
386	0	}
387
388		static uint32_t
389	0	grow_bits(isc_hashmap_t *hashmap) {
390	0	uint32_t newbits = hashmap->tables[hashmap->hindex].hashbits + 1;
391	0	size_t newsize = HASHSIZE(newbits);
392
393	0	while (hashmap->count > APPROX_40_PERCENT(newsize)) {
394	0	newbits += 1;
395	0	newsize = HASHSIZE(newbits);
396	0	}
397	0	if (newbits > HASHMAP_MAX_BITS) {
398	0	newbits = HASHMAP_MAX_BITS;
399	0	}
400
401	0	return newbits;
402	0	}
403
404		static uint32_t
405	0	shrink_bits(isc_hashmap_t *hashmap) {
406	0	uint32_t newbits = hashmap->tables[hashmap->hindex].hashbits - 1;
407
408	0	if (newbits <= HASHMAP_MIN_BITS) {
409	0	newbits = HASHMAP_MIN_BITS;
410	0	}
411
412	0	return newbits;
413	0	}
414
415		static void
416	0	hashmap_rehash_start_grow(isc_hashmap_t *hashmap) {
417	0	uint32_t newbits;
418	0	uint8_t oldindex = hashmap->hindex;
419	0	uint32_t oldbits = hashmap->tables[oldindex].hashbits;
420	0	uint8_t newindex = hashmap_nexttable(oldindex);
421
422	0	REQUIRE(!rehashing_in_progress(hashmap));
423
424	0	newbits = grow_bits(hashmap);
425
426	0	if (newbits > oldbits) {
427	0	hashmap_create_table(hashmap, newindex, newbits);
428	0	hashmap->hindex = newindex;
429	0	}
430	0	}
431
432		static void
433	0	hashmap_rehash_start_shrink(isc_hashmap_t *hashmap) {
434	0	uint32_t newbits;
435	0	uint8_t oldindex = hashmap->hindex;
436	0	uint32_t oldbits = hashmap->tables[oldindex].hashbits;
437	0	uint8_t newindex = hashmap_nexttable(oldindex);
438
439	0	REQUIRE(!rehashing_in_progress(hashmap));
440
441	0	newbits = shrink_bits(hashmap);
442
443	0	if (newbits < oldbits) {
444	0	hashmap_create_table(hashmap, newindex, newbits);
445	0	hashmap->hindex = newindex;
446	0	}
447	0	}
448
449		isc_result_t
450		isc_hashmap_delete(isc_hashmap_t *hashmap, const uint32_t hashval,
451	0	isc_hashmap_match_fn match, const void *key) {
452	0	REQUIRE(ISC_HASHMAP_VALID(hashmap));
453	0	REQUIRE(key != NULL);
454
455	0	hashmap_node_t *node;
456	0	isc_result_t result = ISC_R_NOTFOUND;
457	0	uint32_t psl = 0;
458	0	uint8_t idx;
459
460	0	if (rehashing_in_progress(hashmap)) {
461	0	hashmap_rehash_one(hashmap);
462	0	} else if (under_threshold(hashmap)) {
463	0	hashmap_rehash_start_shrink(hashmap);
464	0	hashmap_rehash_one(hashmap);
465	0	}
466
467		/* Initialize idx after possible shrink start */
468	0	idx = hashmap->hindex;
469
470	0	node = hashmap_find(hashmap, hashval, match, key, &psl, &idx);
471	0	if (node != NULL) {
472	0	INSIST(node->key != NULL);
473	0	(void)hashmap_delete_node(hashmap, node, hashval, psl, idx,
474	0	UINT32_MAX);
475	0	result = ISC_R_SUCCESS;
476	0	}
477
478	0	return result;
479	0	}
480
481		static bool
482	0	over_threshold(isc_hashmap_t *hashmap) {
483	0	uint32_t bits = hashmap->tables[hashmap->hindex].hashbits;
484	0	if (bits == HASHMAP_MAX_BITS) {
485	0	return false;
486	0	}
487	0	size_t threshold = APPROX_90_PERCENT(HASHSIZE(bits));
488	0	return hashmap->count > threshold;
489	0	}
490
491		static bool
492	0	under_threshold(isc_hashmap_t *hashmap) {
493	0	uint32_t bits = hashmap->tables[hashmap->hindex].hashbits;
494	0	if (bits == HASHMAP_MIN_BITS) {
495	0	return false;
496	0	}
497	0	size_t threshold = APPROX_20_PERCENT(HASHSIZE(bits));
498	0	return hashmap->count < threshold;
499	0	}
500
501		static isc_result_t
502		hashmap_add(isc_hashmap_t *hashmap, const uint32_t hashval,
503		isc_hashmap_match_fn match, const uint8_t key, void value,
504	0	void **foundp, uint8_t idx) {
505	0	uint32_t hash;
506	0	uint32_t psl = 0;
507	0	hashmap_node_t node;
508	0	hashmap_node_t *current = NULL;
509	0	uint32_t pos;
510
511	0	INSIST(atomic_load_acquire(&hashmap->iterators) == 0);
512
513	0	hash = isc_hash_bits32(hashval, hashmap->tables[idx].hashbits);
514
515		/* Initialize the node to be store to 'node' */
516	0	hashmap_node_init(&node, hashval, key, value);
517
518	0	psl = 0;
519	0	while (true) {
520	0	pos = (hash + psl) & hashmap->tables[idx].hashmask;
521
522	0	current = &hashmap->tables[idx].table[pos];
523
524		/* Found an empty node */
525	0	if (current->key == NULL) {
526	0	break;
527	0	}
528
529	0	if (current->hashval == hashval) {
530	0	if (match != NULL && match(current->value, key)) {
531	0	SET_IF_NOT_NULL(foundp, current->value);
532	0	return ISC_R_EXISTS;
533	0	}
534	0	}
535
536		/* Found rich node */
537	0	if (node.psl > current->psl) {
538		/* Swap the poor with the rich node */
539	0	ISC_SWAP(*current, node);
540	0	}
541
542	0	node.psl++;
543	0	psl++;
544	0	}
545
546		/*
547		* Possible optimalization - start growing when the poor node is too far
548		*/
549		#if ISC_HASHMAP_GROW_FAST
550		if (psl > hashmap->hashbits[idx]) {
551		if (!rehashing_in_progress(hashmap)) {
552		hashmap_rehash_start_grow(hashmap);
553		}
554		}
555		#endif
556
557	0	hashmap->count++;
558
559		/* We found an empty place, store entry into current node */
560	0	*current = node;
561
562	0	return ISC_R_SUCCESS;
563	0	}
564
565		isc_result_t
566		isc_hashmap_add(isc_hashmap_t *hashmap, const uint32_t hashval,
567		isc_hashmap_match_fn match, const void key, void value,
568	0	void **foundp) {
569	0	REQUIRE(ISC_HASHMAP_VALID(hashmap));
570	0	REQUIRE(key != NULL);
571
572	0	if (rehashing_in_progress(hashmap)) {
573	0	hashmap_rehash_one(hashmap);
574	0	} else if (over_threshold(hashmap)) {
575	0	hashmap_rehash_start_grow(hashmap);
576	0	hashmap_rehash_one(hashmap);
577	0	}
578
579	0	if (rehashing_in_progress(hashmap)) {
580	0	uint8_t fidx = hashmap_nexttable(hashmap->hindex);
581	0	uint32_t psl;
582
583		/* Look for the value in the old table */
584	0	hashmap_node_t *found = hashmap_find(hashmap, hashval, match,
585	0	key, &psl, &fidx);
586	0	if (found != NULL) {
587	0	INSIST(found->key != NULL);
588	0	SET_IF_NOT_NULL(foundp, found->value);
589	0	return ISC_R_EXISTS;
590	0	}
591	0	}
592
593	0	return hashmap_add(hashmap, hashval, match, key, value, foundp,
594	0	hashmap->hindex);
595	0	}
596
597		void
598	0	isc_hashmap_iter_create(isc_hashmap_t hashmap, isc_hashmap_iter_t *iterp) {
599	0	isc_hashmap_iter_t *iter;
600
601	0	REQUIRE(ISC_HASHMAP_VALID(hashmap));
602	0	REQUIRE(iterp != NULL && *iterp == NULL);
603
604	0	iter = isc_mem_get(hashmap->mctx, sizeof(*iter));
605	0	*iter = (isc_hashmap_iter_t){
606	0	.hashmap = hashmap,
607	0	.hindex = hashmap->hindex,
608	0	};
609
610	0	(void)atomic_fetch_add_release(&hashmap->iterators, 1);
611
612	0	*iterp = iter;
613	0	}
614
615		void
616	0	isc_hashmap_iter_destroy(isc_hashmap_iter_t **iterp) {
617	0	isc_hashmap_iter_t *iter;
618	0	isc_hashmap_t *hashmap;
619
620	0	REQUIRE(iterp != NULL && *iterp != NULL);
621
622	0	iter = *iterp;
623	0	*iterp = NULL;
624	0	hashmap = iter->hashmap;
625	0	isc_mem_put(hashmap->mctx, iter, sizeof(*iter));
626
627	0	INSIST(atomic_fetch_sub_release(&hashmap->iterators, 1) > 0);
628	0	}
629
630		static isc_result_t
631	0	isc__hashmap_iter_next(isc_hashmap_iter_t *iter) {
632	0	isc_hashmap_t *hashmap = iter->hashmap;
633
634	0	while (iter->i < iter->size &&
635	0	hashmap->tables[iter->hindex].table[iter->i].key == NULL)
636	0	{
637	0	iter->i++;
638	0	}
639
640	0	if (iter->i < iter->size) {
641	0	iter->cur = &hashmap->tables[iter->hindex].table[iter->i];
642
643	0	return ISC_R_SUCCESS;
644	0	}
645
646	0	if (try_nexttable(hashmap, iter->hindex)) {
647	0	iter->hindex = hashmap_nexttable(iter->hindex);
648	0	iter->i = hashmap->hiter;
649	0	iter->size = hashmap->tables[iter->hindex].size;
650	0	return isc__hashmap_iter_next(iter);
651	0	}
652
653	0	return ISC_R_NOMORE;
654	0	}
655
656		isc_result_t
657	0	isc_hashmap_iter_first(isc_hashmap_iter_t *iter) {
658	0	REQUIRE(iter != NULL);
659
660	0	iter->hindex = iter->hashmap->hindex;
661	0	iter->i = 0;
662	0	iter->size = iter->hashmap->tables[iter->hashmap->hindex].size;
663
664	0	return isc__hashmap_iter_next(iter);
665	0	}
666
667		isc_result_t
668	0	isc_hashmap_iter_next(isc_hashmap_iter_t *iter) {
669	0	REQUIRE(iter != NULL);
670	0	REQUIRE(iter->cur != NULL);
671
672	0	iter->i++;
673
674	0	return isc__hashmap_iter_next(iter);
675	0	}
676
677		isc_result_t
678	0	isc_hashmap_iter_delcurrent_next(isc_hashmap_iter_t *iter) {
679	0	REQUIRE(iter != NULL);
680	0	REQUIRE(iter->cur != NULL);
681
682	0	hashmap_node_t *node =
683	0	&iter->hashmap->tables[iter->hindex].table[iter->i];
684
685	0	if (hashmap_delete_node(iter->hashmap, node, node->hashval, node->psl,
686	0	iter->hindex, iter->size))
687	0	{
688		/*
689		* We have seen the new last element so reduce the size
690		* so we don't iterate over it twice.
691		*/
692	0	INSIST(iter->size != 0);
693	0	iter->size--;
694	0	}
695
696	0	return isc__hashmap_iter_next(iter);
697	0	}
698
699		void
700	0	isc_hashmap_iter_current(isc_hashmap_iter_t it, void *valuep) {
701	0	REQUIRE(it != NULL);
702	0	REQUIRE(it->cur != NULL);
703	0	REQUIRE(valuep != NULL && *valuep == NULL);
704
705	0	*valuep = it->cur->value;
706	0	}
707
708		void
709	0	isc_hashmap_iter_currentkey(isc_hashmap_iter_t it, const unsigned char *key) {
710	0	REQUIRE(it != NULL);
711	0	REQUIRE(it->cur != NULL);
712	0	REQUIRE(key != NULL && *key == NULL);
713
714	0	*key = it->cur->key;
715	0	}
716
717		unsigned int
718	0	isc_hashmap_count(isc_hashmap_t *hashmap) {
719	0	REQUIRE(ISC_HASHMAP_VALID(hashmap));
720
721	0	return hashmap->count;
722	0	}