Encoder-Decoder/DS/hash.c
/*
    Hash Table Implementation
    
    Author      => Abdallah Mohamed Elsharif
    Date        => 18-1-2024
*/

#include "hash.h"

Key *key_new(void *data, int nSize, void (* print)(void *), int (* compare)(void *, void *))
{
    Key *k;

    if ( k = malloc(sizeof(Key)) )
    {
        k->print = print;
        k->compare = compare;
        k->nSize = nSize;

        if ( k->data = malloc(k->nSize) )
        {
            memcpy(k->data, data, k->nSize);
            return k;
        }

        free( k );
    }

    return NULL;
}

int key_compare(Key *k, void *pKeyValue, int nKeySize)
{
    // Check if the key data type wasn't same
    if ( k->nSize != nKeySize )
        return k->nSize - nKeySize;

    return k->compare(k->data, pKeyValue);
}

unsigned long key_hash(Key *k, size_t lMaxSize)
{
    return genhash( k->data, k->nSize, lMaxSize );
}

void key_destroy(Key **k)
{
    free( (*k)->data );
    free( *k );
    ( *k ) = NULL;
}

Item *item_new(void *data, int nSize, void *(* allocate)(size_t), void (* deallocate)(void *), void (* print)(void *), int (* compare)(void *, void *))
{
    Item *i;

    if ( i = malloc(sizeof(Item)) )
    {
        i->allocate = allocate;
        i->deallocate = deallocate;
        i->print = print;
        i->compare = compare;
        i->nSize = nSize;

        if ( i->data = i->allocate(i->nSize) )
        {
            memcpy(i->data, data, i->nSize);
            return i;
        }

        free( i );
    }

    return NULL;
}

void item_destroy(Item **i)
{
    ( *i )->deallocate( (*i)->data );
    free( *i );
    ( *i ) = NULL;
}

Node *node_new(Key *k, Item *i)
{
    Node *node;

    if ( node = malloc(sizeof(Node)) )
    {
        node->key = k;
        node->item = i;
        return node;
    }

    return NULL;
}

// Callback for the list
int node_compare(void *node, void *key)
{
    Node *n;
    
    // We store the addresses of the nodes, so we dereferencing in this way
    n = *(Node **) node; 

    // Compare the sizes of the keys
    if ( n->key->nSize != ((Key *) key)->nSize ) // if the types are not same
        return n->key->nSize - ((Key *) key)->nSize;

    return n->key->compare( n->key->data, ((Key *) key)->data );
}

void node_destroy(Node **node)
{
    free( *node );
    ( *node ) = NULL;
}

Hash *hash_new(size_t lMaxSize, HType type)
{
    Hash *h;

    if ( h = malloc(sizeof(Hash)) )
    {
        h->lMaxSize = lMaxSize;
        h->lSize = h->lCollisions = h->lNextItemIdx = 0;
        h->type = type;

        if ( h->data = calloc(h->lMaxSize, sizeof(void *)) )
            return h;

        free( h );
    }

    return NULL;
}

int hash_empty(Hash *h)
{
    return ( hash_size(h) == 0 );
}

