Page MenuHomeFreeBSD
Files F48022144

rb_toy.c
dougm (Doug Moore)
Actions

Authored By
dougm
Sep 10 2022, 3:18 AM
Size
8 KB
Referenced Files
None
Subscribers
None

rb_toy.c
View Options

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>
struct map_entry;
#ifdef TEST_AUGMENTATION
#define RB_AUGMENT(entry) augment_entry(entry)
#define RB_AUGMENT_CHECK(entry) augment_entry_check(entry)
#endif
#define _RB_DIAGNOSTIC 1
#include "../../../sys/sys/tree.h"
RB_HEAD(entries_tree, map_entry);
RB_PROTOTYPE(entries_tree, map_entry, rb_entry, cmp_entries);
struct map_entry {
unsigned start;
unsigned end;
#ifdef TEST_AUGMENTATION
unsigned first;
unsigned last;
unsigned free_down;
#endif
RB_ENTRY(map_entry) rb_entry;
};
static unsigned num_augments;
#ifdef VERIFY
#include <assert.h>
static unsigned num_nochange_augments;
#define DO_VERIFY(stmt) do { \
num_nochange_augments = 0; \
stmt; \
assert(num_nochange_augments <= 1); \
assert(entries_tree_RB_RANK(RB_ROOT(&rb_root)) >= 0); \
} while (0)
#else
#define DO_VERIFY(stmt) stmt
#endif
struct entries_tree rb_root = RB_INITIALIZER(root);
static int verbose = 0;
static int
cmp_entries(struct map_entry *a, struct map_entry *b)
{
return (b->end < a->end) - (a->end < b->end);
}
#ifndef TEST_AUGMENTATION
#define CLEAR_AUGDATA(element) do {} while(0)
#else
#define CLEAR_AUGDATA(element) do { \
(element)->first = 0; \
(element)->last = 0; \
(element)->free_down = 0; \
} while (0)
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#ifndef ALT_AUG
void
augment_entry(struct map_entry *entry)
{
struct map_entry *child;
unsigned bound, free_down;
++num_augments;
free_down = 0;
bound = entry->start;
if ((child = RB_LEFT(entry, rb_entry)) != NULL) {
free_down = MAX(free_down, child->free_down);
free_down = MAX(free_down, bound - child->last);
bound = child->first;
}
entry->first = bound;
bound = entry->end;
if ((child = RB_RIGHT(entry, rb_entry)) != NULL) {
free_down = MAX(free_down, child->free_down);
free_down = MAX(free_down, child->first - bound);
bound = child->last;
}
entry->last = bound;
entry->free_down = free_down;
}
#else
void
augment_entry(struct map_entry *entry)
{
struct map_entry *left, *right;
unsigned end, free_down, start;
++num_augments;
start = entry->start;
end = entry->end;
left = RB_LEFT(entry, rb_entry);
right = RB_RIGHT(entry, rb_entry);
if (left != NULL) {
entry->first = left->first;
free_down = start - left->last;
if (right != NULL) {
free_down = MAX(free_down, left->free_down);
free_down = MAX(free_down, right->free_down);
}
} else {
entry->first = start;
free_down = 0;
}
if (right != NULL) {
free_down = MAX(free_down, right->first - end);
end = right->last;
}
entry->last = end;
entry->free_down = free_down;
}
#endif
bool
augment_entry_check(struct map_entry *entry)
{
struct map_entry *child;
unsigned bound, delta, free_down;
++num_augments;
free_down = 0;
bound = entry->start;
if ((child = RB_LEFT(entry, rb_entry)) != NULL) {
free_down = MAX(free_down, child->free_down);
free_down = MAX(free_down, bound - child->last);
bound = child->first;
}
delta = bound - entry->first;
entry->first = bound;
bound = entry->end;
if ((child = RB_RIGHT(entry, rb_entry)) != NULL) {
free_down = MAX(free_down, child->free_down);
free_down = MAX(free_down, child->first - bound);
bound = child->last;
}
delta += entry->last - bound;
delta += entry->free_down - free_down;
entry->last = bound;
entry->free_down = free_down;
#ifdef VERIFY
if (delta == 0)
++num_nochange_augments;
#endif
return (delta != 0);
}
#endif
RB_GENERATE(entries_tree, map_entry, rb_entry, cmp_entries);
#ifdef TEST_AUGMENTATION
/* Find the next entry that might abut a big-enough range. */
static struct map_entry *
find_next(struct map_entry *curr, unsigned min_free)
{
struct map_entry *next;
if ((next = RB_RIGHT(curr, rb_entry)) != NULL &&
next->free_down >= min_free) {
/* Find next entry in right subtree. */
do
curr = next;
while ((next = RB_LEFT(curr, rb_entry)) != NULL &&
next->free_down >= min_free);
} else {
/* Find next entry in a left-parent ancestor. */
while ((next = RB_PARENT(curr, rb_entry)) != NULL &&
curr == RB_RIGHT(next, rb_entry))
curr = next;
curr = next;
}
return (curr);
}
static int
find_space(unsigned size)
{
struct map_entry *curr, *first;
struct map_entry *entry = calloc(1, sizeof(*entry));
if (entry == NULL)
return (-1);
/*
* Find the first entry in the lower region that could abut a big-enough
* range.
*/
curr = RB_ROOT(&rb_root);
first = NULL;
while (curr != NULL && curr->free_down >= size) {
first = curr;
curr = RB_LEFT(curr, rb_entry);
}
if (first == NULL)
return (-1);
/*
* Walk the big-enough ranges until one satisfies alignment
* requirements, or violates lowaddr address requirement.
*/
for (curr = first; curr != NULL;
curr = find_next(curr, size)) {
if ((first = RB_LEFT(curr, rb_entry)) != NULL) {
if (curr->start - first->last >= size) {
entry->start = first->last;
entry->end = entry->start + size;
RB_INSERT(entries_tree, &rb_root, entry);
return (0);
}
}
if ((first = RB_RIGHT(curr, rb_entry)) != NULL) {
if (first->first - curr->end >= size) {
entry->start = curr->end;
entry->end = entry->start + size;
RB_INSERT(entries_tree, &rb_root, entry);
return (0);
}
}
}
free(entry);
return (-1);
}
#endif
static void
dump_tree(struct map_entry *element, int depth)
{
int steplen;
if (element == NULL)
return;
struct map_entry *up = _RB_UP(element, rb_entry);
steplen = (_RB_BITS(up) & _RB_R) ? 2 : 1;
dump_tree(RB_RIGHT(element, rb_entry), depth + steplen);
if (verbose) {
printf("%*s[%u:%u]", 4 * depth, "",
element->start, element->end);
#ifdef TEST_AUGMENTATION
printf(":%u", element->free_down);
#endif
printf("\n");
}
steplen = (_RB_BITS(up) & _RB_L) ? 2 : 1;
dump_tree(RB_LEFT(element, rb_entry), depth + steplen);
}
int main()
{
struct timespec tp1, tp2;
struct map_entry *element;
const unsigned maxval = 65536;
struct map_entry nodes[65536];
for (int i = 0; i < maxval; ++i) {
nodes[i].start = i;
nodes[i].end = i+1;
}
for (int i = 0; i < maxval; ++i) {
int r = i + random() % (maxval - i);
unsigned x = nodes[r].start;
unsigned y = nodes[r].end;
nodes[r].start = nodes[i].start;
nodes[r].end = nodes[i].end;
nodes[i].start = x;
nodes[i].end = y;
}
#ifdef REM_ONLY
struct map_entry backup[65536];
struct map_entry *back_root;
for (int i = 0; i < maxval; ++i)
RB_INSERT(entries_tree, &rb_root, &nodes[i]);
memcpy(backup, nodes, sizeof(nodes));
back_root = RB_ROOT(&rb_root);
#endif
#ifdef INSERT_FIRST_FREE
element = malloc(sizeof(*element));
element->start = 0;
element->end = 0;
RB_INSERT(entries_tree, &rb_root, element);
element = malloc(sizeof(*element));
element->start = maxval + 1;
element->end = maxval + 1;
RB_INSERT(entries_tree, &rb_root, element);
#endif
clock_gettime(CLOCK_REALTIME_PRECISE, &tp1);
#ifdef PLAIN
for (int i = 0; i < maxval / 2; ++i)
RB_INSERT(entries_tree, &rb_root, &nodes[i]);
for (int i = 0; i < 4095 * maxval; ++i) {
int j = i + maxval / 2;
CLEAR_AUGDATA(&nodes[j % maxval]);
DO_VERIFY(RB_INSERT(entries_tree, &rb_root, &nodes[j % maxval]));
DO_VERIFY(RB_REMOVE(entries_tree, &rb_root, &nodes[i % maxval]));
}
for (int i = 0; i < maxval / 2; ++i)
RB_REMOVE(entries_tree, &rb_root, &nodes[i]);
#endif
#ifdef INS_ONLY
for (int j = 0; j < 4096; ++j) {
for (int i = 0; i < maxval; ++i) {
int k = (i + j) % maxval;
CLEAR_AUGDATA(&nodes[k]);
RB_INSERT(entries_tree, &rb_root, &nodes[k]);
}
RB_INIT(&rb_root);
}
#endif
#ifdef REM_ONLY
for (int j = 0; j < 8192; ++j) {
for (int i = 0; i < maxval; ++i) {
int k = (i + j) % maxval;
RB_REMOVE(entries_tree, &rb_root, &nodes[k]);
}
memcpy(nodes, backup, sizeof(nodes));
RB_ROOT(&rb_root) = back_root;
}
#endif
#ifdef TEST_AUGMENTATION
#ifdef VERIFY
num_nochange_augments = 0;
#endif
#endif
#ifdef INSERT_FIRST_FREE
find_space(1);
#else
#endif
#ifdef VERIFY
assert(num_nochange_augments <= 1);
assert(entries_tree_RB_RANK(RB_ROOT(&rb_root)) >= 0);
#endif
if (verbose)
dump_tree(RB_ROOT(&rb_root), 0);
clock_gettime(CLOCK_REALTIME_PRECISE, &tp2);
int borrow = tp2.tv_nsec < tp1.tv_nsec;
printf("%ld.%09ld\n",
tp2.tv_sec - tp1.tv_sec - borrow,
tp2.tv_nsec - tp1.tv_nsec + borrow * 1000000000);
fprintf(stderr, "%u\n", num_augments);
return (0);
}

File Metadata

Mime Type
text/x-c
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
5116105
Default Alt Text
rb_toy.c (8 KB)

Event Timeline