khtml/misc/multimap.h

   1 /*
   2  * This file is part of the DOM implementation for KDE.
   3  *
   4  * Copyright (C) 2006 Allan Sandfeld Jensen (kde@carewolf.com)
   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
  27 #include <assert.h>
  28 #include <stdlib.h>
  29
  30 #include <QtCore/QHash>
  31 #include <QtCore/QList>
  32 #include <QtCore/QSet>
  33
  34 template<class T> class MultiMapPtrList;
  35
  36 template<class K, class T>
  37 class KMultiMap {
  38 public:
  39     typedef QSet<T*> Set;
  40     typedef QHash<K*, Set*> Map;
  41     typedef MultiMapPtrList<T*> List;
  42
  43     KMultiMap() {}
  44     ~KMultiMap() {
  45         qDeleteAll(map);
  46         map.clear();
  47     }
  48
  49     void insert(K* key, T* element)
  50     {
  51         Set *set = map.value(key);
  52         if (!set){
  53              set = new Set();
  54              map.insert(key, set);
  55         }
  56         if (!set->contains(element))
  57             set->insert(element);
  58     }
  59     void remove(K* key, T* element)
  60     {
  61         Set *set = map.value(key);
  62         if (set) {
  63             set->remove(element);
  64             if (set->isEmpty()) {
  65                 map.remove(key);
  66                 delete set;
  67             }
  68         }
  69     }
  70     void remove(K* key) {
  71         Set *set = map.value(key);
  72         if (set) {
  73             map.remove(key);
  74             delete set;
  75         }
  76     }
  77     Set* find(K* key) {
  78         return map.value(key);
  79     }
  80 private:
  81     Map map;
  82 };
  83
  84 static inline unsigned int stupidHash(void* ptr)
  85 {
  86     unsigned long val = (unsigned long)ptr;
  87     // remove alignment and multiply by a prime unlikely to be a factor of size
  88     val = (val >> 4) * 1237;
  89     return val;
  90 }
  91
  92 #define START_PTRLIST_SIZE 4
  93 #define MAX_PTRLIST_SIZE 27
  94
  95 class PtrListEntry {
  96 public:
  97     PtrListEntry(unsigned int log_size) : count(0), log_size(log_size), search(log_size), next(0) {
  98 //         entry = new T* [size];
  99         assert(log_size < MAX_PTRLIST_SIZE);
 100         entry = (void**)calloc ((1<<log_size), sizeof(void*));
 101     }
 102     ~PtrListEntry() {
 103 //         delete[] entry;
 104         free(entry);
 105     }
 106     bool insert(void* e) {
 107         unsigned int t_size = size();
 108         if (count == t_size) return false;
 109         unsigned int hash = stupidHash(e);
 110         void** firstFree = 0;
 111         // Only let elements be placed 'search' spots from their hash
 112         for(unsigned int j=0; j<search; j++) {
 113             unsigned int i = (hash + j) & (t_size-1); // modulo size
 114             // We need check to all hashes in 'search' to garuantee uniqueness
 115             if (entry[i] == 0) {
 116                 if (!firstFree)
 117                     firstFree = entry + i;
 118             } else
 119             if (entry[i] == e)
 120                 return true;
 121         }
 122         if (firstFree) {
 123             *firstFree = e;
 124             count++;
 125             return true;
 126         }
 127         // We had more than 'search' collisions
 128         if (count < (t_size/3)*2) {
 129             // only 2/3 full => increase search
 130             unsigned int s = search *2;
 131             if (s >= t_size) s = t_size;
 132             search = s;
 133             return insert(e);
 134         }
 135         return false;
 136     }
 137     // Insert another smaller set into this one
 138     // Is only garuantied to succede when this PtrList is new
 139     void insert(PtrListEntry* listEntry) {
 140         assert(size() >= listEntry->count * 2);
 141         unsigned int old_size = 1U << listEntry->log_size;
 142         for(unsigned int i = 0; i < old_size; i++) {
 143             bool s = true;
 144             void *e = listEntry->entry[i];
 145             if (e) s = insert(e);
 146             assert(s);
 147         }
 148     }
 149     bool remove(void* e) {
 150         if (count == 0) return false;
 151         unsigned int size = (1U<<log_size);
 152         unsigned int hash = stupidHash(e);
 153         // Elements are at most placed 'search' spots from their hash
 154         for(unsigned int j=0; j<search; j++) {
 155             unsigned int i = (hash + j) & (size-1); // modulo size
 156             if (entry[i] == e) {
 157                 entry[i] = 0;
 158                 count--;
 159                 return true;
 160             }
 161         }
 162         return false;
 163     }
 164     bool contains(void* e) {
 165         if (count == 0) return false;
 166         unsigned int t_size = size();
 167         unsigned int hash = stupidHash(e);
 168         // Elements are at most placed 'search' spots from their hash
 169         for(unsigned int j=0; j<search; j++) {
 170             unsigned int i = (hash + j) & (t_size-1); // modulo size
 171             if (entry[i] == e) return true;
 172         }
 173         return false;
 174     }
 175     void* at(unsigned int i) const {
 176         assert (i < (1U<<log_size));
 177         return entry[i];
 178     }
 179     bool isEmpty() const {
 180         return count == 0;
 181     }
 182     bool isFull() const {
 183         return count == size();
 184     }
 185     unsigned int size() const {
 186         return (1U << log_size);
 187     }
 188
 189     unsigned int count;
 190     const unsigned short log_size;
 191     unsigned short search;
 192     PtrListEntry *next;
 193     void** entry;
 194 };
 195
 196 // An unsorted and unique PtrList that is implement as a linked list of hash-sets
 197 // Optimized for fast insert and fast lookup
 198 template<class T>
 199 class MultiMapPtrList {
 200 public:
 201     MultiMapPtrList(unsigned int init_size= 16) : m_first(0), m_current(0), m_pos(0) {
 202         assert(init_size > 0);
 203         unsigned int s = init_size - 1;
 204         unsigned int log_size = 0;
 205         while (s > 0) {
 206             log_size++;
 207             s = s >> 1;
 208         }
 209         m_first = new PtrListEntry(log_size);
 210     }
 211     MultiMapPtrList(const MultiMapPtrList& ptrList) : m_first(0), m_current(0), m_pos(0) {
 212         unsigned int t_count = ptrList.count();
 213         unsigned int log_size = 0;
 214         while (t_count > 0) {
 215             log_size++;
 216             t_count = t_count >> 1;
 217         }
 218         // At least as large as the largest ptrListEntry in the original
 219         if (t_count < ptrList.m_first->log_size) log_size = ptrList.m_first->log_size;
 220         m_first = new PtrListEntry(log_size);
 221
 222         PtrListEntry *t_current = ptrList.m_first;
 223         while (t_current) {
 224             unsigned int t_size = t_current->size();
 225             for(unsigned int i=0; i < t_size; i++) {
 226                 void* e = t_current->at(i);
 227                 if (e != 0) {
 228                     bool t = m_first->insert(e);
 229                     if (!t) {
 230                         // Make a new, but keep the size
 231                         PtrListEntry *t_new = new PtrListEntry(log_size);
 232                         t_new->insert(e);
 233                         t_new->next = m_first;
 234                         m_first = t_new;
 235                     }
 236                 }
 237             }
 238             t_current = t_current->next;
 239         }
 240     }
 241     ~MultiMapPtrList() {
 242         PtrListEntry *t_next, *t_current = m_first;
 243         while (t_current) {
 244             t_next = t_current->next;
 245             delete t_current;
 246             t_current = t_next;
 247         }
 248     }
 249     void append(T* e) {
 250         PtrListEntry *t_last = 0, *t_current = m_first;
 251         int count = 0;
 252         while (t_current) {
 253             if (t_current->insert(e)) return;
 254             t_last = t_current;
 255             t_current = t_current->next;
 256             count++;
 257         }
 258         // Create new hash-set
 259         unsigned int newsize = m_first->log_size+1;
 260         if (newsize > MAX_PTRLIST_SIZE) newsize = MAX_PTRLIST_SIZE;
 261         t_current = new PtrListEntry(newsize);
 262         bool t = t_current->insert(e);
 263         assert(t);
 264         // Prepend it to the list, for insert effeciency
 265         t_current->next = m_first;
 266         m_first = t_current;
 267         // ### rehash some of the smaller sets
 268         /*
 269         if (count > 4) {
 270             // rehash the last in the new
 271             t_current->insert(t_last);
 272         }*/
 273     }
 274     void remove(T* e) {
 275         PtrListEntry *t_next, *t_last = 0, *t_current = m_first;
 276         // Remove has to check every PtrEntry.
 277         while (t_current) {
 278             t_next = t_current->next;
 279             if (t_current->remove(e) && t_current->isEmpty()) {
 280                 if (t_last) {
 281                     t_last->next = t_current->next;
 282                 }
 283                 else {
 284                     assert (m_first == t_current);
 285                     m_first = t_current->next;
 286                 }
 287                 delete t_current;
 288             } else {
 289                 t_last = t_current;
 290             }
 291             t_current = t_next;
 292         }
 293     }
 294     bool contains(T* e) {
 295         PtrListEntry *t_current = m_first;
 296         while (t_current) {
 297             if (t_current->contains(e)) return true;
 298             t_current = t_current->next;
 299         }
 300         return false;
 301     }
 302     bool isEmpty() {
 303         if (!m_first) return true;
 304         PtrListEntry *t_current = m_first;
 305         while (t_current) {
 306             if (!t_current->isEmpty()) return false;
 307             t_current = t_current->next;
 308         }
 309         return true;
 310     }
 311     unsigned int count() const {
 312         unsigned int t_count = 0;
 313         PtrListEntry *t_current = m_first;
 314         while (t_current) {
 315             t_count += t_current->count;
 316             t_current = t_current->next;
 317         }
 318         return t_count;
 319     }
 320 // Iterator functions:
 321     T* first() {
 322         m_current = m_first;
 323         m_pos = 0;
 324         // skip holes
 325         if (m_current && !m_current->at(m_pos))
 326             return next();
 327         else
 328             return current();
 329     }
 330     T* current() {
 331         if (!m_current)
 332             return (T*)0;
 333         else
 334             return (T*)m_current->at(m_pos);
 335     }
 336     T* next() {
 337         if (!m_current) return (T*)0;
 338         m_pos++;
 339         if (m_pos >= m_current->size()) {
 340             m_current = m_current->next;
 341             m_pos = 0;
 342         }
 343         // skip holes
 344         if (m_current && !m_current->at(m_pos))
 345             return next();
 346         else
 347             return current();
 348     }
 349 private:
 350     PtrListEntry *m_first;
 351 // iteration:
 352     PtrListEntry *m_current;
 353     unsigned int m_pos;
 354 };
 355
 356 #undef START_PTRLIST_SIZE
 357 #undef MAX_PTRLIST_SIZE
 358 #endif