Thread: How do people usually implement a table (as a data structure) in C?

I'm writing a bit of C code and find that more than anything, I need a table data structure.

Pretty much just like a SQL table: I have this key, I want this column, give me the value. Not multi-row (i.e., only one row matching a key) but not simple key/value either - for each key, I have many columns.

Is a hash with a key that returns a struct the best way to accomplish this? For cases where there's a very small number of values, I've just been using a linked lists of structs (i.e., walking a list of 10 values is so fast that a hash is probably a waste of time). But for bigger tables, is a hash the way to go?

Of course, this doesn't help if the columns are dynamic :-)

I'm aware of sqlite which I might also use.

sqlite is definitely an option, but may be overkill if you don't need any multi-row stuff. A hash may work, but generally only if you use a good hashing function. A balanced binary tree may work if your keys can be ordered (pretty much anything can). I wouldn't write my own though. Look into something like glib (GLib Reference Manual), that has lots of lightweight data structures that may work. Just not a linked list.

What do you mean the columns are "dynamic", and why don't you think a hash will work there? A hash will work as long as the relationship between a key and what it maps to is consistent. That is, if you look up somebody by social security number (say 123-45-6789), it should always map to the same person (say, Jon Doe). That person's phone number may change, and thus a query for phone number for SSN 123-45-6789 might give back 987-654-3210 or 888-555-1212, but either way, it's the phone number for Jon Doe.

Addendum: If this is a lookup-only table, like you read in a huge database/dictionary, and don't modify the data at runtime (or very rarely do), then you can just read it into an array of structs that contain the data along with the lookup key. Use the C standard qsort function to sort your array and the standard bsearch function to look up the structure you want based on a key. If you have rare modifications, increase your array and add your new element in order, or add it to the end and call qsort again.

Originally Posted by raindog308

I'm writing a bit of C code and find that more than anything, I need a table data structure.

Pretty much just like a SQL table: I have this key, I want this column, give me the value. Not multi-row (i.e., only one row matching a key) but not simple key/value either - for each key, I have many columns.

Is a hash with a key that returns a struct the best way to accomplish this? For cases where there's a very small number of values, I've just been using a linked lists of structs (i.e., walking a list of 10 values is so fast that a hash is probably a waste of time). But for bigger tables, is a hash the way to go?

Of course, this doesn't help if the columns are dynamic :-)

I'm aware of sqlite which I might also use.

If I'm understanding this correctly... you're basically looking for a single indexed information retrieval system? in that case you may want to look into a very basic random access filing system. No point fishing with dynamite if the fish are already jumping into your boat.

Why not use a 2D array for this? Put in all the columns you need. One record per row.

Is the data too massive to fit into RAM?