2
\$\begingroup\$

I am trying to implement an HashMap in C. I am trying to used a linked list style of interfacing to make adding and removing keys easy and efficient. Searching is not something I am considering at this point as it is early in progress. I am looking for any tweaks that could make this faster, more memory efficient, more practical, more dynamic, etc. as well as any serious issues you notice as I am merely an amateur at C programming and haven't much experience.

This is the header file with my declarations and implementation:

#ifndef _M_LINKED_MAP_H_
#define _M_LINKED_MAP_H_

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

/* LinkedMap keys can be 512 characters long inc'l null */
#define M_MAX_KEY 512
#define M_KEY_NOT_FOUND 0
int _M_DEFAULT_VALUE_WARNED_ = 0; /* Issues one warning about zero default behavior */

/* TYPES */

typedef struct __LinkedMapNode {
    char *k; /* key */
    int v; /* value */
    struct __LinkedMapNode *next;

    /* determines whether key assign should happen to current node or node->next */
    int first; 
} __LinkedMapNode;

typedef __LinkedMapNode LinkedMapRoot;

/* FUNCTION DECLARATIONS */

int     LinkedMap_init (__LinkedMapNode *m);
int     setLinkedMapKey(__LinkedMapNode *root, char const *key, int value);
int     putLinkedMapKey(__LinkedMapNode *root, char const *key, int value);
int     getLinkedMapKey(__LinkedMapNode *root, char const *key);
void    delLinkedMapKey(__LinkedMapNode *root, char const *key);
void    LinkedMap_free(__LinkedMapNode *root);
__LinkedMapNode *LinkedMap_malloc();

/* FUNCTION IMPLEMENTATIONS */

int LinkedMap_init(__LinkedMapNode *m) {
    if (!_M_DEFAULT_VALUE_WARNED_) {
        puts("Please note: LinkedMaps return 0 on get if key is not found");
        _M_DEFAULT_VALUE_WARNED_ = 1;
    }
    m->next = NULL;
    m->first = 1; /* True if node is never assigned key */
    return 0;
}

__LinkedMapNode *LinkedMap_malloc() {
    __LinkedMapNode *m = malloc(sizeof(__LinkedMapNode));
    LinkedMap_init(m);
    return m;
}

int setLinkedMapKey(__LinkedMapNode *root, char const *key, int value) {
    /* this function is used to change the value of an existing key in the
     * linked list */
    if (root->next == NULL) {
        puts("You must put a key before you can set it.");
        return 1;
    }
    if (strcmp(root->k, key) != 0) {
        setLinkedMapKey(root->next, key, value); /* search until the key is found */
    } else {
        root->v = value; /* change value */
    }
    return 0;
}

int putLinkedMapKey(__LinkedMapNode *root, char const *key, int value) {
    /* this function is used only to assign new keys to nodes */
    if (root->first) {
        root->k = malloc(M_MAX_KEY);
        strcpy(root->k, key);
        root->v = value;
        root->first = 0; /* node has key, should not be reassigned */
    }
    if (root->next != NULL) {
        putLinkedMapKey(root->next, key, value); /* Recursive Call if possible */
        /* Picks up on all nodes after first assignment before penultimate node */
    }
    else{
        /* If the next node is null, recursion is impossible so 
         * direct assignment is used */
        /* takes on second assignment to root node and all subsequent assign calls */
        root->next = LinkedMap_malloc();
        root->next->k = malloc(M_MAX_KEY);
        strcpy(root->next->k, key);
        root->next->v = value;
    }
    return 0;
}

int getLinkedMapKey(__LinkedMapNode *root, char const *key) {
    if (strcmp(root->k, key) != 0 && root->next != NULL) {
        /* if the keys don't match and there are more check them */
        return getLinkedMapKey(root->next, key);
    }
    if (strcmp(root->k, key) == 0) {
        return root->v;
    }
    if (root->next == NULL) return M_KEY_NOT_FOUND; /* default value is zero if key is not found */
    return M_KEY_NOT_FOUND;
}

void delLinkedMapKey(__LinkedMapNode *root, char const *key) {
    /* Removing a key involves copying the entirety of the following node
     * to the node with the matching key */
    if (root == NULL) return; /* Silent discard if key not found */
    if (root->next == NULL) {
        if (root->k != NULL) free(root->k);
        root = NULL; /* last node is deleted */
        return;
    }
    if (strcmp(root->k, key) == 0) {
        if (root->k != NULL) free(root->k);
        root->k = root->next->k;
        root->v = root->next->v;
        root->next = root->next->next;
    } else {
        /* current root is not the correct key and so the next one is examined */
        delLinkedMapKey(root->next, key);
    }
}

void LinkedMap_free(__LinkedMapNode *root) {
    if (root == NULL) return;
    if (root->next == NULL) {
        if (root->k != NULL) free(root->k);
        free(root);
    }
    else {
        LinkedMap_free(root->next);
    }
}


#endif 
/* _M_LINKED_MAP_H_ */ 
\$\endgroup\$
3
  • \$\begingroup\$ P.S. The __LinkedMapNode is used because the entire Map is interfaceable from the root node so it should be used such that LinkedMapRoot root = LinkedMap_malloc(); is the only node that the user will have to use as all actions can be performed on that \$\endgroup\$ – Tom Dec 29 '15 at 19:20
  • \$\begingroup\$ Thedel function is buggy - there's a path that deletes a node without checking the key. The free function looks buggy too. I think you need more tests and things like valgrind to verify your implementation. Biggest issue is that it's not a hash map at all - hint: you don't hash anything anywhere :-) \$\endgroup\$ – Mat Dec 29 '15 at 19:52
  • \$\begingroup\$ I actually meant LinkedMap not Hash sorry \$\endgroup\$ – Tom Dec 29 '15 at 20:27
