470,826 Members | 2,244 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,826 developers. It's quick & easy.

Example for an dynamically allocated associative array in C

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!

Jun 10 '06 #1
13 2011
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)
Jun 10 '06 #2
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.

Jun 10 '06 #3
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!

Jun 10 '06 #4
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)
Jun 10 '06 #5
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
Jun 10 '06 #6
"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.
Jun 10 '06 #7
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!

Jun 10 '06 #8
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

Jun 10 '06 #9
"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.
Jun 10 '06 #10
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!
Jun 10 '06 #11
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)
Jun 10 '06 #12
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?
Jun 10 '06 #13
"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.
Jun 10 '06 #14

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

27 posts views Thread by Abdullah Kauchali | last post: by
6 posts views Thread by mark4asp | last post: by
4 posts views Thread by Robert | last post: by
8 posts views Thread by Derek Basch | last post: by
41 posts views Thread by Rene Nyffenegger | last post: by
6 posts views Thread by bwaichu | last post: by
reply views Thread by mihailmihai484 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.