Example for an dynamically allocated associative array in C

[Felix H. Dahlke]

Have been hacking on this for about an hour, so I thought that this effort was useless if noone would use it.

The following code generally is a hack-example of the implementation of an associative array in C,
which many people apparently seem to miss when writing plain C.

I tried to follow the KISS principle as usual.

I'd love to hear feedback on this, doesn't matter if you can tell me how to do it better or just like (or dislike) the code.

The license is DWTFYLWI, namely "do whatever the fuck you like with it".

Here it goes:

/*
* tabletests - several functions to implement associative arrays in C
*
* Copyright 2006 Felix H. Dahlke <fh*@textware.de>
* License: DWTFYLWI
*/

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

struct table_struct
{
char **column1;
char **column2;
int number_of_elements;
};

typedef struct table_struct table;

table *
create_table() /* allocates space for a new structure and it's initial elements */
{
table *tabl;

tabl = malloc(sizeof(tabl->number_of_elements) + sizeof(tabl->column1) + sizeof(tabl->column2));

tabl->column1 = malloc(sizeof(tabl->column1));
tabl->column2 = malloc(sizeof(tabl->column2));
tabl->number_of_elements = 0;

return tabl;
}

delete_table(tabl) /* frees the size used by the table */
table *tabl;
{
int x;

if (!tabl)
return;

for (x = 0; x < tabl->number_of_elements; x++) {
free(tabl->column1[x]);
free(tabl->column2[x]);
tabl->column1[x] = tabl->column2[x] = NULL;
}
free(tabl->column1);
free(tabl->column2);
free(tabl);

tabl->column1 = tabl->column2 = NULL;
tabl = NULL;
}

add_to_table(tabl, col1, col2) /* adds elements (rows) to the table */
table *tabl;
char *col1;
char *col2;
{
int num, s1, s2;

if (!tabl)
return;

/* TODO: check for duplicates? not really needed for our purposes */

num = tabl->number_of_elements++;

tabl->column1 = realloc(tabl->column1, (num+1) * sizeof(col1));
tabl->column2 = realloc(tabl->column2, (num+1) * sizeof(col2));

s1 = strlen(col1);
s2 = strlen(col2);

tabl->column1[num] = malloc(s1+1);
tabl->column2[num] = malloc(s2+1);

strncpy(tabl->column1[num], col1, s1);
strncpy(tabl->column2[num], col2, s2);

tabl->column1[num][s1] = tabl->column2[num][s2] = '\0';
}

char *
get_column(tabl, column, key) /* returns the element whose corresponding column matches the given key */
table *tabl;
short column;
char *key;
{
char *value, *key2;
int x;

if (!tabl)
return(NULL);

for (x = 0; x < tabl->number_of_elements; x++) {
switch (column) {
case 1: {
key2 = tabl->column1[x];
value = tabl->column2[x];
break;
}
case 2: {
key2 = tabl->column2[x];
value = tabl->column1[x];
break;
}
default:
return(NULL);
}
if (!strcmp(key, key2))
return(value);
}

return(NULL);
}

print_table(tabl) /* prints the table beautifully */
table *tabl;
{
int x;

if (!tabl)
return;

printf("======================================\n") ;
for (x = 0; x < tabl->number_of_elements; x++)
printf("%s | %s\n======================================\n", tabl->column1[x], tabl->column2[x]);
}

int main()
{
table *hobbies = create_table();

add_to_table(hobbies, "play Tennis", "Bob");
add_to_table(hobbies, "swim", "John");
add_to_table(hobbies, "write code", "Felix");
add_to_table(hobbies, "watch TV", "Daniel");
add_to_table(hobbies, "paint", "Jenny");
print_table(hobbies);
printf("Bob likes to %s.\n", get_column(hobbies, 2, "Bob"));

delete_table(hobbies);
}

--
/~\ the ascii ribbon campaign against html email
\ / and proprietary attachments!
X
/ \ never attach .doc .xls or .ppt files to emails!

