Convert tabs to spaces in design doc templates
[pintos-anon] / 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