Hash map of <string, vector<string>> implementation on C for group anagram problem-solving

group_anagrams_c.c

#define _POSIX_C_SOURCE 200809L

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>


#define MAX_STRING_LENGTH           100
#define HASH_SEED                   5381
#define CHAR_TABLE_SIZE             26
#define FIRST_CHARACTER_IN_TABLE    'a'

typedef struct
{
    char ** array;
    int size;
    int capacity;
} DynamicArray;

DynamicArray * DynamicArray_create()
{
    DynamicArray * dynamicArray = ( DynamicArray * ) malloc( sizeof( DynamicArray ) );
    dynamicArray->array = NULL;
    dynamicArray->size = 0;
    dynamicArray->capacity = 0;

    return dynamicArray;
}

void DynamicArray_initialize( DynamicArray * dynamicArray, int initialCapacity )
{
    dynamicArray->array = ( char ** ) malloc( initialCapacity * sizeof( char * ) );
    dynamicArray->size = 0;
    dynamicArray->capacity = initialCapacity;
}

void DynamicArray_destroy( DynamicArray * dynamicArray )
{
    for ( size_t index = 0; index < dynamicArray->size; index++ )
    {
        free( dynamicArray->array[ index ] );
    }
    free( dynamicArray->array );
    free( dynamicArray );
}

void DynamicArray_add( DynamicArray * dynamicArray, const char * str )
{
    if ( dynamicArray->size == dynamicArray->capacity )
    {
        dynamicArray->capacity *= 2;
        dynamicArray->array = ( char ** ) realloc( dynamicArray->array, dynamicArray->capacity * sizeof( char * ) );
    }

    dynamicArray->array[ dynamicArray->size ] = strdup( str );
    dynamicArray->size++;
}

int DynamicArray_getSize( DynamicArray * dynamicArray )
{
    return dynamicArray->size;
}

void DynamicArray_dump( DynamicArray * dynamicArray, char ** dump )
{
    for( size_t index = 0; index < dynamicArray->size; index++ )
    {
       dump[ index ] = dynamicArray->array[ index ];
    }
}

typedef struct Node
{
    char * key;
    DynamicArray * value;
    struct Node * next;
} Node;

typedef struct Map
{
    int size;
    Node ** table;
} Map;

Map * Map_create( size_t size )
{
    Map * map = ( Map * ) malloc( sizeof( Map ) );
    map->size = 0;
    map->table = ( Node ** ) calloc( size, sizeof( Node * ) );

    return map;
}

void Map_destroy( Map * map, size_t size )
{
    for ( size_t index = 0; index < size; index++ )
    {
        Node * node = map->table[ index ];
        while ( node != NULL )
        {
            Node * temp = node;
            node = node->next;
            DynamicArray_destroy( temp->value );
            free( temp->key );
            free( temp );
        }
    }

    free( map->table );
    free( map );
}

unsigned int hash( char * key, size_t size )
{
    unsigned int hash = HASH_SEED;
    int keySize = strnlen( key, MAX_STRING_LENGTH );

    for ( size_t index = 0; index < keySize; index++ )
    {
        hash = ( ( hash << 5 ) + hash ) + ( int ) key[ index ];
    }

    return hash % size;
}

Node * findNode( Node * node, char * key )
{
    while ( node != NULL )
    {
        if ( strncmp( node->key, key, MAX_STRING_LENGTH ) == 0 )
        {
            return node;
        }
        node = node->next;
    }

    return NULL;
}

void Map_add( Map * map, char * key, char * value, size_t size )
{
    unsigned int index = hash( key, size );
    Node * node = findNode( map->table[ index ], key );
    if ( node == NULL )
    {
        DynamicArray * dynamicArray = DynamicArray_create();
        DynamicArray_initialize( dynamicArray, size );
        DynamicArray_add( dynamicArray, value );

        node = ( Node * ) malloc( sizeof( Node ) );
        node->key = key;
        node->value = dynamicArray;
        node->next = map->table[ index ];
        map->table[ index ] = node;
        map->size++;
    }
}

