struct with ptr array to nested structs assignment and mem allocation

Question

I have a struct containing deep nesting of ptrs to related structs that also contain pointers. I am having issues getting the initialization right because the array of ptrs must have size passed to the init function. See code below:

typedefs:

typedef struct tuple Tuple;
typedef struct dict Dict;
int findKey(Dict *d, char *check);

struct tuple {
    char                   *key;           //named loc
    void                   *val;           //data
};

struct dict {
    unsigned int           size;           //max size
    unsigned int           counter;        //# tuples
    Tuple                  **entries;     //list of tuples
};

init func:

Dict *initDict(const unsigned int size) {
    Dict data = {.size = size, .counter = 0, .entries = (Tuple**) malloc(sizeof(Tuple*) * size)};
    for (unsigned int i = 0; i < size; i++) {
        data.entries[i] = (Tuple*) malloc(sizeof(Tuple));
        data.entries[i]->key = '\0'; /* initially null */
        data.entries[i]->val = '\0'; /* initially null */
    }
    Dict *d = (Dict*) malloc(sizeof(Dict));
    d = &data;
    return d;
}

Dict ops:

short setTuple(Dict *d, char *key, void* val) {
    int i;
    if ((i = findKey(d, key)) != -1) { /* found key */
        d->entries[i]->val = val;
        return 0;
    }
    else {  /* new entry */
        if (d->counter < d->size) { /* find first null */
            for (unsigned int i = 0; i < d->size; i++) {
                if (d->entries[i]->key == NULL) break;
            } /* then replace null slot */
            d->entries[i]->key = (char *) malloc(sizeof(char) * strlen(key));
            d->entries[i]->key = key;
            d->entries[i]->val = (void *) malloc(sizeof(&val));
            d->entries[i]->val = val;
            d->counter++;
            return 0;
        }
        return -1; /* no room */
    }
}

short setTuples(Dict *d, char *json) {

}

void* getTuple(Dict *d, char *key) {
    int i;
    if ((i = findKey(d, key)) != -1) {
        void *val = d->entries[i]->val;
        return val;
    } return (void *) -1; /* not found */
}

void* getIndex(Dict *d, unsigned int index) {
    if (index < d->counter && d->entries[index]->key != NULL) {
        void *val = d->entries[index]->val;
        return val;
    } return (void *) -1; /* not found */
}

/* TODO: add checks for NULL ptr prior to freeing? */
int removeTuple(Dict *d, char *key) {
    int i;
    if ((i = findKey(d, key)) != -1) {
        free(d->entries[i]->key);
        free(d->entries[i]->val);
        free(d->entries[i]);
        d->entries[i]->key = '\0';
        d->entries[i]->val = '\0';
        d->counter--;
        return 0;
    } return -1; /* no room */
}

void destroyDict(Dict *d) {
    for (unsigned int i = 0; i < d->counter; i++) {
        free(d->entries[i]->key);
        free(d->entries[i]->val);
        free(d->entries[i]);
        d->entries[i]->key = '\0';
        d->entries[i]->val = '\0';
        d->entries[i] = '\0';
        d->counter--;
    }
    free(d->entries);
    free(d);
}

/* return index of tuple in dict or -1 if DNE */
int findKey(Dict* d, char* check) {
    unsigned int i;
    for (i = 0; i < d->counter; i++) {
        if (d->entries[i]->key != NULL && strcmp(d->entries[i]->key, check) == 0) {
            return i;
        }
    } return -1; /* not found */
}

