<commit_before>/*
 * hashmap.c
 * Sparkling, a lightweight C-style scripting language
 *
 * Created by <NAME> on 26/09/2014
 * Licensed under the 2-clause BSD License
 *
 * Hash map - arbitrary discrete map from and to SpnValues
 */

#include <limits.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#include "hashmap.h"
#include "str.h"
#include "private.h"


typedef struct Bucket {
	SpnValue key;
	SpnValue value;
} Bucket;

static int bucket_is_used(const Bucket *bucket)
{
	/* nil key with non-nil val (or vice versa) is not allowed */
	assert(isnil(&bucket->key) == isnil(&bucket->value));
	return notnil(&bucket->key);
}

static int bucket_is_empty(const Bucket *bucket)
{
	assert(isnil(&bucket->key) == isnil(&bucket->value));
	return isnil(&bucket->key);
}

/* retains key and value */
static void insert_into_bucket(
	Bucket *bucket,
	const SpnValue *key,
	const SpnValue *value,
	int should_retain
)
{
	assert(bucket_is_empty(bucket));
	assert(notnil(key));
	assert(notnil(value));

	if (should_retain) {
		spn_value_retain(key);
		spn_value_retain(value);
	}

	bucket->key = *key;
	bucket->value = *value;
}

static void erase_bucket(Bucket *bucket)
{
	assert(bucket_is_used(bucket));

	/* relinquish ownership of key and value (RAII/DIRR),
	 * then clean them by setting them to nil.
	 */
	spn_value_release(&bucket->key);
	spn_value_release(&bucket->value);

	bucket->key = spn_nilval;
	bucket->value = spn_nilval;
}

struct SpnHashMap {
	SpnObject  base;
	Bucket    *buckets;         /* actual array for key-value pairs           */
	size_t     allocsize;       /* number of buckets                          */
	size_t     count;           /* number of key-value pairs                  */
	size_t     max_hash_offset; /* global upper bound on number of collisions */
};

static void free_hashmap(void *obj);
static void free_bucket_array(Bucket *buckets, size_t n);
static void expand_and_rehash(SpnHashMap *hm);


static const SpnClass spn_class_hashmap = {
	sizeof(SpnHashMap),
	SPN_CLASS_UID_HASHMAP,
	NULL,
	NULL,
	NULL,
	free_hashmap
};


SpnHashMap *spn_hashmap_new()
{
	SpnHashMap *hm = spn_object_new(&spn_class_hashmap);

	hm->buckets = NULL;
	hm->allocsize = 0;
	hm->count = 0;
	hm->max_hash_offset = 0;

	return hm;
}

static void free_hashmap(void *obj)
{
	SpnHashMap *hm = obj;
	free_bucket_array(hm->buckets, hm->allocsize);
}

size_t spn_hashmap_count(SpnHashMap *hm)
{
	return hm->count;
}

SpnValue spn_makehashmap(void)
{
	SpnValue val;
	val.type = SPN_TYPE_HASHMAP;
	val.v.o = spn_hashmap_new();
	return val;
}


/* Internal functions */

static size_t modulo_mask(SpnHashMap *hm)
{
	/* cannot index into empty table; allocsize must be a power of two */
	assert(hm->allocsize > 0 && !(hm->allocsize & (hm->allocsize - 1)));
	return hm->allocsize - 1;
}

static size_t hash_index(SpnHashMap *hm, const SpnValue *key)
{
	return spn_hash_value(key) & modulo_mask(hm);
}

static int should_rehash(SpnHashMap *hm)
{
	/* keep load factor below 0.75 */
	return hm->allocsize == 0 || hm->count > hm->allocsize * 3 / 4;
}

/* Returns a pointer to the bucket containing 'key',
 * or NULL if the key is not in the hash table.
 */
static Bucket *find_key(SpnHashMap *hm, const SpnValue *key)
{
	size_t h, hash_offset;

	/* do not try dividing by zero;
	 * there are no entries in an empty table.
	 */
	if (hm->allocsize == 0) {
		return NULL;
	}

	/* linear probing */
	h = hash_index(hm, key);
	hash_offset = 0;

	do {
		/* only occupied buckets may contain a key-value pair */
		if (bucket_is_used(&hm->buckets[h])
		 && spn_value_equal(&hm->buckets[h].key, key)) {
			return &hm->buckets[h];
		}

		/* wrap around end of bucket array if necessary */
		h = (h + 1) & modulo_mask(hm);
		hash_offset++;
	} while (hash_offset <= hm->max_hash_offset);

	/* key was not found */
	return NULL;
}

