Skip to content

Instantly share code, notes, and snippets.

@modimore

modimore/set_u32.c

Created Sep 20, 2018
Embed
What would you like to do?
Set for unsigned 32-bit integers in 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;
}
/**
* 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment