/*!
* \file
* <!--
- * Copyright (C) 2004 Giovanni Bajo
- * Copyright (C) 2004 Develer S.r.l. (http://www.develer.com/)
+ * Copyright 2004 Develer S.r.l. (http://www.develer.com/)
+ * Copyright 2004 Giovanni Bajo
* All Rights Reserved.
* -->
*
* \author Giovanni Bajo <rasky@develer.com>
*/
-/*
- * $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 <drv/kdebug.h>
+#include <debug.h>
#include <compiler.h>
+
#include <string.h>
*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;
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;
return hash ^ (hash >> 6) ^ (hash >> 13);
}
+
static HashNodePtr perform_lookup(struct HashTable* ht,
const void* key, uint8_t key_length)
{
// 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;
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;
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)
return true;
}
+
bool ht_insert_with_key(struct HashTable* ht, const void* key, uint8_t key_length, const void* data)
{
#ifdef _DEBUG
return insert(ht, key, key_length, data);
}
+
bool ht_insert(struct HashTable* ht, const void* data)
{
const void* key;
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);
{
int k;
int klen;
-
- do
+
+ do
{
klen = (rand() % 8) + 1;
for (k=0;k<klen;k++)
for (i=0;i<NUM_ELEMENTS;i++)
{
char *found1, *found2;
-
+
found1 = (char*)ht_find_str(&test1, data[i]);
if (strcmp(found1, data[i]) != 0)
{