aolserver-commits

[<co...@us...>]

Update of /cvsroot/aolserver/knutil/src
In directory sc8-pr-cvs11.sourceforge.net:/tmp/cvs-serv6393/src

Added Files:
	atomicint.cpp atomicint.il counter.cpp kncircularmapping.cpp 
	knconsistenthash.cpp kncrashhandler.cpp kncrypt.cpp 
	knerror.cpp knhash.cpp knlog.cpp knmarkuputil.cpp knmemory.cpp 
	knmutex.cpp knnetwork.cpp knnewdelete.cpp knpattern.cpp 
	knperfstatistics.cpp knregex.cpp knrwlock.cpp 
	knrwlogginglock.cpp knset.cpp knsleep.cpp knstring.cpp 
	knstringtokenizer.cpp knsysutility_unix.cpp 
	knsysutility_win32.cpp kntclerrors.cpp kntclfile.cpp 
	kntclinterp.cpp kntemplateuri.cpp kntime.cpp knurl.cpp 
	mtrand.cpp randomnumber.cpp shahash.cpp uuidgenerator.cpp 
Log Message:
Added this library to the AOLServer.com repository.   It contains a number of C/C++ utilities, some of which integrate into AOLServer, and many of which standalone. A portion of the library is required for the knregistration module, which will be checked in next.

I believe this compiles fine in "native" AOLServer, but it has not been tested recently.

--- NEW FILE: atomicint.cpp ---
#include "knexportlibraryknutilmodule.h"
/**
 * (c) Copyright 2008 KnowNow, Inc., Sunnyvale CA
 *
 * @KNOWNOW_LICENSE_START@
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in
 * the documentation and/or other materials provided with the
 * distribution.
 *
 * 3. The name "KnowNow" is a trademark of KnowNow, Inc. and may not
 * be used to endorse or promote any product without prior written
 * permission from KnowNow, Inc.
 *
 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL KNOWNOW, INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * @KNOWNOW_LICENSE_END@
 **/
#include "knutil/atomicint.h"

#ifndef WIN32
#include <unistd.h>
#endif

