cdict.c

Go to the documentation of this file.

 
 
#include <cdict.h>
 
/*declare static functions*/
static void free_hash_table(WORD * hash_table);
static int cto_lower(int c);
static WORD * init_hash_table(void);
static void shuffle(WORD * table, unsigned int);
static unsigned int hashme(cdict_ctx*, char *);
static int cstr_ccmp(const char * str1, const char * str2);
/*****************************************/
 
 
static int cto_lower(int c){
    return c >= 'A' && c <= 'Z'? c + 'a' - 'A':c;
}
 
static int cstr_ccmp(const char * str1, const char * str2){
    char * s1 = (char *) str1;
    char * s2 = (char *) str2;
    while (*s1 != '\0' && *s2 != '\0' && cto_lower(*s1) == cto_lower(*s2)){
        s2++;
        s1++;
    }       
    return cto_lower(*s1) - cto_lower(*s2);
}
 
 
 
 
static WORD * init_hash_table(void){
    WORD * hash_table = (WORD *) malloc(TABLE_SIZE * sizeof(WORD));
    if (NULL == hash_table){
        return NULL;
    }
    for (unsigned long int i=0;i<TABLE_SIZE -1; i++)
        hash_table[i] = i;
    shuffle(hash_table, TABLE_SIZE - 1);
    return hash_table;
}
 
static void free_hash_table(WORD * hash_table){
    if (NULL == hash_table)
        return;
    else
        free(hash_table);
    return;
}
 
 
static void shuffle(WORD * table, unsigned int n){
    srand(time(NULL));
    //srand(1);
    unsigned int i,j, tmp;
    for (i = n-1; i> 0; i--){
        j = rand() % (i+1);
        tmp = table[j];
        table[j] = table[i];
        table[i] = tmp;
    }
}
 
 
 
cdict_ctx* cdict_init(void(*free_func)(void*), void*(*copy_func)(void*)){
    if (copy_func == NULL){
        return NULL;
    }
    WORD * hash_table = init_hash_table();
    if (NULL == hash_table)
        return NULL;
    cdict_ctx * ctx = (cdict_ctx*) malloc (sizeof(cdict_ctx));
    if (NULL == ctx)
        return NULL;
    ctx->hash_table = hash_table;
    ctx->table = (PNODE) malloc(TABLE_SIZE * sizeof(NODE));
    
    if (ctx->table == NULL){
        free(ctx);
        return NULL;
    }
    ctx->free_func = free_func;
    ctx->copy_func = copy_func;
    for (unsigned long int i=0; i< TABLE_SIZE; i++){
        ctx->table[i].key = NULL;
        ctx->table[i].value = NULL;
        ctx->table[i].next = NULL;
    }
 
    ctx->errmsg = (char *) malloc(sizeof(char) * 0xFF);
    ctx->err = 0;
    //let's assign functions to pointers
    return ctx;
}
 
 
static unsigned int hashme(cdict_ctx * ctx, char * key){
    if (key == NULL){
        ctx->err =  ERROR_NULL_VALUE_FOR_KEY;
        strcpy(ctx->errmsg, "Key can not be NULL for a dictionary!");
        return 0;
    }
    unsigned long long int j;
    j=1;
    unsigned int key_len = strlen(key);
    for (unsigned int i=0; i< key_len; ++i){
        j *= (WORD)key[i];
        j = (j % (TABLE_SIZE)) & 0xFFFF;
    }
    return ctx->hash_table[j];
}
 
void * cdict_get(cdict_ctx* ctx, char * key){
    if (NULL == ctx)
        return NULL;
    if (NULL == key){
        ctx->err = ERROR_NULL_VALUE_FOR_KEY;
        strcpy(ctx->errmsg, "The key can not be null for a dictionary!");
        return NULL;
    }
    WORD index = hashme(ctx, key);
    if (ctx->err != ERROR_OK)
        return NULL;
    PNODE tmp = &(ctx->table[index]);
    if (NULL == tmp){
        return NULL;
    }
    while(1){
        if (NULL == tmp)
            return NULL;
        if (tmp->key == NULL)
            return NULL;
        if (strcmp(tmp->key, key) == 0){
            return (void*)tmp->value;
        }else{
            tmp = tmp->next;
            continue;
        }
    }
}
 
 
 
