Skip to content

recp/ds

Folders and files

NameName
Last commit message
Last commit date

Latest commit

7b01d5a Β· Sep 14, 2023

History

98 Commits
Oct 30, 2021
Sep 14, 2023
Sep 14, 2023
Oct 28, 2021
May 19, 2020
Oct 20, 2019
Oct 20, 2019
Oct 30, 2021
Jul 4, 2017
Jul 4, 2017
Jun 24, 2017
Apr 20, 2021
Jun 24, 2017
May 26, 2018
Sep 14, 2023
May 29, 2020

Repository files navigation

πŸ”— Data Structures and Algorithms

Build Status Build status Coverage Status Codacy Badge

This library provides common data structures. It will also provide some data structures which needed in render or game engines. In the future I'll try to optimize memmory access.

There may multiple way to implement a data structure but I tried to implement best way to do that. For instance Red-Black Trees are only implemented as top down insertion/deletion to make it faster.

There are some convenient constructors for common use cases. For instance rb_newtree_str() creates new rb-tree that uses strings as key, rb_newtree_ptr() creates new rb-tree that uses pointers as key. When you use these functions to alloc a data structure then you don't need to provide compare or print functions.

This library prodives allocator api so you can override default allocator.

Usage

#include <ds/rb.h> // Red-Black Tree

int
main(int argc, const char * argv[]) {
  RBTree *tree;
  /* ... */

  /* use string keys */
  tree = rb_newtree_str();

  rb_insert(tree, "key", value);

  /* ... */
  value = rb_find(tree, "key");

  rb_destroy(tree);
}

Todo

  • rbtree
    • top-down insertion
    • top-down deletion
  • forward-list
    • forward-list-separate (reduces FList struct)
  • hash-table
    • builtin hash functions e.g. djb2
    • resizing hash table
  • quick sort implementation for float, double, i32, u32, i64, u64
  • queue (working on this)
  • stack
  • binary heap / priority queue
  • dynamic array
  • octree
  • quadtree
  • kd-tree
  • bvh
  • b-tree

Build

Unix (Autotools)

$ sh autogen.sh
$ ./configure
$ make
$ make check # [Optional]
$ [sudo] make install # [Optional]

Windows (MSBuild)

Windows related build, project files are located in win folder, make sure that you are inside in the libds/win folder. Code Analysis are enabled, it may take awhile to finish build

$ cd win
$ .\build.bat

if msbuild didn't work then you can try to build it with devenv:

$ devenv libds.sln /Build Release

License

MIT. check the LICENSE file