namespace
{

#ifdef WIN32
int getNumberOfProcessors()
{
    SYSTEM_INFO si;

    memset(&si, 0, sizeof(si));
    GetSystemInfo(&si);

    return si.dwNumberOfProcessors;
}
#else
int getNumberOfProcessors()
{
    return sysconf(_SC_NPROCESSORS_ONLN);
}
#endif /* WIN32 */

/*
 * Assume that the number of processors remains static during process
 * lifetime.  This may be dicey if the superuser is using/abusing tools
 * such as Solaris's psradm.
 */
const int gNumberOfProcessors = getNumberOfProcessors();

#ifdef WIN32
#pragma warning(disable : 4035)

/*
 * Return with the result in EAX.
 */
inline int atomicAdd(int *pcnt, int cnt)
{
    if (gNumberOfProcessors == 1)
    {
        __asm
        {
            mov ecx, pcnt
            mov eax, cnt
            xadd dword ptr [ecx], eax
            add eax, cnt
        }
    }
    else
    {
        __asm
        {
            mov ecx, pcnt
            mov eax, cnt
            lock xadd dword ptr [ecx], eax
            add eax, cnt
        }
    }
}

#pragma warning(default : 4035)

inline bool atomicCompareAndSwap(int *pcnt, int oval, int val)
{
    unsigned char c;

    if (gNumberOfProcessors == 1)
    {
        __asm
        {
            mov ecx, pcnt
            mov eax, oval
            mov edx, val
            cmpxchg dword ptr [ecx], edx
            sete c
        }
    }
    else
    {
        __asm
        {
            mov ecx, pcnt
            mov eax, oval
            mov edx, val
            lock cmpxchg dword ptr [ecx], edx
            sete c
        }
    }

    return c != 0;
}

inline bool atomicDecrementAndTest(int *pcnt)
{
    unsigned char c;

    if (gNumberOfProcessors == 1)
    {
        __asm
        {
            mov ecx, pcnt
            dec dword ptr [ecx]
            sete c
        }
    }
    else
    {
        __asm
        {
            mov ecx, pcnt
            lock dec dword ptr [ecx]
            sete c
        }
    }

    return c != 0;
}

inline bool atomicDoubleCompareAndSwap(int64_t *pcnt, int64_t oval, int64_t val)
{
    unsigned char c;

    if (gNumberOfProcessors == 1)
    {
        __asm
        {
            mov esi, pcnt
            mov edx, dword ptr [oval + 4]
            mov eax, dword ptr [oval]
            mov ecx, dword ptr [val + 4]
            mov ebx, dword ptr [val]
            cmpxchg8b qword ptr [esi]
            sete c
        }
    }
    else
    {
        __asm
        {
            mov esi, pcnt
            mov edx, dword ptr [oval + 4]
            mov eax, dword ptr [oval]
            mov ecx, dword ptr [val + 4]
            mov ebx, dword ptr [val]
            lock cmpxchg8b qword ptr [esi]
            sete c
        }
    }

    return c != 0;
}

inline void atomicIncrement(int *pcnt)
{
    if (gNumberOfProcessors == 1)
    {
        __asm
        {
            mov ecx, pcnt
            inc dword ptr [ecx]
        }
    }
    else
    {
        __asm
        {
            mov ecx, pcnt
            lock inc dword ptr [ecx]
        }
    }
}

inline void atomicReadBarrier()
{
    /*
     * A read barrier is only necessary on a multiprocessor box.
     */
    if (gNumberOfProcessors != 1)
    {
        __asm
        {
            lock add dword ptr [esp], 0
        }
    }
}

inline void atomicWriteBarrier()
{
    /*
     * Intel doesn't reorder writes.
     */
}
#elif __linux
inline int atomicAdd(int *pcnt, int cnt)
{
    int rc;

    if (gNumberOfProcessors == 1)
    {
        __asm__ __volatile__(
            "xaddl %0,%2"
            : "=r" (rc)
            : "0" (cnt), "m" (*pcnt)
            : "memory");
    }
    else
    {
        __asm__ __volatile__(
            "lock xaddl %0,%2"
            : "=r" (rc) 
            : "0" (cnt), "m" (*pcnt)
            : "memory");
    }

    return rc + cnt;
}

inline bool atomicCompareAndSwap(int *pcnt, int oval, int val)
{
    unsigned char c;

    if (gNumberOfProcessors == 1)
    {
        __asm__ __volatile__(
            "cmpxchgl %2,%1; sete %0"
            : "=q" (c), "=m" (*pcnt)
            : "r" (val), "1" (*pcnt), "a" (oval));
    }
    else
    {
        __asm__ __volatile__(
            "lock cmpxchgl %2,%1; sete %0"
            : "=q" (c), "=m" (*pcnt)
            : "r" (val), "1" (*pcnt), "a" (oval));
    }

    return c != 0;
}

inline bool atomicDecrementAndTest(int *pcnt)
{
    unsigned char c;

    if (gNumberOfProcessors == 1)
    {
        __asm__ __volatile__(
            "decl %1; sete %0"
            : "=q" (c)
            : "m" (*pcnt)
            : "memory");
    }
    else
    {
        __asm__ __volatile__(
            "lock decl %1; sete %0"
            : "=q" (c)
            : "m" (*pcnt)
            : "memory" );
    }

    return c != 0;
}

inline bool atomicDoubleCompareAndSwap(int64_t *pcnt, int64_t oval, int64_t val)
{
    unsigned char c;

    if (gNumberOfProcessors == 1)
    {
        __asm__ __volatile__(
            "cmpxchg8b %1; sete %0"
            : "=q" (c), "=m" (*pcnt)
            : "1" (*pcnt),
              "A" (oval),
              "c" (static_cast<int>(val >> 32)),
              "b" (static_cast<int>(val)));
    }
    else
    {
        __asm__ __volatile__(
            "lock cmpxchg8b %1; sete %0"
            : "=q" (c), "=m" (*pcnt)
            : "1" (*pcnt),
              "A" (oval),
              "c" (static_cast<int>(val >> 32)),
              "b" (static_cast<int>(val)));
    }

    return c != 0;
}

inline void atomicIncrement(int *pcnt)
{
    if (gNumberOfProcessors == 1)
    {
        __asm__ __volatile__(
            "incl %0"
            : "+m" (*pcnt)
            );
    }
    else
    {
        __asm__ __volatile__(
            "lock incl %0"
            : "+m" (*pcnt)
            );
    }
}

inline void atomicReadBarrier()
{
    if (gNumberOfProcessors == 1)
    {
        __asm__ __volatile__(
            ""
            :
            :
            : "memory");
    }
    else
    {
        int x = 0, y = 1;

        __asm__ __volatile__(
            "xchgl %0,%1"
            : "=r" (x)
            : "m" (y), "0" (x)
            : "memory");
    }
}

inline void atomicWriteBarrier()
{
    __asm__ __volatile__(
        ""
        :
        :
        : "memory");
}

#elif __sun

extern "C" int atomicAdd(int *, int);
extern "C" bool atomicCompareAndSwap(int *, int, int);
extern "C" bool atomicDoubleCompareAndSwap(int64_t *, int64_t *, int64_t *);
extern "C" void atomicReadBarrier();
extern "C" void atomicWriteBarrier();

inline bool atomicDecrementAndTest(int *pcnt)
{
    return atomicAdd(pcnt, -1) == 0;
}

inline bool atomicDoubleCompareAndSwap(int64_t *pcnt, int64_t oval, int64_t val)
{
    return atomicDoubleCompareAndSwap(pcnt, &oval, &val);
}

inline void atomicIncrement(int *pcnt)
{
    atomicAdd(pcnt, 1);
}
#endif /* WIN32 */

} //namespace


