/*

 * 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: ValueHashTableOf.c 568078 2007-08-21 11:43:25Z amassari $

 */

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

//  Include

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

#if defined(XERCES_TMPLSINC)

#include <xercesc/util/ValueHashTableOf.hpp>

#endif

#include <xercesc/util/NullPointerException.hpp>

#include <assert.h>

#include <new>

XERCES_CPP_NAMESPACE_BEGIN

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

//  ValueHashTableOf: Constructors and Destructor

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

template <class TVal>

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

                                        , HashBase* hashBase

                                        , MemoryManager* const manager)

    : fMemoryManager(manager)

    , fBucketList(0)

    , fHashModulus(modulus)

    , fHash(0)

{

	initialize(modulus);

	// set hasher

	fHash = hashBase;

}

template <class TVal>

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

                                        , MemoryManager* const manager)

	: fMemoryManager(manager)

    , fBucketList(0)

    , fHashModulus(modulus)

    , fHash(0)

{

	initialize(modulus);

	// create default hasher

	fHash = new (fMemoryManager) HashXMLCh();

}

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

{

	if (modulus == 0)

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

    // Allocate the bucket list and zero them

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

    (

        fHashModulus * sizeof(ValueHashTableBucketElem<TVal>*)

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

    memset(fBucketList, 0, sizeof(fBucketList[0]) * fHashModulus);

}

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

{

    removeAll();

    // Then delete the bucket list & hasher

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

	delete fHash;

}

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

//  ValueHashTableOf: Element management

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

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

{

    // Just check the bucket list for non-empty elements

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

    {

        if (fBucketList[buckInd] != 0)

            return false;

    }

    return true;

}

template <class TVal> bool ValueHashTableOf<TVal>::

containsKey(const void* const key) const

{

    unsigned int hashVal;

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

    return (findIt != 0);

}

template <class TVal> void ValueHashTableOf<TVal>::

removeKey(const void* const key)

{

    unsigned int hashVal;

    removeBucketElem(key, hashVal);

}

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

{

    // Clean up the buckets first

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

    {

        // Get the bucket list head for this entry

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

        ValueHashTableBucketElem<TVal>* nextElem;

        while (curElem)

        {

            // Save the next element before we hose this one

            nextElem = curElem->fNext;

            // delete the current element and move forward

            // destructor is empty...

            // curElem->~ValueHashTableBucketElem();

            fMemoryManager->deallocate(curElem);

            curElem = nextElem;

        }

        // Clean out this entry

        fBucketList[buckInd] = 0;

    }

}

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

//  ValueHashTableOf: Getters

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

template <class TVal> TVal& ValueHashTableOf<TVal>::get(const void* const key, MemoryManager* const manager)

{

    unsigned int hashVal;

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

    if (!findIt)

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

    return findIt->fData;

}

template <class TVal> const TVal& ValueHashTableOf<TVal>::

get(const void* const key) const

{

    unsigned int hashVal;

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

    if (!findIt)

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

    return findIt->fData;

}

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

//  ValueHashTableOf: Putters

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

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

{

    // First see if the key exists already

    unsigned int hashVal;

    ValueHashTableBucketElem<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)

    {

        newBucket->fData = valueToAdopt;

		newBucket->fKey = key;

    }

     else

    {

        newBucket =            

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

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

        fBucketList[hashVal] = newBucket;

    }

}

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

//  ValueHashTableOf: Private methods

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

template <class TVal> ValueHashTableBucketElem<TVal>* ValueHashTableOf<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

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

    while (curElem)

    {

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

            return curElem;

        curElem = curElem->fNext;

    }

    return 0;

}

template <class TVal> const ValueHashTableBucketElem<TVal>* ValueHashTableOf<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 ValueHashTableBucketElem<TVal>* curElem = fBucketList[hashVal];

    while (curElem)

    {

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

            return curElem;

        curElem = curElem->fNext;

    }

    return 0;

}

template <class TVal> void ValueHashTableOf<TVal>::

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

{

    // Hash the key

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

    assert(hashVal < fHashModulus);

    //

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

    //  element so we can patch around it.

    //

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

    ValueHashTableBucketElem<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;

            }

            // Delete the current element

            // delete curElem;

			// destructor is empty...

            // curElem->~ValueHashTableBucketElem();

            fMemoryManager->deallocate(curElem);                        

            return;

        }

        // Move both pointers upwards

        lastElem = curElem;

        curElem = curElem->fNext;

    }

    // We never found that key

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

}

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

//  ValueHashTableOfEnumerator: Constructors and Destructor

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

template <class TVal> ValueHashTableOfEnumerator<TVal>::

ValueHashTableOfEnumerator(ValueHashTableOf<TVal>* const toEnum

                           , const bool adopt

                           , MemoryManager* const manager)

	: fAdopted(adopt), fCurElem(0), fCurHash((unsigned int)-1), fToEnum(toEnum), fMemoryManager(manager)

{

    if (!toEnum)

        ThrowXMLwithMemMgr(NullPointerException, XMLExcepts::CPtr_PointerIsZero, manager);

    //

    //  Find the next available bucket element in the hash table. If it

    //  comes back zero, that just means the table is empty.

    //

    //  Note that the -1 in the current hash tells it to start from the

    //  beginning.

    //

    findNext();

}

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

{

    if (fAdopted)

        delete fToEnum;

}

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

//  ValueHashTableOfEnumerator: Enum interface

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

template <class TVal> bool ValueHashTableOfEnumerator<TVal>::hasMoreElements() const

{

    //

    //  If our current has is at the max and there are no more elements

    //  in the current bucket, then no more elements.

    //

    if (!fCurElem && (fCurHash == fToEnum->fHashModulus))

        return false;

    return true;

}

template <class TVal> TVal& ValueHashTableOfEnumerator<TVal>::nextElement()

{

    // Make sure we have an element to return

    if (!hasMoreElements())

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

    //

    //  Save the current element, then move up to the next one for the

    //  next time around.

    //

    ValueHashTableBucketElem<TVal>* saveElem = fCurElem;

    findNext();

    return saveElem->fData;

}

template <class TVal> void* ValueHashTableOfEnumerator<TVal>::nextElementKey()

{

    // Make sure we have an element to return

    if (!hasMoreElements())

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

    //

    //  Save the current element, then move up to the next one for the

    //  next time around.

    //

    ValueHashTableBucketElem<TVal>* saveElem = fCurElem;

    findNext();

    return saveElem->fKey;

}

template <class TVal> void ValueHashTableOfEnumerator<TVal>::Reset()

{

    fCurHash = (unsigned int)-1;

    fCurElem = 0;

    findNext();

}

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

//  ValueHashTableOfEnumerator: Private helper methods

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

template <class TVal> void ValueHashTableOfEnumerator<TVal>::findNext()

{

    //

    //  If there is a current element, move to its next element. If this

    //  hits the end of the bucket, the next block will handle the rest.

    //

    if (fCurElem)

        fCurElem = fCurElem->fNext;

    //

    //  If the current element is null, then we have to move up to the

    //  next hash value. If that is the hash modulus, then we cannot

    //  go further.

    //

    if (!fCurElem)

    {

        fCurHash++;

        if (fCurHash == fToEnum->fHashModulus)

            return;

        // Else find the next non-empty bucket

        while (fToEnum->fBucketList[fCurHash]==0)

        {

            // Bump to the next hash value. If we max out return

            fCurHash++;

            if (fCurHash == fToEnum->fHashModulus)

                return;

        }

        fCurElem = fToEnum->fBucketList[fCurHash];

    }

}

XERCES_CPP_NAMESPACE_END