2
Copyright (C) 2009, Torch Mobile Inc. and Linden Research, Inc. All rights reserved.
5
/* ***** BEGIN LICENSE BLOCK *****
6
* Version: MPL 1.1/GPL 2.0/LGPL 2.1
8
* The contents of this file are subject to the Mozilla Public License Version
9
* 1.1 (the "License"); you may not use this file except in compliance with
10
* the License. You may obtain a copy of the License at
11
* http://www.mozilla.org/MPL/
13
* Software distributed under the License is distributed on an "AS IS" basis,
14
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
15
* for the specific language governing rights and limitations under the
18
* The Original Code is Torch Mobile Inc. (http://www.torchmobile.com/) code
20
* The Initial Developer of the Original Code is:
21
* Benjamin Meyer (benjamin.meyer@torchmobile.com)
23
* Alternatively, the contents of this file may be used under the terms of
24
* either the GNU General Public License Version 2 or later (the "GPL"), or
25
* the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
26
* in which case the provisions of the GPL or the LGPL are applicable instead
27
* of those above. If you wish to allow use of your version of this file only
28
* under the terms of either the GPL or the LGPL, and not to allow others to
29
* use your version of this file under the terms of the MPL, indicate your
30
* decision by deleting the provisions above and replace them with the notice
31
* and other provisions required by the GPL or the LGPL. If you do not delete
32
* the provisions above, a recipient may use your version of this file under
33
* the terms of any one of the MPL, the GPL or the LGPL.
35
* ***** END LICENSE BLOCK ***** */
42
#include <qstringlist.h>
44
#if defined(TRIE_DEBUG)
49
A Trie tree (prefix tree) where the lookup takes m in the worst case.
51
The key is stored in *reverse* order
69
void insert(const QStringList &key, const T &value);
70
bool remove(const QStringList &key, const T &value);
71
QList<T> find(const QStringList &key) const;
74
inline bool contains(const QStringList &key) const;
75
inline bool isEmpty() const { return children.isEmpty() && values.isEmpty(); }
78
const Trie<T>* walkTo(const QStringList &key) const;
79
Trie<T>* walkTo(const QStringList &key, bool create = false);
81
template<class T1> friend QDataStream &operator<<(QDataStream &, const Trie<T1>&);
82
template<class T1> friend QDataStream &operator>>(QDataStream &, Trie<T1>&);
85
QStringList childrenKeys;
86
QList<Trie<T> > children;
98
void Trie<T>::clear() {
99
#if defined(TRIE_DEBUG)
100
qDebug() << "Trie::" << __FUNCTION__;
103
childrenKeys.clear();
108
bool Trie<T>::contains(const QStringList &key) const {
113
void Trie<T>::insert(const QStringList &key, const T &value) {
114
#if defined(TRIE_DEBUG)
115
qDebug() << "Trie::" << __FUNCTION__ << key << value;
117
Trie<T> *node = walkTo(key, true);
119
node->values.append(value);
123
bool Trie<T>::remove(const QStringList &key, const T &value) {
124
#if defined(TRIE_DEBUG)
125
qDebug() << "Trie::" << __FUNCTION__ << key << value;
127
Trie<T> *node = walkTo(key, true);
129
bool removed = node->values.removeOne(value);
133
// A faster implementation of removing nodes up the tree
134
// can be created if profile shows this to be slow
135
QStringList subKey = key;
136
while (node->values.isEmpty()
137
&& node->children.isEmpty()
138
&& !subKey.isEmpty()) {
139
QString currentLevelKey = subKey.first();
140
QStringList parentKey = subKey.mid(1);
141
Trie<T> *parent = walkTo(parentKey, false);
143
QStringList::iterator iterator;
144
iterator = qBinaryFind(parent->childrenKeys.begin(),
145
parent->childrenKeys.end(),
147
Q_ASSERT(iterator != parent->childrenKeys.end());
148
int index = iterator - parent->childrenKeys.begin();
149
parent->children.removeAt(index);
150
parent->childrenKeys.removeAt(index);
161
QList<T> Trie<T>::find(const QStringList &key) const {
162
#if defined(TRIE_DEBUG)
163
qDebug() << "Trie::" << __FUNCTION__ << key;
165
const Trie<T> *node = walkTo(key);
172
QList<T> Trie<T>::all() const {
173
#if defined(TRIE_DEBUG)
174
qDebug() << "Trie::" << __FUNCTION__;
176
QList<T> all = values;
177
for (int i = 0; i < children.count(); ++i)
178
all += children[i].all();
183
QDataStream &operator<<(QDataStream &out, const Trie<T>&trie) {
185
out << trie.childrenKeys;
186
out << trie.children;
187
Q_ASSERT(trie.childrenKeys.count() == trie.children.count());
192
QDataStream &operator>>(QDataStream &in, Trie<T> &trie) {
195
in >> trie.childrenKeys;
197
Q_ASSERT(trie.childrenKeys.count() == trie.children.count());
201
// Very fast const walk
203
const Trie<T>* Trie<T>::walkTo(const QStringList &key) const {
204
const Trie<T> *node = this;
205
QStringList::const_iterator childIterator;
206
QStringList::const_iterator begin, end;
208
int depth = key.count() - 1;
210
const QString currentLevelKey = key.at(depth--);
211
begin = node->childrenKeys.constBegin();
212
end = node->childrenKeys.constEnd();
213
childIterator = qBinaryFind(begin, end, currentLevelKey);
214
if (childIterator == end)
216
node = &node->children.at(childIterator - begin);
222
Trie<T>* Trie<T>::walkTo(const QStringList &key, bool create) {
223
QStringList::iterator iterator;
224
Trie<T> *node = this;
225
QStringList::iterator begin, end;
226
int depth = key.count() - 1;
228
const QString currentLevelKey = key.at(depth--);
229
begin = node->childrenKeys.begin();
230
end = node->childrenKeys.end();
231
iterator = qBinaryFind(begin, end, currentLevelKey);
232
#if defined(TRIE_DEBUG)
233
qDebug() << "\t" << node << key << currentLevelKey << node->childrenKeys;
236
if (iterator == end) {
239
iterator = qLowerBound(begin,
242
index = iterator - begin;
243
node->childrenKeys.insert(iterator, currentLevelKey);
244
node->children.insert(index, Trie<T>());
246
index = iterator - begin;
248
Q_ASSERT(index >= 0 && index < node->children.count());
249
node = &node->children[index];
added
removed
src/cookiejar/networkcookiejar/trie_p.h
