1e18a033bSKonstantin Ananyev
2e18a033bSKonstantin Ananyev/*
3e18a033bSKonstantin Ananyev * Copyright (C) Igor Sysoev
4e18a033bSKonstantin Ananyev * Copyright (C) Nginx, Inc.
5e18a033bSKonstantin Ananyev */
6e18a033bSKonstantin Ananyev
7e18a033bSKonstantin Ananyev
8e18a033bSKonstantin Ananyev#ifndef _NGX_HASH_H_INCLUDED_
9e18a033bSKonstantin Ananyev#define _NGX_HASH_H_INCLUDED_
10e18a033bSKonstantin Ananyev
11e18a033bSKonstantin Ananyev
12e18a033bSKonstantin Ananyev#include <ngx_config.h>
13e18a033bSKonstantin Ananyev#include <ngx_core.h>
14e18a033bSKonstantin Ananyev
15e18a033bSKonstantin Ananyev
16e18a033bSKonstantin Ananyevtypedef struct {
17e18a033bSKonstantin Ananyev    void             *value;
18e18a033bSKonstantin Ananyev    u_short           len;
19e18a033bSKonstantin Ananyev    u_char            name[1];
20e18a033bSKonstantin Ananyev} ngx_hash_elt_t;
21e18a033bSKonstantin Ananyev
22e18a033bSKonstantin Ananyev
23e18a033bSKonstantin Ananyevtypedef struct {
24e18a033bSKonstantin Ananyev    ngx_hash_elt_t  **buckets;
25e18a033bSKonstantin Ananyev    ngx_uint_t        size;
26e18a033bSKonstantin Ananyev} ngx_hash_t;
27e18a033bSKonstantin Ananyev
28e18a033bSKonstantin Ananyev
29e18a033bSKonstantin Ananyevtypedef struct {
30e18a033bSKonstantin Ananyev    ngx_hash_t        hash;
31e18a033bSKonstantin Ananyev    void             *value;
32e18a033bSKonstantin Ananyev} ngx_hash_wildcard_t;
33e18a033bSKonstantin Ananyev
34e18a033bSKonstantin Ananyev
35e18a033bSKonstantin Ananyevtypedef struct {
36e18a033bSKonstantin Ananyev    ngx_str_t         key;
37e18a033bSKonstantin Ananyev    ngx_uint_t        key_hash;
38e18a033bSKonstantin Ananyev    void             *value;
39e18a033bSKonstantin Ananyev} ngx_hash_key_t;
40e18a033bSKonstantin Ananyev
41e18a033bSKonstantin Ananyev
42e18a033bSKonstantin Ananyevtypedef ngx_uint_t (*ngx_hash_key_pt) (u_char *data, size_t len);
43e18a033bSKonstantin Ananyev
44e18a033bSKonstantin Ananyev
45e18a033bSKonstantin Ananyevtypedef struct {
46e18a033bSKonstantin Ananyev    ngx_hash_t            hash;
47e18a033bSKonstantin Ananyev    ngx_hash_wildcard_t  *wc_head;
48e18a033bSKonstantin Ananyev    ngx_hash_wildcard_t  *wc_tail;
49e18a033bSKonstantin Ananyev} ngx_hash_combined_t;
50e18a033bSKonstantin Ananyev
51e18a033bSKonstantin Ananyev
52e18a033bSKonstantin Ananyevtypedef struct {
53e18a033bSKonstantin Ananyev    ngx_hash_t       *hash;
54e18a033bSKonstantin Ananyev    ngx_hash_key_pt   key;
55e18a033bSKonstantin Ananyev
56e18a033bSKonstantin Ananyev    ngx_uint_t        max_size;
57e18a033bSKonstantin Ananyev    ngx_uint_t        bucket_size;
58e18a033bSKonstantin Ananyev
59e18a033bSKonstantin Ananyev    char             *name;
60e18a033bSKonstantin Ananyev    ngx_pool_t       *pool;
61e18a033bSKonstantin Ananyev    ngx_pool_t       *temp_pool;
62e18a033bSKonstantin Ananyev} ngx_hash_init_t;
63e18a033bSKonstantin Ananyev
64e18a033bSKonstantin Ananyev
65e18a033bSKonstantin Ananyev#define NGX_HASH_SMALL            1
66e18a033bSKonstantin Ananyev#define NGX_HASH_LARGE            2
67e18a033bSKonstantin Ananyev
68e18a033bSKonstantin Ananyev#define NGX_HASH_LARGE_ASIZE      16384
69e18a033bSKonstantin Ananyev#define NGX_HASH_LARGE_HSIZE      10007
70e18a033bSKonstantin Ananyev
71e18a033bSKonstantin Ananyev#define NGX_HASH_WILDCARD_KEY     1
72e18a033bSKonstantin Ananyev#define NGX_HASH_READONLY_KEY     2
73e18a033bSKonstantin Ananyev
74e18a033bSKonstantin Ananyev
75e18a033bSKonstantin Ananyevtypedef struct {
76e18a033bSKonstantin Ananyev    ngx_uint_t        hsize;
77e18a033bSKonstantin Ananyev
78e18a033bSKonstantin Ananyev    ngx_pool_t       *pool;
79e18a033bSKonstantin Ananyev    ngx_pool_t       *temp_pool;
80e18a033bSKonstantin Ananyev
81e18a033bSKonstantin Ananyev    ngx_array_t       keys;
82e18a033bSKonstantin Ananyev    ngx_array_t      *keys_hash;
83e18a033bSKonstantin Ananyev
84e18a033bSKonstantin Ananyev    ngx_array_t       dns_wc_head;
85e18a033bSKonstantin Ananyev    ngx_array_t      *dns_wc_head_hash;
86e18a033bSKonstantin Ananyev
87e18a033bSKonstantin Ananyev    ngx_array_t       dns_wc_tail;
88e18a033bSKonstantin Ananyev    ngx_array_t      *dns_wc_tail_hash;
89e18a033bSKonstantin Ananyev} ngx_hash_keys_arrays_t;
90e18a033bSKonstantin Ananyev
91e18a033bSKonstantin Ananyev
92e18a033bSKonstantin Ananyevtypedef struct {
93e18a033bSKonstantin Ananyev    ngx_uint_t        hash;
94e18a033bSKonstantin Ananyev    ngx_str_t         key;
95e18a033bSKonstantin Ananyev    ngx_str_t         value;
96e18a033bSKonstantin Ananyev    u_char           *lowcase_key;
97e18a033bSKonstantin Ananyev} ngx_table_elt_t;
98e18a033bSKonstantin Ananyev
99e18a033bSKonstantin Ananyev
100e18a033bSKonstantin Ananyevvoid *ngx_hash_find(ngx_hash_t *hash, ngx_uint_t key, u_char *name, size_t len);
101e18a033bSKonstantin Ananyevvoid *ngx_hash_find_wc_head(ngx_hash_wildcard_t *hwc, u_char *name, size_t len);
102e18a033bSKonstantin Ananyevvoid *ngx_hash_find_wc_tail(ngx_hash_wildcard_t *hwc, u_char *name, size_t len);
103e18a033bSKonstantin Ananyevvoid *ngx_hash_find_combined(ngx_hash_combined_t *hash, ngx_uint_t key,
104e18a033bSKonstantin Ananyev    u_char *name, size_t len);
105e18a033bSKonstantin Ananyev
106e18a033bSKonstantin Ananyevngx_int_t ngx_hash_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
107e18a033bSKonstantin Ananyev    ngx_uint_t nelts);
108e18a033bSKonstantin Ananyevngx_int_t ngx_hash_wildcard_init(ngx_hash_init_t *hinit, ngx_hash_key_t *names,
109e18a033bSKonstantin Ananyev    ngx_uint_t nelts);
110e18a033bSKonstantin Ananyev
111e18a033bSKonstantin Ananyev#define ngx_hash(key, c)   ((ngx_uint_t) key * 31 + c)
112e18a033bSKonstantin Ananyevngx_uint_t ngx_hash_key(u_char *data, size_t len);
113e18a033bSKonstantin Ananyevngx_uint_t ngx_hash_key_lc(u_char *data, size_t len);
114e18a033bSKonstantin Ananyevngx_uint_t ngx_hash_strlow(u_char *dst, u_char *src, size_t n);
115e18a033bSKonstantin Ananyev
116e18a033bSKonstantin Ananyev
117e18a033bSKonstantin Ananyevngx_int_t ngx_hash_keys_array_init(ngx_hash_keys_arrays_t *ha, ngx_uint_t type);
118e18a033bSKonstantin Ananyevngx_int_t ngx_hash_add_key(ngx_hash_keys_arrays_t *ha, ngx_str_t *key,
119e18a033bSKonstantin Ananyev    void *value, ngx_uint_t flags);
120e18a033bSKonstantin Ananyev
121e18a033bSKonstantin Ananyev
122e18a033bSKonstantin Ananyev#endif /* _NGX_HASH_H_INCLUDED_ */
123