Mercurial > hg > nginx-mail
comparison src/core/ngx_string.c @ 665:0b460e61bdcd default tip
Merge with nginx 1.0.0.
author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|
date | Mon, 25 Apr 2011 04:22:17 +0400 |
parents | 6c96fdd2dfc3 |
children |
comparison
equal
deleted
inserted
replaced
572:06419a2298a9 | 665:0b460e61bdcd |
---|---|
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 { |
18 while (n--) { | 20 while (n) { |
19 *dst = ngx_tolower(*src); | 21 *dst = ngx_tolower(*src); |
20 dst++; | 22 dst++; |
21 src++; | 23 src++; |
24 n--; | |
22 } | 25 } |
23 } | 26 } |
24 | 27 |
25 | 28 |
26 u_char * | 29 u_char * |
72 * %[0][width][u][x|X]l long | 75 * %[0][width][u][x|X]l long |
73 * %[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 |
74 * %[0][width][u][x|X]D int32_t/uint32_t | 77 * %[0][width][u][x|X]D int32_t/uint32_t |
75 * %[0][width][u][x|X]L int64_t/uint64_t | 78 * %[0][width][u][x|X]L int64_t/uint64_t |
76 * %[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 |
77 * %[0][width][.width]f float | 80 * %[0][width][.width]f double, max valid number fits to %18.15f |
78 * %P ngx_pid_t | 81 * %P ngx_pid_t |
79 * %M ngx_msec_t | 82 * %M ngx_msec_t |
80 * %r rlim_t | 83 * %r rlim_t |
81 * %p void * | 84 * %p void * |
82 * %V ngx_str_t * | 85 * %V ngx_str_t * |
140 u_char * | 143 u_char * |
141 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) |
142 { | 145 { |
143 u_char *p, zero; | 146 u_char *p, zero; |
144 int d; | 147 int d; |
145 float f, scale; | 148 double f, scale; |
146 size_t len, slen; | 149 size_t len, slen; |
147 int64_t i64; | 150 int64_t i64; |
148 uint64_t ui64; | 151 uint64_t ui64; |
149 ngx_msec_t ms; | 152 ngx_msec_t ms; |
150 ngx_uint_t width, sign, hex, max_width, frac_width, i; | 153 ngx_uint_t width, sign, hex, max_width, frac_width, n; |
151 ngx_str_t *v; | 154 ngx_str_t *v; |
152 ngx_variable_value_t *vv; | 155 ngx_variable_value_t *vv; |
153 | 156 |
154 while (*fmt && buf < last) { | 157 while (*fmt && buf < last) { |
155 | 158 |
226 switch (*fmt) { | 229 switch (*fmt) { |
227 | 230 |
228 case 'V': | 231 case 'V': |
229 v = va_arg(args, ngx_str_t *); | 232 v = va_arg(args, ngx_str_t *); |
230 | 233 |
231 len = v->len; | 234 len = ngx_min(((size_t) (last - buf)), v->len); |
232 len = (buf + len < last) ? len : (size_t) (last - buf); | |
233 | |
234 buf = ngx_cpymem(buf, v->data, len); | 235 buf = ngx_cpymem(buf, v->data, len); |
235 fmt++; | 236 fmt++; |
236 | 237 |
237 continue; | 238 continue; |
238 | 239 |
239 case 'v': | 240 case 'v': |
240 vv = va_arg(args, ngx_variable_value_t *); | 241 vv = va_arg(args, ngx_variable_value_t *); |
241 | 242 |
242 len = vv->len; | 243 len = ngx_min(((size_t) (last - buf)), vv->len); |
243 len = (buf + len < last) ? len : (size_t) (last - buf); | |
244 | |
245 buf = ngx_cpymem(buf, vv->data, len); | 244 buf = ngx_cpymem(buf, vv->data, len); |
246 fmt++; | 245 fmt++; |
247 | 246 |
248 continue; | 247 continue; |
249 | 248 |
254 while (*p && buf < last) { | 253 while (*p && buf < last) { |
255 *buf++ = *p++; | 254 *buf++ = *p++; |
256 } | 255 } |
257 | 256 |
258 } else { | 257 } else { |
259 len = (buf + slen < last) ? slen : (size_t) (last - buf); | 258 len = ngx_min(((size_t) (last - buf)), slen); |
260 | |
261 buf = ngx_cpymem(buf, p, len); | 259 buf = ngx_cpymem(buf, p, len); |
262 } | 260 } |
263 | 261 |
264 fmt++; | 262 fmt++; |
265 | 263 |
356 } | 354 } |
357 | 355 |
358 break; | 356 break; |
359 | 357 |
360 case 'f': | 358 case 'f': |
361 f = (float) va_arg(args, double); | 359 f = va_arg(args, double); |
362 | 360 |
363 if (f < 0) { | 361 if (f < 0) { |
364 *buf++ = '-'; | 362 *buf++ = '-'; |
365 f = -f; | 363 f = -f; |
366 } | 364 } |
375 *buf++ = '.'; | 373 *buf++ = '.'; |
376 } | 374 } |
377 | 375 |
378 scale = 1.0; | 376 scale = 1.0; |
379 | 377 |
380 for (i = 0; i < frac_width; i++) { | 378 for (n = frac_width; n; n--) { |
381 scale *= 10.0; | 379 scale *= 10.0; |
382 } | 380 } |
383 | 381 |
384 /* | 382 /* |
385 * (int64_t) cast is required for msvc6: | 383 * (int64_t) cast is required for msvc6: |
386 * it can not convert uint64_t to double | 384 * it can not convert uint64_t to double |
387 */ | 385 */ |
388 ui64 = (uint64_t) ((f - (int64_t) ui64) * scale); | 386 ui64 = (uint64_t) ((f - (int64_t) ui64) * scale + 0.5); |
389 | 387 |
390 buf = ngx_sprintf_num(buf, last, ui64, '0', 0, frac_width); | 388 buf = ngx_sprintf_num(buf, last, ui64, '0', 0, frac_width); |
391 } | 389 } |
392 | 390 |
393 fmt++; | 391 fmt++; |
874 return value; | 872 return value; |
875 } | 873 } |
876 } | 874 } |
877 | 875 |
878 | 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 | |
879 ssize_t | 927 ssize_t |
880 ngx_atosz(u_char *line, size_t n) | 928 ngx_atosz(u_char *line, size_t n) |
881 { | 929 { |
882 ssize_t value; | 930 ssize_t value; |
883 | 931 |
1047 | 1095 |
1048 | 1096 |
1049 ngx_int_t | 1097 ngx_int_t |
1050 ngx_decode_base64(ngx_str_t *dst, ngx_str_t *src) | 1098 ngx_decode_base64(ngx_str_t *dst, ngx_str_t *src) |
1051 { | 1099 { |
1052 size_t len; | |
1053 u_char *d, *s; | |
1054 static u_char basis64[] = { | 1100 static u_char basis64[] = { |
1055 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, |
1056 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, |
1057 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, |
1058 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, |
1069 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, |
1070 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, |
1071 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 |
1072 }; | 1118 }; |
1073 | 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 | |
1074 for (len = 0; len < src->len; len++) { | 1157 for (len = 0; len < src->len; len++) { |
1075 if (src->data[len] == '=') { | 1158 if (src->data[len] == '=') { |
1076 break; | 1159 break; |
1077 } | 1160 } |
1078 | 1161 |
1079 if (basis64[src->data[len]] == 77) { | 1162 if (basis[src->data[len]] == 77) { |
1080 return NGX_ERROR; | 1163 return NGX_ERROR; |
1081 } | 1164 } |
1082 } | 1165 } |
1083 | 1166 |
1084 if (len % 4 == 1) { | 1167 if (len % 4 == 1) { |
1087 | 1170 |
1088 s = src->data; | 1171 s = src->data; |
1089 d = dst->data; | 1172 d = dst->data; |
1090 | 1173 |
1091 while (len > 3) { | 1174 while (len > 3) { |
1092 *d++ = (u_char) (basis64[s[0]] << 2 | basis64[s[1]] >> 4); | 1175 *d++ = (u_char) (basis[s[0]] << 2 | basis[s[1]] >> 4); |
1093 *d++ = (u_char) (basis64[s[1]] << 4 | basis64[s[2]] >> 2); | 1176 *d++ = (u_char) (basis[s[1]] << 4 | basis[s[2]] >> 2); |
1094 *d++ = (u_char) (basis64[s[2]] << 6 | basis64[s[3]]); | 1177 *d++ = (u_char) (basis[s[2]] << 6 | basis[s[3]]); |
1095 | 1178 |
1096 s += 4; | 1179 s += 4; |
1097 len -= 4; | 1180 len -= 4; |
1098 } | 1181 } |
1099 | 1182 |
1100 if (len > 1) { | 1183 if (len > 1) { |
1101 *d++ = (u_char) (basis64[s[0]] << 2 | basis64[s[1]] >> 4); | 1184 *d++ = (u_char) (basis[s[0]] << 2 | basis[s[1]] >> 4); |
1102 } | 1185 } |
1103 | 1186 |
1104 if (len > 2) { | 1187 if (len > 2) { |
1105 *d++ = (u_char) (basis64[s[1]] << 4 | basis64[s[2]] >> 2); | 1188 *d++ = (u_char) (basis[s[1]] << 4 | basis[s[2]] >> 2); |
1106 } | 1189 } |
1107 | 1190 |
1108 dst->len = d - dst->data; | 1191 dst->len = d - dst->data; |
1109 | 1192 |
1110 return NGX_OK; | 1193 return NGX_OK; |
1236 if (ngx_utf8_decode(&next, len) > 0x10ffff) { | 1319 if (ngx_utf8_decode(&next, len) > 0x10ffff) { |
1237 /* invalid UTF-8 */ | 1320 /* invalid UTF-8 */ |
1238 break; | 1321 break; |
1239 } | 1322 } |
1240 | 1323 |
1241 len--; | |
1242 | |
1243 while (src < next) { | 1324 while (src < next) { |
1244 *++dst = *++src; | 1325 *dst++ = *src++; |
1245 len--; | 1326 len--; |
1246 } | 1327 } |
1247 } | 1328 } |
1248 | 1329 |
1249 *dst = '\0'; | 1330 *dst = '\0'; |
1253 | 1334 |
1254 | 1335 |
1255 uintptr_t | 1336 uintptr_t |
1256 ngx_escape_uri(u_char *dst, u_char *src, size_t size, ngx_uint_t type) | 1337 ngx_escape_uri(u_char *dst, u_char *src, size_t size, ngx_uint_t type) |
1257 { | 1338 { |
1258 ngx_uint_t i, n; | 1339 ngx_uint_t n; |
1259 uint32_t *escape; | 1340 uint32_t *escape; |
1260 static u_char hex[] = "0123456789abcdef"; | 1341 static u_char hex[] = "0123456789abcdef"; |
1261 | 1342 |
1262 /* " ", "#", "%", "?", %00-%1F, %7F-%FF */ | 1343 /* " ", "#", "%", "?", %00-%1F, %7F-%FF */ |
1263 | 1344 |
1277 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ | 1358 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ |
1278 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ | 1359 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ |
1279 0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */ | 1360 0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */ |
1280 }; | 1361 }; |
1281 | 1362 |
1282 /* " ", "#", "%", "+", "?", %00-%1F, %7F-%FF */ | 1363 /* " ", "#", "%", "&", "+", "?", %00-%1F, %7F-%FF */ |
1283 | 1364 |
1284 static uint32_t args[] = { | 1365 static uint32_t args[] = { |
1285 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ | 1366 0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */ |
1286 | 1367 |
1287 /* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */ | 1368 /* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */ |
1288 0x80000829, /* 1000 0000 0000 0000 0000 1000 0010 1001 */ | 1369 0x88000869, /* 1000 1000 0000 0000 0000 1000 0110 1001 */ |
1289 | 1370 |
1290 /* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */ | 1371 /* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */ |
1291 0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */ | 1372 0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */ |
1292 | 1373 |
1293 /* ~}| {zyx wvut srqp onml kjih gfed cba` */ | 1374 /* ~}| {zyx wvut srqp onml kjih gfed cba` */ |
1371 | 1452 |
1372 /* find the number of the characters to be escaped */ | 1453 /* find the number of the characters to be escaped */ |
1373 | 1454 |
1374 n = 0; | 1455 n = 0; |
1375 | 1456 |
1376 for (i = 0; i < size; i++) { | 1457 while (size) { |
1377 if (escape[*src >> 5] & (1 << (*src & 0x1f))) { | 1458 if (escape[*src >> 5] & (1 << (*src & 0x1f))) { |
1378 n++; | 1459 n++; |
1379 } | 1460 } |
1380 src++; | 1461 src++; |
1462 size--; | |
1381 } | 1463 } |
1382 | 1464 |
1383 return (uintptr_t) n; | 1465 return (uintptr_t) n; |
1384 } | 1466 } |
1385 | 1467 |
1386 for (i = 0; i < size; i++) { | 1468 while (size) { |
1387 if (escape[*src >> 5] & (1 << (*src & 0x1f))) { | 1469 if (escape[*src >> 5] & (1 << (*src & 0x1f))) { |
1388 *dst++ = '%'; | 1470 *dst++ = '%'; |
1389 *dst++ = hex[*src >> 4]; | 1471 *dst++ = hex[*src >> 4]; |
1390 *dst++ = hex[*src & 0xf]; | 1472 *dst++ = hex[*src & 0xf]; |
1391 src++; | 1473 src++; |
1392 | 1474 |
1393 } else { | 1475 } else { |
1394 *dst++ = *src++; | 1476 *dst++ = *src++; |
1395 } | 1477 } |
1478 size--; | |
1396 } | 1479 } |
1397 | 1480 |
1398 return (uintptr_t) dst; | 1481 return (uintptr_t) dst; |
1399 } | 1482 } |
1400 | 1483 |
1531 | 1614 |
1532 uintptr_t | 1615 uintptr_t |
1533 ngx_escape_html(u_char *dst, u_char *src, size_t size) | 1616 ngx_escape_html(u_char *dst, u_char *src, size_t size) |
1534 { | 1617 { |
1535 u_char ch; | 1618 u_char ch; |
1536 ngx_uint_t i, len; | 1619 ngx_uint_t len; |
1537 | 1620 |
1538 if (dst == NULL) { | 1621 if (dst == NULL) { |
1539 | 1622 |
1540 len = 0; | 1623 len = 0; |
1541 | 1624 |
1542 for (i = 0; i < size; i++) { | 1625 while (size) { |
1543 switch (*src++) { | 1626 switch (*src++) { |
1544 | 1627 |
1545 case '<': | 1628 case '<': |
1546 len += sizeof("<") - 2; | 1629 len += sizeof("<") - 2; |
1547 break; | 1630 break; |
1555 break; | 1638 break; |
1556 | 1639 |
1557 default: | 1640 default: |
1558 break; | 1641 break; |
1559 } | 1642 } |
1643 size--; | |
1560 } | 1644 } |
1561 | 1645 |
1562 return (uintptr_t) len; | 1646 return (uintptr_t) len; |
1563 } | 1647 } |
1564 | 1648 |
1565 for (i = 0; i < size; i++) { | 1649 while (size) { |
1566 ch = *src++; | 1650 ch = *src++; |
1567 | 1651 |
1568 switch (ch) { | 1652 switch (ch) { |
1569 | 1653 |
1570 case '<': | 1654 case '<': |
1582 | 1666 |
1583 default: | 1667 default: |
1584 *dst++ = ch; | 1668 *dst++ = ch; |
1585 break; | 1669 break; |
1586 } | 1670 } |
1671 size--; | |
1587 } | 1672 } |
1588 | 1673 |
1589 return (uintptr_t) dst; | 1674 return (uintptr_t) dst; |
1675 } | |
1676 | |
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; | |
1590 } | 1758 } |
1591 | 1759 |
1592 | 1760 |
1593 /* 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 */ |
1594 | 1762 |