K&R hash function

Question

The part of following code is an implementation of a simple hash lookup algorithm from K&R. lookup searches for s in the table, and returns a pointer to the place where it was found, or NULL if it wasn't there:

struct hashElement *lookup(char *name){
    struct hashElement *currentStruct;
    int cmp;
    for (currentStruct = hashTable[calcIndex(name)]; currentStruct; currentStruct = currentStruct->p)
    if (cmp = strcmp(name, currentStruct->name) == 0)
        return currentStruct;
    return NULL;}

Install uses lookup to determine whether the name being installed is already present:

struct nlist *install(char *name, char *defn)
{
    struct nlist *np;
    unsigned hashval;
    if ((np = lookup(name)) == NULL){
    np = (struct nlist *) malloc(sizeof(*np));
    ...}
...}

If lookup returns NULL, it means that there is no name installed in hash table, and I should allocate memory for new element which type will be nlist.

But, based on this np = (struct nlist *) malloc(sizeof(*np)); *np will allocate memory for NULL if lookup return NULL. Shouldn't I always allocate memory size for nlist instead of *np?

Why don't you see what you get by printing `sizeof(*np)`? Maybe that will give some idea as to which element you are actually allocating space for. — babon, Dec 01 '17 at 10:44
Welcome to Stack Overflow! [Please see this discussion on why not to cast the return value of malloc() and family in C..](https://stackoverflow.com/q/605845/2173917) — Sourav Ghosh, Dec 01 '17 at 10:47

Sourav Ghosh · Accepted Answer · 2017-12-01T10:51:17.690

*np will allocate memory for NULL if lookup return NULL.

Nope, that is not true.

First of all, in

  np = (struct nlist *) malloc(sizeof(*np));

the cast in not needed. That said

 np = malloc(sizeof(*np));

is the same as

np = malloc(sizeof(struct nlist));

as the type of *np is struct nlist. Remember, sizeof operator does not evaluate it's operand unless it's a VLA.

to quote C11, chapter §6.5.3.4

The sizeof operator yields the size (in bytes) of its operand, which may be an expression or the parenthesized name of a type. The size is determined from the type of the operand. The result is an integer. If the type of the operand is a variable length array type, the operand is evaluated; otherwise, the operand is not evaluated and the result is an integer constant.

K&R hash function

1 Answers1