Question

Currently I am learning about set theory. I am trying to implement a set using a hashtable with singly linked lists. I am very confused as to where I should start, as many of the online resources reference basically hash table implementations. How would I go about a template to implement the very basic structures needed for the set in C? Just confused as to where to start.

Currently this is my current structure:

typedef struct s_entry t char *key void *valu struct s entry *next; SEntry typedef struct s_data t long size; long capacity; long changes double load; double loadFactor double increment; SEntry **buckets; SData;

Answer 1

set.h

#ifndef SIMPLE_SET_H__
#define SIMPLE_SET_H__

#include <inttypes.h>       /* uint64_t */

typedef uint64_t (*set_hash_function) (char *key);

typedef struct {
    char* _key;
    uint64_t _hash;
} SimpleSetNode, simple_set_node;

typedef struct {
    simple_set_node **nodes;
    uint64_t number_nodes;
    uint64_t used_nodes;
    set_hash_function hash_function;
} SimpleSet, simple_set;

/* Initialize the set with default values */
int set_init(SimpleSet *set);

/* Initialize the set with a different hash function */
int set_init_alt(SimpleSet *set, set_hash_function hash);

/* Utility function to clear out the set */
int set_clear(SimpleSet *set);

/* Free memory */
int set_destroy(SimpleSet *set);

/* Add element to set, returns SET_TRUE if added, SET_FALSE if already
    present, SET_ALREADY_PRESENT, or SET_CIRCULAR_ERROR if set is
    completely full */
int set_add(SimpleSet *set, char *key);

/* Remove element from the set; Returns SET_TRUE if removed, SET_FALSE if
    not present */
int set_remove(SimpleSet *set, char *key);

/* Check if key in hash; Returns SET_TRUE if present, SET_FALSE if not
    found, or SET_CIRCULAR_ERROR if set is full and not found */
int set_contains(SimpleSet *set, char *key);

/* Return the number of elements in the set */
uint64_t set_length(SimpleSet *set);

/* Set res to the union of s1 and s2
    res = s1 ∪ s2
    The union of a set A with a B is the set of elements that are in either
    set A or B. The union is denoted as A ∪ B */
int set_union(SimpleSet *res, SimpleSet *s1, SimpleSet *s2);

/* Set res to the intersection of s1 and s2
    res = s1 ∩ s2
    The intersection of a set A with a B is the set of elements that are in
    both set A and B. The intersection is denoted as A ∩ B */
int set_intersection(SimpleSet *res, SimpleSet *s1, SimpleSet *s2);

/* Set res to the difference between s1 and s2
    res = s1∖ s2
    The set difference between two sets A and B is written A ∖ B, and means
    the set that consists of the elements of A which are not elements
    of B: x ∈ A ∖ B ⟺ x ∈ A ∧ x ∉ B. Another frequently seen notation
    for S ∖ T is S − T. */
int set_difference(SimpleSet *res, SimpleSet *s1, SimpleSet *s2);

/* Set res to the symmetric difference between s1 and s2
    res = s1 △ s2
    The symmetric difference of two sets A and B is the set of elements either
    in A or in B but not in both. Symmetric difference is denoted
    A △ B or A * B */
int set_symmetric_difference(SimpleSet *res, SimpleSet *s1, SimpleSet *s2);

/* Return SET_TRUE if test is fully contained in s2; returns SET_FALSE
    otherwise
    test ⊆ against
    A set A is a subset of another set B if all elements of the set A are
    elements of the set B. In other words, the set A is contained inside
    the set B. The subset relationship is denoted as A ⊆ B */
int set_is_subset(SimpleSet *test, SimpleSet *against);

/* Inverse of subset; return SET_TRUE if set test fully contains
    (including equal to) set against; return SET_FALSE otherwise
    test ⊇ against
    Superset Definition: A set A is a superset of another set B if all
    elements of the set B are elements of the set A. The superset
    relationship is denoted as A ⊇ B */
int set_is_superset(SimpleSet *test, SimpleSet *against);

/* Strict subset ensures that the test is a subset of against, but that
    the two are also not equal.
    test ⊂ against
    Set A is a strict subset of another set B if all elements of the set A
    are elements of the set B. In other words, the set A is contained inside
    the set B. A ≠ B is required. The strict subset relationship is denoted
    as A ⊂ B */
int set_is_subset_strict(SimpleSet *test, SimpleSet *against);