int AtomicInt::operator+=(int cnt)
{
    return atomicAdd(&m_cnt, cnt);
}

int AtomicInt::operator-=(int cnt)
{
    return atomicAdd(&m_cnt, -cnt);
}

int AtomicInt::operator++()
{
    return atomicAdd(&m_cnt, 1);
}

int AtomicInt::operator++(int)
{
    return atomicAdd(&m_cnt, 1) - 1;
}

int AtomicInt::operator--()
{
    return atomicAdd(&m_cnt, -1);
}

int AtomicInt::operator--(int)
{
    return atomicAdd(&m_cnt, -1) + 1;
}

bool AtomicInt::decrementAndTest()
{
    return atomicDecrementAndTest(&m_cnt);
}

void AtomicInt::increment()
{
    atomicIncrement(&m_cnt);
}

--- NEW FILE: atomicint.il ---
.inline atomicAdd,8
1:
ld [%o0],%o2
add %o2,%o1,%o3
cas [%o0],%o2,%o3
cmp %o2,%o3
bne,pn %icc,1b
nop
add %o2,%o1,%o0
.end

.inline atomicCompareAndSwap,12
cas [%o0],%o1,%o2
xor %o0,%o0,%o0
cmp %o1,%o2
bne,pn %icc,2f
nop
add %o0,1,%o0
2:
.end

.inline atomicDoubleCompareAndSwap,12
ldx [%o1],%o3
ldx [%o2],%o4
casx [%o0],%o3,%o4
xor %o0,%o0,%o0
cmp %o3,%o4
bne,pn %xcc,3f
nop
add %o0,1,%o0
3:
.end

.inline atomicReadBarrier,0
membar #LoadLoad
.end

.inline atomicWriteBarrier,0
membar #StoreStore
.end

--- NEW FILE: counter.cpp ---
#include "knexportlibraryknutilmodule.h"
/**
 * (c) Copyright 2008 KnowNow, Inc., Sunnyvale CA
 *
 * @KNOWNOW_LICENSE_START@
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in
 * the documentation and/or other materials provided with the
 * distribution.
 *
 * 3. The name "KnowNow" is a trademark of KnowNow, Inc. and may not
 * be used to endorse or promote any product without prior written
 * permission from KnowNow, Inc.
 *
 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL KNOWNOW, INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * @KNOWNOW_LICENSE_END@
 **/
