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