int hash_insert(Hash *h, Key *k, Item *i)
{
    void **temp;
    Node *node;
    size_t lCtr;
    unsigned long ulHash;

    // Generate a hash from the key
    ulHash = key_hash( k, h->lMaxSize );

    if ( h->type == REPLACEMENT )
    {
        if ( ! h->data[ulHash] )
        {
            if ( !(node = node_new(k, i)) )
                return 0;

            h->lSize++;
        } else { // Collision case
            node = (Node *) h->data[ulHash];

            // Check if the key exist
            if ( node_compare(&node, k) == 0 )
                return 0; // To avoid manipulating an exist key

            // Remove the old key and item 
            key_destroy( &node->key );
            item_destroy( &node->item );

            // Replace with the new 
            node->key = k;
            node->item = i;

            h->lCollisions++;
        }

        // Insert the node into the table
        h->data[ ulHash ] = (void *) node;
    }

    else if ( h->type == OPEN_ADDRESSING )
    {
        // Check if there are no available entries
        if ( h->lSize == h->lMaxSize )
            return 0;

        // The index of the next entry to be read
        lCtr = 0;

        // Iterate over all entries to ensuring that the key doesn't exist
        while ( hash_next(h, &lCtr, NULL, NULL) )
            if ( node_compare(h->data + lCtr - 1, k) == 0 )
                return 0;

        // Pointing now to the appropriate entry
        temp = h->data + ulHash;

        // Check whether the appropriate entry is available or not
        if ( *temp )
        {
            // This is a f*cking collision case
            h->lCollisions++;

            // Number of entries to the right of the appropriate entry
            lCtr = h->lMaxSize - 1 - ulHash;

            // Find an unused entry next to the appropriate entry
            while ( lCtr-- && *(++temp) );
            
            // WHAT THE FUCK IF ALL ENTRIES ON THE RIGHT WERE UNAVAILABLE ???
            if ( lCtr == -1 )
            {
                // Pointing now to the suitable entry
                temp = h->data + ulHash;

                // The index of the appropriate entry ( Number of entries to the left of it )
                lCtr = ulHash;

                // Search backward until find an available entry
                while ( lCtr-- && *(--temp) );
            }
        }

        // Create the node
        if ( !(node = node_new(k, i)) )
            return 0;

        // insert into the table
        ( *temp ) = (void *) node;
        
        h->lSize++;
    }

    else if ( h->type == CHAINING )
    {
        // Initialize a list for this entry if was not initialized yet
        if ( ! h->data[ulHash] )
            if ( !(h->data[ulHash] = (void *) llist_init()) )
                return 0;

        // Create a node
        if ( !(node = node_new(k, i)) )
            return 0;

        // Collision check
        if ( ! llist_empty((List *) h->data[ulHash]) )
        {
            // Check if the given key was used before
            if ( llist_search((List *) h->data[ulHash], (void *) k, sizeof(Node *)) != -1 )
                return 0;

            h->lCollisions++;
        }

        if ( ! llist_insert(
            (List *) h->data[ulHash],
            (void *) &node, // Insert the address of the node, not the node itself
            sizeof(void *),
            malloc, // malloc and free are suitable for dealing with the node address (we don't need to develop custom allocators)
            free,
            NULL,  // We don't need to print the node.
            node_compare
        ) )
            // Something goes wrong
            return 0;

        h->lSize++;
    }

    else // Unsupported type
        return 0;

    return 1;
}

int hash_update(Hash *h, Key *k, Item *i)
{
    void *pEntry;
    size_t lPos;
    unsigned long ulHash;

    // Calculate the hash from the key value
    ulHash = key_hash(k, h->lMaxSize);

    // Find the target entry
    if ( pEntry = h->data[ulHash] )
    {
        if ( h->type == OPEN_ADDRESSING )
        {
            lPos = ulHash;
            
            // Find the node
            do {
                pEntry = h->data[ lPos ];
                
                if ( pEntry && node_compare(&pEntry, (void *) k) == 0 )
                    break;

            } while ( ++lPos != h->lMaxSize );
            
            // If the node was not on the right
            if ( lPos == h->lMaxSize )
            {
                // Pointing now to the suitable entry
                lPos = ulHash;

                // Search backward
                while ( lPos-- ) 
                    if ( pEntry = h->data[lPos] )
                        if ( node_compare(&pEntry, (void *) k) == 0 )
                            break;

                if ( lPos == -1 ) // Not found
                    return 0;
                
            }

        }

        else if ( h->type == CHAINING )
        {
            // pEntry will be set at the end of the function, so it doesn't affect the behavior of the func
            if ( (lPos = llist_search2((List *) pEntry, (void *) k, sizeof(Node *), &pEntry)) == -1 )
                return 0; // Not found

            // We store the address of the node in the list, so we have to deref as follows
            pEntry = *(void **) pEntry;

        }

        // Destroy the old item
        item_destroy( &((Node *) pEntry)->item );

        // Set the new item
        ((Node *) pEntry)->item = i;

        return 1;
    }

    return 0;
}

size_t hash_size(Hash *h)
{
    return h->lSize;
}

void *hash_get(Hash *h, Key *k)
{
    Item *i;

    // Get the item by the key
    if ( ! (i = hash_get2(h, k)) )
        return NULL;

    return i->data;
}

