ReactOS 0.4.15-dev-7693-gd0e2924
utils.c
Go to the documentation of this file.
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 */
38UINT
40 IN PLIST_CTL ListCtl,
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
114UINT
116 IN PLIST_CTL ListCtl,
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}
UINT BisectListSortedByValue(IN PLIST_CTL ListCtl, IN ULONG_PTR Value, OUT PUINT pValueItem OPTIONAL, IN BOOL BisectRightOrLeft)
Definition: utils.c:115
UINT BisectListSortedByValueEx(IN PLIST_CTL ListCtl, IN ULONG_PTR Value, IN UINT itemStart, IN UINT itemEnd, OUT PUINT pValueItem OPTIONAL, IN BOOL BisectRightOrLeft)
Definition: utils.c:39
unsigned int BOOL
Definition: ntddk_ex.h:94
unsigned int * PUINT
Definition: ndis.h:50
unsigned int UINT
Definition: ndis.h:50
PULONG MinorVersion OPTIONAL
Definition: CrossNt.h:68
int32_t INT
Definition: typedefs.h:58
uint32_t ULONG_PTR
Definition: typedefs.h:65
#define IN
Definition: typedefs.h:39
#define OUT
Definition: typedefs.h:40
_Must_inspect_result_ _In_ WDFKEY _In_ PCUNICODE_STRING _Out_opt_ PUSHORT _Inout_opt_ PUNICODE_STRING Value
Definition: wdfregistry.h:413
#define CB_ERR
Definition: winuser.h:2434