Set for unsigned 32-bit integers in C

set_u32.c

/**
 * Author: Quinn Mortimer
 * Date: 09/2018
 * License: MIT
 * 
 * Copyright Quinn Mortimer 09-2018
 * 
 * A definition of structs and method for interacting
 * with unique collections of integers.
 * 
 * See "set_u32.h" for function signatures, which are much
 * more concise and more relevant to the user than the contents
 * of this file.
 */
#include "set_u32.h"

#include <stdlib.h>

/** Definition of "private" set node struct */
struct set_u32_node_st {
	uint_fast32_t value;
	bool full;
	bool used;
};
typedef struct set_u32_node_st set_u32_node;

/** Definition of set struct, declared in header */
struct set_u32_st {
	size_t _filled;
	size_t _allocated;
	size_t _load_limit;
	struct set_u32_node_st * _nodes;
};

/** Declaration of "private" implementation helper functions */
uint_fast32_t hash_u32(uint_fast32_t x);
uint_fast32_t unhash_u32(uint_fast32_t h);
size_t find_index(set_u32_node * nodes, size_t size, uint_fast32_t item);
set_u32_node * allocate_nodes(size_t size);
void deallocate_nodes(set_u32_node * nodes);

/** Definitions of set interface "public" functions */
set_u32 * set_u32_create(void) {
	const int init_size = 16;
	const float load_factor = 0.75;
	set_u32 * s = (set_u32 *) malloc(sizeof(set_u32));
	s->_nodes = allocate_nodes(init_size);
	s->_allocated = init_size;
	s->_filled = 0;
	s->_load_limit = s->_allocated * load_factor;
	return s;
}

void set_u32_destroy(set_u32 * s) {
	deallocate_nodes(s->_nodes);
	s->_allocated = 0;
	s->_filled = 0;
	s->_load_limit = 0;
}

void set_u32_add(set_u32 * s, uint_fast32_t item) {
	size_t index = find_index(s->_nodes, s->_allocated, item);
	if (!s->_nodes[index].full) {
		++s->_filled;
	}
	s->_nodes[index].value = item;
	s->_nodes[index].used = true;
	s->_nodes[index].full = true;
	
	if (s->_filled > s->_load_limit) {
		set_u32_node * new_nodes = allocate_nodes(s->_allocated * 2);
		for (size_t i = 0; i < s->_allocated; ++i) {
			if (s->_nodes[i].full) {
				size_t new_index = find_index(new_nodes, s->_allocated * 2, s->_nodes[i].value);
				new_nodes[new_index].value = s->_nodes[i].value;
				new_nodes[new_index].used = true;
				new_nodes[new_index].full = true;
			}
		}
		deallocate_nodes(s->_nodes);
		s->_nodes = new_nodes;
		s->_allocated = 2 * s->_allocated;
		s->_load_limit = 0.75 * s->_allocated;
	}
}

bool set_u32_contains(set_u32 * s, uint_fast32_t item) {
	size_t index = find_index(s->_nodes, s->_allocated, item);
	return s->_nodes[index].full && (s->_nodes[index].value == item);
}

void set_u32_remove(set_u32 * s, uint_fast32_t item) {
	size_t index = find_index(s->_nodes, s->_allocated, item);
	if (s->_nodes[index].full) {
		--s->_filled;
	}
	s->_nodes[index].full = false;
}

size_t set_u32_size(set_u32 * s) {
	return s->_filled;
}

/** Definition of "private" implementation helper functions */
size_t find_index(set_u32_node * nodes, size_t size, uint_fast32_t item) {
	uint_fast32_t h = hash_u32(item);
	size_t perturb = h;
	size_t index = h % size;
	while (nodes[index].full && nodes[index].value != item) {
		index = (index * 5 + 1 + perturb) % size;
		perturb = perturb >> 4;
	}
	
	if (nodes[index].full) {
		return index;
	}
	
	size_t best_index = index;
	
	while (nodes[index].used && nodes[index].value != item) {
		index = (index * 5 + 1 + perturb) % size;
		perturb = perturb >> 4;
	}
	
	if (nodes[index].full && nodes[index].value == item) {
		return index;
	}
	return best_index;
}

set_u32_node * allocate_nodes(size_t size) {
	return (set_u32_node *) calloc(size, sizeof(set_u32_node));
}

void deallocate_nodes(set_u32_node * nodes) {
	free(nodes);
}

uint_fast32_t hash_u32(uint_fast32_t x) {
	uint_fast32_t h = x;
	h = h ^ (h>>16);
	h = h * 0xae6a495b;
	h = h ^ (h<<16);
	h = h * 0xae6a495b;
	return h;
}

uint_fast32_t unhash_u32(uint_fast32_t h) {
	uint_fast32_t x = h;
	x = x * 0xe21cbed3;
	x = x ^ (x<<16);
	x = x * 0xe21cbed3;
	x = x ^ (x>>16);
	return x;
}

set_u32.h

/**
 * Author: Quinn Mortimer
 * Date: 09/2018
 * License: MIT
 * 
 * Copyright Quinn Mortimer 09-2018
 *
 * A declaration of types and methods for interacting
 * with unique collections of integers.
 */
#ifndef SET_U32_H
#define SET_U32_H

#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>

struct set_u32_st;
typedef struct set_u32_st set_u32;

set_u32 * set_u32_create(void);
void set_u32_destroy(set_u32 *);

void set_u32_add(set_u32 *, uint_fast32_t);
bool set_u32_contains(set_u32 *, uint_fast32_t);
void set_u32_remove(set_u32 *, uint_fast32_t);
size_t set_u32_size(set_u32 *);

#endif