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, 0 insertions, 345 deletions
diff --git a/khtml/misc/multimap.h b/khtml/misc/multimap.h
deleted file mode 100644
index 125e8e07d..000000000
--- a/khtml/misc/multimap.h
+++ /dev/null
@@ -1,345 +0,0 @@
-/*
- * 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 <tqptrdict.h>
-#include <tqptrlist.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 TQPtrDict<TQPtrList>, but
-// TQPtrList 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:
- TQPtrDict<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-09 19:30:05 +0000