5
\$\begingroup\$

Don't use reserved identiferiers.

From 7.1.3 Reserved identifiers of the C99 standard

All identifiers that begin with an underscore and either an uppercase letter or another underscore are always reserved for any use.

This article is about C++; but it also contains a lot of information relavant to C. What are the rules about using an underscore in a C++ identifier?.

All the following are reserved for the implementation.

_M_LINKED_MAP_H_
_M_DEFAULT_VALUE_WARNED
__LinkedMapNode

Is there a use case were LinkedMap_init() would by used without a call to LinkedMap_malloc? If not just roll them into a single function. If so then keep them separate.

Why does LinkedMap_init() return an int but always return 0. If it can return an error condition then make it a void function. No point in wasting time returning a value if that value can never be used.

int LinkedMap_init(__LinkedMapNode *m) {

Malloc can fail. In your LinkedMap_malloc() you must either check for that before calling LinkedMap_init() or update LinkedMap_init() so that it can cope with a NULL pointer correctly.

__LinkedMapNode *LinkedMap_malloc() {
    __LinkedMapNode *m = malloc(sizeof(__LinkedMapNode));
    LinkedMap_init(m);
    return m;
}

There seems to be a bug in setLinkedMapKey(). If the key is at the end of the chain you fail to find it. Change if (root->next == NULL) { into if (root == NULL) {.

This is very dangerous.

        root->k = malloc(M_MAX_KEY);
        strcpy(root->k, key);

What happens if key is a very long string.

\$\endgroup\$
4
  • \$\begingroup\$ Question: suppose I check for NULL and it is NULL what would be the best course of action? return, abort, or exit? \$\endgroup\$ – Tom Dec 29 '15 at 20:30
  • \$\begingroup\$ Also, I originally had it if (root == NULL) but I would get a segfault if I tried the last node and when I changed it the last node updated properly, I also thought that was odd \$\endgroup\$ – Tom Dec 29 '15 at 20:31
  • \$\begingroup\$ @Tom, about your first question, for library code it is generally better to return some error indicator and let the caller handle the failure as appropriate. Application code can make more assumptions and it is sometimes fine to just abort on a failure case. But regardless of the choice, it is important to detect and handle errors always. \$\endgroup\$ – glampert Dec 29 '15 at 21:52
  • 1
    \$\begingroup\$ @Tom: Return NULL and let the caller check that the result is not NULL. Just because a container you are using does not work does not give that container authority to stop the program. The program may be able to take actions to get more space before retrying. \$\endgroup\$ – Martin York Dec 29 '15 at 22:20
2
\$\begingroup\$

@Loki's answer already pointed out very important things, here are a few others:

  • Use booleans to communicate success or failure of a function if there are only two possible outcomes. All you have to do is #include <stdbool.h> and you'll have the bool type and true/false constants at your disposal.

  • Use enum for compile-time constants. #defines have several weaknesses if compared, such as allowing silent redefinition and not producing a debug symbol (you'd see just a raw numeric constant in your debugger), among others.

  • If you're logging error messages, use the stderr standard stream. That's the expected place to log runtime errors, so users of your code can filter normal stdout output from error messages.

    fprintf(stderr, "some error message here...");
    
  • This seems like it should have been a comment documenting the behavior of the function instead:

    if (!_M_DEFAULT_VALUE_WARNED_) {
        puts("Please note: LinkedMaps return 0 on get if key is not found");
        _M_DEFAULT_VALUE_WARNED_ = 1;
    }
    
  • I suggest using a consistent prefix for your function names. C doesn't have modules or namespaces, so it is a good idea to define some prefix that indicates the module a function belongs to. You could maybe prefix everything with LinkedMap_, example:

    LinkedMap_Init
    LinkedMap_GetKey
    LinkedMap_SetKey
    etc...
    
  • You're blindly strcpying the keys without checking if then fit the M_MAX_KEY limit of 512 chars including null. Never assume calling code will be well behaved. Always check your assumptions, even if with just an assert to trap errors early and help you debugging.

  • I also suggest validating input parameters against NULL if they are never meant to be null pointers.

  • Separate interface from implementation, right now, including your file in more than one .c source file would result in duplicate symbols being defined. C requires you to define your functions just once in a .c file, while the header (.h) contains only forward declarations and data structures.

\$\endgroup\$
3
  • \$\begingroup\$ I don't understand how to separate the declarations because if I try to compile I get undefined symbols \$\endgroup\$ – Tom Dec 29 '15 at 23:11
  • \$\begingroup\$ Much obliged I particularly found useful the addition of name space like naming. \$\endgroup\$ – Tom Dec 29 '15 at 23:28
  • \$\begingroup\$ @Tom, you just move the function implementations to a separate .c file, then compile it with the rest of your program. That should be pretty much it. You are probably not compiling the source file with the definitions, make sure it is included in your workspace/makefile/whatever-build-system you are using. \$\endgroup\$ – glampert Dec 29 '15 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.