Mercurial > hg > nginx-ranges
comparison src/core/ngx_string.c @ 635:e67b227c8dbb default tip
Merge with current.
author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|
date | Mon, 25 Apr 2011 04:07:55 +0400 |
parents | 6c96fdd2dfc3 |
children |
comparison
equal
deleted
inserted
replaced
578:f3a9e57d2e17 | 635:e67b227c8dbb |
---|---|
8 #include <ngx_core.h> | 8 #include <ngx_core.h> |
9 | 9 |
10 | 10 |
11 static u_char *ngx_sprintf_num(u_char *buf, u_char *last, uint64_t ui64, | 11 static u_char *ngx_sprintf_num(u_char *buf, u_char *last, uint64_t ui64, |
12 u_char zero, ngx_uint_t hexadecimal, ngx_uint_t width); | 12 u_char zero, ngx_uint_t hexadecimal, ngx_uint_t width); |
13 static ngx_int_t ngx_decode_base64_internal(ngx_str_t *dst, ngx_str_t *src, | |
14 const u_char *basis); | |
13 | 15 |
14 | 16 |
15 void | 17 void |
16 ngx_strlow(u_char *dst, u_char *src, size_t n) | 18 ngx_strlow(u_char *dst, u_char *src, size_t n) |
17 { | 19 { |
73 * %[0][width][u][x|X]l long | 75 * %[0][width][u][x|X]l long |
74 * %[0][width|m][u][x|X]i ngx_int_t/ngx_uint_t | 76 * %[0][width|m][u][x|X]i ngx_int_t/ngx_uint_t |
75 * %[0][width][u][x|X]D int32_t/uint32_t | 77 * %[0][width][u][x|X]D int32_t/uint32_t |
76 * %[0][width][u][x|X]L int64_t/uint64_t | 78 * %[0][width][u][x|X]L int64_t/uint64_t |
77 * %[0][width|m][u][x|X]A ngx_atomic_int_t/ngx_atomic_uint_t | 79 * %[0][width|m][u][x|X]A ngx_atomic_int_t/ngx_atomic_uint_t |
78 * %[0][width][.width]f float | 80 * %[0][width][.width]f double, max valid number fits to %18.15f |
79 * %P ngx_pid_t | 81 * %P ngx_pid_t |
80 * %M ngx_msec_t | 82 * %M ngx_msec_t |
81 * %r rlim_t | 83 * %r rlim_t |
82 * %p void * | 84 * %p void * |
83 * %V ngx_str_t * | 85 * %V ngx_str_t * |
141 u_char * | 143 u_char * |
142 ngx_vslprintf(u_char *buf, u_char *last, const char *fmt, va_list args) | 144 ngx_vslprintf(u_char *buf, u_char *last, const char *fmt, va_list args) |
143 { | 145 { |
144 u_char *p, zero; | 146 u_char *p, zero; |
145 int d; | 147 int d; |
146 float f, scale; | 148 double f, scale; |
147 size_t len, slen; | 149 size_t len, slen; |
148 int64_t i64; | 150 int64_t i64; |
149 uint64_t ui64; | 151 uint64_t ui64; |
150 ngx_msec_t ms; | 152 ngx_msec_t ms; |
151 ngx_uint_t width, sign, hex, max_width, frac_width, n; | 153 ngx_uint_t width, sign, hex, max_width, frac_width, n; |
227 switch (*fmt) { | 229 switch (*fmt) { |
228 | 230 |
229 case 'V': | 231 case 'V': |
230 v = va_arg(args, ngx_str_t *); | 232 v = va_arg(args, ngx_str_t *); |
231 | 233 |
232 len = v->len; | 234 len = ngx_min(((size_t) (last - buf)), v->len); |
233 len = (buf + len < last) ? len : (size_t) (last - buf); | |
234 | |
235 buf = ngx_cpymem(buf, v->data, len); | 235 buf = ngx_cpymem(buf, v->data, len); |
236 fmt++; | 236 fmt++; |
237 | 237 |
238 continue; | 238 continue; |
239 | 239 |
240 case 'v': | 240 case 'v': |
241 vv = va_arg(args, ngx_variable_value_t *); | 241 vv = va_arg(args, ngx_variable_value_t *); |
242 | 242 |
243 len = vv->len; | 243 len = ngx_min(((size_t) (last - buf)), vv->len); |
244 len = (buf + len < last) ? len : (size_t) (last - buf); | |
245 | |
246 buf = ngx_cpymem(buf, vv->data, len); | 244 buf = ngx_cpymem(buf, vv->data, len); |
247 fmt++; | 245 fmt++; |
248 | 246 |
249 continue; | 247 continue; |
250 | 248 |
255 while (*p && buf < last) { | 253 while (*p && buf < last) { |
256 *buf++ = *p++; | 254 *buf++ = *p++; |
257 } | 255 } |
258 | 256 |
259 } else { | 257 } else { |
260 len = (buf + slen < last) ? slen : (size_t) (last - buf); | 258 len = ngx_min(((size_t) (last - buf)), slen); |
261 | |
262 buf = ngx_cpymem(buf, p, len); | 259 buf = ngx_cpymem(buf, p, len); |
263 } | 260 } |
264 | 261 |
265 fmt++; | 262 fmt++; |
266 | 263 |
357 } | 354 } |
358 | 355 |
359 break; | 356 break; |
360 | 357 |
361 case 'f': | 358 case 'f': |
362 f = (float) va_arg(args, double); | 359 f = va_arg(args, double); |
363 | 360 |
364 if (f < 0) { | 361 if (f < 0) { |
365 *buf++ = '-'; | 362 *buf++ = '-'; |
366 f = -f; | 363 f = -f; |
367 } | 364 } |
384 | 381 |
385 /* | 382 /* |
386 * (int64_t) cast is required for msvc6: | 383 * (int64_t) cast is required for msvc6: |
387 * it can not convert uint64_t to double | 384 * it can not convert uint64_t to double |
388 */ | 385 */ |
389 ui64 = (uint64_t) ((f - (int64_t) ui64) * scale); | 386 ui64 = (uint64_t) ((f - (int64_t) ui64) * scale + 0.5); |
390 | 387 |
391 buf = ngx_sprintf_num(buf, last, ui64, '0', 0, frac_width); | 388 buf = ngx_sprintf_num(buf, last, ui64, '0', 0, frac_width); |
392 } | 389 } |
393 | 390 |
394 fmt++; | 391 fmt++; |
875 return value; | 872 return value; |
876 } | 873 } |
877 } | 874 } |
878 | 875 |
879 | 876 |
877 /* parse a fixed point number, e.g., ngx_atofp("10.5", 4, 2) returns 1050 */ | |
878 | |
879 ngx_int_t | |
880 ngx_atofp(u_char *line, size_t n, size_t point) | |
881 { | |
882 ngx_int_t value; | |
883 ngx_uint_t dot; | |
884 | |
885 if (n == 0) { | |
886 return NGX_ERROR; | |
887 } | |
888 | |
889 dot = 0; | |
890 | |
891 for (value = 0; n--; line++) { | |
892 | |
893 if (point == 0) { | |
894 return NGX_ERROR; | |
895 } | |
896 | |
897 if (*line == '.') { | |
898 if (dot) { | |
899 return NGX_ERROR; | |
900 } | |
901 | |
902 dot = 1; | |
903 continue; | |
904 } | |
905 | |
906 if (*line < '0' || *line > '9') { | |
907 return NGX_ERROR; | |
908 } | |
909 | |
910 value = value * 10 + (*line - '0'); | |
911 point -= dot; | |
912 } | |
913 | |
914 while (point--) { | |
915 value = value * 10; | |
916 } | |
917 | |
918 if (value < 0) { | |
919 return NGX_ERROR; | |
920 | |
921 } else { | |
922 return value; | |
923 } | |
924 } | |
925 | |
926 | |
880 ssize_t | 927 ssize_t |
881 ngx_atosz(u_char *line, size_t n) | 928 ngx_atosz(u_char *line, size_t n) |
882 { | 929 { |
883 ssize_t value; | 930 ssize_t value; |
884 | 931 |
1048 | 1095 |
1049 | 1096 |
1050 ngx_int_t | 1097 ngx_int_t |
1051 ngx_decode_base64(ngx_str_t *dst, ngx_str_t *src) | 1098 ngx_decode_base64(ngx_str_t *dst, ngx_str_t *src) |
1052 { | 1099 { |
1053 size_t len; | |
1054 u_char *d, *s; | |
1055 static u_char basis64[] = { | 1100 static u_char basis64[] = { |
1056 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | 1101 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, |
1057 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | 1102 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, |
1058 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 62, 77, 77, 77, 63, | 1103 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 62, 77, 77, 77, 63, |
1059 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 77, 77, 77, 77, 77, 77, | 1104 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 77, 77, 77, 77, 77, 77, |
1070 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | 1115 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, |
1071 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | 1116 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, |
1072 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77 | 1117 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77 |
1073 }; | 1118 }; |
1074 | 1119 |
1120 return ngx_decode_base64_internal(dst, src, basis64); | |
1121 } | |
1122 | |
1123 | |
1124 ngx_int_t | |
1125 ngx_decode_base64url(ngx_str_t *dst, ngx_str_t *src) | |
1126 { | |
1127 static u_char basis64[] = { | |
1128 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | |
1129 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | |
1130 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 62, 77, 77, | |
1131 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 77, 77, 77, 77, 77, 77, | |
1132 77, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, | |
1133 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 77, 77, 77, 77, 63, | |
1134 77, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, | |
1135 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 77, 77, 77, 77, 77, | |
1136 | |
1137 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | |
1138 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | |
1139 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | |
1140 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | |
1141 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | |
1142 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | |
1143 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, | |
1144 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77 | |
1145 }; | |
1146 | |
1147 return ngx_decode_base64_internal(dst, src, basis64); | |
1148 } | |
1149 | |
1150 | |
1151 static ngx_int_t | |
1152 ngx_decode_base64_internal(ngx_str_t *dst, ngx_str_t *src, const u_char *basis) | |
1153 { | |
1154 size_t len; | |
1155 u_char *d, *s; | |
1156 | |
1075 for (len = 0; len < src->len; len++) { | 1157 for (len = 0; len < src->len; len++) { |
1076 if (src->data[len] == '=') { | 1158 if (src->data[len] == '=') { |
1077 break; | 1159 break; |
1078 } | 1160 } |
1079 | 1161 |
1080 if (basis64[src->data[len]] == 77) { | 1162 if (basis[src->data[len]] == 77) { |
1081 return NGX_ERROR; | 1163 return NGX_ERROR; |
1082 } | 1164 } |
1083 } | 1165 } |
1084 | 1166 |
1085 if (len % 4 == 1) { | 1167 if (len % 4 == 1) { |
1088 | 1170 |
1089 s = src->data; | 1171 s = src->data; |
1090 d = dst->data; | 1172 d = dst->data; |
1091 | 1173 |
1092 while (len > 3) { | 1174 while (len > 3) { |
1093 *d++ = (u_char) (basis64[s[0]] << 2 | basis64[s[1]] >> 4); | 1175 *d++ = (u_char) (basis[s[0]] << 2 | basis[s[1]] >> 4); |
1094 *d++ = (u_char) (basis64[s[1]] << 4 | basis64[s[2]] >> 2); | 1176 *d++ = (u_char) (basis[s[1]] << 4 | basis[s[2]] >> 2); |
1095 *d++ = (u_char) (basis64[s[2]] << 6 | basis64[s[3]]); | 1177 *d++ = (u_char) (basis[s[2]] << 6 | basis[s[3]]); |
1096 | 1178 |
1097 s += 4; | 1179 s += 4; |
1098 len -= 4; | 1180 len -= 4; |
1099 } | 1181 } |
1100 | 1182 |
1101 if (len > 1) { | 1183 if (len > 1) { |
1102 *d++ = (u_char) (basis64[s[0]] << 2 | basis64[s[1]] >> 4); | 1184 *d++ = (u_char) (basis[s[0]] << 2 | basis[s[1]] >> 4); |
1103 } | 1185 } |
1104 | 1186 |
1105 if (len > 2) { | 1187 if (len > 2) { |
1106 *d++ = (u_char) (basis64[s[1]] << 4 | basis64[s[2]] >> 2); | 1188 *d++ = (u_char) (basis[s[1]] << 4 | basis[s[2]] >> 2); |
1107 } | 1189 } |
1108 | 1190 |
1109 dst->len = d - dst->data; | 1191 dst->len = d - dst->data; |
1110 | 1192 |
1111 return NGX_OK; | 1193 return NGX_OK; |
1276 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ | 1358 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ |
1277 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ | 1359 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ |
1278 0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */ | 1360 0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */ |
1279 }; | 1361 }; |
1280 | 1362 |
1281 /* " ", "#", "%", "+", "?", %00-%1F, %7F-%FF */ | 1363 /* " ", "#", "%", "&", "+", "?", %00-%1F, %7F-%FF */ |
1282 | 1364 |
1283 static uint32_t args[] = { | 1365 static uint32_t args[] = { |
1284 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ | 1366 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ |
1285 | 1367 |
1286 /* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */ | 1368 /* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */ |
1287 0x80000829, /* 1000 0000 0000 0000 0000 1000 0010 1001 */ | 1369 0x88000869, /* 1000 1000 0000 0000 0000 1000 0110 1001 */ |
1288 | 1370 |
1289 /* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */ | 1371 /* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */ |
1290 0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */ | 1372 0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */ |
1291 | 1373 |
1292 /* ~}| {zyx wvut srqp onml kjih gfed cba` */ | 1374 /* ~}| {zyx wvut srqp onml kjih gfed cba` */ |
1591 | 1673 |
1592 return (uintptr_t) dst; | 1674 return (uintptr_t) dst; |
1593 } | 1675 } |
1594 | 1676 |
1595 | 1677 |
1678 void | |
1679 ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp, | |
1680 ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) | |
1681 { | |
1682 ngx_str_node_t *n, *t; | |
1683 ngx_rbtree_node_t **p; | |
1684 | |
1685 for ( ;; ) { | |
1686 | |
1687 n = (ngx_str_node_t *) node; | |
1688 t = (ngx_str_node_t *) temp; | |
1689 | |
1690 if (node->key != temp->key) { | |
1691 | |
1692 p = (node->key < temp->key) ? &temp->left : &temp->right; | |
1693 | |
1694 } else if (n->str.len != t->str.len) { | |
1695 | |
1696 p = (n->str.len < t->str.len) ? &temp->left : &temp->right; | |
1697 | |
1698 } else { | |
1699 p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 0) | |
1700 ? &temp->left : &temp->right; | |
1701 } | |
1702 | |
1703 if (*p == sentinel) { | |
1704 break; | |
1705 } | |
1706 | |
1707 temp = *p; | |
1708 } | |
1709 | |
1710 *p = node; | |
1711 node->parent = temp; | |
1712 node->left = sentinel; | |
1713 node->right = sentinel; | |
1714 ngx_rbt_red(node); | |
1715 } | |
1716 | |
1717 | |
1718 ngx_str_node_t * | |
1719 ngx_str_rbtree_lookup(ngx_rbtree_t *rbtree, ngx_str_t *val, uint32_t hash) | |
1720 { | |
1721 ngx_int_t rc; | |
1722 ngx_str_node_t *n; | |
1723 ngx_rbtree_node_t *node, *sentinel; | |
1724 | |
1725 node = rbtree->root; | |
1726 sentinel = rbtree->sentinel; | |
1727 | |
1728 while (node != sentinel) { | |
1729 | |
1730 n = (ngx_str_node_t *) node; | |
1731 | |
1732 if (hash != node->key) { | |
1733 node = (hash < node->key) ? node->left : node->right; | |
1734 continue; | |
1735 } | |
1736 | |
1737 if (val->len != n->str.len) { | |
1738 node = (val->len < n->str.len) ? node->left : node->right; | |
1739 continue; | |
1740 } | |
1741 | |
1742 rc = ngx_memcmp(val->data, n->str.data, val->len); | |
1743 | |
1744 if (rc < 0) { | |
1745 node = node->left; | |
1746 continue; | |
1747 } | |
1748 | |
1749 if (rc > 0) { | |
1750 node = node->right; | |
1751 continue; | |
1752 } | |
1753 | |
1754 return n; | |
1755 } | |
1756 | |
1757 return NULL; | |
1758 } | |
1759 | |
1760 | |
1596 /* ngx_sort() is implemented as insertion sort because we need stable sort */ | 1761 /* ngx_sort() is implemented as insertion sort because we need stable sort */ |
1597 | 1762 |
1598 void | 1763 void |
1599 ngx_sort(void *base, size_t n, size_t size, | 1764 ngx_sort(void *base, size_t n, size_t size, |
1600 ngx_int_t (*cmp)(const void *, const void *)) | 1765 ngx_int_t (*cmp)(const void *, const void *)) |