test_heap.c File Reference

Heap data structure test module. More...

#include "asterisk.h"
#include "asterisk/module.h"
#include "asterisk/utils.h"
#include "asterisk/heap.h"
#include "asterisk/test.h"

Include dependency graph for test_heap.c:

Go to the source code of this file.

Data Structures
struct	node

Functions
static void	__reg_module (void)
static void	__unreg_module (void)
struct ast_module *	AST_MODULE_SELF_SYM (void)
	AST_TEST_DEFINE (heap_test_1)
	AST_TEST_DEFINE (heap_test_2)
	AST_TEST_DEFINE (heap_test_3)
static int	load_module (void)
static int	node_cmp (void *_n1, void *_n2)
static int	unload_module (void)

Variables
static struct ast_module_info	__mod_info = { .name = AST_MODULE, .flags = AST_MODFLAG_LOAD_ORDER , .description = "Heap test module" , .key = "This paragraph is copyright (c) 2006 by Digium, Inc. \In order for your module to load, it must return this \key via a function called \"key\". Any code which \includes this paragraph must be licensed under the GNU \General Public License version 2 or later (at your \option). In addition to Digium's general reservations \of rights, Digium expressly reserves the right to \allow other parties to license this paragraph under \different terms. Any use of Digium, Inc. trademarks or \logos (including \"Asterisk\" or \"Digium\") without \express written permission of Digium, Inc. is prohibited.\n" , .buildopt_sum = AST_BUILDOPT_SUM, .load = load_module, .unload = unload_module, .load_pri = AST_MODPRI_DEFAULT, .support_level = AST_MODULE_SUPPORT_CORE, }
static const struct ast_module_info *	ast_module_info = &__mod_info

Detailed Description

Heap data structure test module.

Author

Russell Bryant russe.nosp@m.ll@d.nosp@m.igium.nosp@m..com

Definition in file test_heap.c.

Function Documentation

__reg_module()

static void __reg_module ( void  )

static

Definition at line 306 of file test_heap.c.

__unreg_module()

static void __unreg_module ( void  )

static

Definition at line 306 of file test_heap.c.

AST_MODULE_SELF_SYM()

struct ast_module* AST_MODULE_SELF_SYM

(

void

)

Definition at line 306 of file test_heap.c.

AST_TEST_DEFINE() [1/3]

AST_TEST_DEFINE

(

heap_test_1

)

Definition at line 57 of file test_heap.c.

References ast_heap_create, ast_heap_destroy(), ast_heap_pop(), ast_heap_push, AST_TEST_FAIL, AST_TEST_NOT_RUN, AST_TEST_PASS, ast_test_status_update, node::index, sip_to_pjsip::info(), node_cmp(), TEST_EXECUTE, TEST_INIT, and node::val.

{
   struct ast_heap *h;
   struct node *obj;
   struct node nodes[3] = {
      { 1, } ,
      { 2, } ,
      { 3, } ,
   };

   switch (cmd) {
   case TEST_INIT:
      info->name = "heap_test_1";
      info->category = "/main/heap/";
      info->summary = "push and pop elements";
      info->description = "Push a few elements onto a heap and make sure that they come back off in the right order.";
      return AST_TEST_NOT_RUN;
   case TEST_EXECUTE:
      break;
   }

   if (!(h = ast_heap_create(8, node_cmp, offsetof(struct node, index)))) {
      return AST_TEST_FAIL;
   }

   ast_heap_push(h, &nodes[0]);

   ast_heap_push(h, &nodes[1]);

   ast_heap_push(h, &nodes[2]);

   obj = ast_heap_pop(h);
   if (obj->val != 3) {
      ast_test_status_update(test, "expected 3, got %ld\n", obj->val);
      return AST_TEST_FAIL;
   }

   obj = ast_heap_pop(h);
   if (obj->val != 2) {
      ast_test_status_update(test, "expected 2, got %ld\n", obj->val);
      return AST_TEST_FAIL;
   }

   obj = ast_heap_pop(h);
   if (obj->val != 1) {
      ast_test_status_update(test, "expected 1, got %ld\n", obj->val);
      return AST_TEST_FAIL;
   }

   obj = ast_heap_pop(h);
   if (obj) {
      ast_test_status_update(test, "got unexpected object\n");
      return AST_TEST_FAIL;
   }

   h = ast_heap_destroy(h);

   return AST_TEST_PASS;
}