/* Strict superset ensures that the test is a superset of against, but that
    the two are also not equal.
    test ⊃ against
    Strict Superset Definition: A set A is a superset of another set B if
    all elements of the set B are elements of the set A. A ≠ B is required.
    The superset relationship is denoted as A ⊃ B */
int set_is_superset_strict(SimpleSet *test, SimpleSet *against);

/* Return an array of the elements in the set
    NOTE: Up to the caller to free the memory */
char** set_to_array(SimpleSet *set, uint64_t *size);

/* Returns based on number elements:
    -1 if left is less than right
    1 if right is less than left
    0 if left is the same size as right and keys match
    2 if size is the same but elements are different */
int set_cmp(SimpleSet *left, SimpleSet *right);

#define SET_TRUE 0
#define SET_FALSE -1
#define SET_MALLOC_ERROR -2
#define SET_CIRCULAR_ERROR -3
#define SET_OCCUPIED_ERROR -4
#define SET_ALREADY_PRESENT 1

#define SET_RIGHT_GREATER -1
#define SET_LEFT_GREATER 1
#define SET_EQUAL 0
#define SET_UNEQUAL 2

#endif /* END SIMPLE SET HEADER */

set.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "set.h"

#define INITIAL_NUM_ELEMENTS 1024
#define MAX_FULLNESS_PERCENT 0.25       /* arbitrary */

/* PRIVATE FUNCTIONS */
static uint64_t __default_hash(char *key);
static int __get_index(SimpleSet *set, char *key, uint64_t hash, uint64_t *index);
static int __assign_node(SimpleSet *set, char *key, uint64_t hash, uint64_t index);
static void __free_index(SimpleSet *set, uint64_t index);
static int __set_contains(SimpleSet *set, char *key, uint64_t hash);
static int __set_add(SimpleSet *set, char *key, uint64_t hash);
static void __relayout_nodes(SimpleSet *set, uint64_t start, short end_on_null);
static void __set_clear(SimpleSet *set);

/*******************************************************************************
***        FUNCTIONS DEFINITIONS
*******************************************************************************/

int set_init(SimpleSet *set) {
    return set_init_alt(set, NULL);
}

int set_init_alt(SimpleSet *set, set_hash_function hash) {
    set->nodes = (simple_set_node**) malloc(INITIAL_NUM_ELEMENTS * sizeof(simple_set_node*));
    if (set->nodes == NULL) {
        return SET_MALLOC_ERROR;
    }
    set->number_nodes = INITIAL_NUM_ELEMENTS;
    uint64_t i;
    for (i = 0; i < set->number_nodes; i++) {
        set->nodes[i] = NULL;
    }
    set->used_nodes = 0;
    set->hash_function = (hash == NULL) ? &__default_hash : hash;
    return SET_TRUE;
}

int set_clear(SimpleSet *set) {
    __set_clear(set);
    return SET_TRUE;
}

int set_destroy(SimpleSet *set) {
    __set_clear(set);
    free(set->nodes);
    set->number_nodes = 0;
    set->used_nodes = 0;
    set->hash_function = NULL;
    return SET_TRUE;
}

int set_add(SimpleSet *set, char *key) {
    uint64_t hash = set->hash_function(key);
    return __set_add(set, key, hash);
}

int set_contains(SimpleSet *set, char *key) {
    uint64_t index, hash = set->hash_function(key);
    return __get_index(set, key, hash, &index);
}

int set_remove(SimpleSet *set, char *key) {
    uint64_t index, hash = set->hash_function(key);
    int pos = __get_index(set, key, hash, &index);
    if (pos != SET_TRUE) {
        return pos;
    }
    // remove this node
    __free_index(set, index);
    // re-layout nodes
    __relayout_nodes(set, index, 0);
    set->used_nodes--;
    return SET_TRUE;
}

uint64_t set_length(SimpleSet *set) {
    return set->used_nodes;
}

char** set_to_array(SimpleSet *set, uint64_t *size) {
    *size = set->used_nodes;
    char** results = malloc(set->used_nodes * sizeof(char*));
    uint64_t i, j = 0;
    size_t len;
    for (i = 0; i < set->number_nodes; i++) {
        if (set->nodes[i] != NULL) {
            len = strlen(set->nodes[i]->_key);
            results[j] = calloc(len + 1, sizeof(char));
            memcpy(results[j], set->nodes[i]->_key, len);
            j++;
        }
    }
    return results;
}

