KHtml

multimap.h
1 /*
2  * This file is part of the DOM implementation for KDE.
3  *
4  * Copyright (C) 2006 Allan Sandfeld Jensen ([email protected])
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Library General Public
8  * License as published by the Free Software Foundation; either
9  * version 2 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Library General Public License for more details.
15  *
16  * You should have received a copy of the GNU Library General Public License
17  * along with this library; see the file COPYING.LIB. If not, write to
18  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19  * Boston, MA 02110-1301, USA.
20  *
21  */
22 
23 #ifndef _MultiMap_h_
24 #define _MultiMap_h_
25 
26 #include <assert.h>
27 #include <stdlib.h>
28 
29 #include <QHash>
30 #include <QList>
31 #include <QSet>
32 
33 template<class T> class MultiMapPtrList;
34 
35 template<class K, class T>
36 class KMultiMap
37 {
38 public:
39  typedef QSet<T *> Set;
40  typedef QHash<K *, Set *> Map;
41  typedef MultiMapPtrList<T *> List;
42 
43  KMultiMap() {}
44  ~KMultiMap()
45  {
46  qDeleteAll(map);
47  map.clear();
48  }
49 
50  void insert(K *key, T *element)
51  {
52  Set *set = map.value(key);
53  if (!set) {
54  set = new Set();
55  map.insert(key, set);
56  }
57  if (!set->contains(element)) {
58  set->insert(element);
59  }
60  }
61  void remove(K *key, T *element)
62  {
63  Set *set = map.value(key);
64  if (set) {
65  set->remove(element);
66  if (set->isEmpty()) {
67  map.remove(key);
68  delete set;
69  }
70  }
71  }
72  void remove(K *key)
73  {
74  Set *set = map.value(key);
75  if (set) {
76  map.remove(key);
77  delete set;
78  }
79  }
80  Set *find(K *key)
81  {
82  return map.value(key);
83  }
84 private:
85  Map map;
86 };
87 
88 static inline unsigned int stupidHash(void *ptr)
89 {
90  unsigned long val = (unsigned long)ptr;
91  // remove alignment and multiply by a prime unlikely to be a factor of size
92  val = (val >> 4) * 1237;
93  return val;
94 }
95 
96 #define START_PTRLIST_SIZE 4
97 #define MAX_PTRLIST_SIZE 27
98 
99 class PtrListEntry
100 {
101 public:
102  PtrListEntry(unsigned int log_size) : count(0), log_size(log_size), search(log_size), next(0)
103  {
104 // entry = new T* [size];
105  assert(log_size < MAX_PTRLIST_SIZE);
106  entry = (void **)calloc((1 << log_size), sizeof(void *));
107  }
108  ~PtrListEntry()
109  {
110 // delete[] entry;
111  free(entry);
112  }
113  bool insert(void *e)
114  {
115  unsigned int t_size = size();
116  if (count == t_size) {
117  return false;
118  }
119  unsigned int hash = stupidHash(e);
120  void **firstFree = 0;
121  // Only let elements be placed 'search' spots from their hash
122  for (unsigned int j = 0; j < search; j++) {
123  unsigned int i = (hash + j) & (t_size - 1); // modulo size
124  // We need check to all hashes in 'search' to garuantee uniqueness
125  if (entry[i] == 0) {
126  if (!firstFree) {
127  firstFree = entry + i;
128  }
129  } else if (entry[i] == e) {
130  return true;
131  }
132  }
133  if (firstFree) {
134  *firstFree = e;
135  count++;
136  return true;
137  }
138  // We had more than 'search' collisions
139  if (count < (t_size / 3) * 2) {
140  // only 2/3 full => increase search
141  unsigned int s = search * 2;
142  if (s >= t_size) {
143  s = t_size;
144  }
145  search = s;
146  return insert(e);
147  }
148  return false;
149  }
150  // Insert another smaller set into this one
151  // Is only garuantied to succede when this PtrList is new
152  void insert(PtrListEntry *listEntry)
153  {
154  assert(size() >= listEntry->count * 2);
155  unsigned int old_size = 1U << listEntry->log_size;
156  for (unsigned int i = 0; i < old_size; i++) {
157  bool s = true;
158  void *e = listEntry->entry[i];
159  if (e) {
160  s = insert(e);
161  }
162  assert(s);
163  }
164  }
165  bool remove(void *e)
166  {
167  if (count == 0) {
168  return false;
169  }
170  unsigned int size = (1U << log_size);
171  unsigned int hash = stupidHash(e);
172  // Elements are at most placed 'search' spots from their hash
173  for (unsigned int j = 0; j < search; j++) {
174  unsigned int i = (hash + j) & (size - 1); // modulo size
175  if (entry[i] == e) {
176  entry[i] = 0;
177  count--;
178  return true;
179  }
180  }
181  return false;
182  }
183  bool contains(void *e)
184  {
185  if (count == 0) {
186  return false;
187  }
188  unsigned int t_size = size();
189  unsigned int hash = stupidHash(e);
190  // Elements are at most placed 'search' spots from their hash
191  for (unsigned int j = 0; j < search; j++) {
192  unsigned int i = (hash + j) & (t_size - 1); // modulo size
193  if (entry[i] == e) {
194  return true;
195  }
196  }
197  return false;
198  }
199  void *at(unsigned int i) const
200  {
201  assert(i < (1U << log_size));
202  return entry[i];
203  }
204  bool isEmpty() const
205  {
206  return count == 0;
207  }
208  bool isFull() const
209  {
210  return count == size();
211  }
212  unsigned int size() const
213  {
214  return (1U << log_size);
215  }
216 
217  unsigned int count;
218  const unsigned short log_size;
219  unsigned short search;
220  PtrListEntry *next;
221  void **entry;
222 };
223 
224 // An unsorted and unique PtrList that is implement as a linked list of hash-sets
225 // Optimized for fast insert and fast lookup
226 template<class T>
227 class MultiMapPtrList
228 {
229 public:
230  MultiMapPtrList(unsigned int init_size = 16) : m_first(0), m_current(0), m_pos(0)
231  {
232  assert(init_size > 0);
233  unsigned int s = init_size - 1;
234  unsigned int log_size = 0;
235  while (s > 0) {
236  log_size++;
237  s = s >> 1;
238  }
239  m_first = new PtrListEntry(log_size);
240  }
241  MultiMapPtrList(const MultiMapPtrList &ptrList) : m_first(0), m_current(0), m_pos(0)
242  {
243  unsigned int t_count = ptrList.count();
244  unsigned int log_size = 0;
245  while (t_count > 0) {
246  log_size++;
247  t_count = t_count >> 1;
248  }
249  // At least as large as the largest ptrListEntry in the original
250  if (t_count < ptrList.m_first->log_size) {
251  log_size = ptrList.m_first->log_size;
252  }
253  m_first = new PtrListEntry(log_size);
254 
255  PtrListEntry *t_current = ptrList.m_first;
256  while (t_current) {
257  unsigned int t_size = t_current->size();
258  for (unsigned int i = 0; i < t_size; i++) {
259  void *e = t_current->at(i);
260  if (e != 0) {
261  bool t = m_first->insert(e);
262  if (!t) {
263  // Make a new, but keep the size
264  PtrListEntry *t_new = new PtrListEntry(log_size);
265  t_new->insert(e);
266  t_new->next = m_first;
267  m_first = t_new;
268  }
269  }
270  }
271  t_current = t_current->next;
272  }
273  }
274  ~MultiMapPtrList()
275  {
276  PtrListEntry *t_next, *t_current = m_first;
277  while (t_current) {
278  t_next = t_current->next;
279  delete t_current;
280  t_current = t_next;
281  }
282  }
283  void append(T *e)
284  {
285  PtrListEntry *t_last = 0, *t_current = m_first;
286  int count = 0;
287  while (t_current) {
288  if (t_current->insert(e)) {
289  return;
290  }
291  t_last = t_current;
292  t_current = t_current->next;
293  count++;
294  }
295  // Create new hash-set
296  unsigned int newsize = m_first->log_size + 1;
297  if (newsize > MAX_PTRLIST_SIZE) {
298  newsize = MAX_PTRLIST_SIZE;
299  }
300  t_current = new PtrListEntry(newsize);
301  bool t = t_current->insert(e);
302  assert(t);
303  // Prepend it to the list, for insert effeciency
304  t_current->next = m_first;
305  m_first = t_current;
306  // ### rehash some of the smaller sets
307  /*
308  if (count > 4) {
309  // rehash the last in the new
310  t_current->insert(t_last);
311  }*/
312  }
313  void remove(T *e)
314  {
315  PtrListEntry *t_next, *t_last = 0, *t_current = m_first;
316  // Remove has to check every PtrEntry.
317  while (t_current) {
318  t_next = t_current->next;
319  if (t_current->remove(e) && t_current->isEmpty()) {
320  if (t_last) {
321  t_last->next = t_current->next;
322  } else {
323  assert(m_first == t_current);
324  m_first = t_current->next;
325  }
326  delete t_current;
327  } else {
328  t_last = t_current;
329  }
330  t_current = t_next;
331  }
332  }
333  bool contains(T *e)
334  {
335  PtrListEntry *t_current = m_first;
336  while (t_current) {
337  if (t_current->contains(e)) {
338  return true;
339  }
340  t_current = t_current->next;
341  }
342  return false;
343  }
344  bool isEmpty()
345  {
346  if (!m_first) {
347  return true;
348  }
349  PtrListEntry *t_current = m_first;
350  while (t_current) {
351  if (!t_current->isEmpty()) {
352  return false;
353  }
354  t_current = t_current->next;
355  }
356  return true;
357  }
358  unsigned int count() const
359  {
360  unsigned int t_count = 0;
361  PtrListEntry *t_current = m_first;
362  while (t_current) {
363  t_count += t_current->count;
364  t_current = t_current->next;
365  }
366  return t_count;
367  }
368 // Iterator functions:
369  T *first()
370  {
371  m_current = m_first;
372  m_pos = 0;
373  // skip holes
374  if (m_current && !m_current->at(m_pos)) {
375  return next();
376  } else {
377  return current();
378  }
379  }
380  T *current()
381  {
382  if (!m_current) {
383  return (T *)0;
384  } else {
385  return (T *)m_current->at(m_pos);
386  }
387  }
388  T *next()
389  {
390  if (!m_current) {
391  return (T *)0;
392  }
393  m_pos++;
394  if (m_pos >= m_current->size()) {
395  m_current = m_current->next;
396  m_pos = 0;
397  }
398  // skip holes
399  if (m_current && !m_current->at(m_pos)) {
400  return next();
401  } else {
402  return current();
403  }
404  }
405 private:
406  PtrListEntry *m_first;
407 // iteration:
408  PtrListEntry *m_current;
409  unsigned int m_pos;
410 };
411 
412 #undef START_PTRLIST_SIZE
413 #undef MAX_PTRLIST_SIZE
414 #endif
MESSAGECORE_EXPORT KMime::Content * next(KMime::Content *node, bool allowChildren=true)
StandardShortcut find(const QKeySequence &keySeq)
bool insert(Part *part, qint64 *insertId=nullptr)
QFuture< void > map(Sequence &sequence, MapFunctor function)
This file is part of the KDE documentation.
Documentation copyright © 1996-2021 The KDE developers.
Generated on Tue Oct 26 2021 22:48:06 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.