#include "knutil/counter.h"

Counter::Counter(int c) : count(c)
{
}

Counter::~Counter()
{
}

--- NEW FILE: kncircularmapping.cpp ---
#include <math.h>
/**
 * (c) Copyright 2008 KnowNow, Inc., Sunnyvale CA
 *
 * @KNOWNOW_LICENSE_START@
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in
 * the documentation and/or other materials provided with the
 * distribution.
 *
 * 3. The name "KnowNow" is a trademark of KnowNow, Inc. and may not
 * be used to endorse or promote any product without prior written
 * permission from KnowNow, Inc.
 *
 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL KNOWNOW, INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * @KNOWNOW_LICENSE_END@
 **/

#include <sstream>
#include <algorithm>

#include "knexportlibraryknutilmodule.h"
#include "knutil/knerror.h"
#include "knutil/knlog.h"
#include "knutil/kncircularmapping.h"

//--------------------------------------------------------------------------
// Bucket Class
//--------------------------------------------------------------------------

class Bucket
{
public:

    Bucket(const std::string& bucketName, double weight) : m_name(bucketName), m_weight(weight)
    {
    }

    std::string             m_name;
    double                  m_weight;

    std::vector<KnCircularMapping::PointT>     m_replicaPoints;
};


bool BucketComp(const Bucket* lhs, const Bucket* rhs)
{
    return lhs->m_name < rhs->m_name;
}

bool insertSorted(std::vector<Bucket*>& v, Bucket* value)
{
    std::pair<std::vector<Bucket*>::iterator, std::vector<Bucket*>::iterator> bounds;

    bounds = equal_range(v.begin(), v.end(), value, BucketComp);

    if(bounds.first == bounds.second)
    {
        if(bounds.first == v.end())
        {
            v.push_back(value);
            return true;
        }

        v.insert(bounds.second, value);
        return true;
    }

    return false;
}

//--------------------------------------------------------------------------
// ReplicaPoint Class
//--------------------------------------------------------------------------

class ReplicaPoint
{
public:

    ReplicaPoint(KnCircularMapping::PointT& point) : m_point(point)
    {
    }

    ~ReplicaPoint()
    {
    }

    Bucket* getFirstBucket()
    {
        if(!m_replicas.size())
        {
            KnLog(KnLogError, "KnConsistentHash: replica point with no replicas.");

            return NULL;
        }

        Bucket* bucket = *m_replicas.begin();

        return bucket;
    }

    bool addReplica(Bucket* bucket) // keep them sorted , return true if conflict
    {
        if(!m_replicas.size())
        {
            m_replicas.push_back(bucket);
            return false;
        }

        bool result = insertSorted(m_replicas, bucket);

        if(!result)
        {
            KnLog(KnLogError, "KnConsistentHash: Bucket with same ID already present at replica");
        }

        KnLog(KnLogWarning, "KnConsistentHash: conflict when adding bucket %s replica at point %u.", bucket->m_name.c_str(), m_point);

        return true;
    }

    KnCircularMapping::PointT   m_point;

    std::vector<Bucket*>        m_replicas; // should be just one or there are conflicts
};


//--------------------------------------------------------------------------
// KnCircularMapping
//--------------------------------------------------------------------------

KnCircularMapping::KnCircularMapping()
{
    m_totalWeight = 0;
}

KnCircularMapping::~KnCircularMapping()
{
    removeAllBuckets();
}

bool KnCircularMapping::addBucket(const char* bucketName, std::vector<PointT>& replicas, double weight)
{
    if (weight <= 0)
        return false;

    if (m_buckets.find(bucketName) != m_buckets.end())
        return false;

    Bucket* bucket = new Bucket(bucketName, weight);
    m_buckets[bucketName] = bucket;
    
    ReplicaPoint* rp;

    bucket->m_replicaPoints = replicas;
    
    for (int i = 0; i < replicas.size(); i++)
    {
        rp = findOrAddReplicaPoint(replicas[i]);
        rp->addReplica(bucket);
    }

    m_totalWeight += weight;

    return true;
}