int set_union(SimpleSet *res, SimpleSet *s1, SimpleSet *s2) {
    if (res->used_nodes != 0) {
        return SET_OCCUPIED_ERROR;
    }
    // loop over both s1 and s2 and get keys and insert them into res
    uint64_t i;
    for (i = 0; i < s1->number_nodes; i++) {
        if (s1->nodes[i] != NULL) {
            __set_add(res, s1->nodes[i]->_key, s1->nodes[i]->_hash);
        }
    }
    for (i = 0; i < s2->number_nodes; i++) {
        if (s2->nodes[i] != NULL) {
            __set_add(res, s2->nodes[i]->_key, s2->nodes[i]->_hash);
        }
    }
    return SET_TRUE;
}

int set_intersection(SimpleSet *res, SimpleSet *s1, SimpleSet *s2) {
    if (res->used_nodes != 0) {
        return SET_OCCUPIED_ERROR;
    }
    // loop over both one of s1 and s2: get keys, check the other, and insert them into res if it is
    uint64_t i;
    for (i = 0; i < s1->number_nodes; i++) {
        if (s1->nodes[i] != NULL) {
            if (__set_contains(s2, s1->nodes[i]->_key, s1->nodes[i]->_hash) == SET_TRUE) {
                __set_add(res, s1->nodes[i]->_key, s1->nodes[i]->_hash);
            }
        }
    }
    return SET_TRUE;
}

/* difference is s1 - s2 */
int set_difference(SimpleSet *res, SimpleSet *s1, SimpleSet *s2) {
    if (res->used_nodes != 0) {
        return SET_OCCUPIED_ERROR;
    }
    // loop over s1 and keep only things not in s2
    uint64_t i;
    for (i = 0; i < s1->number_nodes; i++) {
        if (s1->nodes[i] != NULL) {
            if (__set_contains(s2, s1->nodes[i]->_key, s1->nodes[i]->_hash) != SET_TRUE) {
                __set_add(res, s1->nodes[i]->_key, s1->nodes[i]->_hash);
            }
        }
    }
    return SET_TRUE;
}

int set_symmetric_difference(SimpleSet *res, SimpleSet *s1, SimpleSet *s2) {
    if (res->used_nodes != 0) {
        return SET_OCCUPIED_ERROR;
    }
    uint64_t i;
    // loop over set 1 and add elements that are unique to set 1
    for (i = 0; i < s1->number_nodes; i++) {
        if (s1->nodes[i] != NULL) {
            if (__set_contains(s2, s1->nodes[i]->_key, s1->nodes[i]->_hash) != SET_TRUE) {
                __set_add(res, s1->nodes[i]->_key, s1->nodes[i]->_hash);
            }
        }
    }
    // loop over set 2 and add elements that are unique to set 2
    for (i = 0; i < s2->number_nodes; i++) {
        if (s2->nodes[i] != NULL) {
            if (__set_contains(s1, s2->nodes[i]->_key, s2->nodes[i]->_hash) != SET_TRUE) {
                __set_add(res, s2->nodes[i]->_key, s2->nodes[i]->_hash);
            }
        }
    }
    return SET_TRUE;
}

int set_is_subset(SimpleSet *test, SimpleSet *against) {
    uint64_t i;
    for (i = 0; i < test->number_nodes; i++) {
        if (test->nodes[i] != NULL) {
            if (__set_contains(against, test->nodes[i]->_key, test->nodes[i]->_hash) == SET_FALSE) {
                return SET_FALSE;
            }
        }
    }
    return SET_TRUE;
}

int set_is_subset_strict(SimpleSet *test, SimpleSet *against) {
    if (test->used_nodes >= against->used_nodes) {
        return SET_FALSE;
    }
    return set_is_subset(test, against);
}

int set_is_superset(SimpleSet *test, SimpleSet *against) {
    return set_is_subset(against, test);
}

int set_is_superset_strict(SimpleSet *test, SimpleSet *against) {
    return set_is_subset_strict(against, test);
}

int set_cmp(SimpleSet *left, SimpleSet *right) {
    if (left->used_nodes < right->used_nodes) {
        return -1;
    } else if (right->used_nodes < left->used_nodes) {
        return 1;
    }
    uint64_t i;
    for (i = 0; i < left->number_nodes; i++) {
        if (left->nodes[i] != NULL) {
            if (set_contains(right, left->nodes[i]->_key) != SET_TRUE) {
                return 2;
            }
        }
    }

    return 0;
}