Item *hash_get2(Hash *h, Key *k)
{
    void *ent;
    size_t lPos;
    unsigned long ulHash;

    // Calculate the hash
    ulHash = key_hash(k, h->lMaxSize);

    // Find the target entry
    if ( ent = h->data[ulHash] )
    {
        if ( h->type == REPLACEMENT )
            return ((Node *) ent)->item;

        else if ( h->type == OPEN_ADDRESSING )
        {
            lPos = ulHash;
            
            // Find the node
            do {
                ent = h->data[ lPos ];
                
                if ( ent && node_compare(&ent, (void *) k) == 0 )
                    break;

            } while ( ++lPos != h->lMaxSize );
            
            // If the node was not on the right
            if ( lPos == h->lMaxSize )
            {
                // Pointing now to the suitable entry
                lPos = ulHash;

                // Search backward
                while ( lPos-- ) 
                    if ( ent = h->data[lPos] )
                        if ( node_compare(&ent, (void *) k) == 0 )
                            break;

                if ( lPos == -1 ) // Not found
                    return NULL;
                
            }

            return ((Node *) ent)->item;
        }

        else if ( h->type == CHAINING )
        {
            // Find the node 
            // We must pass the node address size, not the key size because the search func expect a node type, not a key
            // However the comparison function can compare a node with a key 
            if ( (lPos = llist_search2((List *) ent, (void *) k, sizeof(Node *), &ent)) == -1 )
                return NULL; // Not found

            // We store the address of the node in the list, so we have to deref as follows
            ent = *(void **) ent;

            return ((Node *) ent)->item;
        }
    }

    return NULL;
}

Key *hash_getkey(Hash *h, void *pKeyValue, int nKeySize)
{
    void *pEntry;
    Key *pTempKey;
    size_t lPos;
    unsigned long ulHash;

    // Calculate the hash from the key value
    ulHash = genhash(pKeyValue, nKeySize, h->lMaxSize);

    // Find the target entry
    if ( pEntry = h->data[ulHash] )
    {
        if ( h->type == REPLACEMENT )
        {
            if ( key_compare(((Node *) pEntry)->key, pKeyValue, nKeySize) == 0 )
                return ((Node *) pEntry)->key;
        }

        else if ( h->type == OPEN_ADDRESSING )
        {
            lPos = ulHash;
            
            // Find the node
            do {
                pEntry = h->data[ lPos ];
                
                if ( pEntry && key_compare(((Node *) pEntry)->key, pKeyValue, nKeySize) == 0 )
                    break;

            } while ( ++lPos != h->lMaxSize );
            
            // If the node was not on the right
            if ( lPos == h->lMaxSize )
            {
                // Pointing now to the suitable entry
                lPos = ulHash;

                // Search backward
                while ( lPos-- ) 
                    if ( pEntry = h->data[lPos] )
                        if ( key_compare(((Node *) pEntry)->key, pKeyValue, nKeySize) == 0 )
                            break;

                if ( lPos == -1 ) // Not found
                    return NULL;
                
            }

            return ((Node *) pEntry)->key;
        }

        else if ( h->type == CHAINING )
        {
            // Create a temp key from the value for search
            if ( ! (pTempKey = key_new(pKeyValue, nKeySize, NULL, NULL)) )
                return NULL;

            if ( llist_search2((List *) pEntry, (void *) pTempKey, sizeof(Node *), &pEntry) == -1 )
            {
                // Remove the temp key
                key_destroy( &pTempKey );

                return NULL; // Not found
            }

            // Remove the temp key
            key_destroy( &pTempKey );

            // We store the address of the node in the list, so we have to deref as follows
            pEntry = *(void **) pEntry;

            return ((Node *) pEntry)->key;
        }
    }
    
    return NULL;
}

int hash_delete(Hash *h, Key *k)
{
    void **temp;
    void *ent;
    size_t lPos;
    unsigned long ulHash;

    // Calculate the hash
    ulHash = key_hash(k, h->lMaxSize);

    // Find the target entry
    if ( ent = h->data[ulHash] )
    {
        if ( h->type == REPLACEMENT )
        {
            if ( node_compare(&ent, (void *) k) != 0 )
                return 0; // A different key

            key_destroy( &((Node *) ent)->key );
            item_destroy( &((Node *) ent)->item );
            node_destroy( (Node **) h->data + ulHash );
            h->lSize--;
            
            return 1;
        }

        else if ( h->type == OPEN_ADDRESSING )
        {
            // Pointing now to the suitable entry
            temp = h->data + ulHash;

            // Search from the hash index 
            lPos = ulHash;

            // Find the target node
            do {
                
                if ( ent && node_compare(&ent, (void *) k) == 0 )
                    break;

                // Next entry
                ent = *( ++temp );

            } while ( ++lPos != h->lMaxSize );
            
            
            // If the node was not on the right
            if ( lPos == h->lMaxSize )
            {
                // The position of the target entry
                lPos = ulHash;

                // Pointing now to the suitable entry
                temp = h->data + lPos;

                // Search backward
                while ( lPos-- ) 
                    if ( ent = *( --temp ) )
                        if ( node_compare(&ent, (void *) k) == 0 )
                            break;

                if ( lPos == -1 ) // Not found
                    return 0;
                
            }

            key_destroy( &((Node *) ent)->key );
            item_destroy( &((Node *) ent)->item );
            node_destroy( (Node **) temp );
            h->lSize--;

            return 1;
        }

        else if ( h->type == CHAINING )
        {
            size_t lIdx;

            // Find the node
            if ( (lIdx = llist_search2((List *) ent, (void *) k, sizeof(Node *), &ent)) == -1 )
                return 0; // We couldn't find the node

            // Deref the entry ( we have pushed the address of the entry into the list, and the list returns a ptr to our data )
            // That's why we do dereferencing as follows
            ent = *(void **) ent;

            // Cleanup the node
            key_destroy( &((Node *) ent)->key );
            item_destroy( &((Node *) ent)->item );
            node_destroy( (Node **) &ent );
            
            // Delete the node from the list
            if ( ! llist_deleteAt((List *) h->data[ulHash], lIdx) )
                return 0; // Something goes wrong when deleting the node from the list

            // If the list becomes empty, we have to cleanup the list and mark this entry as unused
            if ( llist_empty((List *) h->data[ulHash]) )
            {
                llist_cleanup( (List **) h->data + ulHash );
                h->data[ulHash] = NULL;
            }

            h->lSize--;

            return 1;
        }

    }

    return 0;
}