void insert_nonexistent_norehash(
	SpnHashMap *hm,
	const SpnValue *key,
	const SpnValue *value,
	int should_retain
)
{
	size_t h, hash_offset;

	assert(should_rehash(hm) == 0);    /* table must be large enough  */
	assert(hm->count < hm->allocsize); /* there must be empty buckets */
	assert(find_key(hm, key) == NULL); /* the key must not exist yet  */

	h = hash_index(hm, key);
	hash_offset = 0;

	/* find an empty bucket */
	while (bucket_is_used(&hm->buckets[h])) {
		h = (h + 1) & modulo_mask(hm);
		hash_offset++;
	}

	insert_into_bucket(&hm->buckets[h], key, value, should_retain);
	assert(bucket_is_used(&hm->buckets[h]));

	hm->count++;

	if (hash_offset > hm->max_hash_offset) {
		hm->max_hash_offset = hash_offset;<commit_msg>that one does not need to be public<commit_after>/*
 * hashmap.c
 * Sparkling, a lightweight C-style scripting language
 *
 * Created by <NAME> on 26/09/2014
 * Licensed under the 2-clause BSD License
 *
 * Hash map - arbitrary discrete map from and to SpnValues
 */

#include <limits.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

#include "hashmap.h"
#include "str.h"
#include "private.h"


typedef struct Bucket {
	SpnValue key;
	SpnValue value;
} Bucket;

static int bucket_is_used(const Bucket *bucket)
{
	/* nil key with non-nil val (or vice versa) is not allowed */
	assert(isnil(&bucket->key) == isnil(&bucket->value));
	return notnil(&bucket->key);
}

static int bucket_is_empty(const Bucket *bucket)
{
	assert(isnil(&bucket->key) == isnil(&bucket->value));
	return isnil(&bucket->key);
}

/* retains key and value */
static void insert_into_bucket(
	Bucket *bucket,
	const SpnValue *key,
	const SpnValue *value,
	int should_retain
)
{
	assert(bucket_is_empty(bucket));
	assert(notnil(key));
	assert(notnil(value));

	if (should_retain) {
		spn_value_retain(key);
		spn_value_retain(value);
	}

	bucket->key = *key;
	bucket->value = *value;
}

static void erase_bucket(Bucket *bucket)
{
	assert(bucket_is_used(bucket));

	/* relinquish ownership of key and value (RAII/DIRR),
	 * then clean them by setting them to nil.
	 */
	spn_value_release(&bucket->key);
	spn_value_release(&bucket->value);

	bucket->key = spn_nilval;
	bucket->value = spn_nilval;
}

struct SpnHashMap {
	SpnObject  base;
	Bucket    *buckets;         /* actual array for key-value pairs           */
	size_t     allocsize;       /* number of buckets                          */
	size_t     count;           /* number of key-value pairs                  */
	size_t     max_hash_offset; /* global upper bound on number of collisions */
};

static void free_hashmap(void *obj);
static void free_bucket_array(Bucket *buckets, size_t n);
static void expand_and_rehash(SpnHashMap *hm);


static const SpnClass spn_class_hashmap = {
	sizeof(SpnHashMap),
	SPN_CLASS_UID_HASHMAP,
	NULL,
	NULL,
	NULL,
	free_hashmap
};


SpnHashMap *spn_hashmap_new()
{
	SpnHashMap *hm = spn_object_new(&spn_class_hashmap);

	hm->buckets = NULL;
	hm->allocsize = 0;
	hm->count = 0;
	hm->max_hash_offset = 0;

	return hm;
}

static void free_hashmap(void *obj)
{
	SpnHashMap *hm = obj;
	free_bucket_array(hm->buckets, hm->allocsize);
}

size_t spn_hashmap_count(SpnHashMap *hm)
{
	return hm->count;
}

SpnValue spn_makehashmap(void)
{
	SpnValue val;
	val.type = SPN_TYPE_HASHMAP;
	val.v.o = spn_hashmap_new();
	return val;
}


/* Internal functions */

static size_t modulo_mask(SpnHashMap *hm)
{
	/* cannot index into empty table; allocsize must be a power of two */
	assert(hm->allocsize > 0 && !(hm->allocsize & (hm->allocsize - 1)));
	return hm->allocsize - 1;
}

static size_t hash_index(SpnHashMap *hm, const SpnValue *key)
{
	return spn_hash_value(key) & modulo_mask(hm);
}

static int should_rehash(SpnHashMap *hm)
{
	/* keep load factor below 0.75 */
	return hm->allocsize == 0 || hm->count > hm->allocsize * 3 / 4;
}

/* Returns a pointer to the bucket containing 'key',
 * or NULL if the key is not in the hash table.
 */
static Bucket *find_key(SpnHashMap *hm, const SpnValue *key)
{
	size_t h, hash_offset;

	/* do not try dividing by zero;
	 * there are no entries in an empty table.
	 */
	if (hm->allocsize == 0) {
		return NULL;
	}

	/* linear probing */
	h = hash_index(hm, key);
	hash_offset = 0;

	do {
		/* only occupied buckets may contain a key-value pair */
		if (bucket_is_used(&hm->buckets[h])
		 && spn_value_equal(&hm->buckets[h].key, key)) {
			return &hm->buckets[h];
		}

		/* wrap around end of bucket array if necessary */
		h = (h + 1) & modulo_mask(hm);
		hash_offset++;
	} while (hash_offset <= hm->max_hash_offset);

	/* key was not found */
	return NULL;
}

static void insert_nonexistent_norehash(
	SpnHashMap *hm,
	const SpnValue *key,
	const SpnValue *value,
	int should_retain
)
{
	size_t h, hash_offset;

	assert(should_rehash(hm) == 0);    /* table must be large enough  */
	assert(hm->count < hm->allocsize); /* there must be empty buckets */
	assert(find_key(hm, key) == NULL); /* the key must not exist yet  */

	h = hash_index(hm, key);
	hash_offset = 0;

	/* find an empty bucket */
	while (bucket_is_used(&hm->buckets[h])) {
		h = (h + 1) & modulo_mask(hm);
		hash_offset++;
	}

	insert_into_bucket(&hm->buckets[h], key, value, should_retain);
	assert(bucket_is_used(&hm->buckets[h]));

	hm->count++;

	if (hash_offset > hm->max_hash_offset) {
		hm->max_hash_offset = hash_offset;
{'fraction_non_alphanumeric': 0.13536121673003804, 'fraction_numerical': 0.005866376969038566, 'mean_word_length': 3.79229567933368, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 99, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3655701', 'n_tokens_mistral': 3563, 'n_tokens_neox': 3391, 'n_words': 885}