/*******************************************************************************
***        PRIVATE FUNCTIONS
*******************************************************************************/
static uint64_t __default_hash(char *key) {
    // FNV-1a hash (http://www.isthe.com/chongo/tech/comp/fnv/)
    size_t i, len = strlen(key);
    char *p = calloc(len + 1, sizeof(char));
    memcpy(p, key, len);
    uint64_t h = 14695981039346656073ULL; // FNV_OFFSET 64 bit
    for (i = 0; i < len; i++){
        h = h ^ (unsigned char) p[i];
        h = h * 1099511628211ULL; // FNV_PRIME 64 bit
    }
    free(p);
    return h;
}

static int __set_contains(SimpleSet *set, char *key, uint64_t hash) {
    uint64_t index;
    return __get_index(set, key, hash, &index);
}

static int __set_add(SimpleSet *set, char *key, uint64_t hash) {
    uint64_t index;
    if (__set_contains(set, key, hash) == SET_TRUE) {
        return SET_ALREADY_PRESENT;
    }
    // Expand nodes if we are close to our desired fullness
    if ((float)set->used_nodes / set->number_nodes > MAX_FULLNESS_PERCENT) {
        uint64_t num_els = set->number_nodes * 2; // we want to double each time
        simple_set_node** tmp = realloc(set->nodes, num_els * sizeof(simple_set_node*));
        if (tmp == NULL || set->nodes == NULL) { // malloc failure
            return SET_MALLOC_ERROR;
        }
        set->nodes = tmp;
        uint64_t i, orig_num_els = set->number_nodes;
        for (i = orig_num_els; i < num_els; i++) {
            set->nodes[i] = NULL;
        }
        set->number_nodes = num_els;
        // re-layout all nodes
        __relayout_nodes(set, 0, 1);
    }
    // add element in
    int res = __get_index(set, key, hash, &index);
    if (res == SET_FALSE) { // this is the first open slot
        __assign_node(set, key, hash, index);
        set->used_nodes++;
        return SET_TRUE;
    } else {
        return res;
    }
}

static int __get_index(SimpleSet *set, char *key, uint64_t hash, uint64_t *index) {
    uint64_t i, idx;
    idx = hash % set->number_nodes;
    i = idx;
    size_t len = strlen(key);
    while (1) {
        if (set->nodes[i] == NULL) {
            *index = i;
            return SET_FALSE; // not here OR first open slot
        } else if (hash == set->nodes[i]->_hash && len == strlen(set->nodes[i]->_key) && strncmp(key, set->nodes[i]->_key, len) == 0) {
            *index = i;
            return SET_TRUE;
        } else {
            i++;
            if (i == set->number_nodes) {
                i = 0;
            }

            if (i == idx) { // this means we went all the way around and the set is full
                return SET_CIRCULAR_ERROR;
            }
        }
    }
}

static int __assign_node(SimpleSet *set, char *key, uint64_t hash, uint64_t index) {
    size_t len = strlen(key);
    set->nodes[index] = malloc(sizeof(simple_set_node));
    set->nodes[index]->_key = calloc(len + 1, sizeof(char));
    memcpy(set->nodes[index]->_key, key, len);
    set->nodes[index]->_hash = hash;
    return SET_TRUE;
}

static void __free_index(SimpleSet *set, uint64_t index) {
    free(set->nodes[index]->_key);
    free(set->nodes[index]);
    set->nodes[index] = NULL;
}

static void __relayout_nodes(SimpleSet *set, uint64_t start, short end_on_null) {
    uint64_t index = 0, i;
    for (i = start; i < set->number_nodes; i++) {
        if(set->nodes[i] != NULL) {
            __get_index(set, set->nodes[i]->_key, set->nodes[i]->_hash, &index);
            if (i != index) { // we are moving this node
                __assign_node(set, set->nodes[i]->_key, set->nodes[i]->_hash, index);
                __free_index(set, i);
            }
        } else if (end_on_null == 0 && i != start) {
            break;
        }
    }
}

static void __set_clear(SimpleSet *set) {
    uint64_t i;
    for(i = 0; i < set->number_nodes; i++) {
        if (set->nodes[i] != NULL) {
            __free_index(set, i);
        }
    }
    set->used_nodes = 0;
}