Return to heap_test.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib

bird2 ver 2.0.7

    1: /*
    2:  *	BIRD Library -- Universal Heap Macros Tests
    3:  *
    4:  *	(c) 2015 CZ.NIC z.s.p.o.
    5:  *
    6:  *	Can be freely distributed and used under the terms of the GNU GPL.
    7:  */
    8: 
    9: #include "test/birdtest.h"
   10: #include "sysdep/config.h"
   11: #include "lib/heap.h"
   12: 
   13: #define MAX_NUM 1000
   14: #define SPECIAL_KEY -3213
   15: 
   16: #define MY_CMP(x, y) ((x) < (y))
   17: 
   18: #define MY_HEAP_SWAP(heap,a,b,t)		\
   19:     do {					\
   20:       bt_debug("swap(%u %u) ", a, b);		\
   21:       HEAP_SWAP(heap,a,b,t);			\
   22:     } while(0)
   23: 
   24: static int heap[MAX_NUM+1];
   25: static uint num;
   26: 
   27: /*
   28:  * A valid heap must follow these rules:
   29:  *   - `num >= 0`
   30:  *   - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
   31:  */
   32: static int
   33: is_heap_valid(int heap[], uint num)
   34: {
   35:   uint i;
   36: 
   37:   if (num > MAX_NUM)
   38:     return 0;
   39: 
   40:   for (i = 2; i <= num; i++)
   41:     if (heap[i] < heap[i / 2])
   42:       return 0;
   43: 
   44:   return 1;
   45: }
   46: 
   47: static void
   48: show_heap(void)
   49: {
   50:   uint i;
   51:   bt_debug("\n");
   52:   bt_debug("numbers %u; ", num);
   53:   for (i = 0; i <= num; i++)
   54:     bt_debug("%d ", heap[i]);
   55:   bt_debug(is_heap_valid(heap, num) ? "OK" : "NON-VALID HEAP!");
   56:   bt_debug("\n");
   57: }
   58: 
   59: static void
   60: init_heap(void)
   61: {
   62:   uint i;
   63:   num = 0;
   64:   heap[0] = SPECIAL_KEY;		/* heap[0] should be unused */
   65:   for (i = 1; i <= MAX_NUM; i++)
   66:     heap[i] = 0;
   67: }
   68: 
   69: static int
   70: t_heap_insert(void)
   71: {
   72:   uint i;
   73: 
   74:   init_heap();
   75: 
   76:   for (i = MAX_NUM; i >= 1; i--)
   77:   {
   78:     bt_debug("ins %u at pos %u ", i, MAX_NUM - i);
   79:     heap[MAX_NUM - i + 1] = i;
   80:     HEAP_INSERT(heap, ++num, int, MY_CMP, MY_HEAP_SWAP);
   81:     show_heap();
   82:     bt_assert(is_heap_valid(heap, num));
   83:   }
   84: 
   85:   return 1;
   86: }
   87: 
   88: static int
   89: t_heap_increase_decrease(void)
   90: {
   91:   uint i;
   92: 
   93:   t_heap_insert();
   94: 
   95:   for (i = 1; i <= MAX_NUM; i++)
   96:   {
   97:     if ((int)i > heap[i])
   98:     {
   99:       bt_debug("inc %u ", i);
  100:       heap[i] = i;
  101:       HEAP_INCREASE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
  102:     }
  103:     else if ((int)i < heap[i])
  104:     {
  105:       bt_debug("dec %u ", i);
  106:       heap[i] = i;
  107:       HEAP_INCREASE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
  108:     }
  109:     show_heap();
  110:     bt_assert(is_heap_valid(heap, num));
  111:   }
  112: 
  113:   return 1;
  114: }
  115: 
  116: static int
  117: t_heap_delete(void)
  118: {
  119:   uint i;
  120: 
  121:   t_heap_insert();
  122: 
  123:   for (i = 1; i <= num; i++)
  124:   {
  125:     bt_debug("del at pos %u ", i);
  126:     HEAP_DELETE(heap, num, int, MY_CMP, MY_HEAP_SWAP, i);
  127:     show_heap();
  128:     bt_assert(is_heap_valid(heap, num));
  129:   }
  130: 
  131:   return 1;
  132: }
  133: 
  134: static int
  135: t_heap_0(void)
  136: {
  137:   init_heap();
  138:   t_heap_insert();
  139:   t_heap_increase_decrease();
  140:   t_heap_delete();
  141: 
  142:   return heap[0] == SPECIAL_KEY;
  143: }
  144: 
  145: static int
  146: t_heap_insert_random(void)
  147: {
  148:   int i, j;
  149:   int expected[MAX_NUM+1];
  150: 
  151:   init_heap();
  152: 
  153:   for (i = 1; i <= MAX_NUM; i++)
  154:   {
  155:     heap[i] = expected[i] = bt_random();
  156:     HEAP_INSERT(heap, ++num, int, MY_CMP, MY_HEAP_SWAP);
  157:     show_heap();
  158:     bt_assert(is_heap_valid(heap, num));
  159:   }
  160: 
  161:   for (i = 1; i <= MAX_NUM; i++)
  162:     for (j = 1; j <= MAX_NUM; j++)
  163:       if(expected[i] == heap[j])
  164: 	break;
  165:       else if (j == MAX_NUM)
  166:       {
  167: 	show_heap();
  168: 	bt_abort_msg("Did not find a number %d in heap.", expected[i]);
  169:       }
  170: 
  171:   return 1;
  172: }
  173: 
  174: int
  175: main(int argc, char *argv[])
  176: {
  177:   bt_init(argc, argv);
  178: 
  179:   bt_test_suite(t_heap_insert, "Inserting a descending sequence of numbers (the worst case)");
  180:   bt_test_suite(t_heap_insert_random, "Inserting pseudo-random numbers");
  181:   bt_test_suite(t_heap_increase_decrease, "Increasing/Decreasing");
  182:   bt_test_suite(t_heap_delete, "Deleting");
  183:   bt_test_suite(t_heap_0, "Is a heap[0] really unused?");
  184: 
  185:   return bt_exit_value();
  186: }