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 } 130