void * cdict_get_nocase(cdict_ctx* ctx, char * key){
    if (NULL == ctx)
        return NULL;
    if (NULL == key){
        ctx->err = ERROR_NULL_VALUE_FOR_KEY;
        strcpy(ctx->errmsg, "The key can not be null for a dictionary!");
        return NULL;
    }
    // make sure you lower case the key first
    char * clone_key  = strdup(key);
    for (int i=0; clone_key[i]; i++)
        clone_key[i] = cto_lower(clone_key[i]);
 
    WORD index = hashme(ctx, clone_key);
    if (ctx->err != ERROR_OK){
        free(clone_key);
        return NULL;
    }
    PNODE tmp = &(ctx->table[index]);
    if (NULL == tmp){
        free(clone_key);
        return NULL;
    }
    while(1){
        if (NULL == tmp){
            free(clone_key);
            return NULL;
        }
        if (tmp->key == NULL){
            free(clone_key);
            return NULL;
        }
        if (cstr_ccmp(tmp->key, clone_key) == 0){
            free(clone_key);
            return (void*)tmp->value;
        }else{
            tmp = tmp->next;
            continue;
        }
    }
}
 
 
int cdict_set_nocase(cdict_ctx *ctx, char * key, void * value){
    if (NULL == ctx)
        return ERROR_DICT_POINTER_IS_NULL;
    if (NULL == key){
        ctx->err = ERROR_NULL_VALUE_FOR_KEY;
        strcpy(ctx->errmsg, "Key can not be NULL!");
        return ERROR_NULL_VALUE_FOR_KEY;
    }
    
    char * clone_key = strdup(key);
 
    // this is here to make sure we make it lower case for hash table
    for (int i=0; clone_key[i]; i++)
        clone_key[i] = cto_lower(clone_key[i]);
 
    WORD hash_val = hashme(ctx, clone_key);
    
    void * clone_val = ctx->copy_func(value);
    
    if (NULL == ctx->table[hash_val].key){
        // no collision
        ctx->table[hash_val].key = clone_key;
        ctx->table[hash_val].value = clone_val;
        ctx->table[hash_val].next = NULL;
        return ERROR_OK;
    }else{
        // we have collision
        PNODE tmp = &(ctx->table[hash_val]);
        while(tmp->next != NULL){
            if (strcmp(tmp->key, clone_key) != 0){
                tmp = tmp->next;
                continue;
            }else{
                break;
            }
        }
        if (strcmp(tmp->key, clone_key) == 0){
            if (tmp->value != NULL)
                ctx->free_func(tmp->value);
            // we don't need the clone_key
            free(clone_key);
            tmp->value = clone_val;
            return ERROR_OK;
        }else{
            tmp->next = (PNODE) malloc(sizeof(NODE));
            if (NULL == tmp->next){
                ctx->err = CDICT_ERROR_CAN_NOT_ALLOCATE_MEMORY;
                ctx->free_func(clone_val);
                free(clone_key);
                strcpy(ctx->errmsg, "Can not allocate memory for the new key-value pair!");
                return CDICT_ERROR_CAN_NOT_ALLOCATE_MEMORY;
            }
            tmp = tmp->next;
            tmp->key = clone_key;
            tmp->value = clone_val;
            tmp->next = NULL;
            return ERROR_OK;
        }
    }
}
 
 
 
 
 
