jarun/dslib

dslib

dslib is a library of cohesive data structures. The goal of dslib is to demonstrate how complex data structures (and related algorithms) can be developed by reusing simpler ones. In general, textbooks come with numerous unrelated examples, each relevant to a specific data structure. dslib, on the other hand, grows by building on the elementary data structures.

The core component is a circular doubly linked list. Library-internal data structures are dynamically (de)allocated.

Most of the code conforms to the Linux kernel coding standards (verified against checkpatch.pl), other than a few unavoidable instances.

dslib is an academic library. However, we'll be glad if someone finds any other application of it.

Table of Contents

• Building blocks
• APIs
• Thread-safety
• Compilation
• Testing
• Developers
• Contributions

Building blocks

There are test cases for each DS. Though not very organized, they provide an insight into the usage of dslib.

APIs

A complete list of APIs can be found in apilist.txt. Most of the APIs are iterative. The following 2 APIs are recursive and the iterative implementations are left as an exercise:

bool delete_tree_node(tree_pp head, int val);
bool delete_avl_node(avl_pp head, int val);

Thread-safety

Currently the Thread-Safe mode is implemented only for AVL. The lock functions are in common.h and common.c and it's easy to extend thread-safety in other structures.

Compilation

The following compilation steps are tested on Ubuntu 14.04.4 x86_64:

$ git clone https://github.com/jarun/dslib/
$ cd dslib
$ make

To install dslib, run:

$ sudo make install

To remove dslib from your system, run:

$ sudo make uninstall

Clean up (cleans test executables too):

$ make clean

Testing

Make sure dslib is installed. To compile test cases under test subdirectory:

$ sudo make install
$ make test

Only informative logs are enabled. For DEBUG logs, set:

int current_log_level = DEBUG;

in the source test file.

Developers

• Arun Prakash Jana (Copyright © 2015)
• Ananya Jana

Contributions

Contributions are welcome! We would love to see more data structures and APIs added to dslib.