Page MenuHomeFreeBSD
Files F46132450

rb_toy.c
dougm (Doug Moore)
Actions

Authored By
dougm
Aug 4 2022, 10:59 PM
Size
6 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 {
RB_ENTRY(map_entry) rb_entry;
unsigned start;
unsigned end;
#ifdef TEST_AUGMENTATION
unsigned first;
unsigned last;
unsigned free_down;
#endif
};
#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))
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;
}
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;
rh = (RB_RED_RIGHT(element, rb_entry) ? 2 : 1);
rh += dump_tree(RB_RIGHT(element, rb_entry), depth + rh);
if (verbose) {
printf("%*s[%u:%u]\n", 4 * depth, "",
element->start, element->end);
#ifdef TEST_AUGMENTATION
printf(":%u", element->free_down);
#endif
printf("\n");
}
lh = (RB_RED_LEFT(element, rb_entry) ? 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;
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
int count;
for (count = 0; count < 400000000; ++count) {
unsigned val;
struct map_entry key;
val = 1 + random() % maxval;
//printf("Enter: ");
//scanf("%d", &val);
key.end = val;
#ifdef TEST_AUGMENTATION
#ifdef VERIFY
num_nochange_augments = 0;
#endif
#endif
element = RB_FIND(entries_tree, &rb_root, &key);
if (element) {
// printf("-%u\n", val);
RB_REMOVE(entries_tree, &rb_root, element);
free(element);
} else {
// printf("%u\n", val);
#ifdef INSERT_FIRST_FREE
find_space(1);
#else
element = calloc(1, sizeof(*element));
element->start = val-1;
element->end = val;
RB_INSERT(entries_tree, &rb_root, element);
#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
5029657
Default Alt Text
rb_toy.c (6 KB)

Event Timeline