80

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.
0

8 Answers 8

26

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.

3
  • 3
    As of 2013-07, that sourceforge project appears to be dead. I noticed that the docs didn't mention the word "error" anywhere, nor mention any error handling. Jacob Navia's C Container Library is much, much better in this area, and has ~370 pages of formal documentation - but sadly, his ccl isn't open source. Jul 4, 2013 at 14:57
  • As of May-2014, the link is not dead.
    – 101010
    May 10, 2014 at 0:35
  • 1
    Actually, Jacob Navia's C Container Library is open source - see code.google.com/p/ccl - I emailed the author and confirmed that the "non-commercial" restrictions mentioned elsewhere on his site don't apply to CCL.
    – starseeker
    Apr 4, 2015 at 17:02
11

Sglib is an excellent 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. Faster 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 presents the generic Linux Kernel Linked List and a generic hash table based in the Linux Kernel Linked List.

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

2
  • 2
    You said "Using void* to implement generic containers in C may be inefficient." -- Can you please explain why you think so?
    – Arun
    Jul 12, 2013 at 16:47
  • @Arun I guess it have to do with bad memory locality. You can have data laying nicely inside some data structures, but generic void * will likely point all over your process's address space. Aug 24, 2020 at 16:46
10

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.

4
  • 1
    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. Jun 12, 2009 at 14:23
  • 2
    @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. Mar 25, 2010 at 18:25
  • 2
    @Michael Burr: GPL and LGPL in short mean can't be used in a commercial environment or true open source environment. I would suggest to also those considering this as a solution to look elsewhere.
    – Matthieu N.
    Jan 6, 2011 at 20:18
  • 1
    @Zenikoder: that's true for many, maybe even most, commercial projects. But the particulars of whether or not GPL or LGPL code can be used in a commercial project depends entirely on the requirements of the commercial project. I've worked a couple places that were fine with using LGPL code as long as it was used only in in DLL form. Jan 6, 2011 at 23:59
8

How about ccl? This is a container library which has been (unsuccessfully) proposed for C standard. Maybe it's best fit for you. You can see https://code.google.com/p/ccl/ https://github.com/jacob-navia/ccl. Enjoy it.

1
  • 2
    This answer was not already given by @navicore. He was talking about a different library with a few-pixels-different acronym. Jul 4, 2013 at 7:07
5

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).

2
  • 4
    Eventually, you can find that the code is at code.google.com/p/cii and is licenced under the extremely flexible MIT licence. May 24, 2009 at 2:43
  • This library doesn't seem to offer C-style fine-grained error handling, but rather the coarse approach of exceptions with setjmp/longjmp. It's not a good candidate for code where uptime is critical. Jul 4, 2013 at 7:03
2

#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.

2

Some of the ones that I have heard of (but never used) are

  • Glib
  • iMatix Standard Function Library
  • disparate elements from the Linux kernel headers (e.g. list)
2

This seems to cover most of the containers and some algorithms. There is also no licensing, all the headers contain - 'code may be used without restriction.' http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=13867&lngWId=3

Not the answer you're looking for? Browse other questions tagged or ask your own question.