int cdict_set(cdict_ctx *ctx, char * key, void * value){
    if (NULL == ctx)
        return ERROR_DICT_POINTER_IS_NULL;
    if (NULL == key){
        ctx->err = ERROR_NULL_VALUE_FOR_KEY;
        strcpy(ctx->errmsg, "Key can not be NULL!");
        return ERROR_NULL_VALUE_FOR_KEY;
    }
 
    WORD hash_val = hashme(ctx, key);
    
    char * clone_key = strdup(key);
    void * clone_val = ctx->copy_func(value);
    
    if (NULL == ctx->table[hash_val].key){
        // no collision
        ctx->table[hash_val].key = clone_key;
        ctx->table[hash_val].value = clone_val;
        ctx->table[hash_val].next = NULL;
        return ERROR_OK;
    }else{
        // we have collision
        PNODE tmp = &(ctx->table[hash_val]);
        while(tmp->next != NULL){
            if (strcmp(tmp->key, clone_key) != 0){
                tmp = tmp->next;
                continue;
            }else{
                break;
            }
        }
        if (strcmp(tmp->key, clone_key) == 0){
            if (tmp->value != NULL)
                ctx->free_func(tmp->value);
            // we don't need the clone_key
            free(clone_key);
            tmp->value = clone_val;
            return ERROR_OK;
        }else{
            tmp->next = (PNODE) malloc(sizeof(NODE));
            if (NULL == tmp->next){
                ctx->err = CDICT_ERROR_CAN_NOT_ALLOCATE_MEMORY;
                ctx->free_func(clone_val);
                free(clone_key);
                strcpy(ctx->errmsg, "Can not allocate memory for the new key-value pair!");
                return CDICT_ERROR_CAN_NOT_ALLOCATE_MEMORY;
            }
            tmp = tmp->next;
            tmp->key = clone_key;
            tmp->value = clone_val;
            tmp->next = NULL;
            return ERROR_OK;
        }
    }
}
 
 
void cdict_free(cdict_ctx * ctx){
    PNODE tmp = NULL;
    PNODE tmp_1 = NULL;
    if (NULL == ctx)
        return;
    //free the pointer to errmsg
    free(ctx->errmsg);
    // we need to empty the hash_table
    if (ctx->table != NULL){
        for (unsigned int i=0; i< TABLE_SIZE; i++){
            if (ctx->table[i].key == NULL)
                continue;
            tmp = ctx->table[i].next;
            free(ctx->table[i].key);
            ctx->free_func(ctx->table[i].value);
            while (tmp){
                tmp_1 = tmp;
                free(tmp_1->key);
                ctx->free_func(tmp_1->value);
                tmp = tmp_1->next;
                free(tmp_1);
            }
        }
    }
    free(ctx->table);
    free_hash_table(ctx->hash_table);
    free(ctx);
    return;
}
 
int cdict_has_key(cdict_ctx* ctx, char * key){
    if (NULL == ctx)
        return 0;
    if (NULL == key){
        ctx->err = ERROR_NULL_VALUE_FOR_KEY;
        strcpy(ctx->errmsg, "The key can not be null for a dictionary");
        return 0;
    }
    WORD index = hashme(ctx, key);
    if (ctx->err != ERROR_OK)
        return 0;
    PNODE tmp = &(ctx->table[index]);
    while(1){
        if (NULL == tmp)
            return 0;
        if (tmp->key == NULL)
            return 0;
        if (strcmp(tmp->key, key) == 0){
            return 1;
        }else{
            tmp = tmp->next;
            continue;
        }
    }
    return 0;
}
 
 
int cdict_has_key_nocase(cdict_ctx* ctx, char * key){
    if (NULL == ctx)
        return 0;
    if (NULL == key){
        ctx->err = ERROR_NULL_VALUE_FOR_KEY;
        strcpy(ctx->errmsg, "The key can not be null for a dictionary");
        return 0;
    }
    WORD index = hashme(ctx, key);
    if (ctx->err != ERROR_OK)
        return 0;
    PNODE tmp = &(ctx->table[index]);
    while(1){
        if (NULL == tmp)
            return 0;
        if (tmp->key == NULL)
            return 0;
        if (cstr_ccmp(tmp->key, key) == 0){
            return 1;
        }else{
            tmp = tmp->next;
            continue;
        }
    }
    return 0;
}
 
 
 
 
void cdict_free_keylist(cdict_keylist* klst, int clone_keys){
    if (clone_keys)
        for (unsigned int i=0; i< klst->len; ++i)
            free(klst->lst[i]);
    free(klst->lst);
    free(klst);
    return;
}
 
 
 