What's your question? Please post a [MCVE], not your entire code — Vittorio Romeo, Mar 06 '17 at 18:48
Always relevant: [Please see this about casting the result of malloc](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc). You also don't check that malloc succeeded. — StoryTeller - Unslander Monica, Mar 06 '17 at 18:50
Curious, who or what text suggested `(Tuple*)` casting as in `data.entries[i] = (Tuple*) malloc(sizeof(Tuple));`? — chux - Reinstate Monica, Mar 06 '17 at 18:54
`d->entries[i]->key = (char *) malloc(sizeof(char) * strlen(key)); d->entries[i]->key = key;` is insufficient memory allocation and is lost in the 2nd assignment. Likely want `memcpy/strcpy` — chux - Reinstate Monica, Mar 06 '17 at 18:56
`d = &data;` --> `*d = data;` and I suggest `Tuple **entries;` --> `Tuple *entries;` — BLUEPIXY, Mar 06 '17 at 18:58
@chux I see that would be the right solution, what is the portable of memcpy/strcpy ? I believe it is POSIX standard, any cross-platform alternatives you can think of? — Tyler Moore, Mar 06 '17 at 20:40
`memcpy/strcpy` have been in the C standard library since C89. All compliant C compilers support them. I think you need `strdup()` code - [example](http://stackoverflow.com/a/39694254/2410359) — chux - Reinstate Monica, Mar 06 '17 at 20:45
@chux yeah It looks like either strcpy or strdup for the strings, then void ptrs though probably memcpy thanks — Tyler Moore, Mar 07 '17 at 00:17

score 1 · Answer 1 · answered Mar 06 '17 at 19:00

Dict *initDict(const unsigned int size) {
    Dict data = { /*...*/ };
    // ...
    Dict *d = (Dict*) malloc(sizeof(Dict));
    d = &data;
    return d;
}

Two glaring problems are present here:

d = &data; that immediately leaks the memory you allocated with malloc.
return d; continuing on from (1), you return the address of a local variable. Thus your programs behavior is undefined.

If you want to copy initialize the newly allocated memory with the values you set in the local variable, it's that pointer that needs to be dereferenced, and then the pointee assigned:

Dict *initDict(const unsigned int size) {
    Dict data = { /*...*/ };
    // ...
    Dict *d = malloc(sizeof(Dict));
    if(d)
      *d = data;
    else {
      // Everything you allocated for data must be cleaned here.
    }
    return d;
}

Where I also added a check you are sorely missing whenever your original code uses malloc. Check that the pointer isn't NULL!

I totally missed that error check there thanks for pointing that out — Tyler Moore, Mar 06 '17 at 20:35

Tyler Moore · Answer 2 · 2017-03-07T05:32:18.777

Just wanted to post my implementation to round out this question. I actually went with a more dynamic approach using 2 separate "blocks", where one holds the table data and the other block holds my ptr array. Linking the data this way allows for dynamic ops and separation of duties / redundancy, flexibility and not to mention NOT creating a dependent relation to reallocating memory. @teppic has an amazing walkthrough here: dynamic ptrs to structs as well.

EDIT: I added some code cleanup (missed a couple old statements) along with some data hiding / abstraction of the table completely and now all tests are success, enjoy!

Declarations:

typedef struct tuple Tuple;
typedef struct dict Dict;
int findKey(Dict *d, char *check);

struct tuple {
    char                   *key;           //named loc
    void                   *val;           //data
};

struct dict {
    unsigned int           size;           //max size
    unsigned int           counter;        //# tuples
    Tuple                  *table;         //table of tuples
    Tuple                  **entries;      //arr of ptrs
};

Init:

Dict *initDict(const unsigned int size) {
    Dict *d = (Dict *) malloc(sizeof(Dict));
    if (d) {
        d->size = size;
        d->counter = 0;
        d->table = malloc(sizeof(Tuple*) * size);
        d->entries = malloc(sizeof(Tuple*) * size);

        if (d->table && d->entries) {
            for (unsigned int i = 0; i < size; ++i) {
                d->entries[i] = d->table + i;
            }
            return d;
        }      /*       Failed to init:      */
        else { /* Data must be cleaned here. */
            free(d->entries);
            free(d->table);
            free(d);
        } exit(-1); /* fall through */
    } exit(-1);  /* fail safe */
}

setTuple (FIXED :o)

short setTuple(Dict *d, char *key, void* val) {
    int i;
    if ((i = findKey(d, key)) != -1) { /* found key */
        d->entries[i]->val = val;
        return 0;
    }
    else {  /* new entry */
        if (d->counter < d->size) { /* find first null */
            unsigned int i = 0;     /*   reset   */
            for (i; i < d->size; i++) {
            /* getting segv on break statement? */
                if (! d->entries[i] || ! d->entries[i]->key) break;
            } /* then replace null slot */
            d->entries[i]->key = key;
            d->entries[i]->val = val;
            d->counter++;
            return 0;
        } /* no room left in dict */
    } return -1;
}

There's a few other but for brevity.. here is the memory cleanup:

int removeTuple(Dict *d, char *key) {
    int i;
    if ((i = findKey(d, key)) != -1) {
        d->entries[i]->key = '\0';
        d->entries[i]->val = '\0';
        d->counter--;
        return 0;
    } return -1; /* no room */
}

void destroyDict(Dict *d) {
    for (unsigned int i = 0; i < d->counter; i++) {
        d->entries[i] = '\0';
        d->counter--;
    }
    free(d->entries);
    free(d->table);
    free(d);
}

Once the blocks are freed then thats it, linked lists FTW :) Note the counter implemented in the dict as well, provides a reference to check against when performing "get" tuple. That along with setting the fields explicitly to null makes searching much faster (comparable to a "blacklist") of keys we know won't have the one we want.

struct with ptr array to nested structs assignment and mem allocation

2 Answers2