testheap.c

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