[Richard Heathfield]

Felix H. Dahlke said:

Have been hacking on this for about an hour, so I thought that this effort
was useless if noone would use it.
If I can read it all the way through without the alarm bells going off, I'll
certainly consider using it.

The following code generally is a hack-example of the implementation of an
associative array in C, which many people apparently seem to miss when
writing plain C.
<snip>
tabl = malloc(sizeof(tabl->number_of_elements) + sizeof(tabl->column1) +
sizeof(tabl->column2));

tabl->column1 = malloc(sizeof(tabl->column1));

The bells! The bells!

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Chris McDonald]

Hello Felix,

I'd love to hear feedback on this, doesn't matter if you can tell me
how to do it better or just like (or dislike) the code.

Thanks for posting this (but, be prepared for others shouting "send it
to comp.programming").

<politely> As this stands, and without API facility to iterate across a
row, or down a column, what does your dynamically allocated associative
array provide that a hashtable wouldn't provide?

--
Chris.

[Felix H. Dahlke]

On Sat, 10 Jun 2006 01:33:49 +0000, Richard Heathfield wrote:

tabl = malloc(sizeof(tabl->number_of_elements) + sizeof(tabl->column1)
+
sizeof(tabl->column2));

tabl->column1 = malloc(sizeof(tabl->column1));
The bells! The bells!

I'm actually not that C guru, but I expect this to be correct (though ugly
looking). Could you tell me whats dangerous about this code or perhaps
point me to some lecture?

On Sat, 10 Jun 2006 01:42:42 +0000, Chris McDonald wrote: Thanks for posting this (but, be prepared for others shouting "send it
to comp.programming)
New to Usenet posting, sorry for that.
<politely> As this stands, and without API facility to iterate across a
row, or down a column, what does your dynamically allocated associative
array provide that a hashtable wouldn't provide?

*after some investigation*
Approximately nothing.
So I'm wondering why people keep asking about this, I assumed nothing like
this to exist in C and never needed it myself.

Good practice for me anyways.
--
/~\ the ascii ribbon campaign against html email
\ / and proprietary attachments!
X
/ \ never attach .doc .xls or .ppt files to emails!

[Richard Heathfield]

Felix H. Dahlke said:

On Sat, 10 Jun 2006 01:33:49 +0000, Richard Heathfield wrote:

> tabl = malloc(sizeof(tabl->number_of_elements) + sizeof(tabl->column1)
> +
> sizeof(tabl->column2));
>
> tabl->column1 = malloc(sizeof(tabl->column1));

The bells! The bells!

I'm actually not that C guru, but I expect this to be correct (though ugly
looking). Could you tell me whats dangerous about this code or perhaps
point me to some lecture?

The first obvious problem is the first malloc, which should simply be:

tab1 = malloc(sizeof *tab1);

The second obvious problem is the absence of a check of tab1 against NULL
before attempting to dereference it.

The third obvious problem is that the second malloc should be:

tab1->column1 = malloc(sizeof *tab1->column1);

After three obvious problems within two lines of code, I stopped looking.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Frank Silvermann]

Richard Heathfield wrote:

Felix H. Dahlke said:

On Sat, 10 Jun 2006 01:33:49 +0000, Richard Heathfield wrote:

tabl = malloc(sizeof(tabl->number_of_elements) + sizeof(tabl->column1)
+
sizeof(tabl->column2));

tabl->column1 = malloc(sizeof(tabl->column1));
The bells! The bells!

I'm actually not that C guru, but I expect this to be correct (though ugly
looking). Could you tell me whats dangerous about this code or perhaps
point me to some lecture?

The first obvious problem is the first malloc, which should simply be:

tab1 = malloc(sizeof *tab1);

The second obvious problem is the absence of a check of tab1 against NULL
before attempting to dereference it.

The third obvious problem is that the second malloc should be:

tab1->column1 = malloc(sizeof *tab1->column1);

