-
Notifications
You must be signed in to change notification settings - Fork 11
/
db_redblack.h
40 lines (30 loc) · 1.44 KB
/
db_redblack.h
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
#pragma once
#include "base64.h"
#include "db.h"
// red-black tree descent stack
#define RB_bits 24
typedef struct {
uint32_t lvl; // height of the stack
DbAddr entry[RB_bits]; // stacked tree nodes
} PathStk;
typedef struct {
DbAddr left, right, addr; // next nodes down, entry addr
uint32_t payLoad; // length of payload following
uint16_t keyLen; // length of key after payload
uint8_t red; // is tree node red?
} RedBlack;
#define rbkey(entry) ((char *)(entry + 1) + entry->payLoad)
RedBlack *rbFind(DbMap *parent, DbAddr *childNames, char *name, uint32_t nameLen, PathStk *path);
RedBlack *rbNew (DbMap *map, char *key, uint32_t keyLen, uint32_t payload);
RedBlack *rbStart(DbMap *map, PathStk *path, DbAddr *root);
RedBlack *rbNext(DbMap *map, PathStk *path);
void rbAdd(DbMap *map, DbAddr *root, RedBlack *entry, PathStk *path);
bool rbDel (DbMap *map, DbAddr *root, RedBlack *entry);
void rbKill (DbMap *map, DbAddr root);
void rbLeftRotate (DbMap *map, DbAddr *root, DbAddr slot, RedBlack *parent, int cmp);
void rbLeftRotate (DbMap *map, DbAddr *root, DbAddr slot, RedBlack *parent, int cmp);
void rbAdd (DbMap *map, DbAddr *root, RedBlack *entry, PathStk *path);
bool rbDel (DbMap *map, DbAddr *root, RedBlack *entry);RedBlack *rbNew (DbMap *map, char *key, uint32_t keyLen, uint32_t payLoad);
RedBlack *rbStart(DbMap *map, PathStk *path, DbAddr *root);
RedBlack *rbNext(DbMap *map, PathStk *path);
void rbKill (DbMap *map, DbAddr slot);