test/class/ompi_rb

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
comp_fn
comp_key
test_keys
test1
mem_node_compare
test2
main
   1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil -*- */
   2 /*
   3  * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
   4  *                         University Research and Technology
   5  *                         Corporation.  All rights reserved.
   6  * Copyright (c) 2004-2013 The University of Tennessee and The University
   7  *                         of Tennessee Research Foundation.  All rights
   8  *                         reserved.
   9  * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
  10  *                         University of Stuttgart.  All rights reserved.
  11  * Copyright (c) 2004-2005 The Regents of the University of California.
  12  *                         All rights reserved.
  13  * Copyright (c) 2006-2010 Cisco Systems, Inc.  All rights reserved.
  14  * Copyright (c) 2015      Los Alamos National Security, LLC. All rights
  15  *                         reserved.
  16  * $COPYRIGHT$
  17  *
  18  * Additional copyrights may follow
  19  *
  20  * $HEADER$
  21  */
  22 
  23 #include "opal_config.h"
  24 #include <stdint.h>
  25 #ifdef HAVE_SYS_TIME_H
  26 #include <sys/time.h>
  27 #else
  28 #include <sys/_time.h>
  29 #endif
  30 #include <string.h>
  31 #include "support.h"
  32 #include "opal/class/opal_rb_tree.h"
  33 #include "opal/mca/mpool/base/base.h"
  34 
  35 #define NUM_KEYS 10000
  36 #define SEED  1
  37 int keys[] = {
  38     0, 1, 2, 3, 4, 5, 6, 7
  39 };
  40 
  41 int values[] = {
  42     10, 11, 12, 13, 14, 15, 16, 17
  43 };
  44 
  45 int comp_fn(void * ele1, void * ele2);
  46 void test1(void);
  47 int comp_key(void* key1, void* key2);
  48 void test_keys(void);
  49 
  50 int comp_fn(void * ele1, void * ele2)
  51 {
  52     if(*((int *) ele1) > *((int *) ele2)) {
  53         return(1);
  54     }
  55     if(*((int *) ele1) < *((int *) ele2)) {
  56         return(-1);
  57     }
  58     return(0);
  59 }
  60 
  61 struct my_key_t{
  62     void *base;
  63     void *bound;
  64 }; typedef struct my_key_t my_key_t;
  65 
  66 struct my_val_t{
  67     my_key_t* key;
  68     int val;
  69 }; typedef struct my_val_t my_val_t;
  70 
  71 
  72 int comp_key(void* key1, void* key2) {
  73     if( ((my_key_t*) key1)->base <
  74         ((my_key_t*) key2)->base) {
  75         return -1;
  76     }
  77     else if ( ((my_key_t*) key1)->base >
  78               ((my_key_t*) key2)->bound) {
  79         return 1;
  80     }
  81     else {
  82         return 0;
  83     }
  84 }
  85 
  86 
  87 void test_keys(void)
  88 {
  89     opal_rb_tree_t tree;
  90     int rc, i;
  91     my_key_t keys[NUM_KEYS];
  92     my_val_t vals[NUM_KEYS];
  93     char buf[200];
  94     my_key_t *cur_key;
  95     my_val_t *cur_val;
  96     long tmp;
  97 
  98     OBJ_CONSTRUCT(&tree, opal_rb_tree_t);
  99     rc = opal_rb_tree_init(&tree, comp_key);
 100     srand(SEED);
 101     for(i = 0; i < NUM_KEYS; i++) {
 102         cur_key = &(keys[i]);
 103         cur_val = &(vals[i]);
 104         cur_val->key = cur_key;
 105         cur_val->val = i;
 106         tmp = (long) rand();
 107         cur_key->base = (void*) tmp;
 108         tmp += (long) rand();
 109         cur_key->bound = (void*) tmp;
 110         rc = opal_rb_tree_insert(&tree, cur_key, cur_val);
 111         if(OPAL_SUCCESS != rc) {
 112             test_failure("error inserting element in the tree");
 113         }
 114     }
 115     for(i = 0; i < NUM_KEYS; i+=2) {
 116         cur_key = &(keys[i]);
 117         rc = opal_rb_tree_delete(&tree, cur_key);
 118         if(OPAL_SUCCESS != rc) {
 119             test_failure("error deleting element in the tree");
 120         }
 121     }
 122     for(i = 1; i < NUM_KEYS; i+=2) {
 123         cur_key = &(keys[i]);
 124         cur_val = (my_val_t*) opal_rb_tree_find(&tree, cur_key);
 125         if(cur_val == NULL) {
 126             test_failure("lookup returned NULL item");
 127         }
 128         else if(cur_val->val != i && (cur_val->key->base > cur_key->base ||
 129                                       cur_val->key->bound < cur_key->base)) {
 130             sprintf(buf, "lookup returned invalid item, returned %d, extected %d",
 131                     cur_val->val, i);
 132             test_failure(buf);
 133         }
 134 
 135     }
 136 }
 137 
 138 void test1(void)
 139 {
 140     opal_rb_tree_t tree;
 141     int rc;
 142     void * result;
 143 
 144     OBJ_CONSTRUCT(&tree, opal_rb_tree_t);
 145     rc = opal_rb_tree_init(&tree, comp_fn);
 146     if(!test_verify_int(OPAL_SUCCESS, rc)) {
 147         test_failure("failed to properly initialize the tree");
 148     }
 149 
 150     rc = opal_rb_tree_insert(&tree, &keys[0], &values[0]);
 151     if(!test_verify_int(OPAL_SUCCESS, rc)) {
 152         test_failure("failed to properly insert a new node");
 153     }
 154     result = opal_rb_tree_find(&tree, &keys[0]);
 155     if(NULL == result) {
 156         test_failure("lookup returned null!");
 157     }
 158     if(!test_verify_int(values[0], *((int *) result))) {
 159         test_failure("failed to properly insert a new node");
 160     }
 161 
 162     rc = opal_rb_tree_insert(&tree, &keys[1], &values[1]);
 163     if(!test_verify_int(OPAL_SUCCESS, rc)) {
 164         test_failure("failed to properly insert a new node");
 165     }
 166     result = opal_rb_tree_find(&tree, &keys[1]);
 167     if(NULL == result) {
 168         test_failure("lookup returned null!");
 169     }
 170     if(!test_verify_int(values[1], *((int *) result))) {
 171         test_failure("failed to properly insert a new node");
 172     }
 173 
 174     rc = opal_rb_tree_insert(&tree, &keys[2], &values[2]);
 175     if(!test_verify_int(OPAL_SUCCESS, rc)) {
 176         test_failure("failed to properly insert a new node");
 177     }
 178     result = opal_rb_tree_find(&tree, &keys[2]);
 179     if(NULL == result) {
 180         test_failure("lookup returned null!");
 181     }
 182     if(!test_verify_int(values[2], *((int *) result))) {
 183         test_failure("failed to properly insert a new node");
 184     }
 185 
 186     rc = opal_rb_tree_insert(&tree, &keys[3], &values[3]);
 187     if(!test_verify_int(OPAL_SUCCESS, rc)) {
 188         test_failure("failed to properly insert a new node");
 189     }
 190     result = opal_rb_tree_find(&tree, &keys[3]);
 191     if(NULL == result) {
 192         test_failure("lookup returned null!");
 193     }
 194     if(!test_verify_int(values[3], *((int *) result))) {
 195         test_failure("failed to properly insert a new node");
 196     }
 197 
 198     rc = opal_rb_tree_insert(&tree, &keys[4], &values[4]);
 199     if(!test_verify_int(OPAL_SUCCESS, rc)) {
 200         test_failure("failed to properly insert a new node");
 201     }
 202     result = opal_rb_tree_find(&tree, &keys[4]);
 203     if(NULL == result) {
 204         test_failure("lookup returned null!");
 205     }
 206     if(!test_verify_int(values[4], *((int *) result))) {
 207         test_failure("failed to properly insert a new node");
 208     }
 209 
 210     rc = opal_rb_tree_insert(&tree, &keys[5], &values[5]);
 211     if(!test_verify_int(OPAL_SUCCESS, rc)) {
 212         test_failure("failed to properly insert a new node");
 213     }
 214     result = opal_rb_tree_find(&tree, &keys[5]);
 215     if(NULL == result) {
 216         test_failure("lookup returned null!");
 217     }
 218     if(!test_verify_int(values[5], *((int *) result))) {
 219         test_failure("failed to properly insert a new node");
 220     }
 221 
 222     rc = opal_rb_tree_insert(&tree, &keys[6], &values[6]);
 223     if(!test_verify_int(OPAL_SUCCESS, rc)) {
 224         test_failure("failed to properly insert a new node");
 225     }
 226     result = opal_rb_tree_find(&tree, &keys[6]);
 227     if(NULL == result) {
 228         test_failure("lookup returned null!");
 229     }
 230     if(!test_verify_int(values[6], *((int *) result))) {
 231         test_failure("failed to properly insert a new node");
 232     }
 233 
 234     rc = opal_rb_tree_insert(&tree, &keys[7], &values[7]);
 235     if(!test_verify_int(OPAL_SUCCESS, rc)) {
 236         test_failure("failed to properly insert a new node");
 237     }
 238     result = opal_rb_tree_find(&tree, &keys[7]);
 239     if(NULL == result) {
 240         test_failure("lookup returned null!");
 241     }
 242     if(!test_verify_int(values[7], *((int *) result))) {
 243         test_failure("failed to properly insert a new node");
 244     }
 245 
 246     rc = opal_rb_tree_size(&tree);
 247     if(!test_verify_int(8, rc)) {
 248         test_failure("failed to properly insert a new node");
 249     }
 250 
 251     rc = opal_rb_tree_delete(&tree, &keys[0]);
 252     if(!test_verify_int(OPAL_SUCCESS, rc)) {
 253         test_failure("failed to properly delete a node");
 254     }
 255     result = opal_rb_tree_find(&tree, &keys[0]);
 256     if(NULL != result) {
 257         test_failure("lookup returned a value instead of null!");
 258     } else {
 259         test_success();
 260     }
 261 
 262     OBJ_DESTRUCT(&tree);
 263 }
 264 
 265 /* the following test is based on memory lookups in the mpool */
 266 int mem_node_compare(void * key1, void * key2);
 267 void test2(void);
 268 
 269 /* the maximum number of memory pools a piece of memory can be registered with */
 270 #define MAX_REGISTRATIONS 10
 271 
 272 /* the number of memory segments to allocate */
 273 #define NUM_ALLOCATIONS 500
 274 
 275 struct opal_test_rb_key_t
 276 {
 277     void * bottom;          /* the bottom of the memory range */
 278     void * top;             /* the top of the memory range */
 279 };
 280 typedef struct opal_test_rb_key_t opal_test_rb_key_t;
 281 
 282 struct opal_test_rb_value_t
 283 {
 284     opal_free_list_item_t super; /* the parent class */
 285     opal_test_rb_key_t key; /* the key which holds the memory pointers */
 286     mca_mpool_base_module_t* registered_mpools[MAX_REGISTRATIONS];
 287                             /* the mpools the memory is registered with */
 288 };
 289 typedef struct opal_test_rb_value_t opal_test_rb_value_t;
 290 
 291 OBJ_CLASS_INSTANCE(opal_test_rb_value_t, opal_free_list_item_t, NULL, NULL);
 292 
 293 int mem_node_compare(void * key1, void * key2)
 294 {
 295     if(((opal_test_rb_key_t *) key1)->bottom <
 296        ((opal_test_rb_key_t *) key2)->bottom)
 297     {
 298         return -1;
 299     }
 300     else if(((opal_test_rb_key_t *) key1)->bottom >
 301             ((opal_test_rb_key_t *) key2)->top)
 302     {
 303         return 1;
 304     }
 305     return 0;
 306 }
 307 
 308 void test2(void)
 309 {
 310     opal_free_list_t key_list;
 311     opal_free_list_item_t * new_value;
 312     opal_rb_tree_t tree;
 313     int rc, i, size;
 314     void * result, * lookup;
 315     void * mem[NUM_ALLOCATIONS];
 316     opal_free_list_item_t * key_array[NUM_ALLOCATIONS];
 317     struct timeval start, end;
 318 
 319     OBJ_CONSTRUCT(&key_list, opal_free_list_t);
 320     opal_free_list_init (&key_list, sizeof(opal_test_rb_value_t),
 321             opal_cache_line_size,
 322             OBJ_CLASS(opal_test_rb_value_t),
 323             0,opal_cache_line_size,
 324             0, -1 , 128, NULL, 0, NULL, NULL, NULL);
 325 
 326     OBJ_CONSTRUCT(&tree, opal_rb_tree_t);
 327     rc = opal_rb_tree_init(&tree, mem_node_compare);
 328     if(!test_verify_int(OPAL_SUCCESS, rc)) {
 329         test_failure("failed to properly initialize the tree");
 330     }
 331 
 332     size = 1;
 333     for(i = 0; i < NUM_ALLOCATIONS; i++)
 334     {
 335         mem[i] = malloc(size);
 336         if(NULL == mem[i])
 337         {
 338             test_failure("system out of memory");
 339             return;
 340         }
 341         new_value = opal_free_list_get (&key_list);
 342         if(NULL == new_value)
 343         {
 344             test_failure("failed to get memory from free list");
 345         }
 346         key_array[i] = new_value;
 347         ((opal_test_rb_value_t *) new_value)->key.bottom = mem[i];
 348         ((opal_test_rb_value_t *) new_value)->key.top =
 349                                             (void *) ((size_t) mem[i] + size - 1);
 350         ((opal_test_rb_value_t *) new_value)->registered_mpools[0] = (void *)(intptr_t) i;
 351         rc = opal_rb_tree_insert(&tree, &((opal_test_rb_value_t *)new_value)->key,
 352                         new_value);
 353         if(OPAL_SUCCESS != rc)
 354         {
 355             test_failure("failed to properly insert a new node");
 356         }
 357         size += 1;
 358     }
 359 
 360     gettimeofday(&start, NULL);
 361     for(i = 0; i < NUM_ALLOCATIONS; i++)
 362     {
 363         lookup = (void *) ((size_t) mem[i] + i);
 364         result = opal_rb_tree_find(&tree, &lookup);
 365         if(NULL == result)
 366         {
 367             test_failure("lookup returned null!");
 368         } else if(i != ((int)(intptr_t) ((opal_test_rb_value_t *) result)->registered_mpools[0]))
 369         {
 370             test_failure("lookup returned wrong node!");
 371         }
 372         result = opal_rb_tree_find(&tree, &lookup);
 373         if(NULL == result)
 374         {
 375             test_failure("lookup returned null!");
 376         } else if(i != ((int)(intptr_t) ((opal_test_rb_value_t *) result)->registered_mpools[0]))
 377         {
 378             test_failure("lookup returned wrong node!");
 379         }
 380     }
 381 
 382     gettimeofday(&end, NULL);
 383 
 384 #if 0
 385     i = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
 386     printf("In a %d node tree, %d lookups took %f microseonds each\n",
 387             NUM_ALLOCATIONS, NUM_ALLOCATIONS * 2,
 388             (float) i / (float) (NUM_ALLOCATIONS * 2));
 389 #endif
 390 
 391     for(i = 0; i < NUM_ALLOCATIONS; i++)
 392     {
 393         if(NULL != mem[i])
 394         {
 395             free(mem[i]);
 396         }
 397         opal_free_list_return (&(key_list), key_array[i]);
 398     }
 399 
 400     OBJ_DESTRUCT(&tree);
 401     OBJ_DESTRUCT(&key_list);
 402 }
 403 
 404 int main(int argc, char **argv)
 405 {
 406     test_init("opal_rb_tree_t");
 407 
 408     test1();
 409     test2();
 410     /* test_keys(); */
 411     return test_finalize();
 412 }
/* [<][>][^][v][top][bottom][index][help] */
root/test/class/ompi_rb_tree.c

DEFINITIONS
