test-bsearch-insert-pos.c revision 27a44fcfd8d19bffe0f267f20a2b5d3fe7600fdd
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen/* Copyright (c) 2007-2012 Dovecot authors, see the included COPYING file */
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen#include "test-lib.h"
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen#include "bsearch-insert-pos.h"
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainenstatic int cmp_uint(const unsigned int *i1, const unsigned int *i2)
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen{
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen return *i1 - *i2;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen}
b215a8a123623782554a83f3025ef4e771bd8f01Timo Sirainen
b215a8a123623782554a83f3025ef4e771bd8f01Timo Sirainenvoid test_bsearch_insert_pos(void)
b215a8a123623782554a83f3025ef4e771bd8f01Timo Sirainen{
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen static const unsigned int input[] = {
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen 1, 5, 9, 15, 16, -1U,
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen 1, 5, 9, 15, 16, 17, -1U,
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen -1U
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen };
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen static const unsigned int max_key = 18;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen const unsigned int *cur;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen unsigned int key, len, i, idx;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen bool success;
ad0f1d2f2e7f1d42b2de403b04a0ffe1675109ccTimo Sirainen
ad0f1d2f2e7f1d42b2de403b04a0ffe1675109ccTimo Sirainen cur = input;
ad0f1d2f2e7f1d42b2de403b04a0ffe1675109ccTimo Sirainen for (i = 0; cur[0] != -1U; i++) {
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen for (len = 0; cur[len] != -1U; len++) ;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen for (key = 0; key < max_key; key++) {
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen if (bsearch_insert_pos(&key, cur, len, sizeof(*cur),
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen cmp_uint, &idx))
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen success = cur[idx] == key;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen else if (idx == 0)
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen success = cur[0] > key;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen else if (idx == len)
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen success = cur[len-1] < key;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen else {
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen success = cur[idx-1] < key &&
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen cur[idx+1] > key;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen }
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen if (!success)
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen break;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen }
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen cur += len + 1;
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen
ad0f1d2f2e7f1d42b2de403b04a0ffe1675109ccTimo Sirainen test_out(t_strdup_printf("bsearch_insert_pos(%d,%d)", i, key),
ad0f1d2f2e7f1d42b2de403b04a0ffe1675109ccTimo Sirainen success);
ad0f1d2f2e7f1d42b2de403b04a0ffe1675109ccTimo Sirainen }
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen}
a64adf62fa33f2463a86f990217b0c9078531a40Timo Sirainen