0,0 → 1,350 |
// 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 |
int cdict_init(CDict *s); |
|
/// Initializes dictionary structure with non-standard user data |
int cdict_init_ud(CDict *s, CDICT_USER_DATA_T user_data); |
|
/// Initializes dictionary structure with non-standard user data |
int cdict_init_pud(CDict *s, CDICT_USER_DATA_T *user_data); |
|
/// Inserts a value by key (receives pointers to val and key) |
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) |
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) |
CDICT_VAL_T cdict_get_p(CDict *s, CDICT_KEY_T *pkey); |
|
/// Gives a vaule by key (receives a value of key) |
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 |
|
#ifdef CDICT_HASHTAB_ITEM_ALLOCATORS_OVERRIDDEN |
#error "FUCK!" |
#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; |
} |
|
int cdict_init(CDict *s) { |
return cdict_init_pud(s, NULL); |
} |
|
int cdict_init_ud(CDict *s, CDICT_USER_DATA_T user_data) { |
return cdict_init_pud(s, &user_data); |
} |
|
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; |
} |
|
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; |
} |
|
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); |
} |
|
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; |
} |
|
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 |