[ACPPAGE] Make use of the PCH.
[reactos.git] / dll / cpl / console / utils.c
1 /*
2 * PROJECT: ReactOS Console Configuration DLL
3 * LICENSE: GPL - See COPYING in the top level directory
4 * FILE: dll/cpl/console/utils.c
5 * PURPOSE: Utility functions
6 * PROGRAMMERS: Hermes Belusca-Maito (hermes.belusca@sfr.fr)
7 */
8
9 #include "console.h"
10
11 #define NDEBUG
12 #include <debug.h>
13
14
15 /*
16 * A function that locates the insertion point (index) for a given value 'Value'
17 * in a list 'List' to maintain its sorted order by increasing values.
18 *
19 * - When 'BisectRightOrLeft' == TRUE, the bisection is performed to the right,
20 * i.e. the returned insertion point comes after (to the right of) any existing
21 * entries of 'Value' in 'List'.
22 * The returned insertion point 'i' partitions the list 'List' into two halves
23 * such that:
24 * all(val <= Value for val in List[start:i[) for the left side, and
25 * all(val > Value for val in List[i:end+1[) for the right side.
26 *
27 * - When 'BisectRightOrLeft' == FALSE, the bisection is performed to the left,
28 * i.e. the returned insertion point comes before (to the left of) any existing
29 * entries of 'Value' in 'List'.
30 * The returned insertion point 'i' partitions the list 'List' into two halves
31 * such that:
32 * all(val < Value for val in List[start:i[) for the left side, and
33 * all(val >= Value for val in List[i:end+1[) for the right side.
34 *
35 * The exact value of List[i] may, or may not, be equal to Value, depending on
36 * whether or not 'Value' is actually present on the list.
37 */
38 UINT
39 BisectListSortedByValueEx(
40 IN PLIST_CTL ListCtl,
41 IN ULONG_PTR Value,
42 IN UINT itemStart,
43 IN UINT itemEnd,
44 OUT PUINT pValueItem OPTIONAL,
45 IN BOOL BisectRightOrLeft)
46 {
47 UINT iItemStart, iItemEnd, iItem;
48 ULONG_PTR itemData;
49
50 /* Sanity checks */
51 if (itemStart > itemEnd)
52 return CB_ERR; // Fail
53
54 /* Initialize */
55 iItemStart = itemStart;
56 iItemEnd = itemEnd;
57 iItem = iItemStart;
58
59 if (pValueItem)
60 *pValueItem = CB_ERR;
61
62 while (iItemStart <= iItemEnd)
63 {
64 /*
65 * Bisect. Note the following:
66 * - if iItemEnd == iItemStart + 1, then iItem == iItemStart;
67 * - if iItemStart == iItemEnd, then iItemStart == iItem == iItemEnd.
68 * In all but the last case, iItemStart <= iItem < iItemEnd.
69 */
70 iItem = (iItemStart + iItemEnd) / 2;
71
72 itemData = ListCtl->GetData(ListCtl, iItem);
73 if (itemData == CB_ERR)
74 return CB_ERR; // Fail
75
76 if (Value == itemData)
77 {
78 /* Found a candidate */
79 if (pValueItem)
80 *pValueItem = iItem;
81
82 /*
83 * Try to find the last element (if BisectRightOrLeft == TRUE)
84 * or the first element (if BisectRightOrLeft == FALSE).
85 */
86 if (BisectRightOrLeft)
87 {
88 iItemStart = iItem + 1; // iItemStart may be > iItemEnd
89 }
90 else
91 {
92 if (iItem <= itemStart) break;
93 iItemEnd = iItem - 1; // iItemEnd may be < iItemStart, i.e. iItemStart may be > iItemEnd
94 }
95 }
96 else if (Value < itemData)
97 {
98 if (iItem <= itemStart) break;
99 /* The value should be before iItem */
100 iItemEnd = iItem - 1; // iItemEnd may be < iItemStart, i.e. iItemStart may be > iItemEnd, if iItem == iItemStart.
101 }
102 else // if (itemData < Value)
103 {
104 /* The value should be after iItem */
105 iItemStart = iItem + 1; // iItemStart may be > iItemEnd, if iItem == iItemEnd.
106 }
107
108 /* Here, iItemStart may be == iItemEnd */
109 }
110
111 return iItemStart;
112 }
113
114 UINT
115 BisectListSortedByValue(
116 IN PLIST_CTL ListCtl,
117 IN ULONG_PTR Value,
118 OUT PUINT pValueItem OPTIONAL,
119 IN BOOL BisectRightOrLeft)
120 {
121 INT iItemEnd = ListCtl->GetCount(ListCtl);
122 if (iItemEnd == CB_ERR || iItemEnd <= 0)
123 return CB_ERR; // Fail
124
125 return BisectListSortedByValueEx(ListCtl, Value,
126 0, (UINT)(iItemEnd - 1),
127 pValueItem,
128 BisectRightOrLeft);
129 }