blob: 880a4b5b8e49244edc9c8c97a23973b676d2623d (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
#include "./sorted_list.h"
int ZoO_sorted_list_index_of
(
ZoO_index const list_length,
const void * const sorted_list,
const void * const elem,
size_t const type_size,
int (*compare) (const void *, const void *, const void *),
const void * const other,
ZoO_index result [const restrict static 1]
)
{
int cmp;
ZoO_index i, current_min, current_max;
const char * sorted_list_access;
sorted_list_access = (char *) sorted_list;
/* This is a binary search. */
if (list_length == 0)
{
*result = 0;
return -1;
}
current_min = 0;
current_max = (list_length - 1);
for (;;)
{
/* FIXME: overflow-safe? */
i = ((current_min + current_max) / 2);
if (i == list_length)
{
/* FIXME: I don't see how this one can be true */
*result = list_length;
return -1;
}
cmp = compare(elem, (sorted_list_access + (i * type_size)), other);
if (cmp > 0)
{
if ((current_min > current_max))
{
*result = (i + 1);
return -1;
}
/* FIXME: overflow-safe? */
current_min = (i + 1);
}
else if (cmp < 0)
{
if ((current_min > current_max) || (i == 0))
{
*result = i;
return -1;
}
/* overflow-safe */
current_max = (i - 1);
}
else
{
*result = i;
return 0;
}
}
}
|