AST_TEST_DEFINE() [2/3]

AST_TEST_DEFINE

(

heap_test_2

)

Definition at line 117 of file test_heap.c.

References ast_free, ast_heap_create, ast_heap_destroy(), ast_heap_pop(), ast_heap_push, ast_heap_verify(), ast_malloc, ast_random(), AST_TEST_FAIL, AST_TEST_NOT_RUN, AST_TEST_PASS, ast_test_status_update, node::index, sip_to_pjsip::info(), last, node_cmp(), nodes, NULL, TEST_EXECUTE, TEST_INIT, total, and node::val.

{
   struct ast_heap *h = NULL;
   static const unsigned int total = 100000;
   struct node *nodes = NULL;
   struct node *node;
   unsigned int i = total;
   long last = LONG_MAX;
   long cur;
   enum ast_test_result_state res = AST_TEST_PASS;

   switch (cmd) {
   case TEST_INIT:
      info->name = "heap_test_2";
      info->category = "/main/heap/";
      info->summary = "load test";
      info->description =
            "Push one hundred thousand random elements on to a heap, "
            "verify that the heap has been properly constructed, "
            "and then ensure that the elements are come back off "
            "in the proper order.";
      return AST_TEST_NOT_RUN;
   case TEST_EXECUTE:
      break;
   }

   if (!(nodes = ast_malloc(total * sizeof(*node)))) {
      res = AST_TEST_FAIL;
      goto return_cleanup;
   }

   if (!(h = ast_heap_create(20, node_cmp, offsetof(struct node, index)))) {
      res = AST_TEST_FAIL;
      goto return_cleanup;
   }

   while (i--) {
      nodes[i].val = ast_random();
      ast_heap_push(h, &nodes[i]);
   }

   if (ast_heap_verify(h)) {
      res = AST_TEST_FAIL;
      goto return_cleanup;
   }

   i = 0;
   while ((node = ast_heap_pop(h))) {
      cur = node->val;
      if (cur > last) {
         ast_test_status_update(test, "i: %u, cur: %ld, last: %ld\n", i, cur, last);
         res = AST_TEST_FAIL;
         goto return_cleanup;
      }
      last = cur;
      i++;
   }

   if (i != total) {
      ast_test_status_update(test, "Stopped popping off after only getting %u nodes\n", i);
      res = AST_TEST_FAIL;
      goto return_cleanup;
   }

return_cleanup:
   if (h) {
      h = ast_heap_destroy(h);
   }
   if (nodes) {
      ast_free(nodes);
   }

   return res;
}

AST_TEST_DEFINE() [3/3]

AST_TEST_DEFINE

(

heap_test_3

)

Definition at line 192 of file test_heap.c.

References ast_free, ast_heap_create, ast_heap_destroy(), ast_heap_pop(), ast_heap_push, ast_heap_remove(), ast_heap_verify(), ast_malloc, ast_random(), AST_TEST_FAIL, AST_TEST_NOT_RUN, AST_TEST_PASS, ast_test_status_update, node::index, sip_to_pjsip::info(), last, node_cmp(), nodes, NULL, TEST_EXECUTE, TEST_INIT, and node::val.