cdict_keylist * cdict_keys(cdict_ctx* ctx, int clone_keys){
    unsigned long int cnt = 0;
    PNODE tmp = NULL;
    for (unsigned long int i=0; i< TABLE_SIZE; i++){
        if (ctx->table[i].key != NULL){
            cnt += 1;
            tmp = ctx->table[i].next;
            while(tmp && tmp->key){
                cnt += 1;
                tmp = tmp->next;
            }
        }
    }
    cdict_keylist *klst = (cdict_keylist*) malloc(sizeof(cdict_keylist));
    if (!klst){
        ctx->err = CDICT_ERROR_CAN_NOT_ALLOCATE_MEMORY;
        strcpy(ctx->errmsg, "Can not allocate memory for keys");
        return NULL;
    }
    klst->len = cnt;
    if (cnt == 0)
        return klst;
    // allocate cnt * (sizeof(char *))
    klst->lst = (char**) malloc (cnt * sizeof(char*));
    if (NULL == klst->lst){
        ctx->err = CDICT_ERROR_CAN_NOT_ALLOCATE_MEMORY;
        strcpy(ctx->errmsg, "Can not allocate memory for keys");
        free(klst);
        return NULL;
    }
    tmp = NULL;
    cnt = 0;
    ctx->err = ERROR_OK;
    for (unsigned long int i=0; i< TABLE_SIZE; ++i){
        if (ctx->table[i].key != NULL){
            klst->lst[cnt] = clone_keys?strdup(ctx->table[i].key):ctx->table[i].key;
            cnt += 1;
            tmp = ctx->table[i].next;
            while (tmp && tmp->key){
                klst->lst[cnt] = clone_keys?strdup(tmp->key):tmp->key;
                cnt += 1;
                tmp = tmp->next;
            }
        }
    }
    return klst;
}
 
void cdict_remove(cdict_ctx * ctx, char * key){
    if (!ctx)
        return;
    if (!key)
        return;
    PNODE tmp, tmp_1;
    WORD index = hashme(ctx, key);
    // if key is not there return
    if (!cdict_has_key(ctx, key))
        return;
    // key is there
    tmp = &(ctx->table[index]);
    if (strcmp(key, tmp->key) == 0){
        // in the main chain
        if (tmp->next == NULL){
            free(tmp->key);
            tmp->key = NULL;
            ctx->free_func(tmp->value);
            tmp->value = NULL;
            return;
        }else{
            // with link
            free(tmp->key);
            ctx->free_func(tmp->value);
            tmp->key = strdup(tmp->next->key);
            tmp->value = ctx->copy_func(tmp->next->value);
            tmp_1 = tmp->next;
            tmp->next = tmp_1->next;
            // now remove tmp_1
            free(tmp_1->key);
            ctx->free_func(tmp_1->value);
            free(tmp_1);
            return;
        }
    }
    // not in the main chain
    tmp_1 = tmp;
    tmp = tmp->next;
    while (tmp){
        if (strcmp(tmp->key, key) == 0){
            break;
        }
        tmp_1 = tmp;
        tmp = tmp->next;
    }
    // tmp is the candidate, tmp_1 is its parent
    if (tmp->next == NULL){
        // it's a leaf
        free(tmp->key);
        ctx->free_func(tmp->value);
        free(tmp);
        tmp_1->next = NULL;
        return;
    }else{
        // it's in the middle
        tmp_1->next = tmp->next;
        free(tmp->key);
        ctx->free_func(tmp->value);
        free(tmp);
        return;
    }
    return;
}