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
   6 int atoi(const char *str)
   7 {
   8         return strtol(str, 0, 10);
   9 }
  10
  11 long atol(const char *str)
  12 {
  13         return strtol(str, 0, 10);
  14 }
  15
  16 long strtol(const char *str, char **endp, int base)
  17 {
  18         long acc = 0;
  19         int sign = 1;
  20         int valid = 0;
  21         const char *start = str;
  22
  23         while(isspace(*str)) str++;
  24
  25         if(base == 0) {
  26                 if(str[0] == '0') {
  27                         if(str[1] == 'x' || str[1] == 'X') {
  28                                 base = 16;
  29                         } else {
  30                                 base = 8;
  31                         }
  32                 } else {
  33                         base = 10;
  34                 }
  35         }
  36
  37         if(*str == '+') {
  38                 str++;
  39         } else if(*str == '-') {
  40                 sign = -1;
  41                 str++;
  42         }
  43
  44         while(*str) {
  45                 long val = LONG_MAX;
  46                 char c = tolower(*str);
  47
  48                 if(isdigit(c)) {
  49                         val = *str - '0';
  50                 } else if(c >= 'a' && c <= 'f') {
  51                         val = 10 + c - 'a';
  52                 } else {
  53                         break;
  54                 }
  55                 if(val >= base) {
  56                         break;
  57                 }
  58                 valid = 1;
  59
  60                 acc = acc * base + val;
  61                 str++;
  62         }
  63
  64         if(endp) {
  65                 *endp = (char*)(valid ? str : start);
  66         }
  67
  68         return sign > 0 ? acc : -acc;
  69 }
  70
  71 void itoa(int val, char *buf, int base)
  72 {
  73         char rbuf[16];
  74         char *ptr = rbuf;
  75         int neg = 0;
  76
  77         if(base <= 0) base = 10;
  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 xtoa(unsigned int val, char *buf)
 107 {
 108         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 & 0xf;
 117                 *ptr++ = digit < 10 ? (digit + '0') : (digit - 10 + 'a');
 118                 val >>= 4;
 119         }
 120
 121         ptr--;
 122
 123         while(ptr >= rbuf) {
 124                 *buf++ = *ptr--;
 125         }
 126         *buf = 0;
 127 }
 128
 129 void utoa(unsigned int val, char *buf, int base)
 130 {
 131         static char rbuf[16];
 132         char *ptr = rbuf;
 133
 134         if(base == 16) {
 135                 xtoa(val, buf);
 136                 return;
 137         }
 138
 139         if(base <= 0) base = 10;
 140
 141         if(val == 0) {
 142                 *ptr++ = '0';
 143         }
 144
 145         while(val) {
 146                 unsigned int digit = val % base;
 147                 *ptr++ = digit < 10 ? (digit + '0') : (digit - 10 + 'a');
 148                 val /= base;
 149         }
 150
 151         ptr--;
 152
 153         while(ptr >= rbuf) {
 154                 *buf++ = *ptr--;
 155         }
 156         *buf = 0;
 157 }
 158
 159 #define QSORT_THRESHOLD 4
 160 #define ITEM(idx)       ((char*)arr + (idx) * itemsz)
 161
 162 #define SWAP(p, q) \
 163         do { \
 164                 int nn = itemsz; \
 165                 char *pp = (p); \
 166                 char *qq = (q); \
 167                 do { \
 168                         char tmp = *pp; \
 169                         *pp++ = *qq; \
 170                         *qq++ = tmp; \
 171                 } while(--nn > 0); \
 172         } while(0)
 173
 174 static void ins_sort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
 175 {
 176         int i;
 177         char *it, *a, *b;
 178
 179         if(count <= 1) return;
 180
 181         it = (char*)arr + itemsz;
 182         for(i=1; i<count; i++) {
 183                 a = it;
 184                 it += itemsz;
 185                 while(a > (char*)arr && cmp(a, (b = a - itemsz)) < 0) {
 186                         SWAP(a, b);
 187                         a -= itemsz;
 188                 }
 189         }
 190 }
 191
 192 void qsort(void *arr, size_t count, size_t itemsz, int (*cmp)(const void*, const void*))
 193 {
 194         char *ma, *mb, *mc, *left, *right;
 195         size_t sepidx, nleft, nright;
 196
 197         if(count <= 1) return;
 198
 199         if(count < QSORT_THRESHOLD) {
 200                 ins_sort(arr, count, itemsz, cmp);
 201                 return;
 202         }
 203
 204         ma = arr;
 205         mb = ITEM(count / 2);
 206         mc = ITEM(count - 1);
 207         if(cmp(ma, mb) < 0) SWAP(ma, mb);
 208         if(cmp(mc, ma) < 0) SWAP(mc, ma);
 209
 210         left = ma + itemsz;
 211         right = mc - itemsz;
 212         for(;;) {
 213                 while(cmp(left, ma) < 0) left += itemsz;
 214                 while(cmp(ma, right) < 0) right -= itemsz;
 215                 if(left >= right) break;
 216                 SWAP(left, right);
 217         }
 218         SWAP(ma, right);
 219         sepidx = (right - (char*)arr) / itemsz;
 220         nleft = sepidx;
 221         nright = count - nleft - 1;
 222
 223         qsort(ma, nleft, itemsz, cmp);
 224         qsort(right + itemsz, nright, itemsz, cmp);
 225 }