00001 #include "kal_eheap.h"
00002
00003 #include <stdio.h>
00004 #include <stdlib.h>
00005 #include <assert.h>
00006
00007 kal_define_eheap(int, int);
00008
00009 kal_eheap_t(int, int) h;
00010
00011 kal_eheap_t(int, int) *a;
00012 kal_eheap_t(int, int) *b;
00013
00014 #define HEAP_BITS 3
00015 #define HEAP_SIZE (1 << HEAP_BITS)
00016
00017 int main(int argc, char **argv) {
00018 qos_rv rv = kal_eheap_init(&h, HEAP_BITS);
00019 int k, v;
00020
00021 a = b;
00022
00023 if (rv != QOS_OK)
00024 return -1;
00025
00026 qos_log_debug("Size of heap: %d\n", kal_eheap_size(&h));
00027 assert(kal_eheap_size(&h) == 0);
00028 rv = kal_eheap_add(&h, 4, 20, NULL);
00029 if (rv != QOS_OK)
00030 return -1;
00031 qos_log_debug("Size of heap: %d\n", kal_eheap_size(&h));
00032 assert(kal_eheap_size(&h) == 1);
00033
00034 rv = kal_eheap_add(&h, 7, 35, NULL);
00035 rv = kal_eheap_add(&h, 1, 5, NULL);
00036 rv = kal_eheap_add(&h, 12, 60, NULL);
00037 rv = kal_eheap_add(&h, 3, 12, NULL);
00038 qos_log_debug("Size of heap: %d\n", kal_eheap_size(&h));
00039 assert(kal_eheap_size(&h) == 5);
00040
00041 assert((kal_eheap_get_min(&h, &k, &v) == QOS_OK) && (k == 1) && (v == 5));
00042 kal_eheap_del_min(&h);
00043 assert((kal_eheap_get_min(&h, &k, &v) == QOS_OK) && (k == 3) && (v == 12));
00044 kal_eheap_del_min(&h);
00045 assert((kal_eheap_get_min(&h, &k, &v) == QOS_OK) && (k == 4) && (v == 20));
00046 kal_eheap_del_min(&h);
00047 assert((kal_eheap_get_min(&h, &k, &v) == QOS_OK) && (k == 7) && (v == 35));
00048 kal_eheap_del_min(&h);
00049 assert((kal_eheap_get_min(&h, &k, &v) == QOS_OK) && (k == 12) && (v == 60));
00050 kal_eheap_del_min(&h);
00051
00052 kal_eheap_add(&h, 7, 35, NULL);
00053 kal_eheap_add(&h, 1, 5, NULL);
00054 kal_eheap_add(&h, 12, 60, NULL);
00055 kal_eheap_add(&h, 3, 12, NULL);
00056 kal_eheap_add(&h, 4, 20, NULL);
00057
00058 qos_log_debug("Heap dump:\n");
00059 while (kal_eheap_size(&h) > 0) {
00060 rv = kal_eheap_get_min(&h, &k, &v);
00061 if (rv != QOS_OK)
00062 return -1;
00063 qos_log_debug("Min heap elem: %d, %d\n", k, v);
00064 rv = kal_eheap_del_min(&h);
00065 if (rv != QOS_OK)
00066 return -1;
00067 }
00068
00069 qos_chk_do(kal_eheap_get_min(&h, &k, &v) == QOS_E_EMPTY, exit(-1));
00070
00071 kal_eheap_iterator_t(int, int) it1, it2, it3;
00072
00073 qos_log_debug("Rebuilding heap...\n");
00074
00075 rv = kal_eheap_add(&h, 7, 35, &it1);
00076 rv = kal_eheap_add(&h, 1, 5, &it2);
00077 rv = kal_eheap_add(&h, 5, 25, &it3);
00078
00079 qos_log_debug("Deleting random elem...\n");
00080
00081 kal_eheap_del(&h, &it3);
00082 qos_log_debug("ptr=%p, ptr->pos=%d\n", &it3, it3.pos);
00083 assert(! kal_eheap_iterator_valid(&it3));
00084
00085 qos_log_debug("Heap dump:\n");
00086 while (kal_eheap_size(&h) > 0) {
00087 rv = kal_eheap_get_min(&h, &k, &v);
00088 if (rv != QOS_OK)
00089 return -1;
00090 qos_log_debug("Min heap elem: %d, %d\n", k, v);
00091 rv = kal_eheap_del_min(&h);
00092 if (rv != QOS_OK)
00093 return -1;
00094 }
00095
00096 int i;
00097 for (i = 0; i < HEAP_SIZE; i++) {
00098 int rnd = 1 + (int) (100.0 * (rand() / (RAND_MAX + 1.0)));
00099 rv = kal_eheap_add(&h, rnd, rnd, NULL);
00100 if (rv != QOS_OK) {
00101 qos_log_debug("Error while inserting\n");
00102 return -1;
00103 }
00104 }
00105 rv = kal_eheap_add(&h, 5, 25, NULL);
00106 if (rv != QOS_E_FULL) {
00107 qos_log_debug("Should have experienced an error on full heap\n");
00108 return -1;
00109 }
00110
00111 for (i = 0; i < HEAP_SIZE; i++) {
00112 rv = kal_eheap_del_min(&h);
00113 if (rv != QOS_OK) {
00114 qos_log_debug("Error while extracting min\n");
00115 return -1;
00116 }
00117 }
00118 rv = kal_eheap_del_min(&h);
00119 if (rv != QOS_E_EMPTY) {
00120 qos_log_debug("Should have experienced an error on empty heap\n");
00121 return -1;
00122 }
00123
00124 kal_eheap_cleanup(&h);
00125
00126 qos_log_debug("Test successful\n");
00127 return 0;
00128 }
