Archive for October, 2009

C Container Library

2009/10/05

A container library is a data structure library for containing data. Common examples are stack, hash-table, tree and queue. Container libraries for C++ and Java are standardized by the Standard Template Library and the Java Collections Framework. However, C programs such as the Linux kernel, GTK/GLib, Apache httpd, usually implement their own modules for individual projects. There are a few generic C container libraries which I will discuss later. For some reason, none of them don’t get much attention, not to mention getting standardized. Browsing through the latest Fedora and Ubuntu packages, I don’t find any C container related library. (If you know any, please let me know by leaving a comment here.)

Before discussing individual existing c container libraries, I will give way to categorize them by memory management.

  • user-managed
    User of the library manages the container’s data structure memory. Usually the container data structure is put together with the data. The most notable example is the Linux kernel linked list.

    struct student {
       int student_id;
       /* This is the container DS. */
       struct list_head list;
    };
    
    struct list_head *pos;
    list_for_each(pos, &head) {
       /* list_entry() is just pointer arithmetic */
       struct student *stu = list_entry(pos, struct student, list);
       printf("%d\n", stu->student_id);
    }
    

    The main advantage of this type is memory efficiency, because container DS struct list_head is allocated together with data DS struct student.

  • lib-managed
    TO BE CONTINUED…
  • immortal
Advertisements