Mercurial > hg > nginx
view src/core/ngx_regex.h @ 9167:3038bd4d7816
Core: changed ngx_queue_sort() to use merge sort.
This improves nginx startup times significantly when using very large number
of locations due to computational complexity of the sorting algorithm being
used: insertion sort is O(n*n) on average, while merge sort is O(n*log(n)).
In particular, in a test configuration with 20k locations total startup
time is reduced from 8 seconds to 0.9 seconds.
Prodded by Yusuke Nojima,
https://mailman.nginx.org/pipermail/nginx-devel/2023-September/NUL3Y2FPPFSHMPTFTL65KXSXNTX3NQMK.html
author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|
date | Wed, 18 Oct 2023 04:30:11 +0300 |
parents | d07456044b61 |
children |
line wrap: on
line source
/* * Copyright (C) Igor Sysoev * Copyright (C) Nginx, Inc. */ #ifndef _NGX_REGEX_H_INCLUDED_ #define _NGX_REGEX_H_INCLUDED_ #include <ngx_config.h> #include <ngx_core.h> #if (NGX_PCRE2) #define PCRE2_CODE_UNIT_WIDTH 8 #include <pcre2.h> #define NGX_REGEX_NO_MATCHED PCRE2_ERROR_NOMATCH /* -1 */ typedef pcre2_code ngx_regex_t; #else #include <pcre.h> #define NGX_REGEX_NO_MATCHED PCRE_ERROR_NOMATCH /* -1 */ typedef struct { pcre *code; pcre_extra *extra; } ngx_regex_t; #endif #define NGX_REGEX_CASELESS 0x00000001 #define NGX_REGEX_MULTILINE 0x00000002 typedef struct { ngx_str_t pattern; ngx_pool_t *pool; ngx_uint_t options; ngx_regex_t *regex; int captures; int named_captures; int name_size; u_char *names; ngx_str_t err; } ngx_regex_compile_t; typedef struct { ngx_regex_t *regex; u_char *name; } ngx_regex_elt_t; void ngx_regex_init(void); ngx_int_t ngx_regex_compile(ngx_regex_compile_t *rc); ngx_int_t ngx_regex_exec(ngx_regex_t *re, ngx_str_t *s, int *captures, ngx_uint_t size); #if (NGX_PCRE2) #define ngx_regex_exec_n "pcre2_match()" #else #define ngx_regex_exec_n "pcre_exec()" #endif ngx_int_t ngx_regex_exec_array(ngx_array_t *a, ngx_str_t *s, ngx_log_t *log); #endif /* _NGX_REGEX_H_INCLUDED_ */