Hash.cpp

/*
 *  XMail by Davide Libenzi (Intranet and Internet mail server)
 *  Copyright (C) 1999,..,2010  Davide Libenzi
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 *  Davide Libenzi <davidel@xmailserver.org>
 *
 */

#include "SysInclude.h"
#include "SysDep.h"
#include "SvrDefines.h"
#include "Hash.h"



#define HMASK_TOP_BIT (1UL << (sizeof(long) * 8 - 1))


struct Hash {
    HashOps Ops;
    unsigned long ulCount;
    unsigned long ulHMask;
    SysListHead *pBkts;
};


HASH_HANDLE HashCreate(HashOps const *pOps, unsigned long ulSize)
{
    unsigned long i, ulHMask;
    Hash *pHash;

    if ((pHash = (Hash *) SysAlloc(sizeof(Hash))) == NULL)
        return INVALID_HASH_HANDLE;
    pHash->Ops = *pOps;
    for (ulHMask = 2; !(ulHMask & HMASK_TOP_BIT) && ulHMask <= ulSize; ulHMask <<= 1);
    ulHMask--;
    pHash->ulHMask = ulHMask;
    if ((pHash->pBkts = (SysListHead *)
         SysAlloc((ulHMask + 1) * sizeof(SysListHead))) == NULL) {
        SysFree(pHash);
        return INVALID_HASH_HANDLE;
    }
    for (i = 0; i <= ulHMask; i++)
        SYS_INIT_LIST_HEAD(&pHash->pBkts[i]);

    return (HASH_HANDLE) pHash;
}

void HashFree(HASH_HANDLE hHash, void (*pFree)(void *, HashNode *),
          void *pPrivate)
{
    Hash *pHash = (Hash *) hHash;
    unsigned long i;
    SysListHead *pHead, *pPos;
    HashNode *pHNode;

    if (pHash != NULL) {
        if (pFree != NULL) {
            for (i = 0; i <= pHash->ulHMask; i++) {
                pHead = &pHash->pBkts[i];
                while ((pPos = SYS_LIST_FIRST(pHead)) != NULL) {
                    pHNode = SYS_LIST_ENTRY(pPos, HashNode, Lnk);
                    SYS_LIST_DEL(&pHNode->Lnk);
                    (*pFree)(pPrivate, pHNode);
                }
            }
        }
        SysFree(pHash->pBkts);
        SysFree(pHash);
    }
}

unsigned long HashGetCount(HASH_HANDLE hHash)
{
    Hash *pHash = (Hash *) hHash;

    return pHash->ulCount;
}

void HashInitNode(HashNode *pHNode)
{
    ZeroData(*pHNode);
    SYS_INIT_LIST_HEAD(&pHNode->Lnk);
}

static int HashGrow(Hash *pHash)
{
    unsigned long i, ulHIdx, ulHMask;
    SysListHead *pBkts, *pHead, *pPos;
    HashNode *pHNode;

    ulHMask = pHash->ulHMask + 1;
    if (ulHMask & HMASK_TOP_BIT)
        return 0;
    ulHMask = (ulHMask << 1) - 1;
    if ((pBkts = (SysListHead *)
         SysAlloc((ulHMask + 1) * sizeof(SysListHead))) == NULL)
        return ErrGetErrorCode();
    for (i = 0; i <= ulHMask; i++)
        SYS_INIT_LIST_HEAD(&pBkts[i]);
    for (i = 0; i <= pHash->ulHMask; i++) {
        pHead = &pHash->pBkts[i];
        while ((pPos = SYS_LIST_FIRST(pHead)) != NULL) {
            pHNode = SYS_LIST_ENTRY(pPos, HashNode, Lnk);
            SYS_LIST_DEL(&pHNode->Lnk);
            ulHIdx = (*pHash->Ops.pGetHashVal)(pHash->Ops.pPrivate,
                               &pHNode->Key) & ulHMask;
            SYS_LIST_ADDT(&pHNode->Lnk, &pBkts[ulHIdx]);
        }
    }
    SysFree(pHash->pBkts);
    pHash->pBkts = pBkts;
    pHash->ulHMask = ulHMask;

    return 0;
}

