Page MenuHomeFreeBSD
Files F46792064

rb_toy.c
dougm (Doug Moore)
Actions

Authored By
dougm
Aug 17 2022, 5:05 AM
Size
7 KB
Referenced Files
None
Subscribers
None

rb_toy.c
View Options

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.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
#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;
};
#ifdef VERIFY
#include <assert.h>
static unsigned num_nochange_augments;
#endif
struct entries_tree rb_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);
}
#ifdef TEST_AUGMENTATION
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#ifdef ORIG_AUG
void
augment_entry(struct map_entry *entry)
{
struct map_entry *child;
unsigned free_down;
free_down = 0;
if ((child = RB_LEFT(entry, rb_entry)) != NULL) {
free_down = MAX(free_down, child->free_down);
free_down = MAX(free_down, entry->start - child->last);
entry->first = child->first;
} else
entry->first = entry->start;
if ((child = RB_RIGHT(entry, rb_entry)) != NULL) {
free_down = MAX(free_down, child->free_down);
free_down = MAX(free_down, child->first - entry->end);
entry->last = child->last;
} else
entry->last = entry->end;
entry->free_down = free_down;
}
#else
void
augment_entry(struct map_entry *entry)
{
struct map_entry *left, *right;
unsigned end, free_down, start;
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, free_down;
bool changed;
free_down = 0;
bound = entry->start;
if ((child = RB_LEFT(entry, rb_entry)) != NULL) {
free_down = MAX(child->free_down, bound - child->last);
bound = child->first;
}
changed = entry->first != bound;
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;
}
changed = changed ||
(entry->last != bound) || (entry->free_down != free_down);
entry->last = bound;
entry->free_down = free_down;
#ifdef VERIFY
if (!changed)
++num_nochange_augments;
#endif
// if (verbose)
// printf("aug: [%u:%u]%d\n", entry->start, entry->end, changed);
return (changed);
}
#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 int
dump_tree(struct map_entry *element, int depth)
{
int lh, rh;
if (element == NULL)
return 0;
__uintptr_t bits = RB_BITS(element, rb_entry);
rh = (bits & RB_RED_R) ? 2 : 1;
rh += dump_tree(RB_RIGHT(element, rb_entry), depth + rh);
if (verbose) {
printf("%*s[%u:%u]", 4 * depth, "",
element->start, element->end);
#ifdef TEST_AUGMENTATION
printf(":%u", element->free_down);
#endif
printf("\n");
}
lh = (bits & RB_RED_R) ? 2 : 1;
lh += dump_tree(RB_LEFT(element, rb_entry), depth + lh);
#ifdef VERIFY
assert(lh == rh);
assert(lh != 2 ||
RB_LEFT(element, rb_entry) != NULL ||
RB_RIGHT(element, rb_entry) != NULL);
#ifdef TEST_AUGMENTATION
rh = augment_entry_check(element);
assert(!rh);
#endif
#endif
return (lh);
}
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 = 0;
nodes[i].end = i;
}
for (int i = 0; i < maxval; ++i) {
int r = i + random() % (maxval - i);
unsigned x = nodes[r].end;
nodes[r].end = nodes[i].end;
nodes[i].end = x;
}
clock_gettime(CLOCK_REALTIME_PRECISE, &tp1);
#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
#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;
RB_INSERT(entries_tree, &rb_root, &nodes[j % maxval]);
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;
RB_INSERT(entries_tree, &rb_root, &nodes[k]);
}
RB_ROOT(&rb_root) = NULL;
}
#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);
dump_tree(RB_ROOT(&rb_root), 0);
#else
if (verbose)
dump_tree(RB_ROOT(&rb_root), 0);
#endif
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);
return (0);
}

File Metadata

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

Event Timeline