int hash_next(Hash *h, size_t *ulpPos, Key **k, Item **i)
{
    void *entry;
    Node *node;

    // Check whether the given position is in the expected range or not
    if ( hash_empty(h) || *ulpPos >= h->lMaxSize )
        goto FAIL;

    // Find the next available entry
    if ( ! (entry = h->data[ *ulpPos ]) )
    {
        do {
            // Check if we reach the end of the table
            if ( ++(*ulpPos) == h->lMaxSize )
                goto FAIL;

            entry = h->data[ *ulpPos ];
        } while ( ! entry );
    }

    if ( h->type == REPLACEMENT || h->type == OPEN_ADDRESSING )
    {
        if ( k )
            *k = ( (Node *) entry )->key;

        if ( i )
            *i = ( (Node *) entry )->item;

        // Next position 
        ( *ulpPos )++;
        
        return 1;
    }

    else if ( h->type == CHAINING )
    {   

        // Get current node
        if ( node = *(Node **) llist_getitemAt((List *) entry, h->lNextItemIdx) )
        {
            if ( k )
                *k = node->key;

            if ( i )
                *i = node->item;

            // Set next item index    
            h->lNextItemIdx++;

            // If the next item reaches the end of the list, we have to reset it to zero, then jump on the next entry
            if ( h->lNextItemIdx == llist_size((List *) entry) )
            {
                h->lNextItemIdx = 0;
                ( *ulpPos )++;
            }

            return 1;
        }
        
    }

FAIL:
    // Failed to get the node data
    if ( k )
        *k = NULL;

    if ( i )
        *i = NULL;

    return 0;
}

void hash_print(Hash *h)
{
    Item *pItem = NULL;
    Key *pKey = NULL;
    size_t lPos = 0;

    puts("{");

    while ( hash_next(h, &lPos, &pKey, &pItem) )
    {
        printf("\t");
        pKey->print( pKey->data );
        printf(": ");
        pItem->print( pItem->data );
        printf(",  // ( 0x%X )\n", key_hash(pKey, h->lMaxSize));
    }

    puts("}");
}

void hash_destroy(Hash **h)
{
    void **temp;
    Item *pItem = NULL;
    Key *pKey = NULL;
    size_t lPos = 0;

    if ( ! hash_empty(*h) )
    {
        // Destroy all keys and items
        while ( hash_next(*h, &lPos, &pKey, &pItem) )
        {
            key_destroy( &pKey );
            item_destroy( &pItem );
        }

        temp = (*h)->data;

        // Deallocate all entries
        while ( (*h)->lMaxSize-- )
        {
            if ( *temp )
            {
                if ( (*h)->type == CHAINING )
                    llist_cleanup( (List **) temp );

                else
                    node_destroy( (Node **) temp );
            }

            // Next entry
            temp++;
        }
    }

    free( (*h)->data );
    free( *h );
    ( *h ) = NULL;
}

unsigned long genhash(void *data, int nSize, size_t lMaxSize)
{
    unsigned long ulHash = 0;

    for (int nIdx = 0; nIdx < nSize; nIdx++)
        ulHash += *( (unsigned char *) data + nIdx );

    return ulHash % lMaxSize;
}