X-Git-Url: https://codewiz.org/gitweb?a=blobdiff_plain;f=mware%2Fhashtable.c;h=72aae36d4aa0cbe1913edf00a7e7b4bcc68dfbe8;hb=0f018838e0d5130255728bbf3aa69e44e4954239;hp=603f30eb2bf5e3a7a4d42192f9ac28ad2f237447;hpb=5f7d3d48d08f112c1b601e1a37060beb665c3bd7;p=bertos.git diff --git a/mware/hashtable.c b/mware/hashtable.c index 603f30eb..72aae36d 100755 --- a/mware/hashtable.c +++ b/mware/hashtable.c @@ -1,8 +1,8 @@ /*! * \file * * @@ -59,45 +59,45 @@ * \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.4 2004/12/08 09:42:30 bernie + *#* Suppress warning. + *#* + *#* Revision 1.3 2004/10/03 20:43:22 bernie + *#* Import changes from sc/firmware. + *#* + *#* 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 + *#* + *#*/ + #include "hashtable.h" -#include +#include #include + #include @@ -137,6 +137,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 +148,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; @@ -160,6 +162,7 @@ static uint16_t calc_hash(const void* _key, uint8_t key_length) return hash ^ (hash >> 6) ^ (hash >> 13); } + static HashNodePtr perform_lookup(struct HashTable* ht, const void* key, uint8_t key_length) { @@ -181,9 +184,9 @@ 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; @@ -209,11 +212,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 +227,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 +244,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 +263,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 +283,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 +331,8 @@ static bool single_test(void) { int k; int klen; - - do + + do { klen = (rand() % 8) + 1; for (k=0;k