Return to hashtable.h CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / strongswan / src / libstrongswan / collections

strongswan 5.9.2

    1: /*
    2:  * Copyright (C) 2008-2020 Tobias Brunner
    3:  * HSR Hochschule fuer Technik Rapperswil
    4:  *
    5:  * This program is free software; you can redistribute it and/or modify it
    6:  * under the terms of the GNU General Public License as published by the
    7:  * Free Software Foundation; either version 2 of the License, or (at your
    8:  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
    9:  *
   10:  * This program is distributed in the hope that it will be useful, but
   11:  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   12:  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   13:  * for more details.
   14:  */
   15: 
   16: /**
   17:  * @defgroup hashtable hashtable
   18:  * @{ @ingroup collections
   19:  */
   20: 
   21: #ifndef HASHTABLE_H_
   22: #define HASHTABLE_H_
   23: 
   24: #include <collections/enumerator.h>
   25: 
   26: typedef struct hashtable_t hashtable_t;
   27: typedef struct hashlist_t hashlist_t;
   28: 
   29: /**
   30:  * Prototype for a function that computes the hash code from the given key.
   31:  *
   32:  * @param key			key to hash
   33:  * @return				hash code
   34:  */
   35: typedef u_int (*hashtable_hash_t)(const void *key);
   36: 
   37: /**
   38:  * Hashtable hash function calculation the hash solely based on the key pointer.
   39:  *
   40:  * @param key			key to hash
   41:  * @return				hash of key
   42:  */
   43: u_int hashtable_hash_ptr(const void *key);
   44: 
   45: /**
   46:  * Hashtable hash function calculation the hash for char* keys.
   47:  *
   48:  * @param key			key to hash, a char*
   49:  * @return				hash of key
   50:  */
   51: u_int hashtable_hash_str(const void *key);
   52: 
   53: /**
   54:  * Prototype for a function that compares the two keys for equality.
   55:  *
   56:  * @param key			first key (the one we are looking for/inserting)
   57:  * @param other_key		second key
   58:  * @return				TRUE if the keys are equal
   59:  */
   60: typedef bool (*hashtable_equals_t)(const void *key, const void *other_key);
   61: 
   62: /**
   63:  * Hashtable equals function comparing pointers.
   64:  *
   65:  * @param key			key to compare
   66:  * @param other_key		other key to compare
   67:  * @return				TRUE if key == other_key
   68:  */
   69: bool hashtable_equals_ptr(const void *key, const void *other_key);
   70: 
   71: /**
   72:  * Hashtable equals function comparing char* keys.
   73:  *
   74:  * @param key			key to compare
   75:  * @param other_key		other key to compare
   76:  * @return				TRUE if streq(key, other_key)
   77:  */
   78: bool hashtable_equals_str(const void *key, const void *other_key);
   79: 
   80: /**
   81:  * Prototype for a function that compares the two keys in order to sort them.
   82:  *
   83:  * @param key			first key (the one we are looking for/inserting)
   84:  * @param other_key		second key
   85:  * @return				less than, equal to, or greater than 0 if key is
   86:  *						less than, equal to, or greater than other_key
   87:  */
   88: typedef int (*hashtable_cmp_t)(const void *key, const void *other_key);
   89: 
   90: /**
   91:  * Class implementing a hash table.
   92:  *
   93:  * General purpose hash table. This hash table is not synchronized.
   94:  *
   95:  * The insertion order is maintained when enumerating entries.
   96:  */
   97: struct hashtable_t {
   98: 
   99: 	/**
  100: 	 * Create an enumerator over the hash table key/value pairs.
  101: 	 *
  102: 	 * @return			enumerator over (void *key, void *value)
  103: 	 */
  104: 	enumerator_t *(*create_enumerator)(hashtable_t *this);
  105: 
  106: 	/**
  107: 	 * Adds the given value with the given key to the hash table, if there
  108: 	 * exists no entry with that key. NULL is returned in this case.
  109: 	 * Otherwise the existing value is replaced and the function returns the
  110: 	 * old value.
  111: 	 *
  112: 	 * @param key		the key to store
  113: 	 * @param value		the value to store
  114: 	 * @return			NULL if no item was replaced, the old value otherwise
  115: 	 */
  116: 	void *(*put)(hashtable_t *this, const void *key, void *value);
  117: 
  118: 	/**
  119: 	 * Returns the value with the given key, if the hash table contains such an
  120: 	 * entry, otherwise NULL is returned.
  121: 	 *
  122: 	 * @param key		the key of the requested value
  123: 	 * @return			the value, NULL if not found
  124: 	 */
  125: 	void *(*get)(hashtable_t *this, const void *key);
  126: 
  127: 	/**
  128: 	 * Removes the value with the given key from the hash table and returns the
  129: 	 * removed value (or NULL if no such value existed).
  130: 	 *
  131: 	 * @param key		the key of the value to remove
  132: 	 * @return			the removed value, NULL if not found
  133: 	 */
  134: 	void *(*remove)(hashtable_t *this, const void *key);
  135: 
  136: 	/**
  137: 	 * Removes the key and value pair from the hash table at which the given
  138: 	 * enumerator currently points.
  139: 	 *
  140: 	 * @param enumerator	enumerator, from create_enumerator
  141: 	 */
  142: 	void (*remove_at)(hashtable_t *this, enumerator_t *enumerator);
  143: 
  144: 	/**
  145: 	 * Gets the number of items in the hash table.
  146: 	 *
  147: 	 * @return			number of items
  148: 	 */
  149: 	u_int (*get_count)(hashtable_t *this);
  150: 
  151: 	/**
  152: 	 * Destroys a hash table object.
  153: 	 */
  154: 	void (*destroy)(hashtable_t *this);
  155: 
  156: 	/**
  157: 	 * Destroys a hash table object and calls the given function for each
  158: 	 * item and its key in the hash table.
  159: 	 *
  160: 	 * @param function	function to call on each item and key
  161: 	 */
  162: 	void (*destroy_function)(hashtable_t *this,
  163: 							 void (*)(void *val, const void *key));
  164: };
  165: 
  166: /**
  167:  * Class implementing a hash table with ordered keys/items and special query
  168:  * method.
  169:  *
  170:  * @note The ordering only pertains to keys/items in the same bucket (with or
  171:  * without the same hash value), not to the order when enumerating. So unlike
  172:  * hashtable_t this class does not guarantee any specific order when enumerating
  173:  * all entries.
  174:  *
  175:  * This is intended to be used with hash functions that intentionally return the
  176:  * same hash value for different keys so multiple items can be retrieved for a
  177:  * key.
  178:  *
  179:  * It's like storing sorted linked lists in a hash table but with less overhead.
  180:  */
  181: struct hashlist_t {
  182: 
  183: 	/**
  184: 	 * Implements the hash table interface.
  185: 	 */
  186: 	hashtable_t ht;
  187: 
  188: 	/**
  189: 	 * Returns the first value with a matching key if the hash table contains
  190: 	 * such an entry, otherwise NULL is returned.
  191: 	 *
  192: 	 * Compared to get() the given match function is used to compare the keys
  193: 	 * for equality.  The hash function does have to be devised specially in
  194: 	 * order to make this work if the match function compares keys differently
  195: 	 * than the equals/comparison function provided to the constructor.
  196: 	 *
  197: 	 * This basically allows to enumerate all entries with the same hash value
  198: 	 * in their key's order (insertion order, i.e. without comparison function)
  199: 	 * is only guaranteed for items with the same hash value.
  200: 	 *
  201: 	 * @param key		the key to match against
  202: 	 * @param match		match function to be used when comparing keys
  203: 	 * @return			the value, NULL if not found
  204: 	 */
  205: 	void *(*get_match)(hashlist_t *this, const void *key,
  206: 					   hashtable_equals_t match);
  207: 
  208: 	/**
  209: 	 * Destroys a hash list object.
  210: 	 */
  211: 	void (*destroy)(hashlist_t *this);
  212: };
  213: 
  214: /**
  215:  * Creates an empty hash table object.
  216:  *
  217:  * @param hash			hash function
  218:  * @param equals		equals function
  219:  * @param size			initial size
  220:  * @return				hashtable_t object
  221:  */
  222: hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
  223: 							  u_int size);
  224: 
  225: /**
  226:  * Creates an empty hash list object with each bucket's keys in insertion order.
  227:  *
  228:  * @param hash			hash function
  229:  * @param equals		equals function
  230:  * @param size			initial size
  231:  * @return				hashtable_t object
  232:  */
  233: hashlist_t *hashlist_create(hashtable_hash_t hash, hashtable_equals_t equals,
  234: 							u_int size);
  235: 
  236: /**
  237:  * Creates an empty hash list object with sorted keys in each bucket.
  238:  *
  239:  * @param hash			hash function
  240:  * @param cmp			comparison function
  241:  * @param size			initial size
  242:  * @return				hashtable_t object.
  243:  */
  244: hashlist_t *hashlist_create_sorted(hashtable_hash_t hash,
  245: 								   hashtable_cmp_t cmp, u_int size);
  246: 
  247: #endif /** HASHTABLE_H_ @}*/