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.  Runs in O(n lg n) time and O(1) space in
  56    CNT. */
  57 void
  58 qsort (void *array, size_t cnt, size_t size,
  59        int (*compare) (const void *, const void *))
  60 {
  61   sort (array, cnt, size, compare_thunk, &compare);
  62 }
  63
  64 /* Swaps elements with 1-based indexes A_IDX and B_IDX in ARRAY
  65    with elements of SIZE bytes each. */
  66 static void
  67 do_swap (unsigned char *array, size_t a_idx, size_t b_idx, size_t size)
  68 {
  69   unsigned char *a = array + (a_idx - 1) * size;
  70   unsigned char *b = array + (b_idx - 1) * size;
  71   size_t i;
  72
  73   for (i = 0; i < size; i++)
  74     {
  75       unsigned char t = a[i];
  76       a[i] = b[i];
  77       b[i] = t;
  78     }
  79 }
  80
  81 /* Compares elements with 1-based indexes A_IDX and B_IDX in
  82    ARRAY with elements of SIZE bytes each, using COMPARE to
  83    compare elements, passing AUX as auxiliary data, and returns a
  84    strcmp()-type result. */
  85 static int
  86 do_compare (unsigned char *array, size_t a_idx, size_t b_idx, size_t size,
  87             int (*compare) (const void *, const void *, void *aux),
  88             void *aux)
  89 {
  90   return compare (array + (a_idx - 1) * size, array + (b_idx - 1) * size, aux);
  91 }
  92
  93 /* "Float down" the element with 1-based index I in ARRAY of CNT
  94    elements of SIZE bytes each, using COMPARE to compare
  95    elements, passing AUX as auxiliary data. */
  96 static void
  97 heapify (unsigned char *array, size_t i, size_t cnt, size_t size,
  98          int (*compare) (const void *, const void *, void *aux),
  99          void *aux)
 100 {
 101   for (;;)
 102     {
 103       /* Set `max' to the index of the largest element among I
 104          and its children (if any). */
 105       size_t left = 2 * i;
 106       size_t right = 2 * i + 1;
 107       size_t max = i;
 108       if (left <= cnt && do_compare (array, left, max, size, compare, aux) > 0)
 109         max = left;
 110       if (right <= cnt
 111           && do_compare (array, right, max, size, compare, aux) > 0)
 112         max = right;
 113
 114       /* If the maximum value is already in element I, we're
 115          done. */
 116       if (max == i)
 117         break;
 118
 119       /* Swap and continue down the heap. */
 120       do_swap (array, i, max, size);
 121       i = max;
 122     }
 123 }
 124
 125 /* Sorts ARRAY, which contains CNT elements of SIZE bytes each,
 126    using COMPARE to compare elements, passing AUX as auxiliary
 127    data.  When COMPARE is passed a pair of elements A and B,
 128    respectively, it must return a strcmp()-type result, i.e. less
 129    than zero if A < B, zero if A == B, greater than zero if A >
 130    B.  Runs in O(n lg n) time and O(1) space in CNT. */
 131 void
 132 sort (void *array, size_t cnt, size_t size,
 133       int (*compare) (const void *, const void *, void *aux),
 134       void *aux)
 135 {
 136   size_t i;
 137
 138   ASSERT (array != NULL || cnt == 0);
 139   ASSERT (compare != NULL);
 140   ASSERT (size > 0);
 141
 142   /* Build a heap. */
 143   for (i = cnt / 2; i > 0; i--)
 144     heapify (array, i, cnt, size, compare, aux);
 145
 146   /* Sort the heap. */
 147   for (i = cnt; i > 1; i--)
 148     {
 149       do_swap (array, 1, i, size);
 150       heapify (array, 1, i - 1, size, compare, aux);
 151     }
 152 }
 153
 154 /* Searches ARRAY, which contains CNT elements of SIZE bytes
 155    each, for the given KEY.  Returns a match is found, otherwise
 156    a null pointer.  If there are multiple matches, returns an
 157    arbitrary one of them.
 158
 159    ARRAY must be sorted in order according to COMPARE.
 160
 161    Uses COMPARE to compare elements.  When COMPARE is passed a
 162    pair of elements A and B, respectively, it must return a
 163    strcmp()-type result, i.e. less than zero if A < B, zero if A
 164    == B, greater than zero if A > B. */
 165 void *
 166 bsearch (const void *key, const void *array, size_t cnt,
 167          size_t size, int (*compare) (const void *, const void *))
 168 {
 169   return binary_search (key, array, cnt, size, compare_thunk, &compare);
 170 }
 171
 172 /* Searches ARRAY, which contains CNT elements of SIZE bytes
 173    each, for the given KEY.  Returns a match is found, otherwise
 174    a null pointer.  If there are multiple matches, returns an
 175    arbitrary one of them.
 176
 177    ARRAY must be sorted in order according to COMPARE.
 178
 179    Uses COMPARE to compare elements, passing AUX as auxiliary
 180    data.  When COMPARE is passed a pair of elements A and B,
 181    respectively, it must return a strcmp()-type result, i.e. less
 182    than zero if A < B, zero if A == B, greater than zero if A >
 183    B. */
 184 void *
 185 binary_search (const void *key, const void *array, size_t cnt, size_t size,
 186                int (*compare) (const void *, const void *, void *aux),
 187                void *aux)
 188 {
 189   const unsigned char *first = array;
 190   const unsigned char *last = array + size * cnt;
 191
 192   while (first < last)
 193     {
 194       size_t range = (last - first) / size;
 195       const unsigned char *middle = first + (range / 2) * size;
 196       int cmp = compare (key, middle, aux);
 197
 198       if (cmp < 0)
 199         last = middle;
 200       else if (cmp > 0)
 201         first = middle + size;
 202       else
 203         return (void *) middle;
 204     }
 205
 206   return NULL;
 207 }
 208