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