After three obvious problems within two lines of code, I stopped looking.

http://www.cl.cam.ac.uk/~cwc22/hashtable/ was the link I looked at, and
I don't think the link survived its transfer to usenet. Looked standard
and clean. (Caveat: I thought that about my last girlfriend...) Chapter
8 of _C Unleashed_ with source on the disk might save the OP a lot of
grief too. frank

[Keith Thompson]

"Felix H. Dahlke" <fh*@textware.de> writes:

On Sat, 10 Jun 2006 01:33:49 +0000, Richard Heathfield wrote:

> tabl = malloc(sizeof(tabl->number_of_elements) + sizeof(tabl->column1)
> +
> sizeof(tabl->column2));
>
> tabl->column1 = malloc(sizeof(tabl->column1));

The bells! The bells!

I'm actually not that C guru, but I expect this to be correct (though ugly
looking). Could you tell me whats dangerous about this code or perhaps
point me to some lecture?

Without seeing the rest of the code ...

tabl->column1 is a pointer (it must be, since you're assigning the
result of malloc() to it). So sizeof(tabl->column1) is the size of a
pointer. You almost certainly want the size of what it points to.

The usual idiom to avoid this problem is:

ptr = malloc(sizeof *ptr);

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Young]

DWTFYLWI

good£¡

"Felix H. Dahlke" <fh*@textware.de> wrote in message
news:pa****************************@textware.de...

Have been hacking on this for about an hour, so I thought that this effort was useless if noone would use it.
The following code generally is a hack-example of the implementation of an associative array in C, which many people apparently seem to miss when writing plain C.

I tried to follow the KISS principle as usual.

I'd love to hear feedback on this, doesn't matter if you can tell me how to do it better or just like (or dislike) the code.
The license is DWTFYLWI, namely "do whatever the fuck you like with it".

Here it goes:

/*
* tabletests - several functions to implement associative arrays in C
*
* Copyright 2006 Felix H. Dahlke <fh*@textware.de>
* License: DWTFYLWI
*/

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

struct table_struct
{
char **column1;
char **column2;
int number_of_elements;
};

typedef struct table_struct table;

table *
create_table() /* allocates space for a new structure and it's initial elements */ {
table *tabl;

tabl = malloc(sizeof(tabl->number_of_elements) + sizeof(tabl->column1) + sizeof(tabl->column2));
tabl->column1 = malloc(sizeof(tabl->column1));
tabl->column2 = malloc(sizeof(tabl->column2));
tabl->number_of_elements = 0;

return tabl;
}

delete_table(tabl) /* frees the size used by the table */
table *tabl;
{
int x;

if (!tabl)
return;

for (x = 0; x < tabl->number_of_elements; x++) {
free(tabl->column1[x]);
free(tabl->column2[x]);
tabl->column1[x] = tabl->column2[x] = NULL;
}
free(tabl->column1);
free(tabl->column2);
free(tabl);

tabl->column1 = tabl->column2 = NULL;
tabl = NULL;
}

add_to_table(tabl, col1, col2) /* adds elements (rows) to the table */
table *tabl;
char *col1;
char *col2;
{
int num, s1, s2;

if (!tabl)
return;

/* TODO: check for duplicates? not really needed for our purposes */

num = tabl->number_of_elements++;

tabl->column1 = realloc(tabl->column1, (num+1) * sizeof(col1));
tabl->column2 = realloc(tabl->column2, (num+1) * sizeof(col2));

s1 = strlen(col1);
s2 = strlen(col2);

tabl->column1[num] = malloc(s1+1);
tabl->column2[num] = malloc(s2+1);

strncpy(tabl->column1[num], col1, s1);
strncpy(tabl->column2[num], col2, s2);

tabl->column1[num][s1] = tabl->column2[num][s2] = '\0';
}

