boxdd-sys 0.4.0

// SPDX-FileCopyrightText: 2023 Erin Catto
// SPDX-License-Identifier: MIT

#include "table.h"

#include "atomic.h"
#include "bitset.h"
#include "core.h"
#include "ctz.h"

#include <stdbool.h>
#include <string.h>

#if B2_SNOOP_TABLE_COUNTERS
b2AtomicInt b2_findCount;
b2AtomicInt b2_probeCount;
#endif

b2HashSet b2CreateSet( int capacity )
{
	b2HashSet set = { 0 };

	// Capacity must be a power of 2
	if ( capacity > 16 )
	{
		set.capacity = b2RoundUpPowerOf2( capacity );
	}
	else
	{
		set.capacity = 16;
	}

	set.count = 0;
	set.items = b2Alloc( set.capacity * sizeof( b2SetItem ) );
	memset( set.items, 0, set.capacity * sizeof( b2SetItem ) );

	return set;
}

void b2DestroySet( b2HashSet* set )
{
	b2Free( set->items, set->capacity * sizeof( b2SetItem ) );
	set->items = NULL;
	set->count = 0;
	set->capacity = 0;
}

void b2ClearSet( b2HashSet* set )
{
	set->count = 0;
	memset( set->items, 0, set->capacity * sizeof( b2SetItem ) );
}

// I need a good hash because the keys are built from pairs of increasing integers.
// A simple hash like hash = (integer1 XOR integer2) has many collisions.
// https://lemire.me/blog/2018/08/15/fast-strongly-universal-64-bit-hashing-everywhere/
// https://preshing.com/20130107/this-hash-set-is-faster-than-a-judy-array/
// todo try: https://www.jandrewrogers.com/2019/02/12/fast-perfect-hashing/
// todo try:
// https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/

// I compared with CC on https://jacksonallan.github.io/c_cpp_hash_tables_benchmark/ and got slightly better performance
// in the washer benchmark.
// I compared with verstable across 8 benchmarks and the performance was similar.

#if 0
// Fast-hash
// https://jonkagstrom.com/bit-mixer-construction
// https://code.google.com/archive/p/fast-hash
static uint64_t b2KeyHash( uint64_t key )
{
	key ^= key >> 23;
	key *= 0x2127599BF4325C37ULL;
	key ^= key >> 47;
	return key;
}
#elif 1
static uint64_t b2KeyHash( uint64_t key )
{
	// Murmur hash
	uint64_t h = key;
	h ^= h >> 33;
	h *= 0xff51afd7ed558ccduLL;
	h ^= h >> 33;
	h *= 0xc4ceb9fe1a85ec53uLL;
	h ^= h >> 33;
	return h;
}
#endif

static int b2FindSlot( const b2HashSet* set, uint64_t key, uint64_t hash )
{
#if B2_SNOOP_TABLE_COUNTERS
	b2AtomicFetchAddInt( &b2_findCount, 1 );
#endif

	uint32_t capacity = set->capacity;
	uint32_t index = (uint32_t)hash & ( capacity - 1 );
	const b2SetItem* items = set->items;
	while ( items[index].key != 0 && items[index].key != key )
	{
#if B2_SNOOP_TABLE_COUNTERS
		b2AtomicFetchAddInt( &b2_probeCount, 1 );
#endif
		index = ( index + 1 ) & ( capacity - 1 );
	}

	return index;
}

static void b2AddKeyHaveCapacity( b2HashSet* set, uint64_t key, uint64_t hash )
{
	int index = b2FindSlot( set, key, hash );
	b2SetItem* items = set->items;

	B2_ASSERT( items[index].key == 0 );
	items[index].key = key;
	set->count += 1;
}

static void b2GrowTable( b2HashSet* set )
{
	uint32_t oldCount = set->count;
	B2_UNUSED( oldCount );

	uint32_t oldCapacity = set->capacity;
	b2SetItem* oldItems = set->items;

	set->count = 0;
	// Capacity must be a power of 2
	set->capacity = 2 * oldCapacity;
	set->items = b2Alloc( set->capacity * sizeof( b2SetItem ) );
	memset( set->items, 0, set->capacity * sizeof( b2SetItem ) );

	// Transfer items into new array
	for ( uint32_t i = 0; i < oldCapacity; ++i )
	{
		b2SetItem* item = oldItems + i;
		if ( item->key == 0 )
		{
			// this item was empty
			continue;
		}

		uint64_t hash = b2KeyHash( item->key );
		b2AddKeyHaveCapacity( set, item->key, hash );
	}

	B2_ASSERT( set->count == oldCount );

	b2Free( oldItems, oldCapacity * sizeof( b2SetItem ) );
}

bool b2ContainsKey( const b2HashSet* set, uint64_t key )
{
	// key of zero is a sentinel
	B2_ASSERT( key != 0 );
	uint64_t hash = b2KeyHash( key );
	int index = b2FindSlot( set, key, hash );
	return set->items[index].key == key;
}

int b2GetHashSetBytes( b2HashSet* set )
{
	return set->capacity * (int)sizeof( b2SetItem );
}

bool b2AddKey( b2HashSet* set, uint64_t key )
{
	// key of zero is a sentinel
	B2_ASSERT( key != 0 );

	uint64_t hash = b2KeyHash( key );
	B2_ASSERT( hash != 0 );

	int index = b2FindSlot( set, key, hash );
	if ( set->items[index].key != 0 )
	{
		// Already in set
		B2_ASSERT( set->items[index].key == key );
		return true;
	}

	if ( 2 * set->count >= set->capacity )
	{
		b2GrowTable( set );
	}

	b2AddKeyHaveCapacity( set, key, hash );
	return false;
}

// See https://en.wikipedia.org/wiki/Open_addressing
bool b2RemoveKey( b2HashSet* set, uint64_t key )
{
	uint64_t hash = b2KeyHash( key );
	int i = b2FindSlot( set, key, hash );
	b2SetItem* items = set->items;
	if ( items[i].key == 0 )
	{
		// Not in set
		return false;
	}

	// Mark item i as unoccupied
	items[i].key = 0;

	B2_ASSERT( set->count > 0 );
	set->count -= 1;

	// Attempt to fill item i
	int j = i;
	uint32_t capacity = set->capacity;
	for ( ;; )
	{
		j = ( j + 1 ) & ( capacity - 1 );
		if ( items[j].key == 0 )
		{
			break;
		}

		// k is the first item for the hash of j
		uint64_t hash_j = b2KeyHash( items[j].key );
		int k = hash_j & ( capacity - 1 );

		// determine if k lies cyclically in (i,j]
		// i <= j: | i..k..j |
		// i > j: |.k..j  i....| or |....j     i..k.|
		if ( i <= j )
		{
			if ( i < k && k <= j )
			{
				continue;
			}
		}
		else
		{
			if ( i < k || k <= j )
			{
				continue;
			}
		}

		// Move j into i
		items[i] = items[j];

		// Mark item j as unoccupied
		items[j].key = 0;

		i = j;
	}

	return true;
}

// This function is here because ctz.h is included by
// this file but not in bitset.c
int b2CountSetBits( b2BitSet* bitSet )
{
	int popCount = 0;
	uint32_t blockCount = bitSet->blockCount;
	for ( uint32_t i = 0; i < blockCount; ++i )
	{
		popCount += b2PopCount64( bitSet->bits[i] );
	}

	return popCount;
}