blob: b6c6a3771a0d41ea090e289646405f0d4a55aeec [file] [log] [blame]
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
#include <assert.h>
#include "CUnit/Basic.h"
#include "avltree.h"
#include "murmur3.h"
#define DEBUG 1
/* STATICS we use across multiple tests */
struct avltree avl_tree_1;
/* dirent-like structure */
typedef struct avl_unit_val {
struct avltree_node node_n;
struct avltree_node node_hk;
struct {
uint64_t k;
uint32_t p; /* nprobes , eff. metric */
} hk;
char *name;
uint64_t fsal_cookie;
} avl_unit_val_t;
static inline int avl_unit_hk_cmpf(const struct avltree_node *lhs,
const struct avltree_node *rhs)
{
avl_unit_val_t *lk, *rk;
lk = avltree_container_of(lhs, avl_unit_val_t, node_hk);
rk = avltree_container_of(rhs, avl_unit_val_t, node_hk);
if (lk->hk.k < rk->hk.k)
return -1;
if (lk->hk.k == rk->hk.k)
return 0;
return 1;
}
avl_unit_val_t *avl_unit_new_val(const char *name)
{
avl_unit_val_t *v = gsh_malloc(sizeof(avl_unit_val_t));
memset(v, 0, sizeof(avl_unit_val_t));
v->name = (char *)name;
return v;
}
static int qp_avl_insert(struct avltree *t, avl_unit_val_t *v)
{
/*
* Insert with quadatic, linear probing. A unique k is assured for
* any k whenever size(t) < max(uint64_t).
*
* First try quadratic probing, with coeff. 2 (since m = 2^n.)
* A unique k is not assured, since the codomain is not prime.
* If this fails, fall back to linear probing from hk.k+1.
*
* On return, the stored key is in v->hk.k, the iteration
* count in v->hk.p.
**/
struct avltree_node *tmpnode;
uint32_t j, j2;
uint32_t hk[4];
assert(avltree_size(t) < UINT64_MAX);
MurmurHash3_x64_128(v->name, strlen(v->name), 67, hk);
memcpy(&v->hk.k, hk, 8);
for (j = 0; j < UINT64_MAX; j++) {
v->hk.k = (v->hk.k + (j * 2));
tmpnode = avltree_insert(&v->node_hk, t);
if (!tmpnode) {
/* success, note iterations and return */
v->hk.p = j;
return 0;
}
}
/* warn debug */
memcpy(&v->hk.k, hk, 8);
for (j2 = 1 /* tried j=0 */; j2 < UINT64_MAX; j2++) {
v->hk.k = v->hk.k + j2;
tmpnode = avltree_insert(&v->node_hk, t);
if (!tmpnode) {
/* success, note iterations and return */
v->hk.p = j + j2;
return 0;
}
j2++;
}
/* warn crit */
return -1;
}
/* This permits inlining, also elides some locally-scoped stores in
* do_lookup. */
static inline struct avltree_node *
avltree_inline_lookup(const struct avltree_node *key,
const struct avltree *tree)
{
struct avltree_node *node = tree->root;
int is_left = 0, res = 0;
while (node) {
res = avl_unit_hk_cmpf(node, key); /* may inline */
if (res == 0)
return node;
is_left = res;
if (is_left > 0)
node = node->left;
else
node = node->right;
}
return NULL;
}
static avl_unit_val_t *qp_avl_lookup_s(struct avltree *t, avl_unit_val_t *v,
int maxj)
{
struct avltree_node *node;
avl_unit_val_t *v2;
uint32_t j, j2;
uint32_t hk[4];
assert(avltree_size(t) < UINT64_MAX);
MurmurHash3_x64_128(v->name, strlen(v->name), 67, hk);
memcpy(&v->hk.k, hk, 8);
for (j = 0; j < maxj; j++) {
v->hk.k = (v->hk.k + (j * 2));
node = avltree_inline_lookup(&v->node_hk, t);
if (node) {
/* it's almost but not entirely certain that node is
* related to v. in the general case, j is also not
* constrained to be v->hk.p */
v2 = avltree_container_of(node, avl_unit_val_t,
node_hk);
if (!strcmp(v->name, v2->name))
return v2;
}
}
/* warn crit */
return NULL;
}
static struct dir_data {
char *name;
} dir_data[] = {
".gitignore", "Makefile", "Makefile.gate", "acpi-ext.c",
"acpi-processor.c", "acpi.c", "asm-offsets.c", "audit.c",
"brl_emu.c", "cpufreq", "crash.c", "crash_dump.c",
"cyclone.c", "dma-mapping.c", "efi.c", "efi_stub.S",
"entry.S", "entry.h", "err_inject.c", "esi.c", "esi_stub.S",
"fsys.S", "fsyscall_gtod_data.h", "ftrace.c", "gate-data.S",
"gate.S", "gate.lds.S", "head.S", "ia64_ksyms.c",
"init_task.c", "iosapic.c", "irq.c", "irq_ia64.c",
"irq_lsapic.c", "ivt.S", "jprobes.S", "kprobes.c",
"machine_kexec.c", "machvec.c", "mca.c", "mca_asm.S",
"mca_drv.c", "mca_drv.h", "mca_drv_asm.S", "minstate.h",
"module.c", "msi_ia64.c", "nr-irqs.c", "numa.c", "pal.S",
"palinfo.c", "paravirt.c", "paravirt_inst.h",
"paravirt_patch.c", "paravirt_patchlist.c",
"paravirt_patchlist.h", "paravirtentry.S", "patch.c",
"pci-dma.c", "pci-swiotlb.c", "perfmon.c",
"perfmon_default_smpl.c", "perfmon_generic.h",
"perfmon_itanium.h", "perfmon_mckinley.h",
"perfmon_montecito.h", "process.c", "ptrace.c",
"relocate_kernel.S", "sal.c", "salinfo.c", "setup.c",
"sigframe.h", "signal.c", "smp.c", "smpboot.c",
"sys_ia64.c", "time.c", "topology.c", "traps.c",
"unaligned.c", "uncached.c", "unwind.c", "unwind_decoder.c",
"unwind_i.h", "vmlinux.lds.S", 0};
void avl_unit_free_val(avl_unit_val_t *v)
{
gsh_free(v);
}
void avl_unit_clear_tree(struct avltree *t)
{
avl_unit_val_t *v;
struct avltree_node *node, *next_node;
if (avltree_size(t) < 1)
return;
node = avltree_first(t);
while (node) {
next_node = avltree_next(node);
v = avltree_container_of(node, avl_unit_val_t, node_hk);
avltree_remove(&v->node_hk, &avl_tree_1);
gsh_free(v->name);
avl_unit_free_val(v);
node = next_node;
}
}
/* dne */
void avltree_destroy(struct avltree *t)
{
/* return */
}
void avl_unit_clear_and_destroy_tree(struct avltree *t)
{
avl_unit_clear_tree(t);
avltree_destroy(t);
}
/*
* BEGIN SUITE INITIALIZATION and CLEANUP FUNCTIONS
*/
void avl_unit_PkgInit(void)
{
/* nothing */
}
/*
* The suite initialization function.
* Initializes resources to be shared across tests.
* Returns zero on success, non-zero otherwise.
*
*/
int init_suite1(void)
{
avltree_init(&avl_tree_1, avl_unit_hk_cmpf, 0 /* flags */);
return 0;
}
/* The suite cleanup function.
* Closes the temporary resources used by the tests.
* Returns zero on success, non-zero otherwise.
*/
int clean_suite1(void)
{
if (avltree_size(&avl_tree_1) > 0)
avl_unit_clear_tree(&avl_tree_1);
avltree_destroy(&avl_tree_1);
return 0;
}
/*
* END SUITE INITIALIZATION and CLEANUP FUNCTIONS
*/
/*
* BEGIN BASIC TESTS
*/
void inserts_tree_1(void)
{
avl_unit_val_t *v;
char *s;
int ix, code;
ix = 0;
while ((s = dir_data[ix].name) != NULL) {
v = avl_unit_new_val(gsh_strdup(s));
code = qp_avl_insert(&avl_tree_1, v);
if (code == -1)
abort();
if (v->hk.p > 0)
printf("%d positive p %d %s\n", ix, v->hk.p, s);
++ix;
}
}
void check_tree_1(void)
{
int code = 0;
CU_ASSERT_EQUAL(code, 0);
}
void lookups_tree_1(void)
{
struct avltree_node *node;
avl_unit_val_t *v2, *v;
char *s;
int ix;
ix = 0;
while ((s = dir_data[ix].name) != NULL) {
v = avl_unit_new_val(s);
/* lookup mapping */
v2 = qp_avl_lookup_s(&avl_tree_1, v, 1);
if (!v2)
abort();
else
/*
printf("%d %d %s\n", ix, v2->hk.p, v2->name);
*/
++ix;
}
/* free v */
avl_unit_free_val(v);
}
void deletes_tree_1(void)
{
avl_unit_clear_tree(&avl_tree_1);
avltree_init(&avl_tree_1, avl_unit_hk_cmpf, 0 /* flags */);
}
void inserts_tree_2(void)
{
avl_unit_val_t *v;
char s[256];
int ix, code;
for (ix = 0; ix < 100000; ++ix) {
sprintf(s, "file%d", ix);
v = avl_unit_new_val(gsh_strdup(s));
code = qp_avl_insert(&avl_tree_1, v);
if (code == -1)
abort();
if (v->hk.p > 0)
printf("%d positive p %d %s\n", ix, v->hk.p, s);
}
}
void check_tree_2(void)
{
int code = 0;
CU_ASSERT_EQUAL(code, 0);
}
void lookups_tree_2(void)
{
struct avltree_node *node = NULL;
avl_unit_val_t *v2, *v;
char s[256];
int ix;
/* attempts 100K mits, 100K misses */
for (ix = 0; ix < 200000; ++ix) {
sprintf(s, "file%d", ix);
v = avl_unit_new_val(s);
v2 = qp_avl_lookup_s(&avl_tree_1, v, 1);
if (!v2)
if (ix < 100000)
abort();
else
/*
printf("%d %d %s\n", ix, v2->hk.p, v2->name);
*/
}
/* free v */
avl_unit_free_val(v);
}
void deletes_tree_2(void)
{
avl_unit_clear_tree(&avl_tree_1);
}
/* The main() function for setting up and running the tests.
* Returns a CUE_SUCCESS on successful running, another
* CUnit error code on failure.
*/
int main(int argc, char *argv[])
{
/* initialize the CUnit test registry... get this party started */
if (CUE_SUCCESS != CU_initialize_registry())
return CU_get_error();
/* General avl_tree test. */
CU_TestInfo avl_tree_unit_1_arr[] = {
{"Tree insertions 1.", inserts_tree_1}
,
{"Tree check 1.", check_tree_1}
,
{"Tree lookups 1.", lookups_tree_1}
,
{"Tree deletes 1.", deletes_tree_1}
,
{"Tree insertions 2.", inserts_tree_2}
,
{"Tree check 2.", check_tree_2}
,
{"Tree lookups 2.", lookups_tree_2}
,
{"Tree deletes 2.", deletes_tree_2}
,
CU_TEST_INFO_NULL,
};
CU_SuiteInfo suites[] = {
{"Rb tree operations 1", init_suite1, clean_suite1,
avl_tree_unit_1_arr}
,
CU_SUITE_INFO_NULL,
};
CU_ErrorCode error = CU_register_suites(suites);
/* Initialize the avl_tree package */
avl_unit_PkgInit();
/* Run all tests using the CUnit Basic interface */
CU_basic_set_mode(CU_BRM_VERBOSE);
CU_basic_run_tests();
CU_cleanup_registry();
return CU_get_error();
}