IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)

Implémentation d'une table de hachage à référence faible avec Qt

Une table de hachage à référence faible contient des paires clé-valeur sans que l'on puisse les atteindre. On en recense quatre types :

  • la clé est une référence faible ;
  • la valeur est une référence faible ;
  • la clé ou la valeur est une référence faible ;
  • la clé et la valeur sont des références faibles.

Dans cet article, on propose une implémentation basée sur Qt pour le second type : une table de hachage où la valeur est une référence faible. Ceci signifie qu'une paire clé-valeur sera automatiquement enlevées de la table dès que la valeur ne sera plus utilisée dans le programme.

Ce type de structure est utile pour réduire l'utilisation mémoire en partageant les structures de données sans fuite de mémoire.

6 commentaires Donner une note à l´article (5)

Article lu   fois.

Les deux auteurs

Profil ProSite personnel

Profil ProSite personnel

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. L'article original

Cet article est une adaptation en langue française de A Weak Hash Table implementation with Qt.

II. Le principe

L'implémentation proposée utilise les pointeurs intelligents de Qt suivants :

  • QSharedPointer : cette classe contient une référence forte sur un pointeur partagé. C'est automatique, ce qui signifie qu'elle va supprimer le pointeur contenu quand il sort de portée, pourvu qu'aucun autre QSharedPointer ne le référence ;
  • QWeakPointer : ette classe contient une référence faible sur un pointeur.

Comme le lecteur attentif l'aura remarqué, on utilisera des références faibles comme valeurs dans la table de hachage et des références fortes dans le reste du programme.

La prochaine chose à faire est de détecter dans la table le moment où les valeurs deviennent nulles (c'est-à-dire quand l'objet pointé est détruit parce qu'il n'a plus aucune référence). L'implémentation proposée requiert que les valeurs stockées dans la table héritent de QObject ; c'est très pratique car, ainsi, ils émettront un signal destroyed(QObject*) juste avant la destruction proprement dite. On peut alors facilement connecter ce signal à un slot dans la table pour enlever la paire correspondante.

Un dernier problème : quand on reçoit ce signal, trouver la paire correspondante dans la table est normalement très inefficace. En réalité, une table de hachage est optimisée pour une recherche rapide par la clé, non par la valeur. Pour résoudre ce problème, on utilise le système de propriétés dynamiques de QObject : la table de hachage définira une nouvelle propriété dynamique pour les QObject qui y sont insérés. Cette propriété indique la clé correspondante dans la table. Une fois ceci fait, la table doit simplement lire cette propriété quand un QObject est détruit pour le trouver en temps constant (au lieu d'un temps linéaire). Ceci apporte cependant une limitation : la clé doit être stockable dans un QVariant, le type de données des propriétés dynamiques. L'implémentation fournie dans cet article utilise le type QString pour les clés, mais ceci peut être facilement adapté.

III. L'implémentation

Voici le code de cette table de hachage à référence faible.

L'en-tête
TéléchargerSélectionnez
#include <QHash>
#include <QString>
#include <QStringList>
#include <QWeakPointer>
#include <QSharedPointer>
#include <QObject>
 
/*!
 * Implémentation d'une table de hachage à référence faible avec Qt. 
 * Chaque paire clé-valeur est automatiquement retirée de la table
 * quand la valeur n'est plus utilisée dans le reste du programme. 
 */
class WeakHashTable: public QObject
{
  Q_OBJECT
 
public:
  WeakHashTable(QObject *parent = 0);
  void insert(const QString &key, const QSharedPointer<QObject> &value);
  QSharedPointer<QObject> take(const QString &key);
  bool remove(const QString &key);
 
  const QSharedPointer<QObject> value(const QString &key) const;
  const QSharedPointer<QObject> operator[](const QString &key) const;
 
  inline int size() const { return m_table.size(); }
  inline bool contains(const QString &key) const { 
    return m_table.contains(key); 
  }
  inline bool isEmpty() const { return m_table.isEmpty(); }
  inline QStringList keys() const { return m_table.keys(); }
 
private slots:
  void removeValue(QObject* value);
 
private:
  void disconnectSignals(const QSharedPointer<QObject> &ptr) const;
 
private:
  QHash< QString, QWeakPointer<QObject> > m_table;
};
L'implémentation
TéléchargerSélectionnez
#include <QVariant>
#include <QDebug>
#include "weakhashtable.h"
 
const char* PROPERTY_KEY = "WeakHashTableKey";
 
WeakHashTable::WeakHashTable(QObject *parent): QObject(parent)
{
}
 
void WeakHashTable::insert(const QString &key, const
     QSharedPointer<QObject>& value)
{
  Q_ASSERT(!value.isNull());
  // On s'assure que la valeur est retirée de la table
  // à la destruction. 
  value->setProperty(PROPERTY_KEY, key);
  connect(value.data(), SIGNAL(destroyed(QObject*)), 
          SLOT(removeValue(QObject*)));
  // Insertion proprement dite. 
  m_table.insert(key, value.toWeakRef());
}
 
const QSharedPointer<QObject> WeakHashTable::value(const QString &key) const
{
  return m_table.value(key).toStrongRef();
}
 
void WeakHashTable::removeValue(QObject *value)
{
  const QString key = value->property(PROPERTY_KEY).toString();
  qDebug() << "Removing value with key" << key;
  Q_ASSERT(!key.isEmpty());
  Q_ASSERT(m_table.contains(key));
  if(!key.isNull())
    m_table.remove(key);
}
 
bool WeakHashTable::remove(const QString &key)
{
  QSharedPointer<QObject> ptr = m_table.take(key).toStrongRef();
  if(ptr.isNull())
    return false;
  disconnectSignals(ptr);
  return true;
}
 
QSharedPointer<QObject> WeakHashTable::take(const QString &key)
{
  QSharedPointer<QObject> ptr = m_table.take(key).toStrongRef();
  if(!ptr.isNull())
    disconnectSignals(ptr);
  return ptr;
}
 
const QSharedPointer<QObject> WeakHashTable::operator[](const
      QString &key) const
{
  return m_table[key].toStrongRef();
}
 
void WeakHashTable::disconnectSignals(const
     QSharedPointer<QObject> &ptr) const
{
  Q_ASSERT(!ptr.isNull());
  disconnect(ptr.data(), SIGNAL(destroyed(QObject*)), 
             this, SLOT(removeValue(QObject*)), Qt::DirectConnection);
}

IV. Un exemple d'utilisation

On l'utilise comme ceci :

 
Sélectionnez
WeakHashTable h;
// La classe Contact hérite de QObject. 
QSharedPointer<Contact> friend1 = 
  QSharedPointer<Contact>(new Contact("Bob"));
h.insert("Bob", friend1);
// On la récupère alors. 
QSharedPointer<Contact> myfriend = h.value("Bob");

V. Remerciements

Merci à Guillaume Belz et Stoyak pour leur relecture attentive !

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

Copyright © 2012 Christophe Dumez. Aucune reproduction, même partielle, ne peut être faite de ce site ni de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.