testheap.c

   1 #include "dat.h"
   2 #include <stdint.h>
   3 #include <stdlib.h>
   4 #include <stdio.h>
   5 #include <string.h>
   6 #include <sys/time.h>
   7 #include "ct/ct.h"
   8
   9
  10 void
  11 cttest_heap_insert_one()
  12 {
  13     Heap h = {
  14         .less = job_pri_less,
  15         .setpos = job_setpos,
  16     };
  17
  18     Job *j = make_job(1, 0, 1, 0, 0);
  19     assertf(j, "allocate job");
  20
  21     heapinsert(&h, j);
  22     assertf(h.len == 1, "h should contain one item.");
  23     assertf(j->heap_index == 0, "should match");
  24
  25     assert(heapremove(&h, 0));
  26     job_free(j);
  27     free(h.data);
  28 }
  29
  30 void
  31 cttest_heap_insert_and_remove_one()
  32 {
  33     Heap h = {
  34         .less = job_pri_less,
  35         .setpos = job_setpos,
  36     };
  37
  38     Job *j1 = make_job(1, 0, 1, 0, 0);
  39     assertf(j1, "allocate job");
  40
  41     int r = heapinsert(&h, j1);
  42     assertf(r, "insert should succeed");
  43
  44     Job *got = heapremove(&h, 0);
  45     assertf(got == j1, "j1 should come back out");
  46     assertf(h.len == 0, "h should be empty.");
  47
  48     free(h.data);
  49     job_free(j1);
  50 }
  51
  52 void
  53 cttest_heap_priority()
  54 {
  55     Heap h = {
  56         .less = job_pri_less,
  57         .setpos = job_setpos,
  58     };
  59     Job *j, *j1, *j2, *j3;
  60
  61     j1 = make_job(1, 0, 1, 0, 0);
  62     j2 = make_job(2, 0, 1, 0, 0);
  63     j3 = make_job(3, 0, 1, 0, 0);
  64     assertf(j1, "allocate job");
  65     assertf(j2, "allocate job");
  66     assertf(j3, "allocate job");
  67
  68     int r = heapinsert(&h, j2);
  69     assertf(r, "insert should succeed");
  70     assertf(j2->heap_index == 0, "should match");
  71
  72     r = heapinsert(&h, j3);
  73     assertf(r, "insert should succeed");
  74     assertf(j2->heap_index == 0, "should match");
  75     assertf(j3->heap_index == 1, "should match");
  76
  77     r = heapinsert(&h, j1);
  78     assertf(r, "insert should succeed");
  79     assertf(j1->heap_index == 0, "should match");
  80     assertf(j2->heap_index == 2, "should match");
  81     assertf(j3->heap_index == 1, "should match");
  82
  83     j = heapremove(&h, 0);
  84     assertf(j == j1, "j1 should come out first.");
  85     assertf(j2->heap_index == 0, "should match");
  86     assertf(j3->heap_index == 1, "should match");
  87
  88     j = heapremove(&h, 0);
  89     assertf(j == j2, "j2 should come out second.");
  90     assertf(j3->heap_index == 0, "should match");
  91
  92     j = heapremove(&h, 0);
  93     assertf(j == j3, "j3 should come out third.");
  94
  95     free(h.data);
  96     job_free(j1);
  97     job_free(j2);
  98     job_free(j3);
  99 }
 100
 101 void
 102 cttest_heap_fifo_property()
 103 {
 104     Heap h = {
 105         .less = job_pri_less,
 106         .setpos = job_setpos,
 107     };
 108     Job *j, *j3a, *j3b, *j3c;
 109
 110     j3a = make_job(3, 0, 1, 0, 0);
 111     j3b = make_job(3, 0, 1, 0, 0);
 112     j3c = make_job(3, 0, 1, 0, 0);
 113     assertf(j3a, "allocate job");
 114     assertf(j3b, "allocate job");
 115     assertf(j3c, "allocate job");
 116
 117     int r = heapinsert(&h, j3a);
 118     assertf(r, "insert should succeed");
 119     assertf(h.data[0] == j3a, "j3a should be in pos 0");
 120     assertf(j3a->heap_index == 0, "should match");
 121
 122     r = heapinsert(&h, j3b);
 123     assertf(r, "insert should succeed");
 124     assertf(h.data[1] == j3b, "j3b should be in pos 1");
 125     assertf(j3a->heap_index == 0, "should match");
 126     assertf(j3b->heap_index == 1, "should match");
 127
 128     r = heapinsert(&h, j3c);
 129     assertf(r, "insert should succeed");
 130     assertf(h.data[2] == j3c, "j3c should be in pos 2");
 131     assertf(j3a->heap_index == 0, "should match");
 132     assertf(j3b->heap_index == 1, "should match");
 133     assertf(j3c->heap_index == 2, "should match");
 134
 135     j = heapremove(&h, 0);
 136     assertf(j == j3a, "j3a should come out first.");
 137     assertf(j3b->heap_index == 0, "should match");
 138     assertf(j3c->heap_index == 1, "should match");
 139
 140     j = heapremove(&h, 0);
 141     assertf(j == j3b, "j3b should come out second.");
 142     assertf(j3c->heap_index == 0, "should match");
 143
 144     j = heapremove(&h, 0);
 145     assertf(j == j3c, "j3c should come out third.");
 146
 147     free(h.data);
 148     job_free(j3a);
 149     job_free(j3b);
 150     job_free(j3c);
 151 }
 152
 153 void
 154 cttest_heap_many_jobs()
 155 {
 156     Heap h = {
 157         .less = job_pri_less,
 158         .setpos = job_setpos,
 159     };
 160     const int n = 20;
 161     Job *j;
 162
 163     int i;
 164     for (i = 0; i < n; i++) {
 165         j = make_job(1 + rand() % 8192, 0, 1, 0, 0);
 166         assertf(j, "allocation");
 167         int r = heapinsert(&h, j);
 168         assertf(r, "heapinsert");
 169     }
 170
 171     uint last_pri = 0;
 172     for (i = 0; i < n; i++) {
 173         j = heapremove(&h, 0);
 174         assertf(j->r.pri >= last_pri, "should come out in order");
 175         last_pri = j->r.pri;
 176         assert(j);
 177         job_free(j);
 178     }
 179     free(h.data);
 180 }
 181
 182 void
 183 cttest_heap_remove_k()
 184 {
 185     Heap h = {
 186         .less = job_pri_less,
 187         .setpos = job_setpos,
 188     };
 189     const int n = 50;
 190     const int mid = 25;
 191
 192     int c, i;
 193     for (c = 0; c < 50; c++) {
 194         for (i = 0; i < n; i++) {
 195             Job *j = make_job(1 + rand() % 8192, 0, 1, 0, 0);
 196             assertf(j, "allocation");
 197             int r = heapinsert(&h, j);
 198             assertf(r, "heapinsert");
 199         }
 200
 201         /* remove one from the middle */
 202         Job *j0 = heapremove(&h, mid);
 203         assertf(j0, "j0 should not be NULL");
 204         job_free(j0);
 205
 206         /* now make sure the rest are still a valid heap */
 207         uint last_pri = 0;
 208         for (i = 1; i < n; i++) {
 209             Job *j = heapremove(&h, 0);
 210             assertf(j->r.pri >= last_pri, "should come out in order");
 211             last_pri = j->r.pri;
 212             assertf(j, "j should not be NULL");
 213             job_free(j);
 214         }
 215     }
 216     free(h.data);
 217 }
 218
 219 void
 220 ctbench_heap_insert(int n)
 221 {
 222     Job **j = calloc(n, sizeof *j);
 223     int i;
 224     for (i = 0; i < n; i++) {
 225         j[i] = make_job(1, 0, 1, 0, 0);
 226         assert(j[i]);
 227         j[i]->r.pri = -j[i]->r.id;
 228     }
 229     Heap h = {
 230         .less = job_pri_less,
 231         .setpos = job_setpos,
 232     };
 233
 234     ctresettimer();
 235     for (i = 0; i < n; i++) {
 236         heapinsert(&h, j[i]);
 237     }
 238     ctstoptimer();
 239
 240     for (i = 0; i < n; i++)
 241         job_free(heapremove(&h, 0));
 242     free(h.data);
 243     free(j);
 244 }
 245
 246 void
 247 ctbench_heap_remove(int n)
 248 {
 249     Heap h = {
 250         .less = job_pri_less,
 251         .setpos = job_setpos,
 252     };
 253     int i;
 254     for (i = 0; i < n; i++) {
 255         Job *j = make_job(1, 0, 1, 0, 0);
 256         assertf(j, "allocate job");
 257         heapinsert(&h, j);
 258     }
 259     Job **jj = calloc(n, sizeof(Job *)); // temp storage to deallocate jobs later
 260
 261     ctresettimer();
 262     for (i = 0; i < n; i++) {
 263         jj[i] = (Job *)heapremove(&h, 0);
 264     }
 265     ctstoptimer();
 266
 267     free(h.data);
 268     for (i = 0; i < n; i++)
 269         job_free(jj[i]);
 270     free(jj);
 271 }