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 }