haiku/SharedFolders/OpenHashTable.h

9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync/* $Id$ */
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync/** @file
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * OpenHashTable, Haiku Guest Additions.
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync */
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync/*
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * Copyright (C) 2012 Oracle Corporation
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync *
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * This file is part of VirtualBox Open Source Edition (OSE), as
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * available from http://www.virtualbox.org. This file is free software;
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * you can redistribute it and/or modify it under the terms of the GNU
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * General Public License (GPL) as published by the Free Software
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * Foundation, in version 2 as it comes in the "COPYING" file of the
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync */
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync/*
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * This code is based on:
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync *
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * VirtualBox Guest Additions for Haiku.
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync *
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * Copyright 2007, Hugo Santos. All Rights Reserved.
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync * Distributed under the terms of the MIT License.
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync */
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#ifndef _KERNEL_UTIL_OPEN_HASH_TABLE_H
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#define _KERNEL_UTIL_OPEN_HASH_TABLE_H
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#include <OS.h>
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#include <stdlib.h>
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#include <string.h>
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#ifdef _KERNEL_MODE
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync#    include <KernelExport.h>
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync#    include "kernel_cpp.h"
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#endif
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync/*!
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    The Definition template must have four methods: `HashKey', `Hash',
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    `Compare' and `GetLink;. It must also define several types as shown in the
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    following example:
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    struct Foo {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        int bar;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        Foo* fNext;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    };
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    struct HashTableDefinition {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        typedef int        KeyType;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        typedef    Foo        ValueType;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        size_t HashKey(int key) const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return key >> 1;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        size_t Hash(Foo* value) const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return HashKey(value->bar);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        bool Compare(int key, Foo* value) const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return value->bar == key;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        Foo*& GetLink(Foo* value) const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return value->fNext;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    };
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync*/
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsyncstruct MallocAllocator
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync{
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    void* Allocate(size_t size) const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return malloc(size);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    void Free(void* memory) const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        free(memory);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync};
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsynctemplate<typename Definition, bool AutoExpand = true,
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    bool CheckDuplicates = false, typename Allocator = MallocAllocator>
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsyncclass BOpenHashTable
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync{
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsyncpublic:
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    typedef BOpenHashTable<Definition, AutoExpand, CheckDuplicates> HashTable;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    typedef typename Definition::KeyType      KeyType;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    typedef typename Definition::ValueType    ValueType;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    static const size_t kMinimumSize = 8;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    // All allocations are of power of 2 lengths.
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    // regrowth factor: 200 / 256 = 78.125%
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    //                   50 / 256 = 19.53125%
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    BOpenHashTable()
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        :
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fTableSize(0),
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fItemCount(0),
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fTable(NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    BOpenHashTable(const Definition& definition)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        :
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fDefinition(definition),
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fTableSize(0),
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fItemCount(0),
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fTable(NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    BOpenHashTable(const Definition& definition, const Allocator& allocator)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        :
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fDefinition(definition),
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fAllocator(allocator),
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fTableSize(0),
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fItemCount(0),
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fTable(NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    ~BOpenHashTable()
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fAllocator.Free(fTable);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    status_t Init(size_t initialSize = kMinimumSize)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (initialSize > 0 && !_Resize(initialSize))
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return B_NO_MEMORY;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return B_OK;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    size_t TableSize() const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return fTableSize;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    size_t CountElements() const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return fItemCount;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    ValueType* Lookup(const KeyType& key) const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (fTableSize == 0)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return NULL;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        ValueType* slot = fTable[index];
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        while (slot)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            if (fDefinition.Compare(key, slot))
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                break;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            slot = _Link(slot);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return slot;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    status_t Insert(ValueType* value)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (fTableSize == 0)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            if (!_Resize(kMinimumSize))
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                return B_NO_MEMORY;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        else if (AutoExpand && fItemCount >= (fTableSize * 200 / 256))
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            _Resize(fTableSize * 2);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        InsertUnchecked(value);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return B_OK;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    void InsertUnchecked(ValueType* value)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (CheckDuplicates && _ExhaustiveSearch(value))
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#ifdef _KERNEL_MODE
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            panic("Hash Table: value already in table.");
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#else
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            debugger("Hash Table: value already in table.");
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#endif
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        _Insert(fTable, fTableSize, value);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fItemCount++;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    // TODO: a ValueType* Remove(const KeyType& key) method is missing
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    bool Remove(ValueType* value)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (!RemoveUnchecked(value))
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return false;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (AutoExpand && fTableSize > kMinimumSize
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            && fItemCount < (fTableSize * 50 / 256))
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            _Resize(fTableSize / 2);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return true;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    bool RemoveUnchecked(ValueType* value)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        size_t index = fDefinition.Hash(value) & (fTableSize - 1);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        ValueType* previous = NULL;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        ValueType* slot = fTable[index];
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        while (slot)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            ValueType* next = _Link(slot);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            if (value == slot)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                if (previous)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    _Link(previous) = next;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                else
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    fTable[index] = next;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                break;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            previous = slot;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            slot = next;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (slot == NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return false;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (CheckDuplicates && _ExhaustiveSearch(value))
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#ifdef _KERNEL_MODE
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            panic("Hash Table: duplicate detected.");
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#else
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            debugger("Hash Table: duplicate detected.");
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync#endif
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fItemCount--;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return true;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    /*!    Removes all elements from the hash table. No resizing happens. The
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        elements are not deleted. If \a returnElements is \c true, the method
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        returns all elements chained via their hash table link.
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    */
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    ValueType* Clear(bool returnElements = false)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (this->fItemCount == 0)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return NULL;
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        ValueType* result = NULL;
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (returnElements)
285c5b7b574681acee011fa88d0783c38fa7010avboxsync                {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            ValueType** nextPointer = &result;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            // iterate through all buckets
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            for (size_t i = 0; i < fTableSize; i++)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                ValueType* element = fTable[i];
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                if (element != NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    // add the bucket to the list
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    *nextPointer = element;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    // update nextPointer to point to the fNext of the last
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    // element in the bucket
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    while (element != NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                        nextPointer = &_Link(element);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                        element = *nextPointer;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        memset(this->fTable, 0, sizeof(ValueType*) * this->fTableSize);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return result;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    /*!    If the table needs resizing, the number of bytes for the required
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        allocation is returned. If no resizing is needed, 0 is returned.
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    */
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    size_t ResizeNeeded() const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        size_t size = fTableSize;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (size == 0 || fItemCount >= (size * 200 / 256))
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            // grow table
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            if (size == 0)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                size = kMinimumSize;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            while (fItemCount >= size * 200 / 256)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                size <<= 1;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        else if (size > kMinimumSize && fItemCount < size * 50 / 256)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            // shrink table
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            while (fItemCount < size * 50 / 256)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                size >>= 1;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            if (size < kMinimumSize)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                size = kMinimumSize;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (size == fTableSize)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return 0;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return size * sizeof(ValueType*);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    /*!    Resizes the table using the given allocation. The allocation must not
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        be \c NULL. It must be of size \a size, which must a value returned
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        earlier by ResizeNeeded(). If the size requirements have changed in the
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        meantime, the method free()s the given allocation and returns \c false,
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        unless \a force is \c true, in which case the supplied allocation is
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        used in any event.
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        Otherwise \c true is returned.
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        If \a oldTable is non-null and resizing is successful, the old table
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        will not be freed, but will be returned via this parameter instead.
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    */
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    bool Resize(void* allocation, size_t size, bool force = false,
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        void** oldTable = NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (!force && size != ResizeNeeded())
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            fAllocator.Free(allocation);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return false;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        _Resize((ValueType**)allocation, size / sizeof(ValueType*), oldTable);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return true;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    class Iterator
285c5b7b574681acee011fa88d0783c38fa7010avboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    public:
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        Iterator(const HashTable* table)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            : fTable(table)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            Rewind();
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        Iterator(const HashTable* table, size_t index, ValueType* value)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            : fTable(table), fIndex(index), fNext(value) {}
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        bool HasNext() const { return fNext != NULL; }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        ValueType* Next()
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            ValueType* current = fNext;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            _GetNext();
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return current;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        void Rewind()
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            // get the first one
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            fIndex = 0;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            fNext = NULL;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            _GetNext();
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    protected:
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        Iterator() {}
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        void _GetNext()
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            if (fNext)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                fNext = fTable->_Link(fNext);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            while (fNext == NULL && fIndex < fTable->fTableSize)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                fNext = fTable->fTable[fIndex++];
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        const HashTable* fTable;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        size_t fIndex;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        ValueType* fNext;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    };
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    Iterator GetIterator() const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return Iterator(this);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    Iterator GetIterator(const KeyType& key) const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (fTableSize == 0)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return Iterator(this, fTableSize, NULL);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        size_t index = fDefinition.HashKey(key) & (fTableSize - 1);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        ValueType* slot = fTable[index];
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        while (slot)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            if (fDefinition.Compare(key, slot))
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                break;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            slot = _Link(slot);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (slot == NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return Iterator(this, fTableSize, NULL);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return Iterator(this, index + 1, slot);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsyncprotected:
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    // for g++ 2.95
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    friend class Iterator;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    void _Insert(ValueType** table, size_t tableSize, ValueType* value)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        size_t index = fDefinition.Hash(value) & (tableSize - 1);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        _Link(value) = table[index];
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        table[index] = value;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    bool _Resize(size_t newSize)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        ValueType** newTable
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            = (ValueType**)fAllocator.Allocate(sizeof(ValueType*) * newSize);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (newTable == NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            return false;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        _Resize(newTable, newSize);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return true;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    void _Resize(ValueType** newTable, size_t newSize, void** _oldTable = NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        for (size_t i = 0; i < newSize; i++)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            newTable[i] = NULL;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        if (fTable)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            for (size_t i = 0; i < fTableSize; i++)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                ValueType* bucket = fTable[i];
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                while (bucket)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    ValueType* next = _Link(bucket);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    _Insert(newTable, newSize, bucket);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    bucket = next;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            if (_oldTable != NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                *_oldTable = fTable;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            else
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                fAllocator.Free(fTable);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        else if (_oldTable != NULL)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            *_oldTable = NULL;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fTableSize = newSize;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        fTable = newTable;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    ValueType*& _Link(ValueType* bucket) const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return fDefinition.GetLink(bucket);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    bool _ExhaustiveSearch(ValueType* value) const
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        for (size_t i = 0; i < fTableSize; i++)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            ValueType* bucket = fTable[i];
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            while (bucket) {
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                if (bucket == value)
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                    return true;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync                bucket = _Link(bucket);
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync            }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync        return false;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    }
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    Definition        fDefinition;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    Allocator        fAllocator;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    size_t            fTableSize;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    size_t            fItemCount;
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync    ValueType**        fTable;
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync};
9fc464631dc4a68fbb5eb6419d61fbe91b6b16bdvboxsync
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync#endif    // _KERNEL_UTIL_OPEN_HASH_TABLE_H
8e9d8c088aac57bedb558d3164bb681a582e4474vboxsync