Return to heap_test.c CVS log

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

Annotation of embedaddon/bird2/lib/heap_test.c, revision 1.1

1.1     ! misho       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: }