src/test/test-prioq.c

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