root/test/class/opal_tree.c

DEFINITIONS

1. main
2. check_descendants
3. test_comp
4. test_serialize
5. test_deserialize
6. test_get_key

   1 /*
   2  * Copyright (c) 2011      Oracle and/or its affiliates.  All rights reserved.
   3  * Copyright (c) 2014 Cisco Systems, Inc.  All rights reserved.
   4  * $COPYRIGHT$
   5  *
   6  * Additional copyrights may follow
   7  *
   8  * $HEADER$
   9  */
  10 
  11 #include "opal_config.h"
  12 #include <assert.h>
  13 
  14 #include "support.h"
  15 #include "opal/class/opal_tree.h"
  16 #include "opal/runtime/opal.h"
  17 #include "opal/constants.h"
  18 
  19 #include <math.h>
  20 #include <string.h>
  21 
  22 /*
  23  * Data type used for testing
  24  */
  25 typedef struct test_data {
  26     /* tree data structure */
  27     opal_tree_item_t tree_element;
  28     /* test data */
  29     size_t data;
  30 } test_data_t;
  31 
  32 OBJ_CLASS_INSTANCE(test_data_t,
  33                    opal_tree_item_t,
  34                    NULL, NULL);
  35 
  36 static void check_descendants(opal_tree_item_t* item, unsigned *data,
  37                               unsigned level, int *err_order,
  38                               int *err_ancestor);
  39 static int test_comp(opal_tree_item_t *item, void *key);
  40 static int test_serialize(opal_tree_item_t *item, opal_buffer_t *buffer);
  41 static int test_deserialize(opal_buffer_t *serial_data,
  42                             opal_tree_item_t **item);
  43 static void *test_get_key(opal_tree_item_t *item);
  44 
  45 int main(int argc, char **argv)
  46 {
  47     /* local variables */
  48     opal_tree_t tree, x;
  49     opal_buffer_t *serial_tree;
  50     size_t i, j, tree_size, size_levels, size_elements, total_elements;
  51     int err_order, err_ancestor, rc;
  52     unsigned key;
  53     test_data_t *elements;
  54     opal_tree_item_t *item, *rm_item;
  55 
  56     rc = opal_init_util(&argc, &argv);
  57     test_verify_int(OPAL_SUCCESS, rc);
  58     if (OPAL_SUCCESS != rc) {
  59         test_finalize();
  60         exit(1);
  61     }
  62 
  63     test_init("opal_tree_t");
  64 
  65     /* initialize tree */
  66 
  67     OBJ_CONSTRUCT(&tree, opal_tree_t);
  68     opal_tree_init(&tree, test_comp, test_serialize, test_deserialize, test_get_key);
  69     OBJ_CONSTRUCT(&x, opal_tree_t);
  70     opal_tree_init(&x, test_comp, test_serialize, test_deserialize, test_get_key);
  71 
  72     /* check length of tree */
  73     tree_size=opal_tree_get_size(&tree);
  74     if( 0 == tree_size ) {
  75         test_success();
  76     } else {
  77         test_failure(" opal_tree_get_size");
  78     }
  79 
  80     /* check for empty */
  81     if (opal_tree_is_empty(&tree)) {
  82         test_success();
  83     } else {
  84         test_failure(" opal_tree_is_empty(empty tree)");
  85     }
  86 
  87     /* create test elements */
  88     size_levels = 4;
  89     size_elements=4;
  90     total_elements = size_elements * size_levels;
  91     elements=(test_data_t *)malloc(sizeof(test_data_t)*total_elements);
  92     assert(elements);
  93     for(i=0 ; i < total_elements; i++) {
  94         OBJ_CONSTRUCT(elements + i, test_data_t);
  95         (elements+i)->data=i;
  96     }
  97 
  98     /* check get_root */
  99     item = opal_tree_get_root(&tree);
 100 
 101 
 102     /* populate a 4 level tree (this is weighted to the left side) */
 103     for (i = 0; i < size_levels; i++) {
 104         for(j=0 ; j < size_elements ; j++) {
 105             opal_tree_add_child(item,(opal_tree_item_t *)(elements+
 106                                                           (i*size_elements)+
 107                                                           j));
 108         }
 109         item = opal_tree_get_first_child(item);
 110     }
 111 
 112     /* checking for tree size */
 113     tree_size=opal_tree_get_size(&tree);
 114     if( tree_size == total_elements ) {
 115         test_success();
 116     } else {
 117         test_failure(" count off for populating 4 level tree");
 118     }
 119 
 120     /* checking for empty on non-empty tree */
 121     if (!opal_tree_is_empty(&tree)) {
 122         test_success();
 123     } else {
 124         test_failure(" opal_tree_is_empty(non-empty tree)");
 125     }
 126 
 127     /* check that we have correct tree ordering */
 128     err_order = 0;
 129     err_ancestor = 0;
 130     if (!opal_tree_is_empty(&tree)) {
 131         item = opal_tree_get_root(&tree);
 132         i = 0;
 133         check_descendants(item, (unsigned *)&i, 0, &err_order, &err_ancestor);
 134     }
 135 
 136     if (!err_order) {
 137         test_success();
 138     } else {
 139         test_failure(" order values incorrect");
 140     }
 141     if (!err_ancestor) {
 142         test_success();
 143     } else {
 144         test_failure(" invalid ancestor count");
 145     }
 146 
 147     /* test matching code */
 148     /* check for invalid matching */
 149     key = 444;
 150     item = opal_tree_find_with(opal_tree_get_root(&tree), (void*)&key);
 151     if (NULL == item) {
 152         test_success();
 153     } else {
 154         test_failure(" failed invalid matching item test");
 155     }
 156 
 157     /* check matching, note nest tests because they rely on previous tests */
 158     /* check for valid matching descendants */
 159     key = 4;
 160     item = opal_tree_find_with(opal_tree_get_root(&tree), (void*)&key);
 161     if (NULL != item && ((test_data_t*)item)->data == key) {
 162         test_success();
 163         /* check for valid matching siblings */
 164         key = 7;
 165         item = opal_tree_find_with(item, (void*)&key);
 166         if (NULL != item && ((test_data_t*)item)->data == key) {
 167             test_success();
 168             /* check for valid matching ancestors */
 169             key = 2;
 170             item = opal_tree_find_with(item, (void*)&key);
 171             if (NULL != item && ((test_data_t*)item)->data == key) {
 172                 test_success();
 173             } else {
 174                 test_failure(" failed valid matching ancestors test");
 175             }
 176         } else {
 177             test_failure(" failed valid matching siblings test");
 178         }
 179     } else {
 180         test_failure(" failed valid matching descendants test");
 181     }
 182 
 183     /* check subtree removal */
 184     /* find the first key = 3 item and remove it */
 185     key = 8;
 186     tree_size=opal_tree_get_size(&tree);
 187     item = opal_tree_find_with(opal_tree_get_root(&tree), (void*)&key);
 188     rm_item = opal_tree_remove_subtree(item);
 189     if (NULL == rm_item) {
 190         test_failure(" rm_item should not be NULL");
 191     }
 192     /* validate the tree count adjusted */
 193     if (5 != (tree_size - opal_tree_get_size(&tree))) {
 194         test_failure(" failed subtree removal tree size test");
 195     } else {
 196         /* validate cannot find children in tree */
 197         key = 13;
 198         if (NULL !=
 199             opal_tree_find_with(opal_tree_get_root(&tree), (void*)&key)) {
 200             test_failure(" failed subtree removal item children removed test");
 201         } else {
 202             /* validate cannot find the item */
 203             key = 8;
 204             if (NULL !=
 205                 opal_tree_find_with(opal_tree_get_root(&tree), (void*)&key)) {
 206                 test_failure(" failed subtree removal item removed test");
 207             } else {
 208                 test_success();
 209             }
 210         }
 211     }
 212 
 213     /* check serialization-deserialization */
 214     /* serialize tree */
 215     serial_tree = OBJ_NEW(opal_buffer_t);
 216 
 217     if (OPAL_SUCCESS == opal_tree_serialize(opal_tree_get_root(&tree),
 218                                             serial_tree)) {
 219         opal_tree_t tmp_tree;
 220         opal_buffer_t *serial2_tree;
 221 
 222         /* create new tree */
 223         OBJ_CONSTRUCT(&tmp_tree, opal_tree_t);
 224         opal_tree_init(&tmp_tree, test_comp, test_serialize,
 225                        test_deserialize, test_get_key);
 226 
 227         /* deserialize tree */
 228         opal_tree_deserialize(serial_tree, &(tmp_tree.opal_tree_sentinel));
 229         /* serialize tmp tree */
 230         serial2_tree = OBJ_NEW(opal_buffer_t);
 231         if (OPAL_SUCCESS == opal_tree_serialize(opal_tree_get_root(&tmp_tree),
 232                                                 serial2_tree)) {
 233             void *payload1, *payload2;
 234             int32_t size1, size2;
 235 
 236             /* compare new with original serialization */
 237         serial_tree->unpack_ptr = serial_tree->base_ptr;
 238         serial2_tree->unpack_ptr = serial2_tree->unpack_ptr;
 239             opal_dss.unload(serial_tree, &payload1, &size1);
 240             opal_dss.unload(serial2_tree, &payload2, &size2);
 241             if (size1 == size2) {
 242                 if (0 == memcmp(payload1, payload2, size1)) {
 243                     test_success();
 244                 } else {
 245                     test_failure(" failed tree deserialization data compare");
 246                 }
 247             } else {
 248                 test_failure(" failed tree deserialization size compare");
 249             }
 250         } else {
 251             test_failure(" failed tree second pass serialization");
 252         }
 253     } else {
 254         test_failure(" failed tree serialization");
 255     }
 256 
 257     if (NULL != elements) free(elements);
 258 
 259     opal_finalize_util ();
 260 
 261     return test_finalize();
 262 }
 263 
 264 /*
 265  * check all the descendants from our level and below for correct data and
 266  * level.  Note this will traverse the tree in a weird fashion where you
 267  * go across all siblings and then start searching down the last siblings
 268  * children.  As the current tests are set up if one populated more than just
 269  * the left sided children things will probably fail.
 270  */
 271 static void check_descendants(opal_tree_item_t* item,
 272                               unsigned *data,
 273                               unsigned level,
 274                               int *err_order, int *err_ancestor)
 275 {
 276     test_data_t *ele;
 277 
 278     /* loop over all siblings and then down first child  */
 279     while (item) {
 280         /* check item for correctness */
 281         ele = (test_data_t *)item;
 282         if (ele->data != *data) {
 283             (*err_order)++;
 284         }
 285         if (item->opal_tree_num_ancestors != level) {
 286             (*err_ancestor)++;
 287         }
 288         (*data)++;
 289         check_descendants(opal_tree_get_next_sibling(item), data, level,
 290                           err_order, err_ancestor);
 291         item = opal_tree_get_first_child(item);
 292         level++;
 293     }
 294     return;
 295 }
 296 
 297 static int test_comp(opal_tree_item_t *item, void *key)
 298 {
 299     if (((test_data_t *)item)->data > *((unsigned *) key)) {
 300         return(1);
 301     }
 302     if (((test_data_t *)item)->data < *((unsigned *) key)) {
 303         return(-1);
 304     }
 305     return(0);
 306 }
 307 
 308 static int test_serialize(opal_tree_item_t *item, opal_buffer_t *buffer)
 309 {
 310     test_data_t *ele = (test_data_t *)item;
 311 
 312     return(opal_dss.pack(buffer, &ele->data, 1, OPAL_INT32));
 313 }
 314 
 315 static int test_deserialize(opal_buffer_t *serial_data, opal_tree_item_t **item)
 316 {
 317     int rc = OPAL_SUCCESS, idx = 1;
 318     test_data_t *ele;
 319 
 320     ele = (test_data_t *)malloc(sizeof(test_data_t));
 321     OBJ_CONSTRUCT(ele, test_data_t);
 322     if (OPAL_SUCCESS == (rc = opal_dss.unpack(serial_data, &ele->data, &idx,
 323                                               OPAL_INT32))) {
 324         *item = (opal_tree_item_t*)ele;
 325     } else {
 326         *item = NULL;
 327     }
 328     return(rc);
 329 }
 330 
 331 static void *test_get_key(opal_tree_item_t *item)
 332 {
 333     return (void*) (((test_data_t *)item)->data);
 334 }