Groonga 3.0.9 Source Code Document
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
ngx_string.c
Go to the documentation of this file.
1 
2 /*
3  * Copyright (C) Igor Sysoev
4  * Copyright (C) Nginx, Inc.
5  */
6 
7 
8 #include <ngx_config.h>
9 #include <ngx_core.h>
10 
11 
12 static u_char *ngx_sprintf_num(u_char *buf, u_char *last, uint64_t ui64,
13  u_char zero, ngx_uint_t hexadecimal, ngx_uint_t width);
14 static ngx_int_t ngx_decode_base64_internal(ngx_str_t *dst, ngx_str_t *src,
15  const u_char *basis);
16 
17 
18 void
19 ngx_strlow(u_char *dst, u_char *src, size_t n)
20 {
21  while (n) {
22  *dst = ngx_tolower(*src);
23  dst++;
24  src++;
25  n--;
26  }
27 }
28 
29 
30 u_char *
31 ngx_cpystrn(u_char *dst, u_char *src, size_t n)
32 {
33  if (n == 0) {
34  return dst;
35  }
36 
37  while (--n) {
38  *dst = *src;
39 
40  if (*dst == '\0') {
41  return dst;
42  }
43 
44  dst++;
45  src++;
46  }
47 
48  *dst = '\0';
49 
50  return dst;
51 }
52 
53 
54 u_char *
55 ngx_pstrdup(ngx_pool_t *pool, ngx_str_t *src)
56 {
57  u_char *dst;
58 
59  dst = ngx_pnalloc(pool, src->len);
60  if (dst == NULL) {
61  return NULL;
62  }
63 
64  ngx_memcpy(dst, src->data, src->len);
65 
66  return dst;
67 }
68 
69 
70 /*
71  * supported formats:
72  * %[0][width][x][X]O off_t
73  * %[0][width]T time_t
74  * %[0][width][u][x|X]z ssize_t/size_t
75  * %[0][width][u][x|X]d int/u_int
76  * %[0][width][u][x|X]l long
77  * %[0][width|m][u][x|X]i ngx_int_t/ngx_uint_t
78  * %[0][width][u][x|X]D int32_t/uint32_t
79  * %[0][width][u][x|X]L int64_t/uint64_t
80  * %[0][width|m][u][x|X]A ngx_atomic_int_t/ngx_atomic_uint_t
81  * %[0][width][.width]f double, max valid number fits to %18.15f
82  * %P ngx_pid_t
83  * %M ngx_msec_t
84  * %r rlim_t
85  * %p void *
86  * %V ngx_str_t *
87  * %v ngx_variable_value_t *
88  * %s null-terminated string
89  * %*s length and string
90  * %Z '\0'
91  * %N '\n'
92  * %c char
93  * %% %
94  *
95  * reserved:
96  * %t ptrdiff_t
97  * %S null-terminated wchar string
98  * %C wchar
99  */
100 
101 
102 u_char * ngx_cdecl
103 ngx_sprintf(u_char *buf, const char *fmt, ...)
104 {
105  u_char *p;
106  va_list args;
107 
108  va_start(args, fmt);
109  p = ngx_vslprintf(buf, (void *) -1, fmt, args);
110  va_end(args);
111 
112  return p;
113 }
114 
115 
116 u_char * ngx_cdecl
117 ngx_snprintf(u_char *buf, size_t max, const char *fmt, ...)
118 {
119  u_char *p;
120  va_list args;
121 
122  va_start(args, fmt);
123  p = ngx_vslprintf(buf, buf + max, fmt, args);
124  va_end(args);
125 
126  return p;
127 }
128 
129 
130 u_char * ngx_cdecl
131 ngx_slprintf(u_char *buf, u_char *last, const char *fmt, ...)
132 {
133  u_char *p;
134  va_list args;
135 
136  va_start(args, fmt);
137  p = ngx_vslprintf(buf, last, fmt, args);
138  va_end(args);
139 
140  return p;
141 }
142 
143 
144 u_char *
145 ngx_vslprintf(u_char *buf, u_char *last, const char *fmt, va_list args)
146 {
147  u_char *p, zero;
148  int d;
149  double f;
150  size_t len, slen;
151  int64_t i64;
152  uint64_t ui64, frac;
153  ngx_msec_t ms;
154  ngx_uint_t width, sign, hex, max_width, frac_width, scale, n;
155  ngx_str_t *v;
156  ngx_variable_value_t *vv;
157 
158  while (*fmt && buf < last) {
159 
160  /*
161  * "buf < last" means that we could copy at least one character:
162  * the plain character, "%%", "%c", and minus without the checking
163  */
164 
165  if (*fmt == '%') {
166 
167  i64 = 0;
168  ui64 = 0;
169 
170  zero = (u_char) ((*++fmt == '0') ? '0' : ' ');
171  width = 0;
172  sign = 1;
173  hex = 0;
174  max_width = 0;
175  frac_width = 0;
176  slen = (size_t) -1;
177 
178  while (*fmt >= '0' && *fmt <= '9') {
179  width = width * 10 + *fmt++ - '0';
180  }
181 
182 
183  for ( ;; ) {
184  switch (*fmt) {
185 
186  case 'u':
187  sign = 0;
188  fmt++;
189  continue;
190 
191  case 'm':
192  max_width = 1;
193  fmt++;
194  continue;
195 
196  case 'X':
197  hex = 2;
198  sign = 0;
199  fmt++;
200  continue;
201 
202  case 'x':
203  hex = 1;
204  sign = 0;
205  fmt++;
206  continue;
207 
208  case '.':
209  fmt++;
210 
211  while (*fmt >= '0' && *fmt <= '9') {
212  frac_width = frac_width * 10 + *fmt++ - '0';
213  }
214 
215  break;
216 
217  case '*':
218  slen = va_arg(args, size_t);
219  fmt++;
220  continue;
221 
222  default:
223  break;
224  }
225 
226  break;
227  }
228 
229 
230  switch (*fmt) {
231 
232  case 'V':
233  v = va_arg(args, ngx_str_t *);
234 
235  len = ngx_min(((size_t) (last - buf)), v->len);
236  buf = ngx_cpymem(buf, v->data, len);
237  fmt++;
238 
239  continue;
240 
241  case 'v':
242  vv = va_arg(args, ngx_variable_value_t *);
243 
244  len = ngx_min(((size_t) (last - buf)), vv->len);
245  buf = ngx_cpymem(buf, vv->data, len);
246  fmt++;
247 
248  continue;
249 
250  case 's':
251  p = va_arg(args, u_char *);
252 
253  if (slen == (size_t) -1) {
254  while (*p && buf < last) {
255  *buf++ = *p++;
256  }
257 
258  } else {
259  len = ngx_min(((size_t) (last - buf)), slen);
260  buf = ngx_cpymem(buf, p, len);
261  }
262 
263  fmt++;
264 
265  continue;
266 
267  case 'O':
268  i64 = (int64_t) va_arg(args, off_t);
269  sign = 1;
270  break;
271 
272  case 'P':
273  i64 = (int64_t) va_arg(args, ngx_pid_t);
274  sign = 1;
275  break;
276 
277  case 'T':
278  i64 = (int64_t) va_arg(args, time_t);
279  sign = 1;
280  break;
281 
282  case 'M':
283  ms = (ngx_msec_t) va_arg(args, ngx_msec_t);
284  if ((ngx_msec_int_t) ms == -1) {
285  sign = 1;
286  i64 = -1;
287  } else {
288  sign = 0;
289  ui64 = (uint64_t) ms;
290  }
291  break;
292 
293  case 'z':
294  if (sign) {
295  i64 = (int64_t) va_arg(args, ssize_t);
296  } else {
297  ui64 = (uint64_t) va_arg(args, size_t);
298  }
299  break;
300 
301  case 'i':
302  if (sign) {
303  i64 = (int64_t) va_arg(args, ngx_int_t);
304  } else {
305  ui64 = (uint64_t) va_arg(args, ngx_uint_t);
306  }
307 
308  if (max_width) {
309  width = NGX_INT_T_LEN;
310  }
311 
312  break;
313 
314  case 'd':
315  if (sign) {
316  i64 = (int64_t) va_arg(args, int);
317  } else {
318  ui64 = (uint64_t) va_arg(args, u_int);
319  }
320  break;
321 
322  case 'l':
323  if (sign) {
324  i64 = (int64_t) va_arg(args, long);
325  } else {
326  ui64 = (uint64_t) va_arg(args, u_long);
327  }
328  break;
329 
330  case 'D':
331  if (sign) {
332  i64 = (int64_t) va_arg(args, int32_t);
333  } else {
334  ui64 = (uint64_t) va_arg(args, uint32_t);
335  }
336  break;
337 
338  case 'L':
339  if (sign) {
340  i64 = va_arg(args, int64_t);
341  } else {
342  ui64 = va_arg(args, uint64_t);
343  }
344  break;
345 
346  case 'A':
347  if (sign) {
348  i64 = (int64_t) va_arg(args, ngx_atomic_int_t);
349  } else {
350  ui64 = (uint64_t) va_arg(args, ngx_atomic_uint_t);
351  }
352 
353  if (max_width) {
354  width = NGX_ATOMIC_T_LEN;
355  }
356 
357  break;
358 
359  case 'f':
360  f = va_arg(args, double);
361 
362  if (f < 0) {
363  *buf++ = '-';
364  f = -f;
365  }
366 
367  ui64 = (int64_t) f;
368  frac = 0;
369 
370  if (frac_width) {
371 
372  scale = 1;
373  for (n = frac_width; n; n--) {
374  scale *= 10;
375  }
376 
377  frac = (uint64_t) ((f - (double) ui64) * scale + 0.5);
378 
379  if (frac == scale) {
380  ui64++;
381  frac = 0;
382  }
383  }
384 
385  buf = ngx_sprintf_num(buf, last, ui64, zero, 0, width);
386 
387  if (frac_width) {
388  if (buf < last) {
389  *buf++ = '.';
390  }
391 
392  buf = ngx_sprintf_num(buf, last, frac, '0', 0, frac_width);
393  }
394 
395  fmt++;
396 
397  continue;
398 
399 #if !(NGX_WIN32)
400  case 'r':
401  i64 = (int64_t) va_arg(args, rlim_t);
402  sign = 1;
403  break;
404 #endif
405 
406  case 'p':
407  ui64 = (uintptr_t) va_arg(args, void *);
408  hex = 2;
409  sign = 0;
410  zero = '0';
411  width = NGX_PTR_SIZE * 2;
412  break;
413 
414  case 'c':
415  d = va_arg(args, int);
416  *buf++ = (u_char) (d & 0xff);
417  fmt++;
418 
419  continue;
420 
421  case 'Z':
422  *buf++ = '\0';
423  fmt++;
424 
425  continue;
426 
427  case 'N':
428 #if (NGX_WIN32)
429  *buf++ = CR;
430 #endif
431  *buf++ = LF;
432  fmt++;
433 
434  continue;
435 
436  case '%':
437  *buf++ = '%';
438  fmt++;
439 
440  continue;
441 
442  default:
443  *buf++ = *fmt++;
444 
445  continue;
446  }
447 
448  if (sign) {
449  if (i64 < 0) {
450  *buf++ = '-';
451  ui64 = (uint64_t) -i64;
452 
453  } else {
454  ui64 = (uint64_t) i64;
455  }
456  }
457 
458  buf = ngx_sprintf_num(buf, last, ui64, zero, hex, width);
459 
460  fmt++;
461 
462  } else {
463  *buf++ = *fmt++;
464  }
465  }
466 
467  return buf;
468 }
469 
470 
471 static u_char *
472 ngx_sprintf_num(u_char *buf, u_char *last, uint64_t ui64, u_char zero,
473  ngx_uint_t hexadecimal, ngx_uint_t width)
474 {
475  u_char *p, temp[NGX_INT64_LEN + 1];
476  /*
477  * we need temp[NGX_INT64_LEN] only,
478  * but icc issues the warning
479  */
480  size_t len;
481  uint32_t ui32;
482  static u_char hex[] = "0123456789abcdef";
483  static u_char HEX[] = "0123456789ABCDEF";
484 
485  p = temp + NGX_INT64_LEN;
486 
487  if (hexadecimal == 0) {
488 
489  if (ui64 <= NGX_MAX_UINT32_VALUE) {
490 
491  /*
492  * To divide 64-bit numbers and to find remainders
493  * on the x86 platform gcc and icc call the libc functions
494  * [u]divdi3() and [u]moddi3(), they call another function
495  * in its turn. On FreeBSD it is the qdivrem() function,
496  * its source code is about 170 lines of the code.
497  * The glibc counterpart is about 150 lines of the code.
498  *
499  * For 32-bit numbers and some divisors gcc and icc use
500  * a inlined multiplication and shifts. For example,
501  * unsigned "i32 / 10" is compiled to
502  *
503  * (i32 * 0xCCCCCCCD) >> 35
504  */
505 
506  ui32 = (uint32_t) ui64;
507 
508  do {
509  *--p = (u_char) (ui32 % 10 + '0');
510  } while (ui32 /= 10);
511 
512  } else {
513  do {
514  *--p = (u_char) (ui64 % 10 + '0');
515  } while (ui64 /= 10);
516  }
517 
518  } else if (hexadecimal == 1) {
519 
520  do {
521 
522  /* the "(uint32_t)" cast disables the BCC's warning */
523  *--p = hex[(uint32_t) (ui64 & 0xf)];
524 
525  } while (ui64 >>= 4);
526 
527  } else { /* hexadecimal == 2 */
528 
529  do {
530 
531  /* the "(uint32_t)" cast disables the BCC's warning */
532  *--p = HEX[(uint32_t) (ui64 & 0xf)];
533 
534  } while (ui64 >>= 4);
535  }
536 
537  /* zero or space padding */
538 
539  len = (temp + NGX_INT64_LEN) - p;
540 
541  while (len++ < width && buf < last) {
542  *buf++ = zero;
543  }
544 
545  /* number safe copy */
546 
547  len = (temp + NGX_INT64_LEN) - p;
548 
549  if (buf + len > last) {
550  len = last - buf;
551  }
552 
553  return ngx_cpymem(buf, p, len);
554 }
555 
556 
557 /*
558  * We use ngx_strcasecmp()/ngx_strncasecmp() for 7-bit ASCII strings only,
559  * and implement our own ngx_strcasecmp()/ngx_strncasecmp()
560  * to avoid libc locale overhead. Besides, we use the ngx_uint_t's
561  * instead of the u_char's, because they are slightly faster.
562  */
563 
564 ngx_int_t
565 ngx_strcasecmp(u_char *s1, u_char *s2)
566 {
567  ngx_uint_t c1, c2;
568 
569  for ( ;; ) {
570  c1 = (ngx_uint_t) *s1++;
571  c2 = (ngx_uint_t) *s2++;
572 
573  c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
574  c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
575 
576  if (c1 == c2) {
577 
578  if (c1) {
579  continue;
580  }
581 
582  return 0;
583  }
584 
585  return c1 - c2;
586  }
587 }
588 
589 
590 ngx_int_t
591 ngx_strncasecmp(u_char *s1, u_char *s2, size_t n)
592 {
593  ngx_uint_t c1, c2;
594 
595  while (n) {
596  c1 = (ngx_uint_t) *s1++;
597  c2 = (ngx_uint_t) *s2++;
598 
599  c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
600  c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
601 
602  if (c1 == c2) {
603 
604  if (c1) {
605  n--;
606  continue;
607  }
608 
609  return 0;
610  }
611 
612  return c1 - c2;
613  }
614 
615  return 0;
616 }
617 
618 
619 u_char *
620 ngx_strnstr(u_char *s1, char *s2, size_t len)
621 {
622  u_char c1, c2;
623  size_t n;
624 
625  c2 = *(u_char *) s2++;
626 
627  n = ngx_strlen(s2);
628 
629  do {
630  do {
631  if (len-- == 0) {
632  return NULL;
633  }
634 
635  c1 = *s1++;
636 
637  if (c1 == 0) {
638  return NULL;
639  }
640 
641  } while (c1 != c2);
642 
643  if (n > len) {
644  return NULL;
645  }
646 
647  } while (ngx_strncmp(s1, (u_char *) s2, n) != 0);
648 
649  return --s1;
650 }
651 
652 
653 /*
654  * ngx_strstrn() and ngx_strcasestrn() are intended to search for static
655  * substring with known length in null-terminated string. The argument n
656  * must be length of the second substring - 1.
657  */
658 
659 u_char *
660 ngx_strstrn(u_char *s1, char *s2, size_t n)
661 {
662  u_char c1, c2;
663 
664  c2 = *(u_char *) s2++;
665 
666  do {
667  do {
668  c1 = *s1++;
669 
670  if (c1 == 0) {
671  return NULL;
672  }
673 
674  } while (c1 != c2);
675 
676  } while (ngx_strncmp(s1, (u_char *) s2, n) != 0);
677 
678  return --s1;
679 }
680 
681 
682 u_char *
683 ngx_strcasestrn(u_char *s1, char *s2, size_t n)
684 {
685  ngx_uint_t c1, c2;
686 
687  c2 = (ngx_uint_t) *s2++;
688  c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
689 
690  do {
691  do {
692  c1 = (ngx_uint_t) *s1++;
693 
694  if (c1 == 0) {
695  return NULL;
696  }
697 
698  c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
699 
700  } while (c1 != c2);
701 
702  } while (ngx_strncasecmp(s1, (u_char *) s2, n) != 0);
703 
704  return --s1;
705 }
706 
707 
708 /*
709  * ngx_strlcasestrn() is intended to search for static substring
710  * with known length in string until the argument last. The argument n
711  * must be length of the second substring - 1.
712  */
713 
714 u_char *
715 ngx_strlcasestrn(u_char *s1, u_char *last, u_char *s2, size_t n)
716 {
717  ngx_uint_t c1, c2;
718 
719  c2 = (ngx_uint_t) *s2++;
720  c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
721  last -= n;
722 
723  do {
724  do {
725  if (s1 >= last) {
726  return NULL;
727  }
728 
729  c1 = (ngx_uint_t) *s1++;
730 
731  c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
732 
733  } while (c1 != c2);
734 
735  } while (ngx_strncasecmp(s1, s2, n) != 0);
736 
737  return --s1;
738 }
739 
740 
741 ngx_int_t
742 ngx_rstrncmp(u_char *s1, u_char *s2, size_t n)
743 {
744  if (n == 0) {
745  return 0;
746  }
747 
748  n--;
749 
750  for ( ;; ) {
751  if (s1[n] != s2[n]) {
752  return s1[n] - s2[n];
753  }
754 
755  if (n == 0) {
756  return 0;
757  }
758 
759  n--;
760  }
761 }
762 
763 
764 ngx_int_t
765 ngx_rstrncasecmp(u_char *s1, u_char *s2, size_t n)
766 {
767  u_char c1, c2;
768 
769  if (n == 0) {
770  return 0;
771  }
772 
773  n--;
774 
775  for ( ;; ) {
776  c1 = s1[n];
777  if (c1 >= 'a' && c1 <= 'z') {
778  c1 -= 'a' - 'A';
779  }
780 
781  c2 = s2[n];
782  if (c2 >= 'a' && c2 <= 'z') {
783  c2 -= 'a' - 'A';
784  }
785 
786  if (c1 != c2) {
787  return c1 - c2;
788  }
789 
790  if (n == 0) {
791  return 0;
792  }
793 
794  n--;
795  }
796 }
797 
798 
799 ngx_int_t
800 ngx_memn2cmp(u_char *s1, u_char *s2, size_t n1, size_t n2)
801 {
802  size_t n;
803  ngx_int_t m, z;
804 
805  if (n1 <= n2) {
806  n = n1;
807  z = -1;
808 
809  } else {
810  n = n2;
811  z = 1;
812  }
813 
814  m = ngx_memcmp(s1, s2, n);
815 
816  if (m || n1 == n2) {
817  return m;
818  }
819 
820  return z;
821 }
822 
823 
824 ngx_int_t
825 ngx_dns_strcmp(u_char *s1, u_char *s2)
826 {
827  ngx_uint_t c1, c2;
828 
829  for ( ;; ) {
830  c1 = (ngx_uint_t) *s1++;
831  c2 = (ngx_uint_t) *s2++;
832 
833  c1 = (c1 >= 'A' && c1 <= 'Z') ? (c1 | 0x20) : c1;
834  c2 = (c2 >= 'A' && c2 <= 'Z') ? (c2 | 0x20) : c2;
835 
836  if (c1 == c2) {
837 
838  if (c1) {
839  continue;
840  }
841 
842  return 0;
843  }
844 
845  /* in ASCII '.' > '-', but we need '.' to be the lowest character */
846 
847  c1 = (c1 == '.') ? ' ' : c1;
848  c2 = (c2 == '.') ? ' ' : c2;
849 
850  return c1 - c2;
851  }
852 }
853 
854 
855 ngx_int_t
856 ngx_atoi(u_char *line, size_t n)
857 {
858  ngx_int_t value;
859 
860  if (n == 0) {
861  return NGX_ERROR;
862  }
863 
864  for (value = 0; n--; line++) {
865  if (*line < '0' || *line > '9') {
866  return NGX_ERROR;
867  }
868 
869  value = value * 10 + (*line - '0');
870  }
871 
872  if (value < 0) {
873  return NGX_ERROR;
874 
875  } else {
876  return value;
877  }
878 }
879 
880 
881 /* parse a fixed point number, e.g., ngx_atofp("10.5", 4, 2) returns 1050 */
882 
883 ngx_int_t
884 ngx_atofp(u_char *line, size_t n, size_t point)
885 {
886  ngx_int_t value;
887  ngx_uint_t dot;
888 
889  if (n == 0) {
890  return NGX_ERROR;
891  }
892 
893  dot = 0;
894 
895  for (value = 0; n--; line++) {
896 
897  if (point == 0) {
898  return NGX_ERROR;
899  }
900 
901  if (*line == '.') {
902  if (dot) {
903  return NGX_ERROR;
904  }
905 
906  dot = 1;
907  continue;
908  }
909 
910  if (*line < '0' || *line > '9') {
911  return NGX_ERROR;
912  }
913 
914  value = value * 10 + (*line - '0');
915  point -= dot;
916  }
917 
918  while (point--) {
919  value = value * 10;
920  }
921 
922  if (value < 0) {
923  return NGX_ERROR;
924 
925  } else {
926  return value;
927  }
928 }
929 
930 
931 ssize_t
932 ngx_atosz(u_char *line, size_t n)
933 {
934  ssize_t value;
935 
936  if (n == 0) {
937  return NGX_ERROR;
938  }
939 
940  for (value = 0; n--; line++) {
941  if (*line < '0' || *line > '9') {
942  return NGX_ERROR;
943  }
944 
945  value = value * 10 + (*line - '0');
946  }
947 
948  if (value < 0) {
949  return NGX_ERROR;
950 
951  } else {
952  return value;
953  }
954 }
955 
956 
957 off_t
958 ngx_atoof(u_char *line, size_t n)
959 {
960  off_t value;
961 
962  if (n == 0) {
963  return NGX_ERROR;
964  }
965 
966  for (value = 0; n--; line++) {
967  if (*line < '0' || *line > '9') {
968  return NGX_ERROR;
969  }
970 
971  value = value * 10 + (*line - '0');
972  }
973 
974  if (value < 0) {
975  return NGX_ERROR;
976 
977  } else {
978  return value;
979  }
980 }
981 
982 
983 time_t
984 ngx_atotm(u_char *line, size_t n)
985 {
986  time_t value;
987 
988  if (n == 0) {
989  return NGX_ERROR;
990  }
991 
992  for (value = 0; n--; line++) {
993  if (*line < '0' || *line > '9') {
994  return NGX_ERROR;
995  }
996 
997  value = value * 10 + (*line - '0');
998  }
999 
1000  if (value < 0) {
1001  return NGX_ERROR;
1002 
1003  } else {
1004  return value;
1005  }
1006 }
1007 
1008 
1009 ngx_int_t
1010 ngx_hextoi(u_char *line, size_t n)
1011 {
1012  u_char c, ch;
1013  ngx_int_t value;
1014 
1015  if (n == 0) {
1016  return NGX_ERROR;
1017  }
1018 
1019  for (value = 0; n--; line++) {
1020  ch = *line;
1021 
1022  if (ch >= '0' && ch <= '9') {
1023  value = value * 16 + (ch - '0');
1024  continue;
1025  }
1026 
1027  c = (u_char) (ch | 0x20);
1028 
1029  if (c >= 'a' && c <= 'f') {
1030  value = value * 16 + (c - 'a' + 10);
1031  continue;
1032  }
1033 
1034  return NGX_ERROR;
1035  }
1036 
1037  if (value < 0) {
1038  return NGX_ERROR;
1039 
1040  } else {
1041  return value;
1042  }
1043 }
1044 
1045 
1046 u_char *
1047 ngx_hex_dump(u_char *dst, u_char *src, size_t len)
1048 {
1049  static u_char hex[] = "0123456789abcdef";
1050 
1051  while (len--) {
1052  *dst++ = hex[*src >> 4];
1053  *dst++ = hex[*src++ & 0xf];
1054  }
1055 
1056  return dst;
1057 }
1058 
1059 
1060 void
1061 ngx_encode_base64(ngx_str_t *dst, ngx_str_t *src)
1062 {
1063  u_char *d, *s;
1064  size_t len;
1065  static u_char basis64[] =
1066  "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
1067 
1068  len = src->len;
1069  s = src->data;
1070  d = dst->data;
1071 
1072  while (len > 2) {
1073  *d++ = basis64[(s[0] >> 2) & 0x3f];
1074  *d++ = basis64[((s[0] & 3) << 4) | (s[1] >> 4)];
1075  *d++ = basis64[((s[1] & 0x0f) << 2) | (s[2] >> 6)];
1076  *d++ = basis64[s[2] & 0x3f];
1077 
1078  s += 3;
1079  len -= 3;
1080  }
1081 
1082  if (len) {
1083  *d++ = basis64[(s[0] >> 2) & 0x3f];
1084 
1085  if (len == 1) {
1086  *d++ = basis64[(s[0] & 3) << 4];
1087  *d++ = '=';
1088 
1089  } else {
1090  *d++ = basis64[((s[0] & 3) << 4) | (s[1] >> 4)];
1091  *d++ = basis64[(s[1] & 0x0f) << 2];
1092  }
1093 
1094  *d++ = '=';
1095  }
1096 
1097  dst->len = d - dst->data;
1098 }
1099 
1100 
1101 ngx_int_t
1102 ngx_decode_base64(ngx_str_t *dst, ngx_str_t *src)
1103 {
1104  static u_char basis64[] = {
1105  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1106  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1107  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 62, 77, 77, 77, 63,
1108  52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 77, 77, 77, 77, 77, 77,
1109  77, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
1110  15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 77, 77, 77, 77, 77,
1111  77, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
1112  41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 77, 77, 77, 77, 77,
1113 
1114  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,
1116  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,
1118  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1119  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1120  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1121  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77
1122  };
1123 
1124  return ngx_decode_base64_internal(dst, src, basis64);
1125 }
1126 
1127 
1128 ngx_int_t
1129 ngx_decode_base64url(ngx_str_t *dst, ngx_str_t *src)
1130 {
1131  static u_char basis64[] = {
1132  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1133  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1134  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 62, 77, 77,
1135  52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 77, 77, 77, 77, 77, 77,
1136  77, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,
1137  15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 77, 77, 77, 77, 63,
1138  77, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
1139  41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 77, 77, 77, 77, 77,
1140 
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  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1146  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1147  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77,
1148  77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77, 77
1149  };
1150 
1151  return ngx_decode_base64_internal(dst, src, basis64);
1152 }
1153 
1154 
1155 static ngx_int_t
1156 ngx_decode_base64_internal(ngx_str_t *dst, ngx_str_t *src, const u_char *basis)
1157 {
1158  size_t len;
1159  u_char *d, *s;
1160 
1161  for (len = 0; len < src->len; len++) {
1162  if (src->data[len] == '=') {
1163  break;
1164  }
1165 
1166  if (basis[src->data[len]] == 77) {
1167  return NGX_ERROR;
1168  }
1169  }
1170 
1171  if (len % 4 == 1) {
1172  return NGX_ERROR;
1173  }
1174 
1175  s = src->data;
1176  d = dst->data;
1177 
1178  while (len > 3) {
1179  *d++ = (u_char) (basis[s[0]] << 2 | basis[s[1]] >> 4);
1180  *d++ = (u_char) (basis[s[1]] << 4 | basis[s[2]] >> 2);
1181  *d++ = (u_char) (basis[s[2]] << 6 | basis[s[3]]);
1182 
1183  s += 4;
1184  len -= 4;
1185  }
1186 
1187  if (len > 1) {
1188  *d++ = (u_char) (basis[s[0]] << 2 | basis[s[1]] >> 4);
1189  }
1190 
1191  if (len > 2) {
1192  *d++ = (u_char) (basis[s[1]] << 4 | basis[s[2]] >> 2);
1193  }
1194 
1195  dst->len = d - dst->data;
1196 
1197  return NGX_OK;
1198 }
1199 
1200 
1201 /*
1202  * ngx_utf8_decode() decodes two and more bytes UTF sequences only
1203  * the return values:
1204  * 0x80 - 0x10ffff valid character
1205  * 0x110000 - 0xfffffffd invalid sequence
1206  * 0xfffffffe incomplete sequence
1207  * 0xffffffff error
1208  */
1209 
1210 uint32_t
1211 ngx_utf8_decode(u_char **p, size_t n)
1212 {
1213  size_t len;
1214  uint32_t u, i, valid;
1215 
1216  u = **p;
1217 
1218  if (u >= 0xf0) {
1219 
1220  u &= 0x07;
1221  valid = 0xffff;
1222  len = 3;
1223 
1224  } else if (u >= 0xe0) {
1225 
1226  u &= 0x0f;
1227  valid = 0x7ff;
1228  len = 2;
1229 
1230  } else if (u >= 0xc2) {
1231 
1232  u &= 0x1f;
1233  valid = 0x7f;
1234  len = 1;
1235 
1236  } else {
1237  (*p)++;
1238  return 0xffffffff;
1239  }
1240 
1241  if (n - 1 < len) {
1242  return 0xfffffffe;
1243  }
1244 
1245  (*p)++;
1246 
1247  while (len) {
1248  i = *(*p)++;
1249 
1250  if (i < 0x80) {
1251  return 0xffffffff;
1252  }
1253 
1254  u = (u << 6) | (i & 0x3f);
1255 
1256  len--;
1257  }
1258 
1259  if (u > valid) {
1260  return u;
1261  }
1262 
1263  return 0xffffffff;
1264 }
1265 
1266 
1267 size_t
1268 ngx_utf8_length(u_char *p, size_t n)
1269 {
1270  u_char c, *last;
1271  size_t len;
1272 
1273  last = p + n;
1274 
1275  for (len = 0; p < last; len++) {
1276 
1277  c = *p;
1278 
1279  if (c < 0x80) {
1280  p++;
1281  continue;
1282  }
1283 
1284  if (ngx_utf8_decode(&p, n) > 0x10ffff) {
1285  /* invalid UTF-8 */
1286  return n;
1287  }
1288  }
1289 
1290  return len;
1291 }
1292 
1293 
1294 u_char *
1295 ngx_utf8_cpystrn(u_char *dst, u_char *src, size_t n, size_t len)
1296 {
1297  u_char c, *next;
1298 
1299  if (n == 0) {
1300  return dst;
1301  }
1302 
1303  while (--n) {
1304 
1305  c = *src;
1306  *dst = c;
1307 
1308  if (c < 0x80) {
1309 
1310  if (c != '\0') {
1311  dst++;
1312  src++;
1313  len--;
1314 
1315  continue;
1316  }
1317 
1318  return dst;
1319  }
1320 
1321  next = src;
1322 
1323  if (ngx_utf8_decode(&next, len) > 0x10ffff) {
1324  /* invalid UTF-8 */
1325  break;
1326  }
1327 
1328  while (src < next) {
1329  *dst++ = *src++;
1330  len--;
1331  }
1332  }
1333 
1334  *dst = '\0';
1335 
1336  return dst;
1337 }
1338 
1339 
1340 uintptr_t
1341 ngx_escape_uri(u_char *dst, u_char *src, size_t size, ngx_uint_t type)
1342 {
1343  ngx_uint_t n;
1344  uint32_t *escape;
1345  static u_char hex[] = "0123456789abcdef";
1346 
1347  /* " ", "#", "%", "?", %00-%1F, %7F-%FF */
1348 
1349  static uint32_t uri[] = {
1350  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1351 
1352  /* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */
1353  0x80000029, /* 1000 0000 0000 0000 0000 0000 0010 1001 */
1354 
1355  /* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */
1356  0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1357 
1358  /* ~}| {zyx wvut srqp onml kjih gfed cba` */
1359  0x80000000, /* 1000 0000 0000 0000 0000 0000 0000 0000 */
1360 
1361  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1362  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1363  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1364  0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1365  };
1366 
1367  /* " ", "#", "%", "&", "+", "?", %00-%1F, %7F-%FF */
1368 
1369  static uint32_t args[] = {
1370  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1371 
1372  /* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */
1373  0x88000869, /* 1000 1000 0000 0000 0000 1000 0110 1001 */
1374 
1375  /* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */
1376  0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1377 
1378  /* ~}| {zyx wvut srqp onml kjih gfed cba` */
1379  0x80000000, /* 1000 0000 0000 0000 0000 0000 0000 0000 */
1380 
1381  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1382  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1383  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1384  0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1385  };
1386 
1387  /* not ALPHA, DIGIT, "-", ".", "_", "~" */
1388 
1389  static uint32_t uri_component[] = {
1390  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1391 
1392  /* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */
1393  0xfc009fff, /* 1111 1100 0000 0000 1001 1111 1111 1111 */
1394 
1395  /* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */
1396  0x78000001, /* 0111 1000 0000 0000 0000 0000 0000 0001 */
1397 
1398  /* ~}| {zyx wvut srqp onml kjih gfed cba` */
1399  0xb8000001, /* 1011 1000 0000 0000 0000 0000 0000 0001 */
1400 
1401  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1402  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1403  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1404  0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1405  };
1406 
1407  /* " ", "#", """, "%", "'", %00-%1F, %7F-%FF */
1408 
1409  static uint32_t html[] = {
1410  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1411 
1412  /* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */
1413  0x000000ad, /* 0000 0000 0000 0000 0000 0000 1010 1101 */
1414 
1415  /* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */
1416  0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1417 
1418  /* ~}| {zyx wvut srqp onml kjih gfed cba` */
1419  0x80000000, /* 1000 0000 0000 0000 0000 0000 0000 0000 */
1420 
1421  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1422  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1423  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1424  0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1425  };
1426 
1427  /* " ", """, "%", "'", %00-%1F, %7F-%FF */
1428 
1429  static uint32_t refresh[] = {
1430  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1431 
1432  /* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */
1433  0x00000085, /* 0000 0000 0000 0000 0000 0000 1000 0101 */
1434 
1435  /* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */
1436  0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1437 
1438  /* ~}| {zyx wvut srqp onml kjih gfed cba` */
1439  0x80000000, /* 1000 0000 0000 0000 0000 0000 0000 0000 */
1440 
1441  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1442  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1443  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1444  0xffffffff /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1445  };
1446 
1447  /* " ", "%", %00-%1F */
1448 
1449  static uint32_t memcached[] = {
1450  0xffffffff, /* 1111 1111 1111 1111 1111 1111 1111 1111 */
1451 
1452  /* ?>=< ;:98 7654 3210 /.-, +*)( '&%$ #"! */
1453  0x00000021, /* 0000 0000 0000 0000 0000 0000 0010 0001 */
1454 
1455  /* _^]\ [ZYX WVUT SRQP ONML KJIH GFED CBA@ */
1456  0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1457 
1458  /* ~}| {zyx wvut srqp onml kjih gfed cba` */
1459  0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1460 
1461  0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1462  0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1463  0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1464  0x00000000, /* 0000 0000 0000 0000 0000 0000 0000 0000 */
1465  };
1466 
1467  /* mail_auth is the same as memcached */
1468 
1469  static uint32_t *map[] =
1470  { uri, args, uri_component, html, refresh, memcached, memcached };
1471 
1472 
1473  escape = map[type];
1474 
1475  if (dst == NULL) {
1476 
1477  /* find the number of the characters to be escaped */
1478 
1479  n = 0;
1480 
1481  while (size) {
1482  if (escape[*src >> 5] & (1 << (*src & 0x1f))) {
1483  n++;
1484  }
1485  src++;
1486  size--;
1487  }
1488 
1489  return (uintptr_t) n;
1490  }
1491 
1492  while (size) {
1493  if (escape[*src >> 5] & (1 << (*src & 0x1f))) {
1494  *dst++ = '%';
1495  *dst++ = hex[*src >> 4];
1496  *dst++ = hex[*src & 0xf];
1497  src++;
1498 
1499  } else {
1500  *dst++ = *src++;
1501  }
1502  size--;
1503  }
1504 
1505  return (uintptr_t) dst;
1506 }
1507 
1508 
1509 void
1510 ngx_unescape_uri(u_char **dst, u_char **src, size_t size, ngx_uint_t type)
1511 {
1512  u_char *d, *s, ch, c, decoded;
1513  enum {
1514  sw_usual = 0,
1515  sw_quoted,
1516  sw_quoted_second
1517  } state;
1518 
1519  d = *dst;
1520  s = *src;
1521 
1522  state = 0;
1523  decoded = 0;
1524 
1525  while (size--) {
1526 
1527  ch = *s++;
1528 
1529  switch (state) {
1530  case sw_usual:
1531  if (ch == '?'
1532  && (type & (NGX_UNESCAPE_URI|NGX_UNESCAPE_REDIRECT)))
1533  {
1534  *d++ = ch;
1535  goto done;
1536  }
1537 
1538  if (ch == '%') {
1539  state = sw_quoted;
1540  break;
1541  }
1542 
1543  *d++ = ch;
1544  break;
1545 
1546  case sw_quoted:
1547 
1548  if (ch >= '0' && ch <= '9') {
1549  decoded = (u_char) (ch - '0');
1550  state = sw_quoted_second;
1551  break;
1552  }
1553 
1554  c = (u_char) (ch | 0x20);
1555  if (c >= 'a' && c <= 'f') {
1556  decoded = (u_char) (c - 'a' + 10);
1557  state = sw_quoted_second;
1558  break;
1559  }
1560 
1561  /* the invalid quoted character */
1562 
1563  state = sw_usual;
1564 
1565  *d++ = ch;
1566 
1567  break;
1568 
1569  case sw_quoted_second:
1570 
1571  state = sw_usual;
1572 
1573  if (ch >= '0' && ch <= '9') {
1574  ch = (u_char) ((decoded << 4) + ch - '0');
1575 
1576  if (type & NGX_UNESCAPE_REDIRECT) {
1577  if (ch > '%' && ch < 0x7f) {
1578  *d++ = ch;
1579  break;
1580  }
1581 
1582  *d++ = '%'; *d++ = *(s - 2); *d++ = *(s - 1);
1583 
1584  break;
1585  }
1586 
1587  *d++ = ch;
1588 
1589  break;
1590  }
1591 
1592  c = (u_char) (ch | 0x20);
1593  if (c >= 'a' && c <= 'f') {
1594  ch = (u_char) ((decoded << 4) + c - 'a' + 10);
1595 
1596  if (type & NGX_UNESCAPE_URI) {
1597  if (ch == '?') {
1598  *d++ = ch;
1599  goto done;
1600  }
1601 
1602  *d++ = ch;
1603  break;
1604  }
1605 
1606  if (type & NGX_UNESCAPE_REDIRECT) {
1607  if (ch == '?') {
1608  *d++ = ch;
1609  goto done;
1610  }
1611 
1612  if (ch > '%' && ch < 0x7f) {
1613  *d++ = ch;
1614  break;
1615  }
1616 
1617  *d++ = '%'; *d++ = *(s - 2); *d++ = *(s - 1);
1618  break;
1619  }
1620 
1621  *d++ = ch;
1622 
1623  break;
1624  }
1625 
1626  /* the invalid quoted character */
1627 
1628  break;
1629  }
1630  }
1631 
1632 done:
1633 
1634  *dst = d;
1635  *src = s;
1636 }
1637 
1638 
1639 uintptr_t
1640 ngx_escape_html(u_char *dst, u_char *src, size_t size)
1641 {
1642  u_char ch;
1643  ngx_uint_t len;
1644 
1645  if (dst == NULL) {
1646 
1647  len = 0;
1648 
1649  while (size) {
1650  switch (*src++) {
1651 
1652  case '<':
1653  len += sizeof("&lt;") - 2;
1654  break;
1655 
1656  case '>':
1657  len += sizeof("&gt;") - 2;
1658  break;
1659 
1660  case '&':
1661  len += sizeof("&amp;") - 2;
1662  break;
1663 
1664  case '"':
1665  len += sizeof("&quot;") - 2;
1666  break;
1667 
1668  default:
1669  break;
1670  }
1671  size--;
1672  }
1673 
1674  return (uintptr_t) len;
1675  }
1676 
1677  while (size) {
1678  ch = *src++;
1679 
1680  switch (ch) {
1681 
1682  case '<':
1683  *dst++ = '&'; *dst++ = 'l'; *dst++ = 't'; *dst++ = ';';
1684  break;
1685 
1686  case '>':
1687  *dst++ = '&'; *dst++ = 'g'; *dst++ = 't'; *dst++ = ';';
1688  break;
1689 
1690  case '&':
1691  *dst++ = '&'; *dst++ = 'a'; *dst++ = 'm'; *dst++ = 'p';
1692  *dst++ = ';';
1693  break;
1694 
1695  case '"':
1696  *dst++ = '&'; *dst++ = 'q'; *dst++ = 'u'; *dst++ = 'o';
1697  *dst++ = 't'; *dst++ = ';';
1698  break;
1699 
1700  default:
1701  *dst++ = ch;
1702  break;
1703  }
1704  size--;
1705  }
1706 
1707  return (uintptr_t) dst;
1708 }
1709 
1710 
1711 void
1712 ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,
1713  ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
1714 {
1715  ngx_str_node_t *n, *t;
1716  ngx_rbtree_node_t **p;
1717 
1718  for ( ;; ) {
1719 
1720  n = (ngx_str_node_t *) node;
1721  t = (ngx_str_node_t *) temp;
1722 
1723  if (node->key != temp->key) {
1724 
1725  p = (node->key < temp->key) ? &temp->left : &temp->right;
1726 
1727  } else if (n->str.len != t->str.len) {
1728 
1729  p = (n->str.len < t->str.len) ? &temp->left : &temp->right;
1730 
1731  } else {
1732  p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 0)
1733  ? &temp->left : &temp->right;
1734  }
1735 
1736  if (*p == sentinel) {
1737  break;
1738  }
1739 
1740  temp = *p;
1741  }
1742 
1743  *p = node;
1744  node->parent = temp;
1745  node->left = sentinel;
1746  node->right = sentinel;
1747  ngx_rbt_red(node);
1748 }
1749 
1750 
1751 ngx_str_node_t *
1752 ngx_str_rbtree_lookup(ngx_rbtree_t *rbtree, ngx_str_t *val, uint32_t hash)
1753 {
1754  ngx_int_t rc;
1755  ngx_str_node_t *n;
1756  ngx_rbtree_node_t *node, *sentinel;
1757 
1758  node = rbtree->root;
1759  sentinel = rbtree->sentinel;
1760 
1761  while (node != sentinel) {
1762 
1763  n = (ngx_str_node_t *) node;
1764 
1765  if (hash != node->key) {
1766  node = (hash < node->key) ? node->left : node->right;
1767  continue;
1768  }
1769 
1770  if (val->len != n->str.len) {
1771  node = (val->len < n->str.len) ? node->left : node->right;
1772  continue;
1773  }
1774 
1775  rc = ngx_memcmp(val->data, n->str.data, val->len);
1776 
1777  if (rc < 0) {
1778  node = node->left;
1779  continue;
1780  }
1781 
1782  if (rc > 0) {
1783  node = node->right;
1784  continue;
1785  }
1786 
1787  return n;
1788  }
1789 
1790  return NULL;
1791 }
1792 
1793 
1794 /* ngx_sort() is implemented as insertion sort because we need stable sort */
1795 
1796 void
1797 ngx_sort(void *base, size_t n, size_t size,
1798  ngx_int_t (*cmp)(const void *, const void *))
1799 {
1800  u_char *p1, *p2, *p;
1801 
1802  p = ngx_alloc(size, ngx_cycle->log);
1803  if (p == NULL) {
1804  return;
1805  }
1806 
1807  for (p1 = (u_char *) base + size;
1808  p1 < (u_char *) base + n * size;
1809  p1 += size)
1810  {
1811  ngx_memcpy(p, p1, size);
1812 
1813  for (p2 = p1;
1814  p2 > (u_char *) base && cmp(p2 - size, p) > 0;
1815  p2 -= size)
1816  {
1817  ngx_memcpy(p2, p2 - size, size);
1818  }
1819 
1820  ngx_memcpy(p2, p, size);
1821  }
1822 
1823  ngx_free(p);
1824 }
1825 
1826 
1827 #if (NGX_MEMCPY_LIMIT)
1828 
1829 void *
1830 ngx_memcpy(void *dst, const void *src, size_t n)
1831 {
1832  if (n > NGX_MEMCPY_LIMIT) {
1833  ngx_log_error(NGX_LOG_ALERT, ngx_cycle->log, 0, "memcpy %uz bytes", n);
1834  ngx_debug_point();
1835  }
1836 
1837  return memcpy(dst, src, n);
1838 }
1839 
1840 #endif
Generated on Sun Nov 10 2013 09:49:07 for Groonga 3.0.9 Source Code Document by   doxygen 1.8.1.2