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         char rbuf[16];
  76         char *ptr = rbuf;
  77         int neg = 0;
  78
  79         if(base <= 0) base = 10;
  80
  81         if(val < 0) {
  82                 neg = 1;
  83                 val = -val;
  84         }
  85
  86         if(val == 0) {
  87                 *ptr++ = '0';
  88         }
  89
  90         while(val) {
  91                 int digit = val % base;
  92                 *ptr++ = digit < 10 ? (digit + '0') : (digit - 10 + 'a');
  93                 val /= base;
  94         }
  95
  96         if(neg) {
  97                 *ptr++ = '-';
  98         }
  99
 100         ptr--;
 101
 102         while(ptr >= rbuf) {
 103                 *buf++ = *ptr--;
 104         }
 105         *buf = 0;
 106 }
 107
 108 void xtoa(unsigned int val, char *buf)
 109 {
 110         char rbuf[16];
 111         char *ptr = rbuf;
 112
 113         if(val == 0) {
 114                 *ptr++ = '0';
 115         }
 116
 117         while(val) {
 118                 unsigned int digit = val & 0xf;
 119                 *ptr++ = digit < 10 ? (digit + '0') : (digit - 10 + 'a');
 120                 val >>= 4;
 121         }
 122
 123         ptr--;
 124
 125         while(ptr >= rbuf) {
 126                 *buf++ = *ptr--;
 127         }
 128         *buf = 0;
 129 }
 130
 131 void utoa(unsigned int val, char *buf, int base)
 132 {
 133         static char rbuf[16];
 134         char *ptr = rbuf;
 135
 136         if(base == 16) {
 137                 xtoa(val, buf);
 138                 return;
 139         }
 140
 141         if(base <= 0) base = 10;
 142
 143         if(val == 0) {
 144                 *ptr++ = '0';
 145         }
 146
 147         while(val) {
 148                 unsigned int digit = val % base;
 149                 *ptr++ = digit < 10 ? (digit + '0') : (digit - 10 + 'a');
 150                 val /= base;
 151         }
 152
 153         ptr--;
 154
 155         while(ptr >= rbuf) {
 156                 *buf++ = *ptr--;
 157         }
 158         *buf = 0;
 159 }
 160
 161 #define QSORT_THRESHOLD 4
 162 #define ITEM(idx)       ((char*)arr + (idx) * itemsz)
 163
 164 #define SWAP(p, q) \
 165         do { \
 166                 int nn = itemsz; \
 167                 char *pp = (p); \
 168                 char *qq = (q); \
 169                 do { \
 170                         char tmp = *pp; \
 171                         *pp++ = *qq; \
 172                         *qq++ = tmp; \
 173                 } while(--nn > 0); \
 174         } while(0)
 175
 176 static void ins_sort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
 177 {
 178         int i;
 179         char *it, *a, *b;
 180
 181         if(count <= 1) return;
 182
 183         it = (char*)arr + itemsz;
 184         for(i=1; i<count; i++) {
 185                 a = it;
 186                 it += itemsz;
 187                 while(a > (char*)arr && cmp(a, (b = a - itemsz)) < 0) {
 188                         SWAP(a, b);
 189                         a -= itemsz;
 190                 }
 191         }
 192 }
 193
 194 void qsort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
 195 {
 196         char *ma, *mb, *mc, *left, *right;
 197         size_t sepidx, nleft, nright;
 198
 199         if(count <= 1) return;
 200
 201         if(count < QSORT_THRESHOLD) {
 202                 ins_sort(arr, count, itemsz, cmp);
 203                 return;
 204         }
 205
 206         ma = arr;
 207         mb = ITEM(count / 2);
 208         mc = ITEM(count - 1);
 209         if(cmp(ma, mb) < 0) SWAP(ma, mb);
 210         if(cmp(mc, ma) < 0) SWAP(mc, ma);
 211
 212         left = ma + itemsz;
 213         right = mc - itemsz;
 214         for(;;) {
 215                 while(cmp(left, ma) < 0) left += itemsz;
 216                 while(cmp(ma, right) < 0) right -= itemsz;
 217                 if(left >= right) break;
 218                 SWAP(left, right);
 219         }
 220         SWAP(ma, right);
 221         sepidx = (right - (char*)arr) / itemsz;
 222         nleft = sepidx;
 223         nright = count - nleft - 1;
 224
 225         qsort(ma, nleft, itemsz, cmp);
 226         qsort(right + itemsz, nright, itemsz, cmp);
 227 }