treerace.c
dougm (Doug Moore)
Actions

Authored By

	dougm
	Jul 9 2020, 10:08 PM

Size

1 KB

Referenced Files

None

Subscribers

None

treerace.c
View Options

	#include <assert.h>
	#include <stdio.h>
	#include <stdlib.h>
	//#include <sys/tree.h>
	#include <stdint.h>
	#if 0
	#include "freebsd/src/sys/sys/dm.tree.h"
	#else
	#include "freebsd/src/sys/sys/tree.h"
	#endif

	struct item {
	RB_ENTRY(item) it_entry;
	int val;
	};

	static int
	item_cmp(struct item a, struct item b)
	{
	return a->val < b->val ? -1 : a->val > b->val;
	}

	RB_HEAD(item_tree, item) tree = RB_INITIALIZER(&tree);
	RB_GENERATE_STATIC(item_tree, item, it_entry, item_cmp);

	int main()
	{
	int maxsize = 100000;
	int count;
	struct item ins = malloc(sizeof(ins));
	for (count = 0; count < 4000000; ++count) {
	ins->val = 2*count;
	if (RB_INSERT(item_tree, &tree, ins) == NULL)
	ins = malloc(sizeof(*ins));
	if (count >= maxsize) {
	struct item key;
	key.val = 2*(count - maxsize);
	struct item *found = RB_FIND(item_tree, &tree, &key);
	if (found != NULL) {
	RB_REMOVE(item_tree, &tree, found);
	free(found);
	}
	for (int i = 0; i < 100; ++i) {
	key.val = 2*(count - maxsize + 1 + i);
	found = RB_FIND(item_tree, &tree, &key);
	if (!found)
	printf("uh-oh\n");
	}
	}
	}
	return 0;
	}