char *
get_column(tabl, column, key) /* returns the element whose corresponding column matches the given key */ table *tabl;
short column;
char *key;
{
char *value, *key2;
int x;

if (!tabl)
return(NULL);

for (x = 0; x < tabl->number_of_elements; x++) {
switch (column) {
case 1: {
key2 = tabl->column1[x];
value = tabl->column2[x];
break;
}
case 2: {
key2 = tabl->column2[x];
value = tabl->column1[x];
break;
}
default:
return(NULL);
}
if (!strcmp(key, key2))
return(value);
}

return(NULL);
}

print_table(tabl) /* prints the table beautifully */
table *tabl;
{
int x;

if (!tabl)
return;

printf("======================================\n") ;
for (x = 0; x < tabl->number_of_elements; x++)
printf("%s | %s\n======================================\n", tabl->column1[x], tabl->column2[x]); }

int main()
{
table *hobbies = create_table();

add_to_table(hobbies, "play Tennis", "Bob");
add_to_table(hobbies, "swim", "John");
add_to_table(hobbies, "write code", "Felix");
add_to_table(hobbies, "watch TV", "Daniel");
add_to_table(hobbies, "paint", "Jenny");
print_table(hobbies);
printf("Bob likes to %s.\n", get_column(hobbies, 2, "Bob"));

delete_table(hobbies);
}

--
/~\ the ascii ribbon campaign against html email
\ / and proprietary attachments!
X
/ \ never attach .doc .xls or .ppt files to emails!

[jaysome]

On Sat, 10 Jun 2006 03:23:09 +0200, "Felix H. Dahlke"
<fh*@textware.de> wrote:

Have been hacking on this for about an hour, so I thought that this effort was useless if noone would use it.

The following code generally is a hack-example of the implementation of an associative array in C,
which many people apparently seem to miss when writing plain C.

I tried to follow the KISS principle as usual.

I'd love to hear feedback on this, doesn't matter if you can tell me how to do it better or just like (or dislike) the code.

The license is DWTFYLWI, namely "do whatever the fuck you like with it".

Here it goes:

/*
* tabletests - several functions to implement associative arrays in C
*
* Copyright 2006 Felix H. Dahlke <fh*@textware.de>
* License: DWTFYLWI
*/

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

struct table_struct
{
char **column1;
char **column2;
int number_of_elements;
};

typedef struct table_struct table;

table *
create_table() /* allocates space for a new structure and it's initial elements */
{
table *tabl;

tabl = malloc(sizeof(tabl->number_of_elements) + sizeof(tabl->column1) + sizeof(tabl->column2));

tabl->column1 = malloc(sizeof(tabl->column1));
tabl->column2 = malloc(sizeof(tabl->column2));
tabl->number_of_elements = 0;

return tabl;
}

delete_table(tabl) /* frees the size used by the table */
table *tabl;
{
int x;

if (!tabl)
return;

for (x = 0; x < tabl->number_of_elements; x++) {
free(tabl->column1[x]);
free(tabl->column2[x]);
tabl->column1[x] = tabl->column2[x] = NULL;
}
free(tabl->column1);
free(tabl->column2);
free(tabl);

tabl->column1 = tabl->column2 = NULL;
tabl = NULL;
}

add_to_table(tabl, col1, col2) /* adds elements (rows) to the table */
table *tabl;
char *col1;
char *col2;
{
int num, s1, s2;

if (!tabl)
return;

/* TODO: check for duplicates? not really needed for our purposes */

num = tabl->number_of_elements++;

tabl->column1 = realloc(tabl->column1, (num+1) * sizeof(col1));
tabl->column2 = realloc(tabl->column2, (num+1) * sizeof(col2));

s1 = strlen(col1);
s2 = strlen(col2);

tabl->column1[num] = malloc(s1+1);
tabl->column2[num] = malloc(s2+1);

strncpy(tabl->column1[num], col1, s1);
strncpy(tabl->column2[num], col2, s2);

tabl->column1[num][s1] = tabl->column2[num][s2] = '\0';
}

