/
README
69 lines (61 loc) · 3.91 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
--------- CDS ------------
C Data Structures Library
Author: Jeff Lansing
Email: jlansing3 AT gmail DOT com
Updated: 1/11/2011
Disclaimer: Can be used for personal use. If for commercial use, please ask for my permission.
Please credit my source code before redistributing it elsewhere. I am not responsible
for any damages brought about by the use of this code. Use it at your own risk.
Description: This code is in a very early, pre-alpha state. It was started as a side project to
show I can write efficient data structures in a procedural language like C. It currently supports
all types (with void pointers) for the following data structures:
- dynamic array (cds_dynamic_array)
- singly linked list (cds_slist)
- doubly linked list (cds_dlist)
- stack (cds_stack)
- queue (cds_queue)
- binary search tree (cds_binary_tree)
- hashtable (cds_hash_table)
In the future I plan to implement the following structures:
- skip list
- set
- possibly others
CDS tries to use consistent practices amongst the entire code base
- Every custom type, function, and macro starts with the cds_ or CDS_ prefix
- Data structure functions are typically structured in the following way: cds_datastructurename_function
Therefore, to push_back an element onto a dynamic array you would call cds_dynamic_array_push_back();
This tends to make function calls and type names long, but is good practice, keeps things consistent,
and avoids polluting the namespace
- Most data structure functions return a cds_result enum. Every error code that could be thrown in any
of the provided functions is a cds_result. This keeps results more informative, consistent, and performance
friendly. Rather than returning -1 or NULL when an error occurs, it returns more specific information
(e.g. CDS_BAD_ALLOC). This is better practice because a number of things can potentially go wrong with a given
operation, and this tries to ease the amount of time spent guessing.
- Assertions are given but not fully apparent in all of the code. They can be compiled out of runtime code since
they use optional macros. I'm currently reconsidering the place of assertions in the codebase, and if they mix
well with status return codes.
- Common operations include:
create: allocates the given structure
clear: removes the elements from the given structure
delete: deletes the given structure (but not it's elements)
delete_all: deletes the given structure and it's pointers to other elements
add/push_back/insert/etc: adds the pointer to the structure
remove/pop_back/pop/etc: removes a pointer from the structure
count: get the current count of the structure
find: search for a pointer address or do a value comparison via a cds_cmp_func
- Support for custom memory allocators and log functions that can be interchanged easily at runtime
- Support for custom growth behavoirs, type specific comparisons, and more through function pointers, enums, and macros
Please see the example test cases in the /examples directory. Each can be compiled with the included makefile. The targets
are the name of the data structure in use (e.g. to compile the cds_slist example program compile using "make slist" then
run "bin\slist_test")
Caveats:
Compiler support: Only tested with gcc and msvc. But more testing is pending...
Thread Safety: Would be implemented later down the road...
Const Correctness: Now fixed.
ANSI C: Now fully compatible with C90.
C++: Now "supported" with extern "C" and with stricter casting
Documentation: CDS now uses the Doxygen documentation system. Browse to docs/html to view the reference.
Bugs: They exist, I haven't hammered down every case. In particular, the binary tree and the hash table
are less mature than the rest of the code base. I'm working on handling this when I can.
Everything can compile with -Wall -Wpadded and -ansi without any warnings or errors. At the time being you'll have to
adjust the provided makefile for custom builds.