Container Category

• Sequential Container
  • Vector --- The dynamically growable array
  • LinkedList --- The doubly linked list
• Associative Container
  • TreeMap --- The ordered map to store key value pairs
  • HashMap --- The unordered map to store key value pairs
  • HashSet --- The unordered set to store unique elements
  • Trie --- The string dictionary
• Simple Collection Container
  • Queue --- The FIFO queue
  • Stack --- The LIFO stack
  • PriorityQueue --- The queue to maintain priority ordering for elements

Installation

This section illustrates how to install LibCDS to your working directory.

First of all, we need to prepare the CMake build tool:

• CMake - A cross platform build system.

For Ubuntu 12.04 and above, it should be easy:

$ sudo apt-get install -qq cmake

Now we can build the entire source tree under the package root folder:

$ ./clean.py --rebuild
$ cd build
$ cmake .. -DCMAKE_INSTALL_PREFIX=/path/to/your/destination
$ make
$ make install

Upon finishing, the public header should locate at:
/path/to/your/destination/include/
Plus, the shared library should locate at:
/path/to/your/destination/lib/

If you plan for debug build, you can specify the CMake argument list like this:

$ cmake .. -DCMAKE_BUILD_TYPE=Debug -DCMAKE_INSTALL_PREFIX=/path/to/your/destination

Usage

This chapter illustrates how to link and apply LibCDS in your project.

For header file, you just need to include the main header:

#include "cds.h"

Assume that you apply gcc for compilation, then you need the following options:

-I/path/to/your/destination/include/
-L/path/to/your/destination/lib/
-lcds

Now you successfully link LibCDS with your project! But wait, to run your project, you need to tell the dynamic linker how to find LibCDS:

LD_LIBRARY_PATH=/path/to/your/destination/lib/

For detailed API usage, you can refer to the manual or check the demo programs.

Benchmark

Thanks for the HashMap benchmark with various key-value pair manipulations provided by kbench. The results are compared with the other 49 similar C data structure libraries.

• Criteria - C style string as hash key
• Platform - Linux nuc 3.2.0-4-amd64 #1 SMP Debian 3.2.81-1 x86_64 GNU/Linux
• Date - Tue Oct 25 13:25:20 CEST 2016
• Result sorted by CPU time

Rank	Implementation	CPU (secs)	Memory (Mb)	#	Notes
1	rigtorp-hashmap	0.760	347.100	625792
2	rdestl	0.850	290.004	625792
3	ulib	1.010	240.724	625792
4	libevent	1.110	504.988	625792
5	khash	1.140	240.716	625792
6	ccan	1.210	227.240	625792
7	hashit-overflow	1.290	415.924	636452	Bug here!
8	hashit-open	1.300	346.448	625792
9	mct-closed	1.380	339.140	625792
10	amtl	1.410	332.428	625792
11	sys-apr	1.410	256.584	625792	**
12	sys-glib	1.440	228.968	625792	**
13	oddou-hashmap	1.460	299.112	625792
14	google-dense	1.470	380.128	625792	**
15	gcc-libiberty	1.500	240.180	625792
16	uthash	1.540	618.028	625792
17	tommyds-fixed	1.570	944.988	625792
18	python	1.610	264.492	625792
19	Qt-hash	1.700	255.456	625792	**
20	cfu	1.710	272.376	625792
21	ghthash	1.720	362.476	625792
22	tommyds-dynamic	1.760	903.452	625792
23	generic-c-hashmap	1.770	502.416	698396	Bug here!
24	hashit-chain	1.830	300.464	625792
25	CDS	1.870	252.236	625792
26	tommyds-linear	1.900	889.244	625792
27	eastl	1.910	263.584	625792
28	c-hashtable	1.940	257.360	625792
29	sys-tcl	1.960	256.976	625792	**
30	apr	1.970	253.012	625792
31	c-algoritms	2.000	266.996	625792
32	sys-boost	2.080	263.516	625792	**
33	sys-python	2.160	834.312	625792	**
34	redis	2.280	253.212	625792
35	htable	2.380	541.268	625792
36	gcc-unordered_map	2.550	263.592	625792	**
37	ruby-st	2.950	255.504	625792
38	sys-judy	3.040	259.372	625792	**
39	mct-linked	3.110	363.708	625792
40	sglib	3.220	450.572	625792
41	sys-perl	3.300	301.240	625792	**
42	stb	3.390	282.116	625792
43	st	3.530	245.784	625792
44	google-sparse	4.430	251.376	625792	**
45	sys-LuaHashMap	6.110	354.948	625792	**
46	google-c-sparse	6.140	244.408	625792
47	google-c-dense	6.480	244.408	625792
48	gcc-map	7.730	264.996	625792	**
49	Qt-map	8.560	266.776	625792	**
50	lua-table	102.350	264.744	625792

• Result sorted by memory usage

Rank	Implementation	CPU (secs)	Memory (Mb)	#	Notes
1	ccan	1.21	227.24	625792
2	sys-glib	1.44	228.968	625792	**
3	gcc-libiberty	1.5	240.18	625792
4	khash	1.14	240.716	625792
5	ulib	1.01	240.724	625792
6	google-c-sparse	6.14	244.408	625792
7	google-c-dense	6.48	244.408	625792
8	st	3.53	245.784	625792
9	google-sparse	4.43	251.376	625792	**
10	CDS	1.87	252.236	625792
11	apr	1.97	253.012	625792
12	redis	2.28	253.212	625792
13	Qt-hash	1.7	255.456	625792	**
14	ruby-st	2.95	255.504	625792
15	sys-apr	1.41	256.584	625792	**
16	sys-tcl	1.96	256.976	625792	**
17	c-hashtable	1.94	257.36	625792
18	sys-judy	3.04	259.372	625792	**
19	sys-boost	2.08	263.516	625792	**
20	eastl	1.91	263.584	625792
21	gcc-unordered_map	2.55	263.592	625792	**
22	python	1.61	264.492	625792
23	lua-table	102.35	264.744	625792
24	gcc-map	7.73	264.996	625792	**
25	Qt-map	8.56	266.776	625792	**
26	c-algoritms	2	266.996	625792
27	cfu	1.71	272.376	625792
28	stb	3.39	282.116	625792
29	rdestl	0.85	290.004	625792
30	oddou-hashmap	1.46	299.112	625792
31	hashit-chain	1.83	300.464	625792
32	sys-perl	3.3	301.24	625792	**
33	amtl	1.41	332.428	625792
34	mct-closed	1.38	339.14	625792
35	hashit-open	1.3	346.448	625792
36	rigtorp-hashmap	0.76	347.1	625792
37	sys-LuaHashMap	6.11	354.948	625792	**
38	ghthash	1.72	362.476	625792
39	mct-linked	3.11	363.708	625792
40	google-dense	1.47	380.128	625792	**
41	hashit-overflow	1.29	415.924	636452	Bug here!
42	sglib	3.22	450.572	625792
43	generic-c-hashmap	1.77	502.416	698396	Bug here!
44	libevent	1.11	504.988	625792
45	htable	2.38	541.268	625792
46	uthash	1.54	618.028	625792
47	sys-python	2.16	834.312	625792	**
48	tommyds-linear	1.9	889.244	625792
49	tommyds-dynamic	1.76	903.452	625792
50	tommyds-fixed	1.57	944.988	625792

Contact

Please contact me via the mail andy.zsshen@gmail.com.