cdict.h

// Copyright (c) 2020 Magomed Kostoev
//
// You may use, distribute and modify this code under the terms of the MIT license.
//
// You should have received a copy of the MIT license with this file. If not, please visit
// https://opensource.org/licenses/MIT or boppan.org/MIT for full license details.

// cdict.h - simple dictionaty implementation in C.
//
// Uses hash table with fixed (but configurable) size. Functions named using given type names:
// cdict_<CDICT_KEY_T>_<CDICT_VAL_T>_<name>.
//
// See configuration below (in public "Input macros" section), also:
// CDICT_INST: Instantiate the functions if defined.
//
// Minimal definitions for declaration: CDICT_KEY_T, CDICT_VAL_T
// Minimal definitions for instantiation: CDICT_INST, CDICT_KEY_T, CDICT_VAL_T, CDICT_HASH_FN,
// CDICT_CMP_FN
//
// WARNING: All used definitions will be undefined on header exit.
//
// Dependencies:
//  <stddef.h> or another source of size_t
//  <stdlib.h> or another source of malloc, and calloc
//  <assert.h> or another source of assert

//
// Internal macros for external declarations
//

#define CDICT_CAT2_IMPL(x, y) x ## _ ## y
#define CDICT_CAT2(x, y) CDICT_CAT2_IMPL(x, y)

/// Creates method name according to CDICT_KEY_T and CDICT_VAL_T
#define CDICT_FUN(name) CDICT_CAT2(cdict, CDICT_CAT2(CDICT_KEY_T, CDICT_CAT2(CDICT_VAL_T, name)))

#define cdict_init CDICT_FUN(init)
#define cdict_init_ud CDICT_FUN(init_ud)
#define cdict_init_pud CDICT_FUN(init_pud)
#define cdict_add_pp CDICT_FUN(add_pp)
#define cdict_add_vv CDICT_FUN(add_vv)
#define cdict_get_p CDICT_FUN(get_p)
#define cdict_get_v CDICT_FUN(get_v)
#define cdict_error_message CDICT_FUN(error_message)

#define cdict_hash CDICT_FUN(hash)
#define cdict_keycmp CDICT_FUN(keycmp)
#define cdict_chain_begin CDICT_FUN(begin)
#define cdict_chain_next CDICT_FUN(next)

#define CDictItem CDICT_CAT2(CDictItem, CDICT_CAT2(CDICT_KEY_T, CDICT_VAL_T))
#define CDictItem_s CDICT_CAT2(CDictItem_s, CDICT_CAT2(CDICT_KEY_T, CDICT_VAL_T))
#define CDict CDICT_CAT2(CDict, CDICT_CAT2(CDICT_KEY_T, CDICT_VAL_T))

//
// Input macros
//

/// Type of the dictionary's keys, named type only - used in functions names, default: CStr
#ifndef CDICT_KEY_T
typedef char *CStr;
#define CDICT_CSTR_IS_THERE
#define CDICT_KEY_T CStr
#endif

/// Type of the dictionary's values, named type only - used in functions names, default: CStr
#ifndef CDICT_VAL_T
#ifndef CDICT_CSTR_IS_THERE
typedef char *CStr;
#endif
#define CDICT_VAL_T CStr
#endif

/// Type of user data
#ifndef CDICT_USER_DATA_T
#define CDICT_USER_DATA_T void *
#endif

//
// Public interface
//

#define CDICT_NO_CHECK 0
#define CDICT_REPLACE_EXIST 1
#define CDICT_LEAVE_EXIST 2

#define CDICT_ERR_SUCCESS 0
#define CDICT_ERR_OUT_OF_MEMORY 1
#define CDICT_ERR_THIS_IS_NULL 2
#define CDICT_ERR_HASH_TABLE_IS_NULL 3
#define CDICT_ERR_PKEY0_IS_NULL 4
#define CDICT_ERR_PKEY1_IS_NULL 5
#define CDICT_ERR_PKEY_IS_NULL 6
#define CDICT_ERR_PVAL_IS_NULL 7

typedef struct CDictItem_s {
    struct CDictItem_s *next_collision;
    CDICT_KEY_T key;
    CDICT_VAL_T val;
} CDictItem;

typedef struct {
    CDictItem **hash_table;
    CDICT_USER_DATA_T user_data;
    int error_code;
} CDict;

/// Initializes dictionary structure
static int cdict_init(CDict *s);

/// Initializes dictionary structure with non-standard user data
static int cdict_init_ud(CDict *s, CDICT_USER_DATA_T user_data);

/// Initializes dictionary structure with non-standard user data
static int cdict_init_pud(CDict *s, CDICT_USER_DATA_T *user_data);

/// Inserts a value by key (receives pointers to val and key)
static CDictItem *cdict_add_pp(CDict *s, CDICT_KEY_T *pkey, CDICT_VAL_T *pval, int if_exists);

/// Inserts a value by key (receives values of val and key)
static CDictItem *cdict_add_vv(CDict *s, CDICT_KEY_T key, CDICT_VAL_T val, int if_exists);

