/*

* Copyright (c) 2009 Nokia Corporation and/or its subsidiary(-ies).

* All rights reserved.

* This component and the accompanying materials are made available

* which accompanies this distribution, and is available

* at the URL "http://www.eclipse.org/legal/epl-v10.html".

*

* Initial Contributors:

* Nokia Corporation - initial contribution.

*

* Contributors:

*

* Description: 

*

*/

/*

 * Licensed to the Apache Software Foundation (ASF) under one or more

 * contributor license agreements.  See the NOTICE file distributed with

 * this work for additional information regarding copyright ownership.

 * The ASF licenses this file to You under the Apache License, Version 2.0

 * (the "License"); you may not use this file except in compliance with

 * the License.  You may obtain a copy of the License at

 * 

 *      http://www.apache.org/licenses/LICENSE-2.0

 * 

 * Unless required by applicable law or agreed to in writing, software

 * distributed under the License is distributed on an "AS IS" BASIS,

 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

 * See the License for the specific language governing permissions and

 * limitations under the License.

 */

/*

 * $Id: RefHashTableOf.c 568078 2007-08-21 11:43:25Z amassari $

 */

// ---------------------------------------------------------------------------

//  Include

// ---------------------------------------------------------------------------

#if defined(XERCES_TMPLSINC)

#include <xercesc/util/RefHashTableOf.hpp>

#endif

#include <xercesc/util/Janitor.hpp>

#include <xercesc/util/NullPointerException.hpp>

#include <assert.h>

#include <new>

XERCES_CPP_NAMESPACE_BEGIN

// ---------------------------------------------------------------------------

//  RefHashTableOf: Constructors and Destructor

// ---------------------------------------------------------------------------

template <class TVal>

RefHashTableOf<TVal>::RefHashTableOf( const unsigned int modulus

                                    , const bool adoptElems

                                    , MemoryManager* const manager)

    : fMemoryManager(manager)

    , fAdoptedElems(adoptElems)

    , fBucketList(0)

    , fHashModulus(modulus)

    , fInitialModulus(modulus)

    , fCount(0)

    , fHash(0)

{

    initialize(modulus);

	// create default hasher

	fHash = new (fMemoryManager) HashXMLCh();

}

template <class TVal>

RefHashTableOf<TVal>::RefHashTableOf( const unsigned int modulus

                                    , const bool adoptElems

                                    , HashBase* hashBase

                                    , MemoryManager* const manager)

    : fMemoryManager(manager)

    , fAdoptedElems(adoptElems)

    , fBucketList(0)

    , fHashModulus(modulus)

    , fInitialModulus(modulus)

    , fCount(0)

    , fHash(0)

{

    initialize(modulus);

    // set hasher

    fHash = hashBase;

}

template <class TVal>

RefHashTableOf<TVal>::RefHashTableOf(const unsigned int modulus

                                     , MemoryManager* const manager)

    : fMemoryManager(manager)

    , fAdoptedElems(true)

    , fBucketList(0)

    , fHashModulus(modulus)

    , fInitialModulus(modulus)

    , fCount(0)

    , fHash(0)

{

    initialize(modulus);

    // create default hasher

    fHash = new (fMemoryManager) HashXMLCh();

}

template <class TVal> void RefHashTableOf<TVal>::initialize(const unsigned int modulus)

{

    if (modulus == 0)

        ThrowXMLwithMemMgr(IllegalArgumentException, XMLExcepts::HshTbl_ZeroModulus, fMemoryManager);

    // Allocate the bucket list and zero them

    fBucketList = (RefHashTableBucketElem<TVal>**) fMemoryManager->allocate

    (

        fHashModulus * sizeof(RefHashTableBucketElem<TVal>*)

    ); //new RefHashTableBucketElem<TVal>*[fHashModulus];

    for (unsigned int index = 0; index < fHashModulus; index++)

        fBucketList[index] = 0;

}

template <class TVal> RefHashTableOf<TVal>::~RefHashTableOf()

{

    cleanup();

}

// ---------------------------------------------------------------------------

//  RefHashTableOf: Element management

// ---------------------------------------------------------------------------

template <class TVal> bool RefHashTableOf<TVal>::isEmpty() const

{

    return fCount==0;

}

template <class TVal> bool RefHashTableOf<TVal>::

containsKey(const void* const key) const

{

    unsigned int hashVal;

    const RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);

    return (findIt != 0);

}

template <class TVal> void RefHashTableOf<TVal>::

removeKey(const void* const key)

