Skip to content
/ zda Public

Practical toolbox of data structures and algorithms

License

Notifications You must be signed in to change notification settings

Conzxy/zda

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

94 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Zda

Introduction

The repo is a toolbox that contains various pratical data structures and algorithms, such as red-black tree, linked-list, etc.
These data structures can be split into two catogories:

  • Intrusive data structures
  • Non-intrusive data structure

These intrusive data structures are written in C programming language. I think use C instead of C++ is more great choice since I think the template is also evil in some scenarios, eg. It requires you write all code in header to generic data structure. To instrusive design, template is not required to record the compile time information, such as typename, etc. Thus, I use C to complete them.
The intrusive design to make the data structure be generic, flexible and powerful, eg. you can insert nodes but don't cause dynamic memory allocation, that is, these nodes can be allocated in stack or code segments(global variable). Besides, you can allocate multiple nodes in the same memory region to get great memory locality.

To some data structures, I use C++ with tempaltes, e.g., generic dynamic array, it is difficult to C. If you use macros to implement it, user must register entry type to function-like macro every time. Other methods are wrong, since C lacks of template.

Schedule

C++ wrapper class

The library also provides C++ wrapper class template to make C++ user easy to use. For example,

template <typename Entry, typename Free = LibcFree>
class List {
  /* .. */
};

If you want to know more, please read the code file that ends with the *.hpp extension.

Benchmark

TODO...