bool KnCircularMapping::removeBucket(const char* bucketName)
{
    BucketMapIterator it = m_buckets.find(bucketName);
    if (it == m_buckets.end())
        return false;

    Bucket* bucket = it->second;
    m_buckets.erase(it);

    double weight = bucket->m_weight;
    m_totalWeight -= weight;

    for (int i = 0; i < bucket->m_replicaPoints.size(); i++)
    {
        if(!removeReplicaPoint(bucket->m_replicaPoints[i], bucket))
        {
            KnLog(KnLogError, "KnConsistentHash: could not remove replica point %u for bucket %s.", bucket->m_replicaPoints[i] ,bucket->m_name.c_str());
        }
    }

    SAFE_DELETE(bucket);

    return true;
}

ReplicaPoint* KnCircularMapping::findOrAddReplicaPoint(PointT point)
{
    ReplicaMapRange bounds;
    ReplicaPoint* result;

    bounds = m_replicaMap.equal_range(point);

    if(bounds.first == bounds.second)
    {
        // not found

        result = new ReplicaPoint(point);

        if(bounds.first == m_replicaMap.end())
        {
            m_replicaMap[point] = result;
            return result;
        }

        m_replicaMap.insert(bounds.second, std::pair<const PointT, ReplicaPoint*>(point, result));
        return result;
    }

    return (*bounds.first).second;
}

ReplicaPoint* KnCircularMapping::findReplicaPoint(PointT point)
{
    ReplicaMapIterator it = m_replicaMap.find(point);

    if(it == m_replicaMap.end())
        return NULL;

    return it->second;
}

bool KnCircularMapping::removeReplicaPoint(PointT point, Bucket* bucket)
{
    ReplicaMapRange bounds;

    bounds = m_replicaMap.equal_range(point);

    if(bounds.first == bounds.second)
        return false;

    ReplicaPoint* rp = (*bounds.first).second;

    std::vector<Bucket*>& replicas = rp->m_replicas;

    std::vector<Bucket*>::iterator it = find(replicas.begin(), replicas.end(), bucket);

    if(it == replicas.end())
        return false;

    replicas.erase(it);

    if(!replicas.size())
    {
        m_replicaMap.erase(bounds.first);
        SAFE_DELETE(rp);
    }

    return true;
}

Bucket* KnCircularMapping::findBucketForPoint(PointT point)
{
    if (m_replicaMap.empty() || m_buckets.empty())
        return NULL;

    if (m_buckets.size() == 1)
        return (*m_replicaMap.begin()).second->getFirstBucket();

    ReplicaMapRange bounds;

    bounds = m_replicaMap.equal_range(point);

    if(bounds.first == bounds.second)
    {
        // not found

        if(bounds.first == m_replicaMap.end())
        {
            // point is after all replicas => assign to first replica

            return (*m_replicaMap.begin()).second->getFirstBucket();
        }

        // assign to greater replica
        return (*bounds.second).second->getFirstBucket();
    }

    // assign to this replica as it has the same point value
    return (*bounds.first).second->getFirstBucket();
}

void KnCircularMapping::removeAllBuckets()
{
    ReplicaMapIterator it;
    for(it = m_replicaMap.begin(); it != m_replicaMap.end(); it++)
        SAFE_DELETE(it->second);
    m_replicaMap.clear();

    BucketMapIterator bmi = m_buckets.begin();
    for(; bmi != m_buckets.end(); bmi++)
        SAFE_DELETE(bmi->second);
    m_buckets.clear();
}

double KnCircularMapping::getWeight(const std::string& bucketName)
{
    BucketMapIterator it = m_buckets.find(bucketName.c_str());

    if(it != m_buckets.end())
        return it->second->m_weight;

    return -1;
}

double KnCircularMapping::getTotalWeight()
{
    return m_totalWeight;
}

