src/test/test-prioq.c

	test-prioq.c revision 30bdd695250eeecbf0b36c1e3c90d67ca03953ed
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering/***
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering  This file is part of systemd.
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering  Copyright 2013 Lennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering  systemd is free software; you can redistribute it and/or modify it
5430f7f2bc7330f3088b894166bf3524a067e3d8Lennart Poettering  under the terms of the GNU Lesser General Public License as published by
5430f7f2bc7330f3088b894166bf3524a067e3d8Lennart Poettering  the Free Software Foundation; either version 2.1 of the License, or
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering  (at your option) any later version.
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering  systemd is distributed in the hope that it will be useful, but
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering  WITHOUT ANY WARRANTY; without even the implied warranty of
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
5430f7f2bc7330f3088b894166bf3524a067e3d8Lennart Poettering  Lesser General Public License for more details.
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
5430f7f2bc7330f3088b894166bf3524a067e3d8Lennart Poettering  You should have received a copy of the GNU Lesser General Public License
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering  along with systemd; If not, see <http://www.gnu.org/licenses/>.
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering***/
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering#include <stdlib.h>
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering#include "util.h"
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering#include "set.h"
0dad12c190b7493955cd60d2a1625199b1709f69Lennart Poettering#include "prioq.h"
0dad12c190b7493955cd60d2a1625199b1709f69Lennart Poettering
72f1d5a2880d103dc1c1746f5c02e192e054705eLennart Poettering#define SET_SIZE 1024*4
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poetteringstatic int unsigned_compare(const void *a, const void *b) {
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering        const unsigned *x = a, *y = b;
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        if (*x < *y)
fe6521272ba203ec8f0d5a94f0729960b3f90525Lennart Poettering                return -1;
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
bb99a35a873c35e80b0b47fe045081022660374dLennart Poettering        if (*x > *y)
bb99a35a873c35e80b0b47fe045081022660374dLennart Poettering                return 1;
3ed08c446cfaaae2b234fdfeb0c34ab6b4748c3eLennart Poettering
3ed08c446cfaaae2b234fdfeb0c34ab6b4748c3eLennart Poettering        return 0;
3ed08c446cfaaae2b234fdfeb0c34ab6b4748c3eLennart Poettering}
3ed08c446cfaaae2b234fdfeb0c34ab6b4748c3eLennart Poettering
3ed08c446cfaaae2b234fdfeb0c34ab6b4748c3eLennart Poetteringstatic void test_unsigned(void) {
3ed08c446cfaaae2b234fdfeb0c34ab6b4748c3eLennart Poettering        unsigned buffer[SET_SIZE], i;
3ed08c446cfaaae2b234fdfeb0c34ab6b4748c3eLennart Poettering        Prioq *q;
3ed08c446cfaaae2b234fdfeb0c34ab6b4748c3eLennart Poettering
3ed08c446cfaaae2b234fdfeb0c34ab6b4748c3eLennart Poettering        srand(0);
3ed08c446cfaaae2b234fdfeb0c34ab6b4748c3eLennart Poettering
3ed08c446cfaaae2b234fdfeb0c34ab6b4748c3eLennart Poettering        q = prioq_new(trivial_compare_func);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        assert_se(q);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        for (i = 0; i < ELEMENTSOF(buffer); i++) {
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                unsigned u;
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                u = (unsigned) rand();
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                buffer[i] = u;
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                assert_se(prioq_put(q, UINT_TO_PTR(u), NULL) >= 0);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        }
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        qsort(buffer, ELEMENTSOF(buffer), sizeof(buffer[0]), unsigned_compare);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        for (i = 0; i < ELEMENTSOF(buffer); i++) {
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                unsigned u;
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                assert_se(prioq_size(q) == ELEMENTSOF(buffer) - i);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
bb99a35a873c35e80b0b47fe045081022660374dLennart Poettering                u = PTR_TO_UINT(prioq_pop(q));
bb99a35a873c35e80b0b47fe045081022660374dLennart Poettering                assert_se(buffer[i] == u);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        }
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        assert_se(prioq_isempty(q));
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        prioq_free(q);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering}
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poetteringstruct test {
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        unsigned value;
a5344d2c3b0f14e954ce1c0ef905c5b44bc5bf0aLennart Poettering        unsigned idx;
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering};
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poetteringstatic int test_compare(const void *a, const void *b) {
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        const struct test *x = a, *y = b;
d0bbc21caa6e68693a47db60c93e99422bf2a858Lennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        if (x->value < y->value)
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                return -1;
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        if (x->value > y->value)
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                return 1;
a5344d2c3b0f14e954ce1c0ef905c5b44bc5bf0aLennart Poettering
18c7ed186be28800a2eeb37ad31c9c44480d3d9cLennart Poettering        return 0;
18c7ed186be28800a2eeb37ad31c9c44480d3d9cLennart Poettering}
18c7ed186be28800a2eeb37ad31c9c44480d3d9cLennart Poettering
18c7ed186be28800a2eeb37ad31c9c44480d3d9cLennart Poetteringstatic unsigned test_hash(const void *a) {
18c7ed186be28800a2eeb37ad31c9c44480d3d9cLennart Poettering        const struct test *x = a;
d0bbc21caa6e68693a47db60c93e99422bf2a858Lennart Poettering
fe6521272ba203ec8f0d5a94f0729960b3f90525Lennart Poettering        return x->value;
fe6521272ba203ec8f0d5a94f0729960b3f90525Lennart Poettering}
fe6521272ba203ec8f0d5a94f0729960b3f90525Lennart Poettering
fe6521272ba203ec8f0d5a94f0729960b3f90525Lennart Poetteringstatic void test_struct(void) {
fe6521272ba203ec8f0d5a94f0729960b3f90525Lennart Poettering        Prioq *q;
fe6521272ba203ec8f0d5a94f0729960b3f90525Lennart Poettering        Set *s;
d0bbc21caa6e68693a47db60c93e99422bf2a858Lennart Poettering        unsigned previous = 0, i;
d0bbc21caa6e68693a47db60c93e99422bf2a858Lennart Poettering        int r;
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        srand(0);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        q = prioq_new(test_compare);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        assert_se(q);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
d0bbc21caa6e68693a47db60c93e99422bf2a858Lennart Poettering        s = set_new(test_hash, test_compare);
d0bbc21caa6e68693a47db60c93e99422bf2a858Lennart Poettering        assert_se(s);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
d0bbc21caa6e68693a47db60c93e99422bf2a858Lennart Poettering        for (i = 0; i < SET_SIZE; i++) {
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                struct test *t;
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering                t = new0(struct test, 1);
25d042e81516246b1ebf706a57c47ac19abb0b8aLennart Poettering                assert_se(t);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                t->value = (unsigned) rand();
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering                r = prioq_put(q, t, &t->idx);
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering                assert_se(r >= 0);
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering                if (i % 4 == 0) {
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering                        r = set_put(s, t);
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering                        assert_se(r >= 0);
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering                }
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering        }
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering        for (;;) {
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering                struct test *t;
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering                t = set_steal_first(s);
25d042e81516246b1ebf706a57c47ac19abb0b8aLennart Poettering                if (!t)
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                        break;
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                r = prioq_remove(q, t, &t->idx);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                assert_se(r > 0);
72f1d5a2880d103dc1c1746f5c02e192e054705eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                free(t);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        }
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        for (i = 0; i < SET_SIZE * 3 / 4; i++) {
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                struct test *t;
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                assert_se(prioq_size(q) == (SET_SIZE * 3 / 4) - i);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                t = prioq_pop(q);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                assert_se(t);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering                assert_se(previous <= t->value);
72f1d5a2880d103dc1c1746f5c02e192e054705eLennart Poettering                previous = t->value;
72f1d5a2880d103dc1c1746f5c02e192e054705eLennart Poettering                free(t);
72f1d5a2880d103dc1c1746f5c02e192e054705eLennart Poettering        }
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        assert_se(prioq_isempty(q));
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        prioq_free(q);
72f1d5a2880d103dc1c1746f5c02e192e054705eLennart Poettering
72f1d5a2880d103dc1c1746f5c02e192e054705eLennart Poettering        assert_se(set_isempty(s));
72f1d5a2880d103dc1c1746f5c02e192e054705eLennart Poettering        set_free(s);
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering}
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poetteringint main(int argc, char* argv[]) {
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering
7f3e62571a63ac90de6ac5eefeeb8d3e9aa6f49eLennart Poettering        test_unsigned();
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering        test_struct();
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering        return 0;
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering}
b070e7f3c9ed680c821bd89d42506695f2438506Lennart Poettering