X-Git-Url: https://codewiz.org/gitweb?a=blobdiff_plain;f=mware%2Fhashtable.c;h=d37973390fa98fe906ae440bffe966060a5a0eca;hb=4654a69f5df97af36ee5456d20cbccdc19012dc2;hp=603f30eb2bf5e3a7a4d42192f9ac28ad2f237447;hpb=5f7d3d48d08f112c1b601e1a37060beb665c3bd7;p=bertos.git diff --git a/mware/hashtable.c b/mware/hashtable.c old mode 100755 new mode 100644 index 603f30eb..d3797339 --- a/mware/hashtable.c +++ b/mware/hashtable.c @@ -1,8 +1,33 @@ -/*! +/** * \file * * @@ -59,64 +84,41 @@ * \author Giovanni Bajo */ -/* - * $Log$ - * Revision 1.1 2004/07/14 14:08:16 rasky - * Implementazione di una tabella hash - * - * Revision 1.13 2004/07/12 16:33:36 rasky - * Aggiunta nuova ASSERT2, con stringa di descrizione del problema (disabilitabile tramite una macro di configurazione) - * Modificato il codice del firmware per utilizzare ASSERT2 - * Modificato il progetto in modo da disabilitare le stringhe di errore nel target xROM-xRAM - * - * Revision 1.12 2004/06/14 15:15:24 rasky - * Cambiato key_data in un union invece di castare - * Aggiunto un ASSERT sull'indice calcolata nella key_internal_get_ptr - * - * Revision 1.11 2004/06/14 15:09:04 rasky - * Cambiati i messaggi di assert (è inutile citare il nome della funzione) - * - * Revision 1.10 2004/06/14 15:07:38 rasky - * Convertito il loop di calc_hash a interi (per farlo ottimizzare maggiormente) - * - * Revision 1.9 2004/06/14 14:59:40 rasky - * Rinominanta la macro di configurazione per rispettare il namespace, e aggiunta in un punto in cui mancava - * - * Revision 1.8 2004/06/12 15:18:05 rasky - * Nuova hashtable con chiave esterna o interna a scelta, come discusso - * - * Revision 1.7 2004/06/04 17:16:31 rasky - * Fixato un bug nel caso in cui la chiave ecceda la dimensione massima: il clamp non può essere fatto dentro la perform_lookup perché anche la ht_insert deve avere il valore clampato a disposizione per fare la memcpy - * - * Revision 1.6 2004/05/26 16:36:50 rasky - * Aggiunto il rationale per l'interfaccia degli iteratori - * - * Revision 1.5 2004/05/24 15:28:20 rasky - * Sistemata la documentazione, rimossa keycmp in favore della memcmp - * - */ +/*#* + *#* $Log$ + *#* Revision 1.8 2007/02/06 16:05:01 asterix + *#* Replaced ROTATE_* with ROT* defined in macros.h + *#* + *#* Revision 1.7 2006/07/19 12:56:27 bernie + *#* Convert to new Doxygen style. + *#* + *#* Revision 1.6 2006/06/01 12:27:39 marco + *#* Added utilities for protocols + *#* + *#*/ + #include "hashtable.h" -#include -#include +#include +#include +#include //ROTL(), ROTR(); + #include -#define ROTATE_LEFT_16(num, count) (((num) << (count)) | ((num) >> (16-(count)))) -#define ROTATE_RIGHT_16(num, count) ROTATE_LEFT_16(num, 16-(count)) typedef const void** HashNodePtr; #define NODE_EMPTY(node) (!*(node)) #define HT_HAS_INTERNAL_KEY(ht) (CONFIG_HT_OPTIONAL_INTERNAL_KEY && ht->flags.key_internal) -/*! For hash tables with internal keys, compute the pointer to the internal key for a given \a node. */ -INLINE uint8_t* key_internal_get_ptr(struct HashTable* ht, HashNodePtr node) +/** For hash tables with internal keys, compute the pointer to the internal key for a given \a node. */ +INLINE uint8_t *key_internal_get_ptr(struct HashTable *ht, HashNodePtr node) { uint8_t* key_buf = ht->key_data.mem; size_t index; // Compute the index of the node and use it to move within the whole key buffer index = node - &ht->mem[0]; - ASSERT(index < (1 << ht->max_elts_log2)); + ASSERT(index < (size_t)(1 << ht->max_elts_log2)); key_buf += index * (INTERNAL_KEY_MAX_LENGTH + 1); return key_buf; @@ -137,6 +139,7 @@ INLINE void node_get_key(struct HashTable* ht, HashNodePtr node, const void** ke *key = ht->key_data.hook(*node, key_length); } + INLINE bool node_key_match(struct HashTable* ht, HashNodePtr node, const void* key, uint8_t key_length) { const void* key2; @@ -147,6 +150,7 @@ INLINE bool node_key_match(struct HashTable* ht, HashNodePtr node, const void* k return (key_length == key2_length && memcmp(key, key2, key_length) == 0); } + static uint16_t calc_hash(const void* _key, uint8_t key_length) { const char* key = (const char*)_key; @@ -155,11 +159,12 @@ static uint16_t calc_hash(const void* _key, uint8_t key_length) int len = (int)key_length; for (i = 0; i < len; ++i) - hash = ROTATE_LEFT_16(hash, 4) ^ key[i]; + hash = ROTL(hash, 4) ^ key[i]; return hash ^ (hash >> 6) ^ (hash >> 13); } + static HashNodePtr perform_lookup(struct HashTable* ht, const void* key, uint8_t key_length) { @@ -181,12 +186,12 @@ static HashNodePtr perform_lookup(struct HashTable* ht, // Increment while going through the hash table in case of collision. // This implements the double-hash technique: we use the higher part // of the hash as a step increment instead of just going to the next - // element, to minimize the collisions. + // element, to minimize the collisions. // Notice that the number must be odd to be sure that the whole table - // is traversed. Actually MCD(table_size, step) must be 1, but + // is traversed. Actually MCD(table_size, step) must be 1, but // table_size is always a power of 2, so we just ensure that step is // never a multiple of 2. - step = (ROTATE_RIGHT_16(hash, ht->max_elts_log2) & mask) | 1; + step = (ROTR(hash, ht->max_elts_log2) & mask) | 1; do { @@ -209,11 +214,13 @@ static HashNodePtr perform_lookup(struct HashTable* ht, return NULL; } + void ht_init(struct HashTable* ht) { memset(ht->mem, 0, sizeof(ht->mem[0]) * (1 << ht->max_elts_log2)); } + static bool insert(struct HashTable* ht, const void* key, uint8_t key_length, const void* data) { HashNodePtr node; @@ -222,7 +229,7 @@ static bool insert(struct HashTable* ht, const void* key, uint8_t key_length, co return false; if (HT_HAS_INTERNAL_KEY(ht)) - key_length = MIN(key_length, INTERNAL_KEY_MAX_LENGTH); + key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH); node = perform_lookup(ht, key, key_length); if (!node) @@ -239,6 +246,7 @@ static bool insert(struct HashTable* ht, const void* key, uint8_t key_length, co return true; } + bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data) { #ifdef _DEBUG @@ -257,6 +265,7 @@ bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_lengt return insert(ht, key, key_length, data); } + bool ht_insert(struct HashTable* ht, const void* data) { const void* key; @@ -276,12 +285,13 @@ bool ht_insert(struct HashTable* ht, const void* data) return insert(ht, key, key_length, data); } + const void* ht_find(struct HashTable* ht, const void* key, uint8_t key_length) { HashNodePtr node; - + if (HT_HAS_INTERNAL_KEY(ht)) - key_length = MIN(key_length, INTERNAL_KEY_MAX_LENGTH); + key_length = MIN(key_length, (uint8_t)INTERNAL_KEY_MAX_LENGTH); node = perform_lookup(ht, key, key_length); @@ -323,8 +333,8 @@ static bool single_test(void) { int k; int klen; - - do + + do { klen = (rand() % 8) + 1; for (k=0;k