src/test/test-prioq.c

30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering/***
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  This file is part of systemd.
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  Copyright 2013 Lennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  systemd is free software; you can redistribute it and/or modify it
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  under the terms of the GNU Lesser General Public License as published by
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  the Free Software Foundation; either version 2.1 of the License, or
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  (at your option) any later version.
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  systemd is distributed in the hope that it will be useful, but
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  WITHOUT ANY WARRANTY; without even the implied warranty of
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  Lesser General Public License for more details.
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  You should have received a copy of the GNU Lesser General Public License
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering  along with systemd; If not, see <http://www.gnu.org/licenses/>.
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering***/
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering#include <stdlib.h>
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
b5efdb8af40ea759a1ea584c1bc44ecc81dd00ceLennart Poettering#include "alloc-util.h"
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering#include "prioq.h"
b5efdb8af40ea759a1ea584c1bc44ecc81dd00ceLennart Poettering#include "set.h"
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering#include "siphash24.h"
b5efdb8af40ea759a1ea584c1bc44ecc81dd00ceLennart Poettering#include "util.h"
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering#define SET_SIZE 1024*4
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poetteringstatic int unsigned_compare(const void *a, const void *b) {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        const unsigned *x = a, *y = b;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        if (*x < *y)
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                return -1;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        if (*x > *y)
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                return 1;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        return 0;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering}
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poetteringstatic void test_unsigned(void) {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        unsigned buffer[SET_SIZE], i;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        Prioq *q;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        srand(0);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        q = prioq_new(trivial_compare_func);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        assert_se(q);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        for (i = 0; i < ELEMENTSOF(buffer); i++) {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                unsigned u;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                u = (unsigned) rand();
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                buffer[i] = u;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                assert_se(prioq_put(q, UINT_TO_PTR(u), NULL) >= 0);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        }
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        qsort(buffer, ELEMENTSOF(buffer), sizeof(buffer[0]), unsigned_compare);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        for (i = 0; i < ELEMENTSOF(buffer); i++) {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                unsigned u;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                assert_se(prioq_size(q) == ELEMENTSOF(buffer) - i);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                u = PTR_TO_UINT(prioq_pop(q));
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                assert_se(buffer[i] == u);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        }
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        assert_se(prioq_isempty(q));
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        prioq_free(q);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering}
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poetteringstruct test {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        unsigned value;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        unsigned idx;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering};
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poetteringstatic int test_compare(const void *a, const void *b) {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        const struct test *x = a, *y = b;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        if (x->value < y->value)
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                return -1;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        if (x->value > y->value)
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                return 1;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        return 0;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering}
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
b826ab586c9e0a9c0d438a75c28cf3a8ab485929Tom Gundersenstatic void test_hash(const void *a, struct siphash *state) {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        const struct test *x = a;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
b826ab586c9e0a9c0d438a75c28cf3a8ab485929Tom Gundersen        siphash24_compress(&x->value, sizeof(x->value), state);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering}
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
d5099efc47d4e6ac60816b5381a5f607ab03f06eMichal Schmidtstatic const struct hash_ops test_hash_ops = {
d5099efc47d4e6ac60816b5381a5f607ab03f06eMichal Schmidt        .hash = test_hash,
d5099efc47d4e6ac60816b5381a5f607ab03f06eMichal Schmidt        .compare = test_compare
d5099efc47d4e6ac60816b5381a5f607ab03f06eMichal Schmidt};
d5099efc47d4e6ac60816b5381a5f607ab03f06eMichal Schmidt
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poetteringstatic void test_struct(void) {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        Prioq *q;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        Set *s;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        unsigned previous = 0, i;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        int r;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        srand(0);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        q = prioq_new(test_compare);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        assert_se(q);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
d5099efc47d4e6ac60816b5381a5f607ab03f06eMichal Schmidt        s = set_new(&test_hash_ops);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        assert_se(s);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        for (i = 0; i < SET_SIZE; i++) {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                struct test *t;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                t = new0(struct test, 1);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                assert_se(t);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                t->value = (unsigned) rand();
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                r = prioq_put(q, t, &t->idx);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                assert_se(r >= 0);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                if (i % 4 == 0) {
ef42202ac8ed27e7ff1fc90ef8bc2590046dff25Zbigniew Jędrzejewski-Szmek                        r = set_consume(s, t);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                        assert_se(r >= 0);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                }
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        }
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        for (;;) {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                struct test *t;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                t = set_steal_first(s);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                if (!t)
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                        break;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                r = prioq_remove(q, t, &t->idx);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                assert_se(r > 0);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                free(t);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        }
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        for (i = 0; i < SET_SIZE * 3 / 4; i++) {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                struct test *t;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                assert_se(prioq_size(q) == (SET_SIZE * 3 / 4) - i);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                t = prioq_pop(q);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                assert_se(t);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                assert_se(previous <= t->value);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                previous = t->value;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering                free(t);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        }
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        assert_se(prioq_isempty(q));
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        prioq_free(q);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        assert_se(set_isempty(s));
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        set_free(s);
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering}
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poetteringint main(int argc, char* argv[]) {
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        test_unsigned();
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        test_struct();
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering        return 0;
30bdd695250eeecbf0b36c1e3c90d67ca03953edLennart Poettering}