12#ifndef ARCANE_UTILS_HASHTABLE_H
13#define ARCANE_UTILS_HASHTABLE_H
17#include "arcane/utils/MultiBuffer.h"
18#include "arcane/utils/Array.h"
19#include "arcane/utils/HashFunction.h"
58 Integer nearestPrimeNumber(Integer n);
70 void _throwNotFound ARCANE_NORETURN()
const;
96template <
typename KeyType,
typename TraitsType>
102 typedef typename TraitsType::KeyTypeConstRef KeyTypeConstRef;
103 typedef typename TraitsType::KeyTypeValue KeyTypeValue;
156 KeyType hf = _hash(
id);
157 for (
HashData* i = m_buckets[hf]; i; i = i->m_next) {
175 if (new_table_size == 0) {
183 m_buckets.resize(new_table_size);
185 for (
Integer z = 0, zs = old_buckets.
size(); z < zs; ++z) {
186 for (
HashData* i = old_buckets[z]; i; i = i->m_next) {
187 _baseAdd(_hash(i->m_key), i->m_key, i);
199 for (
Integer z = 0, zs = old_buckets.
size(); z < zs; ++z) {
200 for (
HashData* i = old_buckets[z]; i;) {
203 _baseAdd(_hash(current->
m_key), current->
m_key, current);
210 inline Integer _hash(KeyTypeConstRef
id)
const
214 inline HashData* _baseLookupBucket(
Integer bucket, KeyTypeConstRef
id)
const
216 for (HashData* i = m_buckets[bucket]; i; i = i->m_next) {
226 if (i->m_key ==
id) {
227 m_buckets[bucket] = i->m_next;
231 for (; i->m_next; i = i->m_next) {
232 if (i->m_next->m_key ==
id) {
234 i->m_next = i->m_next->m_next;
242 inline HashData* _baseLookup(KeyTypeConstRef
id)
const
244 return _baseLookupBucket(_hash(
id),
id);
246 inline HashData* _baseRemove(KeyTypeConstRef
id)
248 return _baseRemoveBucket(_hash(
id),
id);
255 m_buckets[bucket] = hd;
261 UniqueArray<HashData*> m_buckets;
Integer size() const
Nombre d'éléments du vecteur.
void rehash()
Repositionne les données après changement de valeur des clés.
HashTableBaseT(Integer table_size, bool use_prime)
Crée une table de taille table_size.
void resize(Integer new_table_size, bool use_prime=false)
Redimensionne la table de hachage.
bool hasKey(KeyTypeConstRef id) const
true si une valeur avec la clé id est présente
void clear()
Supprime tous les éléments de la table.
Classe de base d'une table de hachage simple pour les entités.
HashTableBase(Integer table_size, bool use_prime)
Crée une table de taille table_size.
Integer m_nb_bucket
Nombre de buckets.
Integer nearestPrimeNumber(Integer n)
Retourne le nombre premier le plus proche de n par excès. Le nombre premier le plus proche et supérie...
Integer m_count
Nombre d'éléments.
Integer count() const
Nombre d'éléments dans la table.
Vecteur 1D de données avec sémantique par valeur (style STL).
-*- tab-width: 2; indent-tabs-mode: nil; coding: utf-8-with-signature -*-
Int32 Integer
Type représentant un entier.
void changeKey(const KeyType &new_key)
Change la valeur de la clé.
KeyTypeValue m_key
Clé de recherche.