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