/// Gives a value by key (receives a pointer to key)
static CDICT_VAL_T cdict_get_p(CDict *s, CDICT_KEY_T *pkey);

/// Gives a vaule by key (receives a value of key)
static CDICT_VAL_T cdict_get_v(CDict *s, CDICT_KEY_T key);

#ifdef CDICT_INST

//
// Input macros (instantiation edition)
//

/// The value returned on some error
#ifndef CDICT_VAL_DEFAULT
#define CDICT_VAL_DEFAULT (CDICT_VAL_T){ 0 }
#endif

/// Hashing function for the key type
#ifndef CDICT_HASH_FN
#include <string.h>
#define CDICT_HASH_FN(pkey) strlen(*pkey) ^ (*pkey)[0]
#else
#define CDICT_HASH_FN_OVERRIDEN
#endif

/// Ammount of pointers to elements in hash table
#ifndef CDICT_HASHTAB_SZ
#define CDICT_HASHTAB_SZ 1024
#endif

/// Hash table allocator MUST return zeroed buffer
#ifndef CDICT_HASHTAB_ALLOC_FN
#include <stdlib.h>
#define CDICT_HASHTAB_ALLOC_FN(cdict, size) calloc(1, size)
#else
#define CDICT_HASHTAB_ALLOCATORS_OVERRIDDEN
#endif

/// New hash table items allocator (should be just a function call)
#ifndef CDICT_HASHTAB_ITEM_ALLOC_FN
#include <stdlib.h>
#define CDICT_HASHTAB_ITEM_ALLOC_FN(cdict, size) malloc(size)
#define CDICT_HASHTAB_ITEM_FREE_FN(cdict, ptr) free(ptr)
#else
#ifndef CDICT_HASHTAB_ITEM_FREE_FN
#error "CDICT_HASHTAB_ITEM_FREE_FN should be defiend along with CDICT_HASHTAB_ITEM_ALLOC_FN"
#endif
#define CDICT_HASHTAB_ITEM_ALLOCATORS_OVERRIDDEN
#endif

/// Replacement for assert from <assert.h>
#ifndef CDICT_ASSERT_FN
#include <assert.h>
#define CDICT_ASSERT_FN(x) if (!x) { printf(__FILE__":%d: Disasserted", __LINE__); } assert(x)
#endif

/// Function for comparsion of keys, return should be the same as memcmp
#ifndef CDICT_CMP_FN
#include <string.h>
#define CDICT_CMP_FN(pkey0, pkey1) strcmp(*pkey0, *pkey1)
#else
#define CDICT_CMP_FN_OVERRIDDEN
#endif

//
// Internal macros (instantiation edition)
//

#define CDICT_ASSERT(x) ({ CDICT_ASSERT_FN(x); x; })
// Should write the error code into strucure, but should not rewrite it's already set
#define CDICT_IF_NULL_SET_ERR_RETURN(x, ec, res) if (x == NULL) {   \
        if (s->error_code == CDICT_ERR_SUCCESS) s->error_code = ec; \
        return res;                                                 \
    }
#define CDICT_IF_NULL_RETURN(x, res) if (x == NULL) return res

//
// Predeclarations
//

#ifdef CDICT_HASHTAB_ITEM_ALLOCATORS_OVERRIDDEN
void *CDICT_HASHTAB_ITEM_ALLOC_FN(CDict *s, size_t size);
void CDICT_HASHTAB_ITEM_FREE_FN(CDict *s, CDictItem *ptr);
#endif

#ifdef CDICT_HASHTAB_ALLOCATORS_OVERRIDDEN
void *CDICT_HASHTAB_ALLOC_FN(CDict *s, size_t size);
#endif

#ifdef CDICT_HASH_FN_OVERRIDEN
unsigned long CDICT_HASH_FN(CDICT_KEY_T *pkey);
#endif

#ifdef CDICT_CMP_FN_OVERRIDDEN
int CDICT_CMP_FN(CDICT_KEY_T *pkey0, CDICT_KEY_T *pkey1);
#endif

//
// The code
//

static size_t cdict_hash(CDICT_KEY_T *pkey) {
    return CDICT_HASH_FN(CDICT_ASSERT(pkey)) & (CDICT_HASHTAB_SZ - 1);
}

static int cdict_keycmp(CDICT_KEY_T *pkey0, CDICT_KEY_T *pkey1) {
    return CDICT_CMP_FN(CDICT_ASSERT(pkey0), CDICT_ASSERT(pkey1));
}

static CDictItem **cdict_chain_begin(CDict *s, CDICT_KEY_T *pkey) {
    CDICT_ASSERT(s);
    size_t hash = cdict_hash(CDICT_ASSERT(pkey));
    CDICT_IF_NULL_SET_ERR_RETURN(s->hash_table, CDICT_ERR_HASH_TABLE_IS_NULL, NULL);
    return &s->hash_table[hash];
}

