|
Packit Service |
724aca |
#include "test/jemalloc_test.h"
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
#include "jemalloc/internal/qr.h"
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
/* Number of ring entries, in [2..26]. */
|
|
Packit Service |
724aca |
#define NENTRIES 9
|
|
Packit Service |
724aca |
/* Split index, in [1..NENTRIES). */
|
|
Packit Service |
724aca |
#define SPLIT_INDEX 5
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
typedef struct ring_s ring_t;
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
struct ring_s {
|
|
Packit Service |
724aca |
qr(ring_t) link;
|
|
Packit Service |
724aca |
char id;
|
|
Packit Service |
724aca |
};
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
static void
|
|
Packit Service |
724aca |
init_entries(ring_t *entries) {
|
|
Packit Service |
724aca |
unsigned i;
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
qr_new(&entries[i], link);
|
|
Packit Service |
724aca |
entries[i].id = 'a' + i;
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
static void
|
|
Packit Service |
724aca |
test_independent_entries(ring_t *entries) {
|
|
Packit Service |
724aca |
ring_t *t;
|
|
Packit Service |
724aca |
unsigned i, j;
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
j = 0;
|
|
Packit Service |
724aca |
qr_foreach(t, &entries[i], link) {
|
|
Packit Service |
724aca |
j++;
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
assert_u_eq(j, 1,
|
|
Packit Service |
724aca |
"Iteration over single-element ring should visit precisely "
|
|
Packit Service |
724aca |
"one element");
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
j = 0;
|
|
Packit Service |
724aca |
qr_reverse_foreach(t, &entries[i], link) {
|
|
Packit Service |
724aca |
j++;
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
assert_u_eq(j, 1,
|
|
Packit Service |
724aca |
"Iteration over single-element ring should visit precisely "
|
|
Packit Service |
724aca |
"one element");
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
t = qr_next(&entries[i], link);
|
|
Packit Service |
724aca |
assert_ptr_eq(t, &entries[i],
|
|
Packit Service |
724aca |
"Next element in single-element ring should be same as "
|
|
Packit Service |
724aca |
"current element");
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
t = qr_prev(&entries[i], link);
|
|
Packit Service |
724aca |
assert_ptr_eq(t, &entries[i],
|
|
Packit Service |
724aca |
"Previous element in single-element ring should be same as "
|
|
Packit Service |
724aca |
"current element");
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
TEST_BEGIN(test_qr_one) {
|
|
Packit Service |
724aca |
ring_t entries[NENTRIES];
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
init_entries(entries);
|
|
Packit Service |
724aca |
test_independent_entries(entries);
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
TEST_END
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
static void
|
|
Packit Service |
724aca |
test_entries_ring(ring_t *entries) {
|
|
Packit Service |
724aca |
ring_t *t;
|
|
Packit Service |
724aca |
unsigned i, j;
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
j = 0;
|
|
Packit Service |
724aca |
qr_foreach(t, &entries[i], link) {
|
|
Packit Service |
724aca |
assert_c_eq(t->id, entries[(i+j) % NENTRIES].id,
|
|
Packit Service |
724aca |
"Element id mismatch");
|
|
Packit Service |
724aca |
j++;
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
j = 0;
|
|
Packit Service |
724aca |
qr_reverse_foreach(t, &entries[i], link) {
|
|
Packit Service |
724aca |
assert_c_eq(t->id, entries[(NENTRIES+i-j-1) %
|
|
Packit Service |
724aca |
NENTRIES].id, "Element id mismatch");
|
|
Packit Service |
724aca |
j++;
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
t = qr_next(&entries[i], link);
|
|
Packit Service |
724aca |
assert_c_eq(t->id, entries[(i+1) % NENTRIES].id,
|
|
Packit Service |
724aca |
"Element id mismatch");
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
t = qr_prev(&entries[i], link);
|
|
Packit Service |
724aca |
assert_c_eq(t->id, entries[(NENTRIES+i-1) % NENTRIES].id,
|
|
Packit Service |
724aca |
"Element id mismatch");
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
TEST_BEGIN(test_qr_after_insert) {
|
|
Packit Service |
724aca |
ring_t entries[NENTRIES];
|
|
Packit Service |
724aca |
unsigned i;
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
init_entries(entries);
|
|
Packit Service |
724aca |
for (i = 1; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
qr_after_insert(&entries[i - 1], &entries[i], link);
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
test_entries_ring(entries);
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
TEST_END
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
TEST_BEGIN(test_qr_remove) {
|
|
Packit Service |
724aca |
ring_t entries[NENTRIES];
|
|
Packit Service |
724aca |
ring_t *t;
|
|
Packit Service |
724aca |
unsigned i, j;
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
init_entries(entries);
|
|
Packit Service |
724aca |
for (i = 1; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
qr_after_insert(&entries[i - 1], &entries[i], link);
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
j = 0;
|
|
Packit Service |
724aca |
qr_foreach(t, &entries[i], link) {
|
|
Packit Service |
724aca |
assert_c_eq(t->id, entries[i+j].id,
|
|
Packit Service |
724aca |
"Element id mismatch");
|
|
Packit Service |
724aca |
j++;
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
j = 0;
|
|
Packit Service |
724aca |
qr_reverse_foreach(t, &entries[i], link) {
|
|
Packit Service |
724aca |
assert_c_eq(t->id, entries[NENTRIES - 1 - j].id,
|
|
Packit Service |
724aca |
"Element id mismatch");
|
|
Packit Service |
724aca |
j++;
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
qr_remove(&entries[i], link);
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
test_independent_entries(entries);
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
TEST_END
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
TEST_BEGIN(test_qr_before_insert) {
|
|
Packit Service |
724aca |
ring_t entries[NENTRIES];
|
|
Packit Service |
724aca |
ring_t *t;
|
|
Packit Service |
724aca |
unsigned i, j;
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
init_entries(entries);
|
|
Packit Service |
724aca |
for (i = 1; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
qr_before_insert(&entries[i - 1], &entries[i], link);
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
j = 0;
|
|
Packit Service |
724aca |
qr_foreach(t, &entries[i], link) {
|
|
Packit Service |
724aca |
assert_c_eq(t->id, entries[(NENTRIES+i-j) %
|
|
Packit Service |
724aca |
NENTRIES].id, "Element id mismatch");
|
|
Packit Service |
724aca |
j++;
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
j = 0;
|
|
Packit Service |
724aca |
qr_reverse_foreach(t, &entries[i], link) {
|
|
Packit Service |
724aca |
assert_c_eq(t->id, entries[(i+j+1) % NENTRIES].id,
|
|
Packit Service |
724aca |
"Element id mismatch");
|
|
Packit Service |
724aca |
j++;
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
t = qr_next(&entries[i], link);
|
|
Packit Service |
724aca |
assert_c_eq(t->id, entries[(NENTRIES+i-1) % NENTRIES].id,
|
|
Packit Service |
724aca |
"Element id mismatch");
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
t = qr_prev(&entries[i], link);
|
|
Packit Service |
724aca |
assert_c_eq(t->id, entries[(i+1) % NENTRIES].id,
|
|
Packit Service |
724aca |
"Element id mismatch");
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
TEST_END
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
static void
|
|
Packit Service |
724aca |
test_split_entries(ring_t *entries) {
|
|
Packit Service |
724aca |
ring_t *t;
|
|
Packit Service |
724aca |
unsigned i, j;
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
for (i = 0; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
j = 0;
|
|
Packit Service |
724aca |
qr_foreach(t, &entries[i], link) {
|
|
Packit Service |
724aca |
if (i < SPLIT_INDEX) {
|
|
Packit Service |
724aca |
assert_c_eq(t->id,
|
|
Packit Service |
724aca |
entries[(i+j) % SPLIT_INDEX].id,
|
|
Packit Service |
724aca |
"Element id mismatch");
|
|
Packit Service |
724aca |
} else {
|
|
Packit Service |
724aca |
assert_c_eq(t->id, entries[(i+j-SPLIT_INDEX) %
|
|
Packit Service |
724aca |
(NENTRIES-SPLIT_INDEX) + SPLIT_INDEX].id,
|
|
Packit Service |
724aca |
"Element id mismatch");
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
j++;
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
TEST_BEGIN(test_qr_meld_split) {
|
|
Packit Service |
724aca |
ring_t entries[NENTRIES];
|
|
Packit Service |
724aca |
unsigned i;
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
init_entries(entries);
|
|
Packit Service |
724aca |
for (i = 1; i < NENTRIES; i++) {
|
|
Packit Service |
724aca |
qr_after_insert(&entries[i - 1], &entries[i], link);
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
qr_split(&entries[0], &entries[SPLIT_INDEX], ring_t, link);
|
|
Packit Service |
724aca |
test_split_entries(entries);
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
qr_meld(&entries[0], &entries[SPLIT_INDEX], ring_t, link);
|
|
Packit Service |
724aca |
test_entries_ring(entries);
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
qr_meld(&entries[0], &entries[SPLIT_INDEX], ring_t, link);
|
|
Packit Service |
724aca |
test_split_entries(entries);
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
qr_split(&entries[0], &entries[SPLIT_INDEX], ring_t, link);
|
|
Packit Service |
724aca |
test_entries_ring(entries);
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
qr_split(&entries[0], &entries[0], ring_t, link);
|
|
Packit Service |
724aca |
test_entries_ring(entries);
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
qr_meld(&entries[0], &entries[0], ring_t, link);
|
|
Packit Service |
724aca |
test_entries_ring(entries);
|
|
Packit Service |
724aca |
}
|
|
Packit Service |
724aca |
TEST_END
|
|
Packit Service |
724aca |
|
|
Packit Service |
724aca |
int
|
|
Packit Service |
724aca |
main(void) {
|
|
Packit Service |
724aca |
return test(
|
|
Packit Service |
724aca |
test_qr_one,
|
|
Packit Service |
724aca |
test_qr_after_insert,
|
|
Packit Service |
724aca |
test_qr_remove,
|
|
Packit Service |
724aca |
test_qr_before_insert,
|
|
Packit Service |
724aca |
test_qr_meld_split);
|
|
Packit Service |
724aca |
}
|