int HashAdd(HASH_HANDLE hHash, HashNode *pHNode)
{
    Hash *pHash = (Hash *) hHash;
    unsigned long ulHIdx;
    SysListHead *pHead;

    if (pHash->ulCount >= pHash->ulHMask && HashGrow(pHash) < 0)
        return ErrGetErrorCode();
    ulHIdx = (*pHash->Ops.pGetHashVal)(pHash->Ops.pPrivate,
                       &pHNode->Key) & pHash->ulHMask;
    pHead = &pHash->pBkts[ulHIdx];
    SYS_LIST_ADDT(&pHNode->Lnk, pHead);
    pHash->ulCount++;

    return 0;
}

void HashDel(HASH_HANDLE hHash, HashNode *pHNode)
{
    Hash *pHash = (Hash *) hHash;

    SYS_LIST_DEL(&pHNode->Lnk);
    pHash->ulCount--;
}

int HashGetFirst(HASH_HANDLE hHash, HashDatum const *pKey,
         HashEnum *pHEnum, HashNode **ppHNode)
{
    Hash *pHash = (Hash *) hHash;
    unsigned long ulHIdx;
    SysListHead *pHead, *pPos;
    HashNode *pHNode;

    ulHIdx = (*pHash->Ops.pGetHashVal)(pHash->Ops.pPrivate,
                       pKey) & pHash->ulHMask;
    pHead = &pHash->pBkts[ulHIdx];
    for (pPos = SYS_LIST_FIRST(pHead); pPos != NULL;
         pPos = SYS_LIST_NEXT(pPos, pHead)) {
        pHNode = SYS_LIST_ENTRY(pPos, HashNode, Lnk);
        if ((*pHash->Ops.pCompare)(pHash->Ops.pPrivate, pKey,
                       &pHNode->Key) == 0) {
            *ppHNode = pHNode;
            pHEnum->ulHIdx = ulHIdx;
            pHEnum->pNext = SYS_LIST_NEXT(pPos, pHead);
            return 0;
        }
    }

    ErrSetErrorCode(ERR_NOT_FOUND);
    return ERR_NOT_FOUND;
}

int HashGetNext(HASH_HANDLE hHash, HashDatum const *pKey,
        HashEnum *pHEnum, HashNode **ppHNode)
{
    Hash *pHash = (Hash *) hHash;
    SysListHead *pPos, *pHead;
    HashNode *pHNode;

    pHead = &pHash->pBkts[pHEnum->ulHIdx];
    for (pPos = pHEnum->pNext; pPos != NULL;
         pPos = SYS_LIST_NEXT(pPos, pHead)) {
        pHNode = SYS_LIST_ENTRY(pPos, HashNode, Lnk);
        if ((*pHash->Ops.pCompare)(pHash->Ops.pPrivate, pKey,
                       &pHNode->Key) == 0) {
            *ppHNode = pHNode;
            pHEnum->pNext = SYS_LIST_NEXT(pPos, pHead);
            return 0;
        }
    }

    ErrSetErrorCode(ERR_NOT_FOUND);
    return ERR_NOT_FOUND;
}

static int HashFetchNext(Hash *pHash, unsigned long ulFrom, HashEnum *pHEnum,
             HashNode **ppHNode)
{
    unsigned long i;
    SysListHead *pHead, *pPos;

    for (i = ulFrom; i <= pHash->ulHMask; i++) {
        pHead = &pHash->pBkts[i];
        if ((pPos = SYS_LIST_FIRST(pHead)) != NULL) {
            pHEnum->ulHIdx = i;
            pHEnum->pNext = SYS_LIST_NEXT(pPos, pHead);
            *ppHNode = SYS_LIST_ENTRY(pPos, HashNode, Lnk);

            return 0;
        }
    }

    ErrSetErrorCode(ERR_NOT_FOUND);
    return ERR_NOT_FOUND;
}

int HashFirst(HASH_HANDLE hHash, HashEnum *pHEnum, HashNode **ppHNode)
{
    Hash *pHash = (Hash *) hHash;

    return HashFetchNext(pHash, 0, pHEnum, ppHNode);
}

int HashNext(HASH_HANDLE hHash, HashEnum *pHEnum, HashNode **ppHNode)
{
    Hash *pHash = (Hash *) hHash;
    SysListHead *pPos;

    if ((pPos = pHEnum->pNext) != NULL) {
        pHEnum->pNext = SYS_LIST_NEXT(pPos, &pHash->pBkts[pHEnum->ulHIdx]);
        *ppHNode = SYS_LIST_ENTRY(pPos, HashNode, Lnk);

        return 0;
    }

    return HashFetchNext(pHash, pHEnum->ulHIdx + 1, pHEnum, ppHNode);
}