Mercurial > hg > nginx-ranges

comparison src/core/ngx_string.c @ 635:e67b227c8dbb default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 *))