Mercurial > hg > nginx-quic
annotate src/core/ngx_list.c @ 4497:95ab6658654a
Fix of rbtree lookup on hash collisions.
Previous code incorrectly assumed that nodes with identical keys are linked
together. This might not be true after tree rebalance.
Patch by Lanshun Zhou.
author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|
date | Mon, 27 Feb 2012 22:15:39 +0000 |
parents | d620f497c50f |
children | a82f305487c2 |
rev | line source |
---|---|
441
da8c5707af39
nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents:
416
diff
changeset
|
1 |
da8c5707af39
nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents:
416
diff
changeset
|
2 /* |
444
42d11f017717
nginx-0.1.0-2004-09-29-20:00:49 import; remove years from copyright
Igor Sysoev <igor@sysoev.ru>
parents:
441
diff
changeset
|
3 * Copyright (C) Igor Sysoev |
4412 | 4 * Copyright (C) Nginx, Inc. |
441
da8c5707af39
nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents:
416
diff
changeset
|
5 */ |
da8c5707af39
nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents:
416
diff
changeset
|
6 |
414
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
7 |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
8 #include <ngx_config.h> |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
9 #include <ngx_core.h> |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
10 |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
11 |
766 | 12 ngx_list_t * |
13 ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size) | |
14 { | |
15 ngx_list_t *list; | |
16 | |
17 list = ngx_palloc(pool, sizeof(ngx_list_t)); | |
18 if (list == NULL) { | |
19 return NULL; | |
20 } | |
21 | |
22 list->part.elts = ngx_palloc(pool, n * size); | |
23 if (list->part.elts == NULL) { | |
24 return NULL; | |
25 } | |
26 | |
27 list->part.nelts = 0; | |
28 list->part.next = NULL; | |
29 list->last = &list->part; | |
30 list->size = size; | |
31 list->nalloc = n; | |
32 list->pool = pool; | |
33 | |
34 return list; | |
35 } | |
36 | |
37 | |
38 void * | |
39 ngx_list_push(ngx_list_t *l) | |
414
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
40 { |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
41 void *elt; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
42 ngx_list_part_t *last; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
43 |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
44 last = l->last; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
45 |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
46 if (last->nelts == l->nalloc) { |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
47 |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
48 /* the last part is full, allocate a new list part */ |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
49 |
501 | 50 last = ngx_palloc(l->pool, sizeof(ngx_list_part_t)); |
51 if (last == NULL) { | |
414
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
52 return NULL; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
53 } |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
54 |
501 | 55 last->elts = ngx_palloc(l->pool, l->nalloc * l->size); |
56 if (last->elts == NULL) { | |
414
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
57 return NULL; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
58 } |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
59 |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
60 last->nelts = 0; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
61 last->next = NULL; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
62 |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
63 l->last->next = last; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
64 l->last = last; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
65 } |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
66 |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
67 elt = (char *) last->elts + l->size * last->nelts; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
68 last->nelts++; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
69 |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
70 return elt; |
388a842cbbe1
nginx-0.0.10-2004-09-03-19:50:30 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
71 } |