Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

202 lines (162 sloc) 4.943 kb
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include "ct/ct.h"
#include "dat.h"
void
cttestheap_insert_one()
{
Heap h = {0};
job j;
h.less = job_pri_less;
h.rec = job_setheappos;
j = make_job(1, 0, 1, 0, 0);
assertf(j, "allocate job");
heapinsert(&h, j);
assertf(h.len == 1, "h should contain one item.");
assertf(j->heap_index == 0, "should match");
}
void
cttestheap_insert_and_remove_one()
{
Heap h = {0};
int r;
job j, j1;
h.less = job_pri_less;
h.rec = job_setheappos;
j1 = make_job(1, 0, 1, 0, 0);
assertf(j1, "allocate job");
r = heapinsert(&h, j1);
assertf(r, "insert should succeed");
j = heapremove(&h, 0);
assertf(j == j1, "j1 should come back out");
assertf(h.len == 0, "h should be empty.");
printf("j->heap_index is %zu\n", j->heap_index);
assertf(j->heap_index == -1, "j's heap index should be invalid");
}
void
cttestheap_priority()
{
Heap h = {0};
int r;
job j, j1, j2, j3;
h.less = job_pri_less;
h.rec = job_setheappos;
j1 = make_job(1, 0, 1, 0, 0);
j2 = make_job(2, 0, 1, 0, 0);
j3 = make_job(3, 0, 1, 0, 0);
assertf(j1, "allocate job");
assertf(j2, "allocate job");
assertf(j3, "allocate job");
r = heapinsert(&h, j2);
assertf(r, "insert should succeed");
assertf(j2->heap_index == 0, "should match");
r = heapinsert(&h, j3);
assertf(r, "insert should succeed");
assertf(j2->heap_index == 0, "should match");
assertf(j3->heap_index == 1, "should match");
r = heapinsert(&h, j1);
assertf(r, "insert should succeed");
assertf(j1->heap_index == 0, "should match");
assertf(j2->heap_index == 2, "should match");
assertf(j3->heap_index == 1, "should match");
j = heapremove(&h, 0);
assertf(j == j1, "j1 should come out first.");
assertf(j2->heap_index == 0, "should match");
assertf(j3->heap_index == 1, "should match");
j = heapremove(&h, 0);
assertf(j == j2, "j2 should come out second.");
assertf(j3->heap_index == 0, "should match");
j = heapremove(&h, 0);
assertf(j == j3, "j3 should come out third.");
}
void
cttestheap_fifo_property()
{
Heap h = {0};
int r;
job j, j3a, j3b, j3c;
h.less = job_pri_less;
h.rec = job_setheappos;
j3a = make_job(3, 0, 1, 0, 0);
j3b = make_job(3, 0, 1, 0, 0);
j3c = make_job(3, 0, 1, 0, 0);
assertf(j3a, "allocate job");
assertf(j3b, "allocate job");
assertf(j3c, "allocate job");
r = heapinsert(&h, j3a);
assertf(r, "insert should succeed");
assertf(h.data[0] == j3a, "j3a should be in pos 0");
assertf(j3a->heap_index == 0, "should match");
r = heapinsert(&h, j3b);
assertf(r, "insert should succeed");
assertf(h.data[1] == j3b, "j3b should be in pos 1");
assertf(j3a->heap_index == 0, "should match");
assertf(j3b->heap_index == 1, "should match");
r = heapinsert(&h, j3c);
assertf(r, "insert should succeed");
assertf(h.data[2] == j3c, "j3c should be in pos 2");
assertf(j3a->heap_index == 0, "should match");
assertf(j3b->heap_index == 1, "should match");
assertf(j3c->heap_index == 2, "should match");
j = heapremove(&h, 0);
assertf(j == j3a, "j3a should come out first.");
assertf(j3b->heap_index == 0, "should match");
assertf(j3c->heap_index == 1, "should match");
j = heapremove(&h, 0);
assertf(j == j3b, "j3b should come out second.");
assertf(j3c->heap_index == 0, "should match");
j = heapremove(&h, 0);
assertf(j == j3c, "j3c should come out third.");
}
void
cttestheap_many_jobs()
{
Heap h = {0};
uint last_pri;
int r, i, n = 20;
job j;
h.less = job_pri_less;
h.rec = job_setheappos;
for (i = 0; i < n; i++) {
j = make_job(1 + rand() % 8192, 0, 1, 0, 0);
assertf(j, "allocation");
r = heapinsert(&h, j);
assertf(r, "heapinsert");
}
last_pri = 0;
for (i = 0; i < n; i++) {
j = heapremove(&h, 0);
assertf(j->r.pri >= last_pri, "should come out in order");
last_pri = j->r.pri;
}
}
void
cttestheap_remove_k()
{
Heap h = {0};
uint last_pri;
int r, i, c, n = 20;
job j;
h.less = job_pri_less;
h.rec = job_setheappos;
for (c = 0; c < 50; c++) {
for (i = 0; i < n; i++) {
j = make_job(1 + rand() % 8192, 0, 1, 0, 0);
assertf(j, "allocation");
r = heapinsert(&h, j);
assertf(r, "heapinsert");
}
/* remove one from the middle */
heapremove(&h, 25);
/* now make sure the rest are still a valid heap */
last_pri = 0;
for (i = 1; i < n; i++) {
j = heapremove(&h, 0);
assertf(j->r.pri >= last_pri, "should come out in order");
last_pri = j->r.pri;
}
}
}
Jump to Line
Something went wrong with that request. Please try again.