tags:

views:

2258

answers:

5

Does anyone know of any C container libraries? I am looking for something which gives standard implementations of linked lists, arrays, hash tables etc, much in the same way as the C++ STL does. Key concerns are:

  1. Client code should be able to create containers for multiple different data types without modifying the library.
  2. The interface for creating and using the containers should be intuitive.
+4  A: 

Chuck Falconer has a decent hash library written in C that includes a C++ interface, click on hashlib.zip on the webpage to download.

Ben Pfaff has very nice and extremely well-documented binary and balanced tree library, GNU libavl, that implements most major tree structures including binary search trees, AVL trees, red-black trees and threaded versions of each.

libavl is licensed under the LGPL (as of version 2.0.3), hashlib is GPL.

I'm not sure what you are looking for as far as arrays and linked lists go as the former is supported directly by the language and the latter is generally trivial enough to implement without warranting a library.

Robert Gamble
I recently had a look at Chuck Falconer's hash table and it is quite good. My only complaint is that it is unclear whether one can use it in a commercial project. He asks you to contact him for permission.
Nick
@Nick: There's really nothing unclear about the permissions for using Falconer's hashlib code: it's clearly licensed under the GPL. If your commercial code is fine with the GPL terms (basically if your commercial code is also GPL licensed) there's no need to contact him. If you want other licensing terms than the GPL, he's open to being contacted about that.
Michael Burr
+3  A: 

I just came across SGLIB while looking for a C implementation of a map/dictionary container. Unfortunately, no map but it seems to include the containers you asked about. I have no idea how good it is.

http://sglib.sourceforge.net.

Nick
+2  A: 

I've been using a library I've been growing from Hanson's "C Interface and Implementations" book. His source is downloadable at

cii book website

Everything is an Abstract Data Type. There is List, Set, Table (map).

navicore
Eventually, you can find that the code is at http://code.google.com/p/cii/ and is licenced under the extremely flexible MIT licence.
Jonathan Leffler
+1  A: 

#include "queue.h" to get access to the implementations of singly-linked lists, singly-linked tail queues, lists and tail queues.

I found a generic cache for storing arbitrary objects in memory by D. J. Bernstein (http://cr.yp.to/djbdns.html) to be both clean, simple and super fast. Look up cache.h and cache.c in djdns tarball.

+1  A: 

Sglib is a excelent generic data structures library. The library currently provides generic implementation for: sorting arrays linked lists sorted linked lists double linked lists red-black trees hashed containers

It's very fast. More fastest that glib. It's inspired by the Standard Template Library. Download here

Another solution is Attractive Chaos sotware. C macro library:
kbtree.h: efficient B-tree library in C.
khash.h: fast and light-weighted hash table library in C.
kvec.h: simple vector container in C.

Kulesh Shanmugasundaram present the generic Linux Kernel Linked List and a generic hash table based in the Linux Kernel Linked List

Sglib and Attractive Chaos sotware and and Linux Kernel Linked List are C macros library. Using void* to implement generic containers in C may be inefficient. C macros mimics C++ template and are as efficient as C++ template

Lear