git.mutantstargoat.com Git - rpikern/blob - src/libc/stdlib.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include <ctype.h>
   4 #include <limits.h>
   5 #include <assert.h>
   6 #include <alloca.h>
   7
   8 int atoi(const char *str)
   9 {
  10         return strtol(str, 0, 10);
  11 }
  12
  13 long atol(const char *str)
  14 {
  15         return strtol(str, 0, 10);
  16 }
  17
  18 long strtol(const char *str, char **endp, int base)
  19 {
  20         long acc = 0;
  21         int sign = 1;
  22         int valid = 0;
  23         const char *start = str;
  24
  25         while(isspace(*str)) str++;
  26
  27         if(base == 0) {
  28                 if(str[0] == '0') {
  29                         if(str[1] == 'x' || str[1] == 'X') {
  30                                 base = 16;
  31                         } else {
  32                                 base = 8;
  33                         }
  34                 } else {
  35                         base = 10;
  36                 }
  37         }
  38
  39         if(*str == '+') {
  40                 str++;
  41         } else if(*str == '-') {
  42                 sign = -1;
  43                 str++;
  44         }
  45
  46         while(*str) {
  47                 long val = LONG_MAX;
  48                 char c = tolower(*str);
  49
  50                 if(isdigit(c)) {
  51                         val = *str - '0';
  52                 } else if(c >= 'a' && c <= 'f') {
  53                         val = 10 + c - 'a';
  54                 } else {
  55                         break;
  56                 }
  57                 if(val >= base) {
  58                         break;
  59                 }
  60                 valid = 1;
  61
  62                 acc = acc * base + val;
  63                 str++;
  64         }
  65
  66         if(endp) {
  67                 *endp = (char*)(valid ? str : start);
  68         }
  69
  70         return sign > 0 ? acc : -acc;
  71 }
  72
  73 void itoa(int val, char *buf, int base)
  74 {
  75         static char rbuf[16];
  76         char *ptr = rbuf;
  77         int neg = 0;
  78
  79         if(val < 0) {
  80                 neg = 1;
  81                 val = -val;
  82         }
  83
  84         if(val == 0) {
  85                 *ptr++ = '0';
  86         }
  87
  88         while(val) {
  89                 int digit = val % base;
  90                 *ptr++ = digit < 10 ? (digit + '0') : (digit - 10 + 'a');
  91                 val /= base;
  92         }
  93
  94         if(neg) {
  95                 *ptr++ = '-';
  96         }
  97
  98         ptr--;
  99
 100         while(ptr >= rbuf) {
 101                 *buf++ = *ptr--;
 102         }
 103         *buf = 0;
 104 }
 105
 106 void utoa(unsigned int val, char *buf, int base)
 107 {
 108         static char rbuf[16];
 109         char *ptr = rbuf;
 110
 111         if(val == 0) {
 112                 *ptr++ = '0';
 113         }
 114
 115         while(val) {
 116                 unsigned int digit = val % base;
 117                 *ptr++ = digit < 10 ? (digit + '0') : (digit - 10 + 'a');
 118                 val /= base;
 119         }
 120
 121         ptr--;
 122
 123         while(ptr >= rbuf) {
 124                 *buf++ = *ptr--;
 125         }
 126         *buf = 0;
 127 }
 128
 129 double atof(const char *str)
 130 {
 131         return strtod(str, 0);
 132 }
 133
 134
 135 double strtod(const char *str, char **endp)
 136 {
 137         char *ep;
 138         const char *start = str;
 139         int valid = 0;
 140         long ival = 0, dval = 0;
 141         int ddig = 0;
 142         double res;
 143
 144         /* integer part */
 145         ival = strtol(str, &ep, 10);
 146         if(ep == str && *str != '.') {
 147                 if(endp) *endp = (char*)str;
 148                 return 0.0;
 149         }
 150         if(ep != str) valid = 1;
 151         str = *ep == '.' ? ep + 1 : ep;
 152         if(!isdigit(*str)) {
 153                 goto done;
 154         }
 155         valid = 1;
 156
 157         dval = strtol(str, &ep, 10);
 158         assert(dval >= 0);
 159         ddig = ep - str;
 160         str = ep;
 161
 162 done:
 163         if(*endp) {
 164                 *endp = (char*)(valid ? str : start);
 165         }
 166
 167         res = (double)ival;
 168         if(ddig) {
 169                 double d = (double)dval;
 170                 while(ddig-- > 0) {
 171                         d /= 10.0;
 172                 }
 173                 res += d;
 174         }
 175         return res;
 176 }
 177
 178 void abort(void)
 179 {
 180         panic("Aborted\n");
 181 }
 182
 183 #define QSORT_THRESHOLD 4
 184 #define ITEM(idx)       ((char*)arr + (idx) * itemsz)
 185
 186 #define SWAP(p, q) \
 187         do { \
 188                 int nn = itemsz; \
 189                 char *pp = (p); \
 190                 char *qq = (q); \
 191                 do { \
 192                         char tmp = *pp; \
 193                         *pp++ = *qq; \
 194                         *qq++ = tmp; \
 195                 } while(--nn > 0); \
 196         } while(0)
 197
 198 static void ins_sort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
 199 {
 200         int i;
 201         char *it, *a, *b;
 202
 203         if(count <= 1) return;
 204
 205         it = (char*)arr + itemsz;
 206         for(i=1; i<count; i++) {
 207                 a = it;
 208                 it += itemsz;
 209                 while(a > (char*)arr && cmp(a, (b = a - itemsz)) < 0) {
 210                         SWAP(a, b);
 211                         a -= itemsz;
 212                 }
 213         }
 214 }
 215
 216 void qsort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
 217 {
 218         char *ma, *mb, *mc, *left, *right;
 219         size_t sepidx, nleft, nright;
 220
 221         if(count <= 1) return;
 222
 223         if(count < QSORT_THRESHOLD) {
 224                 ins_sort(arr, count, itemsz, cmp);
 225                 return;
 226         }
 227
 228         ma = arr;
 229         mb = ITEM(count / 2);
 230         mc = ITEM(count - 1);
 231         if(cmp(ma, mb) < 0) SWAP(ma, mb);
 232         if(cmp(mc, ma) < 0) SWAP(mc, ma);
 233
 234         left = ma + itemsz;
 235         right = mc - itemsz;
 236         for(;;) {
 237                 while(cmp(left, ma) < 0) left += itemsz;
 238                 while(cmp(ma, right) < 0) right -= itemsz;
 239                 if(left >= right) break;
 240                 SWAP(left, right);
 241         }
 242         SWAP(ma, right);
 243         sepidx = (right - (char*)arr) / itemsz;
 244         nleft = sepidx;
 245         nright = count - nleft - 1;
 246
 247         qsort(ma, nleft, itemsz, cmp);
 248         qsort(right + itemsz, nright, itemsz, cmp);
 249 }