bool Map_contains( Map * map, char * key, size_t size )
{
    unsigned int index = hash( key, size );
    Node * node = findNode( map->table[ index ], key );

    return ( node != NULL );
}

DynamicArray * Map_get( Map * map, char * key, size_t size )
{
    unsigned int index = hash( key, size );
    Node * node = findNode( map->table[ index ], key );

    return node->value;
}

char * createKey( char * str )
{
    int charsCounts[ CHAR_TABLE_SIZE ] = { 0 };
    for ( size_t index = 0; index < strnlen( str, MAX_STRING_LENGTH ); index++ )
    {
        charsCounts[ str[ index ] - FIRST_CHARACTER_IN_TABLE ]++;
    }

    char * key = malloc( (CHAR_TABLE_SIZE + 1) * sizeof( char ) );
    for ( size_t index = 0; index < CHAR_TABLE_SIZE; index++ )
    {
        key[ index ] = ( char ) ( charsCounts[ index ] + FIRST_CHARACTER_IN_TABLE );
    }
    key[ CHAR_TABLE_SIZE ] = '\0';

    return key;
}

int Map_getSize( Map * map )
{
    return map->size;
}

void prepareResults( Map * map, size_t size, int ** returnColumnSizes, char *** results )
{
    size_t resultIndex = 0;

    for ( size_t index = 0; index < size; index++ )
    {
        Node * node = map->table[ index ];
        while ( node != NULL )
        {
            ( *returnColumnSizes )[ resultIndex ] = DynamicArray_getSize( node->value );
            results[ resultIndex ] = ( char ** ) malloc( ( *returnColumnSizes )[ resultIndex ] * sizeof( char * ) );
            DynamicArray_dump( node->value, results[ resultIndex ] );
            resultIndex++;
            node  = node->next;
        }
    }
}

char *** groupAnagrams( char ** strs, int strsSize, int * returnSize, int ** returnColumnSizes, Map ** map )
{
    Map * anagramsMap = Map_create( strsSize );

    for ( size_t index = 0; index < strsSize; index++ )
    {
        char * key = createKey( strs[ index ] );
        DynamicArray * group;

        if ( Map_contains( anagramsMap, key, strsSize ) )
        {
            group = Map_get( anagramsMap, key, strsSize );
            DynamicArray_add( group, strs[ index ] );
            free( key );
        }
        else
        {
            Map_add( anagramsMap, key, strs[ index ], strsSize );
        }
    }

    *returnSize = Map_getSize( anagramsMap );
    char *** result = (char ***) malloc( *returnSize * sizeof( char ** ) );

    *returnColumnSizes = ( int * ) malloc( *returnSize * sizeof( int ) );
    prepareResults( anagramsMap, strsSize, returnColumnSizes, result );
    *map = anagramsMap;

    return result;
}

void showResult( char *** result, int * returnSize, int ** returnColumnSizes )
{
    printf( "%s", "[ " );
    for ( size_t groupIndex = 0; groupIndex < *returnSize; groupIndex++ )
    {
        printf( "%s", " [ " );
        for ( size_t stringIndex = 0; stringIndex < (*returnColumnSizes)[ groupIndex ]; stringIndex++ )
        {
            printf( " \"%s\" ", result[ groupIndex ][ stringIndex ] );
        }
        printf( "%s", " ] " );
    }
    puts( " ]" );
}

void clearResult( char *** result, int * returnSize, int ** returnColumnSizes )
{
    for ( size_t index = 0; index < *returnSize; index++ )
    {
        free( result[ index ] );
    }
    free( result );
}

int main( void )
{
    char * strs[] = { "eat", "tea", "tan", "ate", "nat", "bat" };
    int returnSize;
    int * returnColumnSizes = NULL;
    Map * map = NULL;

    char *** result = groupAnagrams( strs, 6, &returnSize , &returnColumnSizes, &map );

    showResult( result, &returnSize, &returnColumnSizes );
    Map_destroy( map, 6 );
    clearResult( result, &returnSize, &returnColumnSizes );
    free( returnColumnSizes );

    puts( "End of programm." );
    return EXIT_SUCCESS;
}