summaryrefslogtreecommitdiffstats
path: root/khtml/misc/multimap.h
diff options
context:
space:
mode:
Diffstat (limited to 'khtml/misc/multimap.h')
-rw-r--r--khtml/misc/multimap.h345
1 files changed, 345 insertions, 0 deletions
diff --git a/khtml/misc/multimap.h b/khtml/misc/multimap.h
new file mode 100644
index 000000000..08cb11879
--- /dev/null
+++ b/khtml/misc/multimap.h
@@ -0,0 +1,345 @@
+/*
+ * This file is part of the DOM implementation for KDE.
+ *
+ * Copyright (C) 2006 Allan Sandfeld Jensen (kde@carewolf.com)
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB. If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ *
+ */
+
+#ifndef _MultiMap_h_
+#define _MultiMap_h_
+
+#include <qptrdict.h>
+#include <qptrlist.h>
+#include <assert.h>
+#include <stdlib.h>
+
+template<class T> class MultiMapPtrList;
+
+// KMultiMap is an implementaition of a Map with multiple entries per key.
+// It is originally designed to work like a shell for QPtrDict<QPtrList>, but
+// QPtrList have been replaced with a much faster hash set.
+template<class T>
+class KMultiMap {
+public:
+ KMultiMap() : dict(257) { dict.setAutoDelete(true); }
+ ~KMultiMap() {};
+
+ typedef MultiMapPtrList<T> List;
+
+ void append(void* key, T* element) {
+ List *list = dict.find(key);
+ if (!list){
+ list = new List(8);
+ dict.insert(key, list);
+ }
+ list->append(element);
+ }
+ void remove(void* key, T* element) {
+ List *list = dict.find(key);
+ if (list) {
+ list->remove(element);
+ if (list->isEmpty()) dict.remove(key);
+ }
+ }
+ void remove(void* key) {
+ dict.remove(key);
+ }
+ List* find(void* key) {
+ return dict.find(key);
+ }
+private:
+ QPtrDict<List> dict;
+
+};
+
+static inline unsigned int stupidHash(void* ptr)
+{
+ unsigned long val = (unsigned long)ptr;
+ // remove alignment and multiply by a prime unlikely to be a factor of size
+ val = (val >> 4) * 1237;
+ return val;
+}
+
+#define START_PTRLIST_SIZE 4
+#define MAX_PTRLIST_SIZE 27
+
+class PtrListEntry {
+public:
+ PtrListEntry(unsigned int log_size) : count(0), log_size(log_size), search(log_size), next(0) {
+// entry = new T* [size];
+ assert(log_size < MAX_PTRLIST_SIZE);
+ entry = (void**)calloc ((1<<log_size), sizeof(void*));
+ }
+ ~PtrListEntry() {
+// delete[] entry;
+ free(entry);
+ }
+ bool insert(void* e) {
+ unsigned int t_size = size();
+ if (count == t_size) return false;
+ unsigned int hash = stupidHash(e);
+ void** firstFree = 0;
+ // Only let elements be placed 'search' spots from their hash
+ for(unsigned int j=0; j<search; j++) {
+ unsigned int i = (hash + j) & (t_size-1); // modulo size
+ // We need check to all hashes in 'search' to garuantee uniqueness
+ if (entry[i] == 0) {
+ if (!firstFree)
+ firstFree = entry + i;
+ } else
+ if (entry[i] == e)
+ return true;
+ }
+ if (firstFree) {
+ *firstFree = e;
+ count++;
+ return true;
+ }
+ // We had more than 'search' collisions
+ if (count < (t_size/3)*2) {
+ // only 2/3 full => increase search
+ unsigned int s = search *2;
+ if (s >= t_size) s = t_size;
+ search = s;
+ return insert(e);
+ }
+ return false;
+ }
+ // Insert another smaller set into this one
+ // Is only garuantied to succede when this PtrList is new
+ void insert(PtrListEntry* listEntry) {
+ assert(size() >= listEntry->count * 2);
+ unsigned int old_size = 1U << listEntry->log_size;
+ for(unsigned int i = 0; i < old_size; i++) {
+ bool s = true;
+ void *e = listEntry->entry[i];
+ if (e) s = insert(e);
+ assert(s);
+ }
+ }
+ bool remove(void* e) {
+ if (count == 0) return false;
+ unsigned int size = (1U<<log_size);
+ unsigned int hash = stupidHash(e);
+ // Elements are at most placed 'search' spots from their hash
+ for(unsigned int j=0; j<search; j++) {
+ unsigned int i = (hash + j) & (size-1); // modulo size
+ if (entry[i] == e) {
+ entry[i] = 0;
+ count--;
+ return true;
+ }
+ }
+ return false;
+ }
+ bool contains(void* e) {
+ if (count == 0) return false;
+ unsigned int t_size = size();
+ unsigned int hash = stupidHash(e);
+ // Elements are at most placed 'search' spots from their hash
+ for(unsigned int j=0; j<search; j++) {
+ unsigned int i = (hash + j) & (t_size-1); // modulo size
+ if (entry[i] == e) return true;
+ }
+ return false;
+ }
+ void* at(unsigned int i) const {
+ assert (i < (1U<<log_size));
+ return entry[i];
+ }
+ bool isEmpty() const {
+ return count == 0;
+ }
+ bool isFull() const {
+ return count == size();
+ }
+ unsigned int size() const {
+ return (1U << log_size);
+ }
+
+ unsigned int count;
+ const unsigned short log_size;
+ unsigned short search;
+ PtrListEntry *next;
+ void** entry;
+};
+
+// An unsorted and unique PtrList that is implement as a linked list of hash-sets
+// Optimized for fast insert and fast lookup
+template<class T>
+class MultiMapPtrList {
+public:
+ MultiMapPtrList(unsigned int init_size= 16) : m_first(0), m_current(0), m_pos(0) {
+ assert(init_size > 0);
+ unsigned int s = init_size - 1;
+ unsigned int log_size = 0;
+ while (s > 0) {
+ log_size++;
+ s = s >> 1;
+ }
+ m_first = new PtrListEntry(log_size);
+ }
+ MultiMapPtrList(const MultiMapPtrList& ptrList) : m_first(0), m_current(0), m_pos(0) {
+ unsigned int t_count = ptrList.count();
+ unsigned int log_size = 0;
+ while (t_count > 0) {
+ log_size++;
+ t_count = t_count >> 1;
+ }
+ // At least as large as the largest ptrListEntry in the original
+ if (t_count < ptrList.m_first->log_size) log_size = ptrList.m_first->log_size;
+ m_first = new PtrListEntry(log_size);
+
+ PtrListEntry *t_current = ptrList.m_first;
+ while (t_current) {
+ unsigned int t_size = t_current->size();
+ for(unsigned int i=0; i < t_size; i++) {
+ void* e = t_current->at(i);
+ if (e != 0) {
+ bool t = m_first->insert(e);
+ if (!t) {
+ // Make a new, but keep the size
+ PtrListEntry *t_new = new PtrListEntry(log_size);
+ t_new->insert(e);
+ t_new->next = m_first;
+ m_first = t_new;
+ }
+ }
+ }
+ t_current = t_current->next;
+ }
+ }
+ ~MultiMapPtrList() {
+ PtrListEntry *t_next, *t_current = m_first;
+ while (t_current) {
+ t_next = t_current->next;
+ delete t_current;
+ t_current = t_next;
+ }
+ }
+ void append(T* e) {
+ PtrListEntry *t_last = 0, *t_current = m_first;
+ int count = 0;
+ while (t_current) {
+ if (t_current->insert(e)) return;
+ t_last = t_current;
+ t_current = t_current->next;
+ count++;
+ }
+ // Create new hash-set
+ unsigned int newsize = m_first->log_size+1;
+ if (newsize > MAX_PTRLIST_SIZE) newsize = MAX_PTRLIST_SIZE;
+ t_current = new PtrListEntry(newsize);
+ bool t = t_current->insert(e);
+ assert(t);
+ // Prepend it to the list, for insert effeciency
+ t_current->next = m_first;
+ m_first = t_current;
+ // ### rehash some of the smaller sets
+ /*
+ if (count > 4) {
+ // rehash the last in the new
+ t_current->insert(t_last);
+ }*/
+ }
+ void remove(T* e) {
+ PtrListEntry *t_next, *t_last = 0, *t_current = m_first;
+ // Remove has to check every PtrEntry.
+ while (t_current) {
+ t_next = t_current->next;
+ if (t_current->remove(e) && t_current->isEmpty()) {
+ if (t_last) {
+ t_last->next = t_current->next;
+ }
+ else {
+ assert (m_first == t_current);
+ m_first = t_current->next;
+ }
+ delete t_current;
+ } else {
+ t_last = t_current;
+ }
+ t_current = t_next;
+ }
+ }
+ bool contains(T* e) {
+ PtrListEntry *t_current = m_first;
+ while (t_current) {
+ if (t_current->contains(e)) return true;
+ t_current = t_current->next;
+ }
+ return false;
+ }
+ bool isEmpty() {
+ if (!m_first) return true;
+ PtrListEntry *t_current = m_first;
+ while (t_current) {
+ if (!t_current->isEmpty()) return false;
+ t_current = t_current->next;
+ }
+ return true;
+ }
+ unsigned int count() const {
+ unsigned int t_count = 0;
+ PtrListEntry *t_current = m_first;
+ while (t_current) {
+ t_count += t_current->count;
+ t_current = t_current->next;
+ }
+ return t_count;
+ }
+// Iterator functions:
+ T* first() {
+ m_current = m_first;
+ m_pos = 0;
+ // skip holes
+ if (m_current && !m_current->at(m_pos))
+ return next();
+ else
+ return current();
+ }
+ T* current() {
+ if (!m_current)
+ return (T*)0;
+ else
+ return (T*)m_current->at(m_pos);
+ }
+ T* next() {
+ if (!m_current) return (T*)0;
+ m_pos++;
+ if (m_pos >= m_current->size()) {
+ m_current = m_current->next;
+ m_pos = 0;
+ }
+ // skip holes
+ if (m_current && !m_current->at(m_pos))
+ return next();
+ else
+ return current();
+ }
+private:
+ PtrListEntry *m_first;
+// iteration:
+ PtrListEntry *m_current;
+ unsigned int m_pos;
+};
+
+#undef START_PTRLIST_SIZE
+#undef MAX_PTRLIST_SIZE
+
+#endif
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-17 03:21:41 +0000