ℹ️ New Book: Build Your Own Database
redis/11/test_offset.cpp
#include <assert.h>
#include "avl.cpp"
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type, member) );})
struct Data {
AVLNode node;
uint32_t val = 0;
};
struct Container {
AVLNode *root = NULL;
};
static void add(Container &c, uint32_t val) {
Data *data = new Data();
avl_init(&data->node);
data->val = val;
if (!c.root) {
c.root = &data->node;
return;
}
AVLNode *cur = c.root;
while (true) {
AVLNode **from =
(val < container_of(cur, Data, node)->val)
? &cur->left : &cur->right;
if (!*from) {
*from = &data->node;
data->node.parent = cur;
c.root = avl_fix(&data->node);
break;
}
cur = *from;
}
}
static void dispose(AVLNode *node) {
if (node) {
dispose(node->left);
dispose(node->right);
delete container_of(node, Data, node);
}
}
static void test_case(uint32_t sz) {
Container c;
for (uint32_t i = 0; i < sz; ++i) {
add(c, i);
}
AVLNode *min = c.root;
while (min->left) {
min = min->left;
}
for (uint32_t i = 0; i < sz; ++i) {
AVLNode *node = avl_offset(min, (int64_t)i);
assert(container_of(node, Data, node)->val == i);
for (uint32_t j = 0; j < sz; ++j) {
int64_t offset = (int64_t)j - (int64_t)i;
AVLNode *n2 = avl_offset(node, offset);
assert(container_of(n2, Data, node)->val == j);
}
assert(!avl_offset(node, -(int64_t)i - 1));
assert(!avl_offset(node, sz - i));
}
dispose(c.root);
}
int main() {
for (uint32_t i = 1; i < 500; ++i) {
test_case(i);
}
return 0;
}
( Report an Error | Ask a Question) @ build-your-own.org
See also:
codecrafters.io offers “Build Your Own X” courses in many programming languages.
Including Redis, Git, SQLite, Docker, and more.
Check it out
codecrafters.io offers “Build Your Own X” courses in many programming languages.
Including Redis, Git, SQLite, Docker, and more.