/Users/dbr/ma/src/bas/lml/hash.c

Go to the documentation of this file.

#include "base.h"

#define hashStep (107)

Hash * HashInit( void * set,
                 UINT (*GetIndexOfNewObject)( void *, const void * ),
                 UINT (*GetFirstIndex)( void * ),
                 UINT (*GetNextIndex)( void *, UINT ),
                 boolean (*Equals)( void *, const void *, UINT ),
                 UINT (*HashCode)( void *, const void *, UINT ),
                 UINT (*HashCode2)( void *, UINT, UINT ) ){
    Hash * hash;
    UINT i;

    hash = (Hash *)Malloc( 1, sizeof(Hash) );
    hash->hashSize = 63;
    hash->hash = (UINT *)Malloc( hash->hashSize, sizeof(UINT) );
    for( i = 0; i < hash->hashSize; i++ ){
        hash->hash[i] = NO;
    }
    hash->objectsStored = 0;
    hash->set = set;
    hash->GetIndexOfNewObject = GetIndexOfNewObject;
    hash->GetFirstIndex = GetFirstIndex;
    hash->GetNextIndex = GetNextIndex;
    hash->Equals = Equals;
    hash->HashCode = HashCode;
    hash->HashCode2 = HashCode2;
    return hash;
}

UINT HashAdd( Hash * hash, const void * object ){
    UINT i, ret;

    for( i = hash->HashCode(hash->set, object, hash->hashSize); hash->hash[i] != NO; i = (i + hashStep) % hash->hashSize ){
        if( hash->Equals( hash->set, object, hash->hash[i] ) ){
            return hash->hash[i];
        }
    }
    hash->hash[i] = ret = hash->GetIndexOfNewObject( hash->set, object );
    hash->objectsStored++;
    if( ((U64)(10))*((U64)(hash->objectsStored)) > ((U64)(9))*((U64)(hash->hashSize)) ){
        UINT index;

        hash->hashSize = 2*hash->hashSize + 1;

        hash->hash = Realloc( hash->hash, hash->hashSize, sizeof(UINT) );

        for( i = 0; i < hash->hashSize; i++ ){
            hash->hash[i] = NO;
        }
        for( index = hash->GetFirstIndex( hash->set ); index != NO; index = hash->GetNextIndex( hash->set, index ) ){
            for( i = hash->HashCode2(hash->set, index, hash->hashSize); hash->hash[i] != NO; i = (i + hashStep) % hash->hashSize );
            hash->hash[i] = index;
        }
    }
    return ret;
}

UINT HashGetIndex( Hash * hash, const void * object ){
    UINT i;
    i = hash->HashCode(hash->set, object, hash->hashSize);
    for( ; hash->hash[i] != NO; i = (i + hashStep) % hash->hashSize ){
        if( hash->Equals( hash->set, object, hash->hash[i] ) ){
            return hash->hash[i];
        }
    }
    return NO;
}

void HashFree( Hash * hash ){
    Free( hash->hash );
    Free( hash );
}

void HashReset( Hash * hash ){
    UINT i;

    for( i = 0; i < hash->hashSize; i++ ){
        hash->hash[i] = NO;
    }
    hash->objectsStored = 0;
}