{

    // Hash the key

    unsigned int hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager);

    assert(hashVal < fHashModulus);

    //

    //  Search the given bucket for this key. Keep up with the previous

    //  element so we can patch around it.

    //

    RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];

    RefHashTableBucketElem<TVal>* lastElem = 0;

    while (curElem)

    {

        if (fHash->equals(key, curElem->fKey))

        {

            if (!lastElem)

            {

                // It was the first in the bucket

                fBucketList[hashVal] = curElem->fNext;

            }

             else

            {

                // Patch around the current element

                lastElem->fNext = curElem->fNext;

            }

            // If we adopted the data, then delete it too

            //    (Note:  the userdata hash table instance has data type of void *.

            //    This will generate compiler warnings here on some platforms, but they

            //    can be ignored since fAdoptedElements is false.

            if (fAdoptedElems)

                delete curElem->fData;

            // Then delete the current element and move forward

 	        // delete curElem;

            // destructor doesn't do anything...

			// curElem->~RefHashTableBucketElem();

            fMemoryManager->deallocate(curElem);            

            fCount--;

            return;

        }

        // Move both pointers upwards

        lastElem = curElem;

        curElem = curElem->fNext;

    }

    // We never found that key

    ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);

}

template <class TVal> void RefHashTableOf<TVal>::removeAll()

{

    if(isEmpty())

        return;

    // Clean up the buckets first

    for (unsigned int buckInd = 0; buckInd < fHashModulus; buckInd++)

    {

        // Get the bucket list head for this entry

        RefHashTableBucketElem<TVal>* curElem = fBucketList[buckInd];

        RefHashTableBucketElem<TVal>* nextElem;

        while (curElem)

        {

            // Save the next element before we hose this one

            nextElem = curElem->fNext;

            // If we adopted the data, then delete it too

            //    (Note:  the userdata hash table instance has data type of void *.

            //    This will generate compiler warnings here on some platforms, but they

            //    can be ignored since fAdoptedElements is false.

            if (fAdoptedElems)

                delete curElem->fData;

            // Then delete the current element and move forward

 	        // delete curElem;

            // destructor doesn't do anything...

			// curElem->~RefHashTableBucketElem();

            fMemoryManager->deallocate(curElem);            

            curElem = nextElem;

        }

        // Clean out this entry

        fBucketList[buckInd] = 0;

    }

    fCount = 0;

}

// This method returns the data associated with a key. The key entry is deleted. The caller

// now owns the returned data (case of hashtable adopting the data).

// This function is called by transferElement so that the undeleted data can be transferred

// to a new key which will own that data.

template <class TVal> TVal* RefHashTableOf<TVal>::

orphanKey(const void* const key)

{

    // Hash the key

    TVal* retVal = 0;

    unsigned int hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager);

    assert(hashVal < fHashModulus);

    //

    //  Search the given bucket for this key. Keep up with the previous

    //  element so we can patch around it.

    //

    RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];

    RefHashTableBucketElem<TVal>* lastElem = 0;

    while (curElem)

    {

        if (fHash->equals(key, curElem->fKey))

        {

            if (!lastElem)

            {

                // It was the first in the bucket

                fBucketList[hashVal] = curElem->fNext;

            }

            else

            {

                // Patch around the current element

                lastElem->fNext = curElem->fNext;

            }

            retVal = curElem->fData;

            // Delete the current element

            // delete curElem;

            // destructor doesn't do anything...

			// curElem->~RefHashTableBucketElem();

            fMemoryManager->deallocate(curElem);            

            break;

        }

        // Move both pointers upwards

        lastElem = curElem;

        curElem = curElem->fNext;

    }

    // We never found that key

    if (!retVal)

        ThrowXMLwithMemMgr(NoSuchElementException, XMLExcepts::HshTbl_NoSuchKeyExists, fMemoryManager);

    return retVal;

}

//

// cleanup():

//   similar to destructor

//   called to cleanup the memory, in case destructor cannot be called

//

template <class TVal> void RefHashTableOf<TVal>::cleanup()

{

    removeAll();

    // Then delete the bucket list & hasher

    fMemoryManager->deallocate(fBucketList); //delete [] fBucketList;

    fBucketList = 0;

    delete fHash;

}

//

// reinitialize():

//   similar to constructor

//   called to re-construct the fElemList from scratch again

//

template <class TVal> void RefHashTableOf<TVal>::reinitialize(HashBase* hashBase)

{

    if (fBucketList || fHash)

        cleanup();

    fHashModulus = fInitialModulus;

    initialize(fHashModulus);

    if (hashBase)

        fHash = hashBase;

    else

        fHash = new (fMemoryManager) HashXMLCh();   // create default hasher

}

// this function transfer the data from key1 to key2

// this is equivalent to calling

//  1.  get(key1) to retrieve the data,

//  2.  removeKey(key1),

//  3.  and then put(key2, data)

// except that the data is not deleted in "removeKey" even it is adopted so that it

// can be transferred to key2.

// whatever key2 has originally will be purged (if adopted)

template <class TVal> void RefHashTableOf<TVal>::transferElement(const void* const key1, void* key2)

{

    put(key2, orphanKey(key1));

}

// ---------------------------------------------------------------------------

//  RefHashTableOf: Getters

// ---------------------------------------------------------------------------

template <class TVal> TVal* RefHashTableOf<TVal>::get(const void* const key)

{

    unsigned int hashVal;

    RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);

    if (!findIt)

        return 0;

    return findIt->fData;

}

template <class TVal> const TVal* RefHashTableOf<TVal>::