char *
get_column(tabl, column, key) /* returns the element whose corresponding column matches the given key */
table *tabl;
short column;
char *key;
{
char *value, *key2;
int x;

if (!tabl)
return(NULL);

for (x = 0; x < tabl->number_of_elements; x++) {
switch (column) {
case 1: {
key2 = tabl->column1[x];
value = tabl->column2[x];
break;
}
case 2: {
key2 = tabl->column2[x];
value = tabl->column1[x];
break;
}
default:
return(NULL);
}
if (!strcmp(key, key2))
return(value);
}

return(NULL);
}

print_table(tabl) /* prints the table beautifully */
table *tabl;
{
int x;

if (!tabl)
return;

printf("======================================\n") ;
for (x = 0; x < tabl->number_of_elements; x++)
printf("%s | %s\n======================================\n", tabl->column1[x], tabl->column2[x]);
}

int main()
{
table *hobbies = create_table();

add_to_table(hobbies, "play Tennis", "Bob");
add_to_table(hobbies, "swim", "John");
add_to_table(hobbies, "write code", "Felix");
add_to_table(hobbies, "watch TV", "Daniel");
add_to_table(hobbies, "paint", "Jenny");
print_table(hobbies);
printf("Bob likes to %s.\n", get_column(hobbies, 2, "Bob"));

delete_table(hobbies);
}

Between 49 PC-lint warnings and 3 Microsoft VC++ warnings, I'd suspect
that you don't have your compiler's warning level cranked all the way
up.

Consider what one of them told me about your code:

free(tabl);

tabl->column1 = tabl->column2 = NULL;

Warning 449: Pointer variable 'tabl' previously deallocated.

When you "free()" something, subsequent use of the thing that you
free{}'d invokes undefined behavior. Don't do it. Your mistake is most
likely honest. Don't fret--you're in the majority, if not the
supra-most majority.

--
jay

[Keith Thompson]

"Young" <yc****@gmail.com> writes:

DWTFYLWI

good£¡

Please don't top-post. See <http://www.caliburn.nl/topposting.html>.

Please trim any quoted material that isn't relevant to your reply.
Quoting 170+ lines for a two-line response is wasteful.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Felix H. Dahlke]

Richard Heathfield <in*****@invalid.invalid> wrote:

The first obvious problem is the first malloc, which should simply be:

tab1 = malloc(sizeof *tab1);

The second obvious problem is the absence of a check of tab1 against NULL
before attempting to dereference it.
Yes, you're right with both.
The third obvious problem is that the second malloc should be:

tab1->column1 = malloc(sizeof *tab1->column1);

I think this is right like this. column1 needs to store exactly one
pointer at this point, so the size of 4 bytes (on my machine) should
be perfectly right.

My associative array works like this:

struct (pointer)
column1 (pointer)
element (pointer)
element (pointer)
column2 (pointer)
element (pointer)
element (pointer)

The pointers stored in each element point to a character array, so only
their size is not that of a pointer. CMIIW.

If I turn all warnings on (which I did before posting the code here),
I only see complains about my non-ASCII C.
--
/~\ the ascii ribbon campaign against html email
\ / and proprietary attachments!
X
/ \ never attach .doc .xls or .ppt files to emails!

[Richard Heathfield]

Felix H. Dahlke said:

Richard Heathfield <in*****@invalid.invalid> wrote:

The third obvious problem is that the second malloc should be:

tab1->column1 = malloc(sizeof *tab1->column1);

I think this is right like this.

The bells are ringing louder and louder.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Ben C]

On 2006-06-10, Felix H. Dahlke <fh*@textware.de> wrote:

