• Stars
    star
    50
  • Rank 577,233 (Top 12 %)
  • Language
    C
  • License
    MIT License
  • Created over 7 years ago
  • Updated over 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

🔗 Common Data Structures and Algorithms

🔗 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

More Repositories

1

cglm

📽 Highly Optimized 2D / 3D Graphics Math (glm) for C
C
2,271
star
2

AssetKit

🎨 Modern 2D/3D - Importer • Exporter • Util - Library, also known as (AssetIO)
C
186
star
3

cmt

🎮 C Bindings/Wrappers for Apple's METAL framework
C
168
star
4

gkern

🎥 Graphics Kernel: flexible, highly configurable, extensible render engine (realtime + offline)
C
98
star
5

tm

timers and timeline
C
40
star
6

gpu

🔭 cross platform general purpose GPU library - optimized for rendering
C
31
star
7

json

🔋 In-place lightweight JSON parser
C
25
star
8

im

📷 image loader library for fast load images especially for rendering and image analysis (In Progress)
C
10
star
9

phy

physics engine written in C
C
10
star
10

simple-collada-viewer

A simple viewer to show how to use AssetKit, libgk, assetkit-gl and cglm libraries (with screenshot)
C
6
star
11

libsig

Signal/Event handling lib for C/C++
C++
5
star
12

mathkit

C vector, matrix library (including 3d, opengl math)
C
5
star
13

rays

Physically-based path tracer for production rendering (may include fast ray tracer as altnative render path)
C
5
star
14

assetkit-gl

Bridge library for loading AssetKit to libgk
C
4
star
15

filt

Image Filter
C
3
star
16

asset-xchange

new file format to store 2d/3d assets for game and films
3
star
17

http

http parser and utility
C
2
star
18

ui

🖱 user interface library top of GPU (OpenGL/Metal/Vulkan...)
Objective-C
2
star
19

libui

Cross platform user interface (including graphics) library for C++
C++
1
star
20

netutils

Network Utils for C/C++
C
1
star
21

sample-models

3D sample models for loaders (AssetKit) for testing purpose
1
star
22

Qt-Dispatch

C++
1
star