bool KnCircularMapping::existsBucket(const std::string& bucketName)
{
    return m_buckets.find(bucketName.c_str()) != m_buckets.end();
}

std::string KnCircularMapping::assignPointToBucket(PointT point)
{
    Bucket* bucket = findBucketForPoint(point);

    if(!bucket)
        return "";

    return bucket->m_name;
}

int KnCircularMapping::bucketCount()
{
    return m_buckets.size();
}

--- NEW FILE: knconsistenthash.cpp ---
#include <math.h>
/**
 * (c) Copyright 2008 KnowNow, Inc., Sunnyvale CA
 *
 * @KNOWNOW_LICENSE_START@
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in
 * the documentation and/or other materials provided with the
 * distribution.
 *
 * 3. The name "KnowNow" is a trademark of KnowNow, Inc. and may not
 * be used to endorse or promote any product without prior written
 * permission from KnowNow, Inc.
 *
 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL KNOWNOW, INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * @KNOWNOW_LICENSE_END@
 **/

#include <sstream>
#include <algorithm>
#include <vector>

#include "knexportlibraryknutilmodule.h"
#include "knutil/knerror.h"
#include "knutil/knlog.h"
#include "knutil/knhash.h"
#include "knutil/mtrand.h"
#include "knutil/knconsistenthash.h"

//--------------------------------------------------------------------------
// KnConsistentHash
//--------------------------------------------------------------------------

KnConsistentHash::KnConsistentHash(int replicasPerBucket, KnCircularMapping::PointT pointInterval)
{
    m_replicasPerBucket = replicasPerBucket;
    m_pointInterval = pointInterval;
}

KnConsistentHash::~KnConsistentHash()
{
}

KnConsistentHash::IDHash KnConsistentHash::computeHash(const char* identifier)
{
    return hash32(identifier, strlen(identifier), 1492);
}

KnCircularMapping::PointT KnConsistentHash::computePointForResource(const char* identifier)
{
    MTRand_int32 randGen( computeHash(identifier) );

    return randGen() % m_pointInterval;
}

bool KnConsistentHash::addBucket(const char* bucketName, double weight)
{
    return addBucketUnsafe(bucketName, computeHash(bucketName), weight);
}

bool KnConsistentHash::addBucket(const char* bucketName, IDHash bucketHash, double weight)
{
    KnRWLock::KnWriteLock wlock(m_bucketLock);

    return addBucketUnsafe(bucketName, bucketHash, weight);
}

bool KnConsistentHash::addBucketUnsafe(const char* bucketName, IDHash bucketHash, double weight)
{
    if (weight < 0.000001)
        return m_mapping.removeBucket(bucketName);
    
    if(m_mapping.existsBucket(bucketName))
    {
        // Bucket already exists => remove before adding
        m_mapping.removeBucket(bucketName);
    }

    MTRand_int32 randGen(bucketHash);
    KnCircularMapping::PointT point;

    std::vector<KnCircularMapping::PointT> replicas;
    int replicaCount = floor(weight * m_replicasPerBucket);
    replicas.reserve(replicaCount);

    for (int i = 0; i < replicaCount; i++)
    {
        point = randGen() % m_pointInterval;

        replicas.push_back(point);
    }

    return m_mapping.addBucket(bucketName, replicas, weight);
}

bool KnConsistentHash::removeBucket(const char* bucketName)
{
    KnRWLock::KnWriteLock wlock(m_bucketLock);

    return m_mapping.removeBucket(bucketName);
}

void KnConsistentHash::removeAllBuckets()
{
    KnRWLock::KnWriteLock wlock(m_bucketLock);

    m_mapping.removeAllBuckets();
}

std::string KnConsistentHash::assignPointToBucket(KnCircularMapping::PointT point)
{
    KnRWLock::KnReadLock rlock(m_bucketLock);

    return m_mapping.assignPointToBucket(point);
}

std::string KnConsistentHash::assignResourceToBucket(const char* identifier)
{
    KnRWLock::KnReadLock rlock(m_bucketLock);

    return m_mapping.assignPointToBucket( computePointForResource(identifier) );
}