static CDictItem **cdict_chain_next(CDictItem **ppit) {
    CDICT_ASSERT(ppit);
    CDICT_ASSERT(*ppit);
    return &(*ppit)->next_collision;
}

static int cdict_init(CDict *s) {
    return cdict_init_pud(s, NULL);
}

static int cdict_init_ud(CDict *s, CDICT_USER_DATA_T user_data) {
    return cdict_init_pud(s, &user_data);
}

static int cdict_init_pud(CDict *s, CDICT_USER_DATA_T *user_data) {
    CDICT_IF_NULL_RETURN(s, 0);
    s->user_data = user_data ? *user_data : (CDICT_USER_DATA_T){ 0 };
    s->error_code = CDICT_ERR_SUCCESS;
    s->hash_table = CDICT_HASHTAB_ALLOC_FN(s, sizeof(*s->hash_table) * CDICT_HASHTAB_SZ);
    CDICT_IF_NULL_SET_ERR_RETURN(s->hash_table, CDICT_ERR_OUT_OF_MEMORY, 0);
    return 1;
}

static CDictItem *cdict_add_pp(CDict *s, CDICT_KEY_T *pkey, CDICT_VAL_T *pval, int if_exists) {
    CDICT_IF_NULL_RETURN(s, NULL);
    CDICT_IF_NULL_SET_ERR_RETURN(pkey, CDICT_ERR_PKEY_IS_NULL, NULL);
    CDICT_IF_NULL_SET_ERR_RETURN(pval, CDICT_ERR_PVAL_IS_NULL, NULL);
    CDictItem *next_collision = NULL;
    CDictItem **ppit = cdict_chain_begin(s, pkey);
    CDICT_IF_NULL_RETURN(ppit, NULL);
    while (*ppit) {
        int exists = if_exists == CDICT_NO_CHECK ? 0 : !cdict_keycmp(pkey, &(*ppit)->key);
        if (exists) {
            if (if_exists == CDICT_LEAVE_EXIST) {
                return *ppit;
            } else if (if_exists == CDICT_REPLACE_EXIST) {
                next_collision = (*ppit)->next_collision;
                CDICT_HASHTAB_ITEM_FREE_FN(s, *ppit);
                break;
            }
        }
        ppit = cdict_chain_next(ppit);
    }
    *ppit = CDICT_HASHTAB_ITEM_ALLOC_FN(s, sizeof(**ppit));
    CDictItem *pit = *ppit;
    pit->key = *pkey;
    pit->val = *pval;
    pit->next_collision = next_collision;
    return pit;
}

static CDictItem *cdict_add_vv(CDict *s, CDICT_KEY_T key, CDICT_VAL_T val, int if_exists) {
    return cdict_add_pp(s, &key, &val, if_exists);
}

static CDICT_VAL_T cdict_get_p(CDict *s, CDICT_KEY_T *pkey) {
    CDICT_IF_NULL_RETURN(s, CDICT_VAL_DEFAULT);
    CDICT_IF_NULL_SET_ERR_RETURN(pkey, CDICT_ERR_PKEY_IS_NULL, CDICT_VAL_DEFAULT);
    CDictItem **ppit = cdict_chain_begin(s, pkey);
    CDICT_IF_NULL_RETURN(ppit, CDICT_VAL_DEFAULT);
    while (*ppit) {
        if (!cdict_keycmp(pkey, &(*ppit)->key)) {
            return (*ppit)->val;
        }
        ppit = cdict_chain_next(ppit);
    }
    return CDICT_VAL_DEFAULT;
}

static CDICT_VAL_T cdict_get_v(CDict *s, CDICT_KEY_T key) {
    return cdict_get_p(s, &key);
}

#endif

#undef CDICT_CAT2_IMPL
#undef CDICT_CAT2
#undef CDICT_FUN

#undef cdict_init
#undef cdict_init_ud
#undef cdict_init_pud
#undef cdict_add_pp
#undef cdict_add_vv
#undef cdict_get_p
#undef cdict_get_v

#undef CDICT_KEY_T
#undef CDICT_VAL_T
#undef CDICT_USER_DATA_T

#ifdef CDICT_INST
#undef CDICT_INST
#undef CDICT_HASH_FN
#undef CDICT_HASHTAB_SZ
#undef CDICT_HASHTAB_ALLOC_FN
#undef CDICT_HASHTAB_ITEM_ALLOC_FN
#undef CDICT_HASHTAB_ITEM_FREE_FN
#undef CDICT_ASSERT_FN
#undef CDICT_CMP_FN
#undef CDICT_ASSERT
#undef CDICT_IF_NULL_RETURN
#undef CDICT_IF_NULL_SET_ERR_RETURN
#undef CDICT_HASHTAB_ITEM_ALLOCATORS_OVERRIDDEN
#undef CDICT_HASHTAB_ALLOCATORS_OVERRIDDEN
#undef CDICT_HASH_FN_OVERRIDEN
#undef CDICT_CMP_FN_OVERRIDDEN
#endif