{
   struct ast_heap *h = NULL;
   struct node *nodes = NULL;
   struct node *node;
   static const unsigned int test_size = 100000;
   unsigned int i = test_size;
   long last = LONG_MAX, cur;
   int random_index;
   enum ast_test_result_state res = AST_TEST_PASS;

   switch (cmd) {
   case TEST_INIT:
      info->name = "heap_test_3";
      info->category = "/main/heap/";
      info->summary = "random element removal test";
      info->description =
         "Push a hundred thousand random elements on to a heap, "
         "verify that the heap has been properly constructed, "
         "randomly remove and re-add 10000 elements, and then "
         "ensure that the elements come back off in the proper order.";
      return AST_TEST_NOT_RUN;
   case TEST_EXECUTE:
      break;
   }

   if (!(nodes = ast_malloc(test_size * sizeof(*node)))) {
      ast_test_status_update(test, "memory allocation failure\n");
      res = AST_TEST_FAIL;
      goto return_cleanup;
   }

   if (!(h = ast_heap_create(20, node_cmp, offsetof(struct node, index)))) {
      ast_test_status_update(test, "Failed to allocate heap\n");
      res = AST_TEST_FAIL;
      goto return_cleanup;
   }

   while (i--) {
      nodes[i].val = ast_random();
      ast_heap_push(h, &nodes[i]);
   }

   if (ast_heap_verify(h)) {
      ast_test_status_update(test, "Failed to verify heap after populating it\n");
      res = AST_TEST_FAIL;
      goto return_cleanup;
   }

   i = test_size / 10;
   while (i--) {
      random_index = ast_random() % test_size;
      node = ast_heap_remove(h, &nodes[random_index]);
      if (nodes[random_index].val != node->val){
         ast_test_status_update(test, "Failed to remove what we expected to\n");
         res = AST_TEST_FAIL;
         goto return_cleanup;
      }
      ast_heap_push(h, &nodes[random_index]);
   }

   if (ast_heap_verify(h)) {
      ast_test_status_update(test, "Failed to verify after removals\n");
      res = AST_TEST_FAIL;
      goto return_cleanup;
   }

   i = 0;
   while ((node = ast_heap_pop(h))) {
      cur = node->val;
      if (cur > last) {
         ast_test_status_update(test, "i: %u, cur: %ld, last: %ld\n", i, cur, last);
         res = AST_TEST_FAIL;
         goto return_cleanup;
      }
      last = cur;
      i++;
   }

   if (i != test_size) {
      ast_test_status_update(test, "Stopped popping off after only getting %u nodes\n", i);
      res = AST_TEST_FAIL;
      goto return_cleanup;
   }

return_cleanup:
   if (h) {
      h = ast_heap_destroy(h);
   }
   if (nodes) {
      ast_free(nodes);
   }

   return res;
}

load_module()

static int load_module ( void  )

static

Definition at line 297 of file test_heap.c.

References AST_MODULE_LOAD_SUCCESS, and AST_TEST_REGISTER.

{
   AST_TEST_REGISTER(heap_test_1);
   AST_TEST_REGISTER(heap_test_2);
   AST_TEST_REGISTER(heap_test_3);

   return AST_MODULE_LOAD_SUCCESS;
}

node_cmp()

static int node_cmp ( void *  _n1, void *  _n2  )

static

Definition at line 43 of file test_heap.c.

References node::val.

Referenced by AST_TEST_DEFINE().

{
   struct node *n1 = _n1;
   struct node *n2 = _n2;

   if (n1->val < n2->val) {
      return -1;
   } else if (n1->val == n2->val) {
      return 0;
   } else {
      return 1;
   }
}

unload_module()

static int unload_module ( void  )

static

Definition at line 288 of file test_heap.c.

References AST_TEST_UNREGISTER.

{
   AST_TEST_UNREGISTER(heap_test_1);
   AST_TEST_UNREGISTER(heap_test_2);
   AST_TEST_UNREGISTER(heap_test_3);

   return 0;
}

Variable Documentation

__mod_info

struct ast_module_info __mod_info = { .name = AST_MODULE, .flags = AST_MODFLAG_LOAD_ORDER , .description = "Heap test module" , .key = "This paragraph is copyright (c) 2006 by Digium, Inc. \In order for your module to load, it must return this \key via a function called \"key\". Any code which \includes this paragraph must be licensed under the GNU \General Public License version 2 or later (at your \option). In addition to Digium's general reservations \of rights, Digium expressly reserves the right to \allow other parties to license this paragraph under \different terms. Any use of Digium, Inc. trademarks or \logos (including \"Asterisk\" or \"Digium\") without \express written permission of Digium, Inc. is prohibited.\n" , .buildopt_sum = AST_BUILDOPT_SUM, .load = load_module, .unload = unload_module, .load_pri = AST_MODPRI_DEFAULT, .support_level = AST_MODULE_SUPPORT_CORE, }

static

Definition at line 306 of file test_heap.c.

ast_module_info

const struct ast_module_info* ast_module_info = &__mod_info

static

Definition at line 306 of file test_heap.c.