ReactOS  0.4.15-dev-5606-gf34e425
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  */
38 UINT
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 
114 UINT
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 }
#define IN
Definition: typedefs.h:39
int32_t INT
Definition: typedefs.h:58
uint32_t ULONG_PTR
Definition: typedefs.h:65
unsigned int BOOL
Definition: ntddk_ex.h:94
UINT BisectListSortedByValue(IN PLIST_CTL ListCtl, IN ULONG_PTR Value, OUT PUINT pValueItem OPTIONAL, IN BOOL BisectRightOrLeft)
Definition: utils.c:115
#define CB_ERR
Definition: winuser.h:2425
_Must_inspect_result_ _In_ WDFKEY _In_ PCUNICODE_STRING _Out_opt_ PUSHORT _Inout_opt_ PUNICODE_STRING Value
Definition: wdfregistry.h:406
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 UINT
Definition: ndis.h:50
#define OUT
Definition: typedefs.h:40
unsigned int * PUINT
Definition: ndis.h:50
PULONG MinorVersion OPTIONAL
Definition: CrossNt.h:68