git.mutantstargoat.com Git - mdlife/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 #define QSORT_THRESHOLD 4
 130 #define ITEM(idx)       ((char*)arr + (idx) * itemsz)
 131
 132 #define SWAP(p, q) \
 133         do { \
 134                 int nn = itemsz; \
 135                 char *pp = (p); \
 136                 char *qq = (q); \
 137                 do { \
 138                         char tmp = *pp; \
 139                         *pp++ = *qq; \
 140                         *qq++ = tmp; \
 141                 } while(--nn > 0); \
 142         } while(0)
 143
 144 static void ins_sort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
 145 {
 146         int i;
 147         char *it, *a, *b;
 148
 149         if(count <= 1) return;
 150
 151         it = (char*)arr + itemsz;
 152         for(i=1; i<count; i++) {
 153                 a = it;
 154                 it += itemsz;
 155                 while(a > (char*)arr && cmp(a, (b = a - itemsz)) < 0) {
 156                         SWAP(a, b);
 157                         a -= itemsz;
 158                 }
 159         }
 160 }
 161
 162 void qsort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
 163 {
 164         char *ma, *mb, *mc, *left, *right;
 165         size_t sepidx, nleft, nright;
 166
 167         if(count <= 1) return;
 168
 169         if(count < QSORT_THRESHOLD) {
 170                 ins_sort(arr, count, itemsz, cmp);
 171                 return;
 172         }
 173
 174         ma = arr;
 175         mb = ITEM(count / 2);
 176         mc = ITEM(count - 1);
 177         if(cmp(ma, mb) < 0) SWAP(ma, mb);
 178         if(cmp(mc, ma) < 0) SWAP(mc, ma);
 179
 180         left = ma + itemsz;
 181         right = mc - itemsz;
 182         for(;;) {
 183                 while(cmp(left, ma) < 0) left += itemsz;
 184                 while(cmp(ma, right) < 0) right -= itemsz;
 185                 if(left >= right) break;
 186                 SWAP(left, right);
 187         }
 188         SWAP(ma, right);
 189         sepidx = (right - (char*)arr) / itemsz;
 190         nleft = sepidx;
 191         nright = count - nleft - 1;
 192
 193         qsort(ma, nleft, itemsz, cmp);
 194         qsort(right + itemsz, nright, itemsz, cmp);
 195 }