int KnConsistentHash::bucketCount()
{
    return m_mapping.bucketCount();
}

bool KnConsistentHash::addBucketsFromSet(const KnSet& bucketSet)
{
    if(bucketSet.size() == 0)
        return true;

    KnRWLock::KnWriteLock wlock(m_bucketLock);

    return addBucketsFromSetUnsafe(bucketSet);
}

bool KnConsistentHash::setBucketsFromSet(const KnSet& bucketSet)
{
    if(bucketSet.size() == 0)
        return true;

    KnRWLock::KnWriteLock wlock(m_bucketLock);

    m_mapping.removeAllBuckets();

    return addBucketsFromSetUnsafe(bucketSet);
}

bool KnConsistentHash::addBucketsFromSetUnsafe(const KnSet& bucketSet)
{
    if(bucketSet.size() == 0)
        return true;

    for (size_t ix = 0; ix < bucketSet.size(); ++ix)
    {
        KnSetElem entry = bucketSet[ix];
        KnString bucketName = entry.m_key;

        if(entry.m_value == "")
        {
            // A delete bucket request
            m_mapping.removeBucket(bucketName.c_str());
            continue;
        }

        double weight = entry.m_value.toDouble();

        addBucketUnsafe(bucketName.c_str(), computeHash(bucketName.c_str()), weight);
    }

    return true;
}

double KnConsistentHash::getTotalWeight()
{
    return m_mapping.getTotalWeight();
}

--- NEW FILE: kncrashhandler.cpp ---
#include "knexportlibraryknutilmodule.h"
/**
 * (c) Copyright 2008 KnowNow, Inc., Sunnyvale CA
 *
 * @KNOWNOW_LICENSE_START@
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in
 * the documentation and/or other materials provided with the
 * distribution.
 *
 * 3. The name "KnowNow" is a trademark of KnowNow, Inc. and may not
 * be used to endorse or promote any product without prior written
 * permission from KnowNow, Inc.
 *
 * THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL KNOWNOW, INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * @KNOWNOW_LICENSE_END@
 **/
#include "knutil/kncrashhandler.h"
#include "knutil/knlog.h"
#include "knutil/knmemory.h"
#include "knutil/knmutex.h"

#include "string"


namespace {
    KnMutex             gCrashHandlerMutex;
    std::string         gDumpLocation; // For occasions when we change it.
    bool                gDumpAtAll = true;    // Avoid denial of service by running out of disk (Customer Support called for the default to be false for this reason).
}


#ifdef WIN32

#define _MSJDBG_H
#include "BugslayerUtil.h"

namespace {
    // From http://msdn.microsoft.com/library/default.asp?url=/library/en-us/debug/base/minidumpwritedump.asp:
    // DumpType
    //    [in] The type of information to be generated. This parameter can be 
    //        one or more of the values from the MINIDUMP_TYPE enumeration.
    unsigned int        gMiniDumpType = static_cast<unsigned int>(MiniDumpNormal);
    char*               gMiniDumpFile = "log/liveserver.dmp";
}

LONG __stdcall KnCrashHandler( EXCEPTION_POINTERS * pExPtrs )
{       
    // Count on the BugSlayer's OutputDebugString (annoying) if
    // we're out of stack; if we're a service, we'll have hung
    // before getting here.  Unfortunately, it's not as rare for us as
    // for many other programs, since we're multithreaded (and have therefore
    // declared a stack size), but it's rare enough to have worked out OK for a while.
    // When we get hangs or crashes on Windows with no stack trace or minidump, then
    // we're probably looking at exactly that case. Try increasing the stack size
    // in knrouter.tcl.
    if ( EXCEPTION_STACK_OVERFLOW != pExPtrs->ExceptionRecord->ExceptionCode )
    {
        // None of the BugSlayer routines are thread-safe.  OTOH, it's hard
        // to bring myself to use another mutex at this point, since we deadlock
        // so often for mutex problems. Doing it anyway.
      ...
 
[truncated message content]