get(const void* const key) const

{

    unsigned int hashVal;

    const RefHashTableBucketElem<TVal>* findIt = findBucketElem(key, hashVal);

    if (!findIt)

        return 0;

    return findIt->fData;

}

template <class TVal>

MemoryManager* RefHashTableOf<TVal>::getMemoryManager() const

{

    return fMemoryManager;

}

template <class TVal>

unsigned int RefHashTableOf<TVal>::getHashModulus() const

{

    return fHashModulus;

}

template <class TVal>

unsigned int RefHashTableOf<TVal>::getCount() const

{

    return fCount;

}

// ---------------------------------------------------------------------------

//  RefHashTableOf: Getters

// ---------------------------------------------------------------------------

template <class TVal>

void RefHashTableOf<TVal>::setAdoptElements(const bool aValue)

{

    fAdoptedElems = aValue;

}

// ---------------------------------------------------------------------------

//  RefHashTableOf: Putters

// ---------------------------------------------------------------------------

template <class TVal> void RefHashTableOf<TVal>::put(void* key, TVal* const valueToAdopt)

{

    // Apply 0.75 load factor to find threshold.

    unsigned int threshold = fHashModulus * 3 / 4;

    // If we've grown too big, expand the table and rehash.

    if (fCount >= threshold)

        rehash();

    // First see if the key exists already

    unsigned int hashVal;

    RefHashTableBucketElem<TVal>* newBucket = findBucketElem(key, hashVal);

    //

    //  If so,then update its value. If not, then we need to add it to

    //  the right bucket

    //

    if (newBucket)

    {

        if (fAdoptedElems)

            delete newBucket->fData;

        newBucket->fData = valueToAdopt;

		newBucket->fKey = key;

    }

    else

    {

        //newBucket = new (fMemoryManager) RefHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]);

		newBucket =

             new (fMemoryManager->allocate(sizeof(RefHashTableBucketElem<TVal>)))

             RefHashTableBucketElem<TVal>(key, valueToAdopt, fBucketList[hashVal]);        

        fBucketList[hashVal] = newBucket;

        fCount++;

    }

}

// ---------------------------------------------------------------------------

//  RefHashTableOf: Private methods

// ---------------------------------------------------------------------------

template <class TVal> void RefHashTableOf<TVal>::rehash()

{

    const unsigned int newMod = fHashModulus * 2;

    RefHashTableBucketElem<TVal>** newBucketList =

        (RefHashTableBucketElem<TVal>**) fMemoryManager->allocate

    (

        newMod * sizeof(RefHashTableBucketElem<TVal>*)

    );//new RefHashTableBucketElem<TVal>*[newMod];

    // Make sure the new bucket list is destroyed if an

    // exception is thrown.

    ArrayJanitor<RefHashTableBucketElem<TVal>*>  guard(newBucketList, fMemoryManager);

    memset(newBucketList, 0, newMod * sizeof(newBucketList[0]));

    // Rehash all existing entries.

    for (unsigned int index = 0; index < fHashModulus; index++)

    {

        // Get the bucket list head for this entry

        RefHashTableBucketElem<TVal>* curElem = fBucketList[index];

        while (curElem)

        {

            // Save the next element before we detach this one

            RefHashTableBucketElem<TVal>* const nextElem = curElem->fNext;

            const unsigned int hashVal = fHash->getHashVal(curElem->fKey, newMod, fMemoryManager);

            assert(hashVal < newMod);

            RefHashTableBucketElem<TVal>* const newHeadElem = newBucketList[hashVal];

            // Insert at the start of this bucket's list.

            curElem->fNext = newHeadElem;

            newBucketList[hashVal] = curElem;

            curElem = nextElem;

        }

    }

    RefHashTableBucketElem<TVal>** const oldBucketList = fBucketList;

    // Everything is OK at this point, so update the

    // member variables.

    fBucketList = guard.release();

    fHashModulus = newMod;

    // Delete the old bucket list.

    fMemoryManager->deallocate(oldBucketList);//delete[] oldBucketList;

}

template <class TVal> RefHashTableBucketElem<TVal>* RefHashTableOf<TVal>::

findBucketElem(const void* const key, unsigned int& hashVal)

{

    // Hash the key

    hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager);

    assert(hashVal < fHashModulus);

    // Search that bucket for the key

    RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];

    while (curElem)

    {

		if (fHash->equals(key, curElem->fKey))

            return curElem;

        curElem = curElem->fNext;

    }

    return 0;

}

template <class TVal> const RefHashTableBucketElem<TVal>* RefHashTableOf<TVal>::

findBucketElem(const void* const key, unsigned int& hashVal) const

{

    // Hash the key

    hashVal = fHash->getHashVal(key, fHashModulus, fMemoryManager);

    assert(hashVal < fHashModulus);

    // Search that bucket for the key

    const RefHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];

    while (curElem)

    {

        if (fHash->equals(key, curElem->fKey))

            return curElem;

        curElem = curElem->fNext;

    }