• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * nghttp3
3  *
4  * Copyright (c) 2019 nghttp3 contributors
5  * Copyright (c) 2017 ngtcp2 contributors
6  * Copyright (c) 2012 nghttp2 contributors
7  *
8  * Permission is hereby granted, free of charge, to any person obtaining
9  * a copy of this software and associated documentation files (the
10  * "Software"), to deal in the Software without restriction, including
11  * without limitation the rights to use, copy, modify, merge, publish,
12  * distribute, sublicense, and/or sell copies of the Software, and to
13  * permit persons to whom the Software is furnished to do so, subject to
14  * the following conditions:
15  *
16  * The above copyright notice and this permission notice shall be
17  * included in all copies or substantial portions of the Software.
18  *
19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
22  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
23  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
24  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
25  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26  */
27 #ifndef NGHTTP3_MAP_H
28 #define NGHTTP3_MAP_H
29 
30 #ifdef HAVE_CONFIG_H
31 #  include <config.h>
32 #endif /* HAVE_CONFIG_H */
33 
34 #include <nghttp3/nghttp3.h>
35 
36 #include "nghttp3_mem.h"
37 
38 /* Implementation of unordered map */
39 
40 typedef uint64_t nghttp3_map_key_type;
41 
42 typedef struct nghttp3_map_bucket {
43   uint32_t hash;
44   nghttp3_map_key_type key;
45   void *data;
46 } nghttp3_map_bucket;
47 
48 typedef struct nghttp3_map {
49   nghttp3_map_bucket *table;
50   const nghttp3_mem *mem;
51   size_t size;
52   uint32_t tablelen;
53   uint32_t tablelenbits;
54 } nghttp3_map;
55 
56 /*
57  * Initializes the map |map|.
58  */
59 void nghttp3_map_init(nghttp3_map *map, const nghttp3_mem *mem);
60 
61 /*
62  * Deallocates any resources allocated for |map|. The stored entries
63  * are not freed by this function. Use nghttp3_map_each_free() to free
64  * each entries.
65  */
66 void nghttp3_map_free(nghttp3_map *map);
67 
68 /*
69  * Deallocates each entries using |func| function and any resources
70  * allocated for |map|. The |func| function is responsible for freeing
71  * given the |data| object. The |ptr| will be passed to the |func| as
72  * send argument. The return value of the |func| will be ignored.
73  */
74 void nghttp3_map_each_free(nghttp3_map *map, int (*func)(void *data, void *ptr),
75                            void *ptr);
76 
77 /*
78  * Inserts the new |data| with the |key| to the map |map|.
79  *
80  * This function returns 0 if it succeeds, or one of the following
81  * negative error codes:
82  *
83  * NGHTTP3_ERR_INVALID_ARGUMENT
84  *     The item associated by |key| already exists.
85  * NGHTTP3_ERR_NOMEM
86  *   Out of memory
87  */
88 int nghttp3_map_insert(nghttp3_map *map, nghttp3_map_key_type key, void *data);
89 
90 /*
91  * Returns the data associated by the key |key|.  If there is no such
92  * data, this function returns NULL.
93  */
94 void *nghttp3_map_find(nghttp3_map *map, nghttp3_map_key_type key);
95 
96 /*
97  * Removes the data associated by the key |key| from the |map|.  The
98  * removed data is not freed by this function.
99  *
100  * This function returns 0 if it succeeds, or one of the following
101  * negative error codes:
102  *
103  * NGHTTP3_ERR_INVALID_ARGUMENT
104  *     The data associated by |key| does not exist.
105  */
106 int nghttp3_map_remove(nghttp3_map *map, nghttp3_map_key_type key);
107 
108 /*
109  * Removes all entries from |map|.
110  */
111 void nghttp3_map_clear(nghttp3_map *map);
112 
113 /*
114  * Returns the number of items stored in the map |map|.
115  */
116 size_t nghttp3_map_size(nghttp3_map *map);
117 
118 /*
119  * Applies the function |func| to each data in the |map| with the
120  * optional user supplied pointer |ptr|.
121  *
122  * If the |func| returns 0, this function calls the |func| with the
123  * next data.  If the |func| returns nonzero, it will not call the
124  * |func| for further entries and return the return value of the
125  * |func| immediately.  Thus, this function returns 0 if all the
126  * invocations of the |func| return 0, or nonzero value which the last
127  * invocation of |func| returns.
128  *
129  * Don't use this function to free each data. Use
130  * nghttp3_map_each_free() instead.
131  */
132 int nghttp3_map_each(nghttp3_map *map, int (*func)(void *data, void *ptr),
133                      void *ptr);
134 
135 void nghttp3_map_print_distance(nghttp3_map *map);
136 
137 #endif /* NGHTTP3_MAP_H */
138