1 /* 2 * ProFTPD - FTP server daemon 3 * Copyright (c) 2004-2017 The ProFTPD Project team 4 * 5 * This program is free software; you can redistribute it and/or modify 6 * it under the terms of the GNU General Public License as published by 7 * the Free Software Foundation; either version 2 of the License, or 8 * (at your option) any later version. 9 * 10 * This program is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 * GNU General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License 16 * along with this program; if not, write to the Free Software 17 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA. 18 * 19 * As a special exemption, The ProFTPD Project team and other respective 20 * copyright holders give permission to link this program with OpenSSL, and 21 * distribute the resulting executable, without including the source code for 22 * OpenSSL in the source distribution. 23 */ 24 25 /* Table management */ 26 27 #ifndef PR_TABLE_H 28 #define PR_TABLE_H 29 30 #include "os.h" 31 #include "pool.h" 32 33 typedef struct tab_key { 34 struct tab_key *next; 35 const void *key_data; 36 size_t key_datasz; 37 unsigned int hash; 38 unsigned nents; 39 40 } pr_table_key_t; 41 42 typedef struct tab_entry { 43 struct tab_entry *next, *prev; 44 unsigned int idx; 45 pr_table_key_t *key; 46 const void *value_data; 47 size_t value_datasz; 48 49 } pr_table_entry_t; 50 51 typedef struct table_rec pr_table_t; 52 53 /* Add an entry in the table under the given key. The char * pointer 54 * is stored directly, NOT a copy of the memory to which it points. 55 * If value_datasz is 0, value_data is assumed to be a NUL-terminated string 56 * and strlen() is called on it. 57 */ 58 int pr_table_add(pr_table_t *tab, const char *key_data, const void *value_data, 59 size_t value_datasz); 60 61 /* Add an entry in the table under the given key, making a duplicate of 62 * the given value from the table's pool. If value_datasz is 0, value_data 63 * is assumed to be a NUL-terminated string and strlen() is called on it. 64 */ 65 int pr_table_add_dup(pr_table_t *tab, const char *key_data, 66 const void *value_data, size_t value_datasz); 67 68 /* Allocates a new table from the given pool. flags can be used to 69 * determine the table behavior, e.g. will it allow multiple entries under 70 * the same key (PR_TABLE_FL_MULTI_VALUE). 71 */ 72 pr_table_t *pr_table_alloc(pool *p, int flags); 73 #define PR_TABLE_FL_MULTI_VALUE 0x0001 74 #define PR_TABLE_FL_USE_CACHE 0x0002 75 76 /* Returns the number of entries stored in the table. 77 */ 78 int pr_table_count(pr_table_t *tab); 79 80 /* Similar to Perl's map() function, this function executes the given 81 * callback on every entry in the table, passing in the key/value stored and a 82 * pointer to user-provided data. DO NOT ALTER the table inside the callback 83 * function by adding or removing entries; it will alter the iterator state, 84 * possibly causing entries to be skipped. 85 * 86 * This function is useful for when completely freeing an entire table and 87 * everything in it: do() a free() function on the items, then free the table. 88 * 89 * The flags argument alters how the calling is done: a callback can return -1 90 * to halt the iteration, unless PR_TABLE_DO_FL_ALL is used. 91 */ 92 int pr_table_do(pr_table_t *tab, int cb(const void *key_data, 93 size_t key_datasz, const void *value_data, size_t value_datasz, 94 void *user_data), void *user_data, int flags); 95 #define PR_TABLE_DO_FL_ALL 0x0010 96 97 /* Remove all entries from the table, emptying it. 98 */ 99 int pr_table_empty(pr_table_t *tab); 100 101 /* Returns a count of the number of entries stored under that key. This 102 * means that these tables allow multiple entries under the same key; it is 103 * up to higher-level APIs to impose restrictions such as avoiding duplicates. 104 */ 105 int pr_table_exists(pr_table_t *tab, const char *key_data); 106 107 /* Free the given empty table. If the table is not empty, -1 will be 108 * returned, and errno set to EPERM. 109 */ 110 int pr_table_free(pr_table_t *tab); 111 112 /* Returns the value stored under the given key, or NULL if there is no 113 * entry in the table for the given key. If value_datasz is not NULL, 114 * the size of the returned value will be stored in it. 115 */ 116 const void *pr_table_get(pr_table_t *tab, const char *key_data, 117 size_t *value_datasz); 118 119 /* Retrieve the next key, for iterating over the entire table. Returns 120 * NULL when the end of the table has been reached. 121 */ 122 const void *pr_table_next(pr_table_t *tab); 123 124 /* Returns the value stored under the given key, and removes that entry from 125 * the table. If value_datasz is not NULL, the size of the returned value 126 * will be stored in it. 127 */ 128 const void *pr_table_remove(pr_table_t *tab, const char *key_data, 129 size_t *value_datasz); 130 131 /* Rewind to the start of the table before iterating using pr_table_next(). 132 */ 133 int pr_table_rewind(pr_table_t *tab); 134 135 /* Changes the value stored under the given key to the provided value. 136 * Returns -1 if no such key is in the table. Note that only the first 137 * encountered value under the key is set; this may be need to be called 138 * multiple times in order to set all entries under that key; call 139 * pr_table_exists() to find the number of entries to change. 140 */ 141 int pr_table_set(pr_table_t *tab, const char *key_data, 142 const void *value_data, size_t value_datasz); 143 144 /* Change some of the characteristics of an allocated table tab via 145 * the control cmd. pr_table_ctl() can only be called on an empty table. 146 * Returns 0 on success, -1 on failure (with errno set appropriately). 147 * 148 * cmd may have one of the following values: 149 * 150 * PR_TABLE_CTL_SET_ENT_INSERT 151 * Sets a callback that handles inserting a table entry into its chain. 152 * The default insertor inserts new entries at the start of the chain; 153 * some tables may require that new entries be inserted at the end of 154 * of the chain. 155 * 156 * The arg parameter must be a pointer to a function with the following 157 * signature: 158 * 159 * void (*func)(pr_table_entry_t **head, pr_table_entry_t *ent) 160 * 161 * The function will be called with head as a pointer to the head of 162 * the chain into which ent will be inserted. 163 * 164 * If arg is NULL, the default insertor will be used. 165 * 166 * PR_TABLE_CTL_SET_ENT_REMOVE 167 * Sets a callback that handles removing a table entry for its chain. 168 * 169 * The arg parameter must be a pointer to a function with the following 170 * signature: 171 * 172 * void (*func)(pr_table_entry_t **head, pr_table_entry_t *ent) 173 * 174 * The function will be called with head as a pointer to the head of 175 * the chain from which ent will be removed. 176 * 177 * If arg is NULL, the default remover will be used. 178 * 179 * PR_TABLE_CTL_SET_FLAGS 180 * Sets the flags on the given table. These flags have the same 181 * values as the flags used in pr_table_alloc(). 182 * 183 * PR_TABLE_CTL_SET_KEY_CMP 184 * Sets a callback for handling key comparisons. The default comparator 185 * uses strcmp() on the key data; some tables may require other 186 * comparators, especially if the key data are not strings. 187 * 188 * The arg parameter must be a pointer to a function with the following 189 * signature: 190 * 191 * int (*func)(const void *key1, size_t keysz1, const void *key2, 192 * size_t keysz2) 193 * 194 * If arg is NULL, the default comparator will be used. 195 * 196 * PR_TABLE_CTL_SET_KEY_HASH 197 * Sets a callback for handling the calculation of a hash value for 198 * given key data. The default hash algorithm is the same used in Perl. 199 * 200 * The arg parameter must be a pointer to a function with the following 201 * signature: 202 * 203 * unsigned int (*func)(const void *key, size_t keysz) 204 * 205 * If arg is NULL, the default hash function will be used. 206 * 207 * PR_TABLE_CTL_SET_NCHAINS 208 * Sets the number of chains in a table. New entries are hashed, then 209 * distributed among the chains in a manner that hopefully provides 210 * minimum lookup times. If a table will be holding a large number of 211 * entries, a larger number of chains will ensure a better distribution. 212 * The default number of chains is 256. 213 * 214 * PR_TABLE_CTL_SET_MAX_ENTS 215 * Sets the maximum number of entries the table can hold. Attempts to 216 * insert entries above this maximum result in an ENOSPC error value. 217 * The default maximum number of entries is currently 8192. 218 */ 219 int pr_table_ctl(pr_table_t *tab, int cmd, void *arg); 220 #define PR_TABLE_CTL_SET_ENT_INSERT 1 221 #define PR_TABLE_CTL_SET_ENT_REMOVE 2 222 #define PR_TABLE_CTL_SET_FLAGS 3 223 #define PR_TABLE_CTL_SET_KEY_CMP 4 224 #define PR_TABLE_CTL_SET_KEY_HASH 5 225 #define PR_TABLE_CTL_SET_NCHAINS 6 226 #define PR_TABLE_CTL_SET_MAX_ENTS 7 227 228 /* Returns the table "load", which is the ratio between the number of 229 * entries in the table (e.g. via pr_table_count()) and the number of chains 230 * among which the entries are distributed. Note that a negative return value 231 * indicates an error of some sort; check the errno value in such cases. 232 * 233 * The load factor can be used, in combination with tests surrounding entry 234 * lookup time, to determine how well the key hashing function performs with 235 * regard to collision avoidance, especially as the number of entries increases. 236 */ 237 float pr_table_load(pr_table_t *tab); 238 239 /* Dump table information. */ 240 void pr_table_dump(void (*)(const char *, ...), pr_table_t *tab); 241 242 /* Same as pr_table_add(), except that the key data to use is treated as 243 * an opaque memory region of size key_datasz. This function should be 244 * used if the lookup key is not a string. 245 * 246 * Unlike pr_table_add(), though, if value_datasz is zero, it is not 247 * assumed that value_data is a NUL-terminated string. Callers of this 248 * function must provide the size of the given value_data. 249 */ 250 int pr_table_kadd(pr_table_t *tab, const void *key_data, size_t key_datasz, 251 const void *value_data, size_t value_datasz); 252 253 /* Same as pr_table_exists(), except that the key data to use is treated as 254 * an opaque memory region of size key_datasz. This function should be 255 * used if the lookup key is not a string. 256 */ 257 int pr_table_kexists(pr_table_t *tab, const void *key_data, size_t key_datasz); 258 259 /* Same as pr_table_next(), except that the size of the key is also provided. 260 * This function should be used if the lookup key is not a string. 261 */ 262 const void *pr_table_knext(pr_table_t *tab, size_t *key_datasz); 263 264 /* Same as pr_table_get(), except that the key data to use is treated as 265 * an opaque memory region of size key_datasz. This function should be 266 * used if the lookup key is not a string. 267 */ 268 const void *pr_table_kget(pr_table_t *tab, const void *key_data, 269 size_t key_datasz, size_t *value_datasz); 270 271 /* Same as pr_table_remove(), except that the key data to use is treated as 272 * an opaque memory region of size key_datasz. This function should be 273 * used if the lookup key is not a string. 274 */ 275 const void *pr_table_kremove(pr_table_t *tab, const void *key_data, 276 size_t key_datasz, size_t *value_datasz); 277 278 /* Same as pr_table_set(), except that the key data to use is treated as 279 * an opaque memory region of size key_datasz. This function should be 280 * used if the lookup key is not a string. 281 */ 282 int pr_table_kset(pr_table_t *tab, const void *key_data, size_t key_datasz, 283 const void *value_data, size_t value_datasz); 284 285 /* Similar to pr_table_alloc(), except that the number of chains can 286 * be explicitly configured. 287 */ 288 pr_table_t *pr_table_nalloc(pool *p, int flags, unsigned int nchains); 289 290 /* Similar to pcalloc(), except that the requested memory is allocated 291 * from the table's pool. 292 */ 293 void *pr_table_pcalloc(pr_table_t *tab, size_t sz); 294 295 /* Internal use only. */ 296 int table_handling_signal(int); 297 298 #endif /* PR_TABLE_H */ 299