[...]
I'd love to hear feedback on this, doesn't matter if you can tell me
how to do it better or just like (or dislike) the code.
[snip]
table *
create_table() /* allocates space for a new structure and it's initial elements */
{
table *tabl;

tabl = malloc(sizeof(tabl->number_of_elements) + sizeof(tabl->column1) + sizeof(tabl->column2));
Just
tabl = malloc(sizeof (table));
or
tabl = malloc(sizeof *tabl);

is all you need here. What you have is actually incorrect as well (the
size of a struct type may be greater than the sum of the sizes of the
types inside because of padding).
tabl->column1 = malloc(sizeof(tabl->column1));
tabl->column2 = malloc(sizeof(tabl->column2));
You mean "sizeof *table->column1" or "sizeof(char *)". You have char **
types here, used as pointers to arrays of char *. To make each one big
enough to contain one char *, which I think is what you're doing, it
needs to be sizeof (char *). The type of *table->column1 is char *, so
"sizeof *table->column1" is good too.

Actually sizeof(char *) and sizeof(char **) are usually the same in
practice so that's why you get away with this.

Alternatively, since tab->number_of_elements is 0, just set them both to
NULL:

tabl->column1 = tabl->column2 = NULL;

This seems more consistent.

realloc is quite happy with the NULL pointer, so your code to extend
these columns will still be OK. And free won't mind if you free NULL
either.
delete_table(tabl) /* frees the size used by the table */
table *tabl;
{
int x;

if (!tabl)
return;

for (x = 0; x < tabl->number_of_elements; x++) {
free(tabl->column1[x]);
free(tabl->column2[x]);
tabl->column1[x] = tabl->column2[x] = NULL;
Not much point setting these to NULL since we're deleting everything
anyway.
[...]
free(tabl); tabl->column1 = tabl->column2 = NULL;
tabl = NULL;
After you've freed it, you shouldn't write it (tabl->... is the
problem). No need to set it to NULL anyway-- it's gone!
[...]
num = tabl->number_of_elements++;

tabl->column1 = realloc(tabl->column1, (num+1) * sizeof(col1));
tabl->column2 = realloc(tabl->column2, (num+1) * sizeof(col2)); s1 = strlen(col1);
s2 = strlen(col2);

tabl->column1[num] = malloc(s1+1);
tabl->column2[num] = malloc(s2+1); strncpy(tabl->column1[num], col1, s1);
strncpy(tabl->column2[num], col2, s2);
No need to use strncpy-- we know the destinations are big enough because
we just allocated them. strcpy will do. strncpy doesn't do any harm
though. Apart from this:
tabl->column1[num][s1] = tabl->column2[num][s2] = '\0';

This would have been done for you if you'd used strcpy instead of
strncpy :)

strdup is nice for this (although not ISO standard I don't think).

Also you should check all your malloc returns. Or write a function
"xmalloc" that either allocates successfully or aborts the whole process
if it can't, and then you can use that without checks.

Style point: why use those, I think they're called, "K&R-style"
declarations?

[Keith Thompson]

"Felix H. Dahlke" <fh*@nbd.zaiyon.ath.cx> writes:

Richard Heathfield <in*****@invalid.invalid> wrote:

The first obvious problem is the first malloc, which should simply be:

tab1 = malloc(sizeof *tab1);

The second obvious problem is the absence of a check of tab1 against NULL
before attempting to dereference it.
Yes, you're right with both.

The third obvious problem is that the second malloc should be:

tab1->column1 = malloc(sizeof *tab1->column1);

(I think it was actually "tabl", not "tab1".)
I think this is right like this. column1 needs to store exactly one
pointer at this point, so the size of 4 bytes (on my machine) should
be perfectly right.

"like this" refers to

tabl->column1 = malloc(sizeof tabl->column1);

which is almost certainly incorrect. tabl->column1 is a pointer to
something. Let's say it's of type FOO*. Even if FOO itself happens
to be a pointer type, you *don't* want to allocate sizeof(FOO*) bytes;
you want to allocate sizeof(FOO) bytes. (Not all pointers are
necessarily the same size.)

Again, the usual idiom to allocate a single object is
ptr = malloc(sizeof *ptr);
or, in this case;
tabl->column1 = malloc(sizeof *tabl->column1);

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.