#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "common.h"


/*#define HASH_INDEX(OBJECT)  ( (OBJECT.server+OBJECT.path) % (100000-1) + 1 )*/
#define HASH_INDEX(OBJECT)  ( (OBJECT.server+OBJECT.path) % (HashKey-1) + 1 )

#define NOT_USED(INDEX) ( ObjectsHashTable[INDEX].object.server==INVALID_TAG \
                         && ObjectsHashTable[INDEX].object.path==INVALID_TAG )


OBJECT_IN_HASH_TABLE *ObjectsHashTable = NULL; /* an array indicating the */
                                               /* state of all objects    */
static INT HashKey;
static INT HashTableSize;
static INT OverflowPosition;


static INT get_hash_key(INT hash_table_size)
{
    INT tmp, key;

    if (hash_table_size < 20) {
        key = 10;
    }
    else {
        key = 1;
        tmp = hash_table_size;
        do {
            tmp /= 10;
            key *= 10;
        } while (tmp > 10);
        key = hash_table_size - (hash_table_size % key);
    }
    return (key);
}

/* The ObjectsHashTable should be bigger than the number of unique objects! */
void init_objects_hash_table(INT size)
{
    INT i;

    if (size <= 0) {
        ERROR_LOG("\ninit_objects_hash_table: size <= 0 ! Exit!\n\n");
        exit(-1);
    }

    ObjectsHashTable = (OBJECT_IN_HASH_TABLE *)
                       malloc( size * sizeof(OBJECT_IN_HASH_TABLE) );
    IF_OUT_OF_MEM(ObjectsHashTable, "Objects Hash Table")

    for (i=0; i<size; i++) {
        ObjectsHashTable[i].object.server  = INVALID_TAG;
        ObjectsHashTable[i].object.path    = INVALID_TAG;
        ObjectsHashTable[i].clashed_next   = INVALID_TAG;
        ObjectsHashTable[i].in_which_cache = INVALID_TAG;
        ObjectsHashTable[i].position_in_cache = NULL;
    } 
    HashTableSize = size;
    OverflowPosition = size - 1;
    HashKey = get_hash_key(size);
}

INT find_object_in_hash_table(OBJECT_ID object)
{
    INT index;

    index = HASH_INDEX(object);
    assert(index > 0);

    /* if ( ObjectsHashTable[index].object.path == INVALID_TAG ) { */
    if ( NOT_USED(index) ) {
        return (INVALID_TAG);  /* no object seen with this hash index yet */
    }
    else {
        while ( (index != INVALID_TAG) &&
                !SAME_OBJECT(ObjectsHashTable[index].object, object) ) {
            index = ObjectsHashTable[index].clashed_next;
        }
        return (index); /* if index==INVALID_TAG, means not found */
    }
}

INT add_object_into_hash_table(OBJECT_ID object, INT obj_size, INT last_modify)
{
    INT index, pos;

    index = HASH_INDEX(object);
    assert(index > 0);

    if (ObjectsHashTable[index].object.path == INVALID_TAG) {
        /* no object seen with this hash index yet */
        SET_OBJECT(ObjectsHashTable[index].object, object);
        ObjectsHashTable[index].size = obj_size;
        ObjectsHashTable[index].last_modify = last_modify;
        return index;
    }
    else {
        /* For hash conflicts, we grow from the other end of the hash table */
    
        /* make sure the OverflowPosition is empty; */
        while ( (OverflowPosition>=0) && !NOT_USED(OverflowPosition) ) {
            OverflowPosition--;
        }
        if (OverflowPosition < 0) {
            ERROR_LOG("\nObjectsHashTable array not big enough! Exit!\n\n");
            exit(-1);
        }
    
        /* add the object into this position */
        SET_OBJECT(ObjectsHashTable[OverflowPosition].object, object);
        ObjectsHashTable[OverflowPosition].size = obj_size;
        ObjectsHashTable[OverflowPosition].last_modify = last_modify;
        /* ObjectsHashTable[OverflowPosition].clashed_next = INVALID_TAG; */

        /* add this element to the tail of the corresponding clash-list */
        /* 1st: find the tail of the clash list */
        while (ObjectsHashTable[index].clashed_next != INVALID_TAG) {
            index = ObjectsHashTable[index].clashed_next;
        }
        /* 2nd: make the tail point to this newly added element */
        ObjectsHashTable[index].clashed_next = OverflowPosition;

        pos = OverflowPosition;
        OverflowPosition--;

        return pos;
    }
}

INT reset_the_field_of_position_in_cache()
{
    INT i, num;

    num = 0;
    for (i=0; i<HashTableSize; i++) {
        if (ObjectsHashTable[i].position_in_cache != NULL) {
            ObjectsHashTable[i].position_in_cache = NULL;
            num++;
        }
    }
    return (num);
}

void print_hash_table()
{
    INT index;

    printf("Hash Table:\n");
    for (index=0; index<HashTableSize; index++) {
        if ( !NOT_USED(index) ) {
            printf(" %9lld: hash_key=%-9lld  %9lld , %-9lld  clashed_next: %lld\n",
                   index, HASH_INDEX(ObjectsHashTable[index].object),
                   ObjectsHashTable[index].object.server,
                   ObjectsHashTable[index].object.path,
                   ObjectsHashTable[index].clashed_next );
        }
    }
    printf("\n");
}


/* #define TEST */
#ifdef TEST

main()
{
    INT i;
    OBJECT_ID object;

    init_objects_hash_table(10);

    for (i=0; i<HashTableSize; i++) {
        object.server=i;
        object.path  =10-i;
        add_object_into_hash_table(object, i, 10*i);
    }

    print_hash_table();

}

#endif

