src/lib/test-priorityq.c

/* Copyright (c) 2007-2018 Dovecot authors, see the included COPYING file */

#include "test-lib.h"
#include "priorityq.h"


struct pq_test_item {
    struct priorityq_item item;
    int num;
};

static int cmp_int(const void *p1, const void *p2)
{
    const struct pq_test_item *i1 = p1, *i2 = p2;

    return i1->num - i2->num;
}

void test_priorityq(void)
{
#define PQ_MAX_ITEMS 100
    static const int input[] = {
        1, 2, 3, 4, 5, 6, 7, 8, -1,
        8, 7, 6, 5, 4, 3, 2, 1, -1,
        8, 7, 5, 6, 1, 3, 4, 2, -1,
        -1
    };
    static const int output[] = {
        1, 2, 3, 4, 5, 6, 7, 8
    };
    struct pq_test_item *item, items[PQ_MAX_ITEMS];
    struct priorityq_item *const *all_items;
    unsigned int i, j;
    struct priorityq *pq;
    pool_t pool;
    int prev;

    pool = pool_alloconly_create("priorityq items", 1024);

    /* simple tests with popping only */
    test_begin("priorityq");
    for (i = 0; input[i] != -1; i++) {
        p_clear(pool);
        pq = priorityq_init(cmp_int, 1);
        for (j = 0; input[i] != -1; i++, j++) {
            test_assert(priorityq_count(pq) == j);
            item = p_new(pool, struct pq_test_item, 1);
            item->num = input[i];
            priorityq_add(pq, &item->item);
        }
        all_items = priorityq_items(pq);
        test_assert(priorityq_count(pq) == N_ELEMENTS(output));
        item = (struct pq_test_item *)all_items[0];
        test_assert(item->num == output[0]);
        for (j = 1; j < N_ELEMENTS(output); j++) {
            item = (struct pq_test_item *)all_items[j];
            test_assert(item->num > output[0]);
            test_assert(item->num <= output[N_ELEMENTS(output)-1]);
        }
        for (j = 0; j < N_ELEMENTS(output); j++) {
            test_assert(priorityq_count(pq) == N_ELEMENTS(output) - j);

            item = (struct pq_test_item *)priorityq_peek(pq);
            i_assert(item != NULL);
            test_assert(output[j] == item->num);
            item = (struct pq_test_item *)priorityq_pop(pq);
            i_assert(item != NULL);
            test_assert(output[j] == item->num);
        }
        test_assert(priorityq_count(pq) == 0);
        test_assert(priorityq_peek(pq) == NULL);
        test_assert(priorityq_pop(pq) == NULL);
        priorityq_deinit(&pq);
    }
    test_end();

    /* randomized tests, remove elements */
    test_begin("priorityq randomized");
    for (i = 0; i < 100; i++) {
        pq = priorityq_init(cmp_int, 1);
        for (j = 0; j < PQ_MAX_ITEMS; j++) {
            items[j].num = i_rand_limit(INT_MAX);
            priorityq_add(pq, &items[j].item);
        }
        for (j = 0; j < PQ_MAX_ITEMS; j++) {
            if (i_rand_limit(3) == 0) {
                priorityq_remove(pq, &items[j].item);
                items[j].num = -1;
            }
        }
        prev = 0;
        while (priorityq_count(pq) > 0) {
            item = (struct pq_test_item *)priorityq_pop(pq);
            i_assert(item != NULL);
            test_assert(item->num >= 0 && prev <= item->num);
            prev = item->num;
            item->num = -1;
        }
        for (j = 0; j < PQ_MAX_ITEMS; j++) {
            test_assert(items[j].num == -1);
        }
        priorityq_deinit(&pq);
    }
    test_end();
    pool_unref(&pool);
}