#include #include #include #include "pqueue.h" typedef struct { prio_t pri; int n; } test_node; pqueue test_q; int test_eq (void *node1, void *node2) { return node1 == node2; } void putchars (int c, int n) { int mid = c=='-'?n/2:n; while (n-- > 0) putchar (n==mid?'*':c); } void print_heap () { int node = 1; int nodes = 1; char *envcols = getenv("COLUMNS"); int columns = envcols?atoi(envcols):80; while (1) { int n = nodes; int sep = columns / (nodes + 1) - 3; while (n--) { putchars ((node-1)&&(node%2)?'-':' ', sep); if (node > test_q.csize) { putchar ('\n'); return; } printf ("%3d", test_q.heap[node++]->pri); } nodes *= 2; putchar ('\n'); } } void add (prio_t pri) { static int cnt = 0; test_node *node = (test_node *)malloc (sizeof(test_node)); node->pri = pri; node->n = cnt++; pq_add (node, &test_q); } void test_free (void *ptr) { if (ptr) free (ptr); } void add_array (prio_t prios[], int n) { int i; for (i = 0; i < n; i++) add (prios[i]); } void check_array (prio_t prios[], int n) { int i; for (i = 0; i < n; i++) { test_node *node = (test_node *)pq_del_min (&test_q); if (!node) { printf ("\nMissing nodes!!!\n"); break; } /*printf ("%d ", node->pri);*/ if (node->pri != prios[i]) { printf ("\nExpected %d!!!\n", prios[i]); } free (node); } /*printf ("\n");*/ if (pq_min (&test_q)) printf ("There are more nodes!!!\n"); } #define SIZ(a) (sizeof(a)/sizeof(*a)) #define CHECK(a) add_array(a,SIZ(a)); print_heap(); check_array(a##s,SIZ(a##s)) int main () { static prio_t arr1[] = {1,10,20,12,14,30,32,16}; static prio_t arr1s[] = {1,10,12,14,16,20,32}; static prio_t arr2[] = {1000, 900, 800, 700, 600, 500, 400, 300, 200, 100, 5, 4, 3, 2, 1}; static prio_t arr2s[] = {1, 2, 3, 4, 5, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000}; # define SZ_ARR3 10240 static prio_t arr3[SZ_ARR3]; static prio_t arr3s[SZ_ARR3]; int sz_arr3, i, j, removes; pq_new (&test_q, 0, test_eq); add_array (arr1, SIZ(arr1)); test_free (pq_del (30, &test_q)); print_heap(); check_array (arr1s, SIZ(arr1s)); CHECK(arr2); srand(time(NULL)); sz_arr3 = rand()%(SZ_ARR3/2)+(SZ_ARR3/2); for (i = 0; i < sz_arr3; i++) arr3[i] = (prio_t)rand(); add_array(arr3,sz_arr3); /*print_heap();*/ removes = rand()%sz_arr3; /*printf ("removing:");*/ for (i = 0; i < removes; i++) { j = rand()%sz_arr3; /*printf (" %d", arr3[j]);*/ test_free(pq_del_func(pq_get(arr3[j],&test_q),&test_q)); sz_arr3--; memmove (&arr3[j], &arr3[j+1], sizeof(*arr3)*(sz_arr3-j)); } /* putchar('\n'); for (i = 0; i < sz_arr3; i++) printf ("%d ", arr3[i]); putchar('\n'); */ for (i = 0; i < sz_arr3; i++) { for (j = 0; j < i && arr3[i] > arr3s[j]; j++) ; memmove (&arr3s[j+1], &arr3s[j], sizeof(*arr3)*(i-j)); arr3s[j] = arr3[i]; } /*print_heap();*/ check_array(arr3s,sz_arr3); pq_delete (&test_q); return 0; }