www.delorie.com/gnu/docs/avl/libavl_82.html   search  
 
Buy GNU books!


GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

5.14.3 Testing Overflow

Testing for overflow requires an entirely different set of test functions. The idea is to create a too-tall tree using one of the pathological insertion orders (ascending, descending, zig-zag, shifted ascending), then try out each of the functions that can overflow on it and make sure that they behave as they should.

There is a separate test function for each function that can overflow a stack but which is not tested by test(). These functions are called by driver function test_overflow(), which also takes care of creating, populating, and destroying the tree.

 
&#60;@xref{\NODE\, , Overflow testers.&#62;,124}
/* Tests the tree routines for proper handling of overflows.
   Inserting the n elements of order[] should produce a tree
   with height greater than BST_MAX_HEIGHT.
   Uses allocator as the allocator for tree and node data.
   Use verbosity to set the level of chatter on stdout. */
int 
test_overflow (struct libavl_allocator *allocator,
int order[], int n, int verbosity)
{ /* An overflow tester function. */ typedef int test_func (struct bst_table *, int n); /* An overflow tester. */ struct test
{ test_func *func; /* Tester function. */ const char *name; /* Test name. */ }; /* All the overflow testers. */ static const struct test test[] =
{ {test_bst_t_first, "firstitem"}, {test_bst_t_last, "lastitem"}, {test_bst_t_find, "finditem"}, {test_bst_t_insert, "insertitem"}, {test_bst_t_next, "nextitem"}, {test_bst_t_prev, "previousitem"}, {test_bst_copy, "copytree"}, }; const struct test *i; /* Iterator. */ /* Run all the overflow testers. */ for (i = test; i < test + sizeof test / sizeof *test; i++)
{ struct bst_table *tree; int j; if (verbosity >= 2)
printf ("Running%stest...\n", i-&#62;name); tree = bst_create (compare_ints, NULL, allocator); if (tree == NULL)
{ printf ("Outofmemorycreatingtree.\n"); return 1; } for (j = 0; j < n; j++)
{ void **p = bst_probe (tree, &order[j]); if (p == NULL || *p != &order[j])
{ if (p == NULL && verbosity >= 0) printf ("Outofmemoryininsertion.\n"); else if (p != NULL)
printf ("Duplicateitemintree!\n"); bst_destroy (tree, NULL); return p == NULL; } } if (i-&#62;func (tree, n) == 0) return 0; if (verify_tree (tree, order, n) == 0) return 0; bst_destroy (tree, NULL); } return 1; }
This code is included in @refalso{98

 
int test_overflow (struct libavl_allocator *, int order[], int n, 
int verbosity);

There is an overflow tester for almost every function that can overflow. Here is one example:

 
static int 
test_bst_t_first (struct bst_table *tree, int n)
{ struct bst_traverser trav; int *first; first = bst_t_first (&trav, tree); if (first == NULL || *first != 0)
{ printf ("Firstitemtestfailed:expected0,got%d\n", first != NULL ? *first : -1); return 0; } return 1; }
See also @refalso{644 This code is included in @refalso{122

Exercises:

1. Write the rest of the overflow tester functions. (The test_overflow() function lists all of them.) [answer]


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003