pintos-os.org Git - pintos-anon/blob - src/lib/stdlib.c

   1 #include <ctype.h>
   2 #include <debug.h>
   3 #include <random.h>
   4 #include <stdlib.h>
   5 #include <stdbool.h>
   6
   7 /* Converts a string representation of a signed decimal integer
   8    in S into an `int', which is returned. */
   9 int
  10 atoi (const char *s)
  11 {
  12   bool negative;
  13   int value;
  14
  15   ASSERT (s != NULL);
  16
  17   /* Skip white space. */
  18   while (isspace ((unsigned char) *s))
  19     s++;
  20
  21   /* Parse sign. */
  22   negative = false;
  23   if (*s == '+')
  24     s++;
  25   else if (*s == '-')
  26     {
  27       negative = true;
  28       s++;
  29     }
  30
  31   /* Parse digits.  We always initially parse the value as
  32      negative, and then make it positive later, because the
  33      negative range of an int is bigger than the positive range
  34      on a 2's complement system. */
  35   for (value = 0; isdigit (*s); s++)
  36     value = value * 10 - (*s - '0');
  37   if (!negative)
  38     value = -value;
  39
  40   return value;
  41 }
  42
  43 /* Compares A and B by calling the AUX function. */
  44 static int
  45 compare_thunk (const void *a, const void *b, void *aux)
  46 {
  47   int (**compare) (const void *, const void *) = aux;
  48   return (*compare) (a, b);
  49 }
  50
  51 /* Sorts ARRAY, which contains CNT elements of SIZE bytes each,
  52    using COMPARE.  When COMPARE is passed a pair of elements A
  53    and B, respectively, it must return a strcmp()-type result,
  54    i.e. less than zero if A < B, zero if A == B, greater than
  55    zero if A > B. */
  56 void
  57 qsort (void *array, size_t cnt, size_t size,
  58        int (*compare) (const void *, const void *))
  59 {
  60   quick_sort (array, cnt, size, compare_thunk, &compare);
  61 }
  62
  63 /* Swaps the SIZE bytes at A and B. */
  64 static void
  65 swap (unsigned char *a, unsigned char *b, size_t size)
  66 {
  67   size_t i;
  68
  69   for (i = 0; i < size; i++)
  70     {
  71       unsigned char t = a[i];
  72       a[i] = b[i];
  73       b[i] = t;
  74     }
  75 }
  76
  77 /* Selects a random "pivot" element in ARRAY, which contains CNT
  78    elements of SIZE bytes each, and partitions ARRAY into two
  79    contiguous subranges around the pivot, so that the first N
  80    elements are less than or equal to the pivot and the remaining
  81    elements are greater than the pivot.  Returns N.
  82
  83    Uses COMPARE to compare elements, passing AUX as auxiliary
  84    data.  When COMPARE is passed a pair of elements A and B,
  85    respectively, it must return a strcmp()-type result, i.e. less
  86    than zero if A < B, zero if A == B, greater than zero if A >
  87    B. */
  88 static size_t
  89 randomized_partition (void *array, size_t cnt, size_t size,
  90                       int (*compare) (const void *, const void *, void *aux),
  91                       void *aux)
  92 {
  93   unsigned char *first = array;                 /* Beginning of array. */
  94   unsigned char *last = first + size * cnt;     /* End of array. */
  95   unsigned char *pivot = last - size;           /* Element used as pivot. */
  96   unsigned char *middle;        /* Invariant: elements on left are <= pivot. */
  97   unsigned char *current;
  98
  99   ASSERT (array != NULL);
 100   ASSERT (cnt > 1);
 101   ASSERT (size > 0);
 102   ASSERT (compare != NULL);
 103
 104   /* Choose a random pivot. */
 105   swap (pivot, first + (random_ulong () % cnt) * size, size);
 106
 107   /* Iterate through the array moving elements less than or equal
 108      to the pivot to the middle. */
 109   middle = array;
 110   for (current = first; current < last; current += size)
 111     if (compare (current, pivot, aux) <= 0)
 112       {
 113         swap (middle, current, size);
 114         middle += size;
 115       }
 116
 117   return (middle - first) / size;
 118 }
 119
 120 /* Sorts ARRAY, which contains CNT elements of SIZE bytes each,
 121    using COMPARE to compare elements, passing AUX as auxiliary
 122    data.  When COMPARE is passed a pair of elements A and B,
 123    respectively, it must return a strcmp()-type result, i.e. less
 124    than zero if A < B, zero if A == B, greater than zero if A >
 125    B. */
 126 void
 127 quick_sort (void *array_, size_t cnt, size_t size,
 128             int (*compare) (const void *, const void *, void *aux),
 129             void *aux)
 130 {
 131   unsigned char *array = array_;
 132
 133   ASSERT (array != NULL || cnt == 0);
 134   ASSERT (compare != NULL);
 135   ASSERT (size > 0);
 136
 137   if (cnt > 1)
 138     {
 139       size_t q = randomized_partition (array, cnt, size, compare, aux);
 140
 141       /* Sort smaller partition first to guarantee O(lg n) stack
 142          depth limit. */
 143       if (q < cnt - q)
 144         {
 145           quick_sort (array, q, size, compare, aux);
 146           quick_sort (array + q * size, cnt - q, size, compare, aux);
 147         }
 148       else
 149         {
 150           quick_sort (array + q * size, cnt - q, size, compare, aux);
 151           quick_sort (array, q, size, compare, aux);
 152         }
 153     }
 154 }
 155
 156 /* Searches ARRAY, which contains CNT elements of SIZE bytes
 157    each, for the given KEY.  Returns a match is found, otherwise
 158    a null pointer.  If there are multiple matches, returns an
 159    arbitrary one of them.
 160
 161    ARRAY must be sorted in order according to COMPARE.
 162
 163    Uses COMPARE to compare elements.  When COMPARE is passed a
 164    pair of elements A and B, respectively, it must return a
 165    strcmp()-type result, i.e. less than zero if A < B, zero if A
 166    == B, greater than zero if A > B. */
 167 void *
 168 bsearch (const void *key, const void *array, size_t cnt,
 169          size_t size, int (*compare) (const void *, const void *))
 170 {
 171   return binary_search (key, array, cnt, size, compare_thunk, &compare);
 172 }
 173
 174 /* Searches ARRAY, which contains CNT elements of SIZE bytes
 175    each, for the given KEY.  Returns a match is found, otherwise
 176    a null pointer.  If there are multiple matches, returns an
 177    arbitrary one of them.
 178
 179    ARRAY must be sorted in order according to COMPARE.
 180
 181    Uses COMPARE to compare elements, passing AUX as auxiliary
 182    data.  When COMPARE is passed a pair of elements A and B,
 183    respectively, it must return a strcmp()-type result, i.e. less
 184    than zero if A < B, zero if A == B, greater than zero if A >
 185    B. */
 186 void *
 187 binary_search (const void *key, const void *array, size_t cnt, size_t size,
 188                int (*compare) (const void *, const void *, void *aux),
 189                void *aux)
 190 {
 191   const unsigned char *first = array;
 192   const unsigned char *last = array + size * cnt;
 193
 194   while (first < last)
 195     {
 196       size_t range = (last - first) / size;
 197       const unsigned char *middle = first + (range / 2) * size;
 198       int cmp = compare (key, middle, aux);
 199
 200       if (cmp < 0)
 201         last = middle;
 202       else if (cmp > 0)
 203         first = middle + size;
 204       else
 205         return (void *) middle;
 206     }
 207
 208   return NULL;
 209 }
 210