Bonjour,

Pour un projet perso, je me retrouve à avoir besoins d'un système de cache de données en mémoire. Un système typique clé/valeur. Mais pas seulement.

Le truc c'est qu'au lieu d'un simple système associatif, je veux un système hiérarchique, un tree en fait. La raison c'est que certaines opérations d'invalidation du cache doivent également automatiquement invalider les éléments "enfants". Quand je parle d'invalider le cache, c'est détruire les données pour une certaines clé et donc aussi les clés enfants.

L'autre contrainte, c'est que l'accès en lecture doit être rapide, si possible O(1) en moyenne.

Comment implémenter ce genre de solution ?

Voilà ce que j'ai fait:
Déjà pour commencer, j'ai trouvé cette class:
tree.hh: an STL-like C++ tree class
http://www.aei.mpg.de/~peekas/tree/

J'ai donc pensé à créer un nouveau container qui réunit à la fois ce genre de tree pour le storage et aussi un boost::unordered_map pour un accès rapide à partir d'une clé.

Le tree contient des shared_ptr sur ce genre de type:

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
struct data {
  std::string key;
  std::string value;
  // destucteur...
};
En parallèle j'ai un unordered_map<string key, weak_ptr<data> >

Quand j'ajoute une nouvelle entrée dans le tree, un std::pair<string, weak_ptr<data> > est également ajouté dans le map.

Le destructeur de la struct data se charge de détruire son entrée associée dans le unordered_map.
Le truc c'est que les 2 containers (tree et map) soient synchronisés, d'où l'usage de shared_ptr et weak_ptr pour que le ref counting ne soit pas corrompu.

Voilà ce que j'ai. Ca semble fonctionner pas mal mais je n'ai pas trop regardé pour ce qui est de l'exception safety..
(j'utilise gcc 4.5 donc les types utilisés sont dans std:: )

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <memory>
#include <algorithm>
#include <unordered_map>
#include <string>
#include <boost/noncopyable.hpp>
#include "tree.hh"
 
template<typename Key = std::string, typename Value = std::string>
struct cache : boost::noncopyable
{
	struct cache_node;
 
	typedef Key key_type;
	typedef Value value_type;
 
	typedef std::shared_ptr<cache_node> shared_node;
	typedef std::weak_ptr<cache_node> weak_node;
 
	typedef tree<shared_node> tree_type;
	typedef std::unordered_map<key_type, weak_node> table_type;
 
	typedef typename tree_type::iterator iterator;
 
	struct cache_node : boost::noncopyable
	{
		cache_node(const key_type& key, const value_type& value, table_type& lookup)
			: key(key), value(value), lookup(lookup)
		{ }
 
		~cache_node() { 
			typename table_type::iterator it = lookup.find(key);
			if (it != lookup.end()) {
				lookup.erase(it);
			}
		}
 
		key_type key;
		value_type value;
		table_type& lookup;
	};
 
 
	void add(const key_type& key, const value_type& value)
	{
		typename table_type::const_iterator it = table.find(key);
		if (it != table.end()) {
			quick_del(it);
		}
		typename tree_type::iterator top = nodes.begin();
		shared_node p(new cache_node(key, value, table));
		nodes.insert(top, p);
		table[key] = weak_node(p);
	}	
 
	void add(iterator& parent, const key_type& key, const value_type& value)
	{
		typename table_type::const_iterator it = table.find(key);
		if (it != table.end()) {
			quick_del(it);
		}
		shared_node p(new cache_node(key, value, table));
		nodes.append_child(parent, p);
		table[key] = weak_node(p);
	}	
 
	void add(const key_type& parent, const key_type& key, const value_type& value)
	{
		iterator itp = location(parent);
		if (valid(itp)) {
			add(itp, key, value);
		}
	}
 
	iterator location(const key_type& key) const
	{
		iterator itr = nodes.end();
		typename table_type::const_iterator it = table.find(key);
		if (it != table.end()) {
			shared_node s = it->second.lock();
			itr = find(nodes.begin(), nodes.end(), s);
		}
		return itr;
	}
 
	bool valid(const iterator& it) const
	{
		return it != nodes.end();
	}
 
 
	void del(const key_type& key)
	{
		typename table_type::const_iterator it = table.find(key);
		if (it != table.end()) {
			quick_del(it);
		}
	}	
 
	value_type get(const key_type& key) const
	{
		typename table_type::const_iterator it = table.find(key);
		if (it != table.end()) {
			shared_node s = it->second.lock();
			return s->value;
		}
		return value_type();
	}
 
	bool has(const key_type& key) const
	{
		return table.find(key) != table.end();
	}		
 
	void clear()
	{
		nodes.clear();
	}
 
private:
	void quick_del(const typename table_type::const_iterator& it)
	{
		typename tree_type::iterator itr;
		{
			shared_node s = it->second.lock();
			itr = find(nodes.begin(), nodes.end(), s);
		}
		if (itr != nodes.end()) {
			nodes.erase(itr);
		}
	}	
 
private:	
	table_type table;
	tree_type nodes;
 
};
Coté userland:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
 
cache<std::string, std::string> c;
 
c.add("key1", "value_1");
c.get("key1"); // "value_1"
 
c.add("key1", "key2", "value_2"); // key1 as parent
c.has("key2"); // true
 
c.del("key1"); // key1 et key2 sont détruits