Article 113 - Set Implementation

This article describes an implementation of the Set Structure.

For information about the Set Structure, see Article 31 - Programming Data Structures.

To program a Set, we need to understand the interface of a Set.

Interface

  • New Hash Container
  • Add Entry
  • Remove Entry
  • Does Entry Exist

Implementation

In this implementation, we use the Node structure from the Link List Article, see Article 83 - Data Structure - How to Implement Linked List in C.

Set Structures.

struct HashContainer;

typedef struct HashEntry{
    int key;
    int content;
    struct HashContainer * hashContainer;
} EntryEntry;

typedef struct HashContainer{
    int numberOfEntries;
    HashEntry * entries[1000];
} HashContainer;

New Hash Container Function.

HashContainer * newHashContainer(){
    int i;
    HashContainer * hashContainer = 
        ( HashContainer * )malloc( sizeof( HashContainer ) );

    if( hashContainer ){
        for( i = 0; i < 1000; i++ ){
            hashContainer->entries[i] = 0;
        }

        hashContainer->numberOfEntries = 0;
    }

    return hashContainer;
}

Add Entry Function.

int addEntry( HashContainer * hashContainer, int key, int content = 0,
     int isMap = 0 ){
    HashContainer * newHashContainer;
    int result;
    int hashedKey = key % 1000;

    if( !hashContainer ){
        return -1;
    }

    //not a map and element exist, return gracefully
    if( !isMap && doesEntryExist( hashContainer, key ) ){
        return 0;
    }

    if( !hashContainer->entries[ hashedKey ] ){
        //no entry at this hash key, add new hash entry

        HashEntry * hashEntry = 
            ( HashEntry * )malloc( sizeof( HashEntry ) );

        if( !hashEntry ){
            return -2;
        }

        hashEntry->key = key;
        hashEntry->content = content;
        hashEntry->hashContainer = 0;

        hashContainer->entries[ hashedKey ] = hashEntry;

        hashContainer->numberOfEntries++;
    }
    else if( hashContainer->entries[ hashedKey ]->hashContainer ){
        //collision at key, with container
        //recurse into container and try again

        return addEntry( hashContainer->entries[ hashedKey ]->
            hashContainer, key / 1000, content );
    }
    else{
        //collision at key, without container
        //add container and then entry into container, if no map
        //if map, update content if keys match
        //otherwise, add container and recurse
        //since one key could be substring of other key

        if( isMap && hashContainer->entries[ hashedKey ]->key == key ){
            hashContainer->entries[ hashedKey ]->content = content;
        }

        newHashContainer = newHashContainer();

        //add existing entry into child container before removing
        result = addEntry( newHashContainer, hashContainer->
            entries[ hashedKey ]->key / 1000, hashContainer->
            entries[ hashedKey ]->content );

        if( result ){
            return result;
        }

        hashContainer->entries[ hashedKey ]->hashContainer = 
            newHashContainer;

        result = addEntry( newHashContainer, key / 1000, content );
        if( result ){
            return result;
        }

        hashContainer->entries[ hashedKey ]->key = 0;
        hashContainer->entries[ hashedKey ]->content = 0;
    }

    return 0;
}

Remove Entry Function.

int removeEntry( HashContainer * hashContainer, int key ){
    int HashEntry * previousHashEntry = 0;
    int result;
    int hashedKey = key % 1000;

    if( !hashContainer ){
        return -1;
    }

    //entry exists, remove entry
    if( hashContainer->entries[ hashedKey ] ){
        if( hashContainer->entries[ hashedKey ]->hashContainer ){
            //entry contained in child container, recurse and find it

            result = removeEntry( hashContainer->
                entries[ hashedKey ]->hashContainer, key / 1000 );
            if( result ){
                return result;
            }

            if( hashContainer->entries[ hashedKey ]->h
                ashContainer->numberOfEntries == 0 ){

                free( hashContainer->entries[ hashedKey ]->
                    hashContainer );
                free( hashContainer->entries[ hashedKey ] );
                hashContainer->entries[ hashedKey ] = 0;
                hashContainer->numberOfEntries--;
            }
        }
        else if( hashContainer->entries[ hashedKey ]->key == key ){
            free( hashContainer->entries[ hashedKey ] );
            hashContainer->entries[ hashedKey ] = 0;
            hashContainer->numberOfEntries--;
        }
    }

    return 0;
}

Does Entry Exist Function.

int doesEntryExist( HashContainer * hashContainer, int key ){
    int hashedKey = key % 1000;

    if( !hashContainer ){
        return 0; //null containers defaults to no entry exists
    }

    if( hashContainer->entries[ hashedKey ] ){
        if( hashContainer->entries[ hashedKey ]->hashContainer ){
            return doesEntryExist( hashContainer->
                entries[ hashedKey ]->hashContainer, key / 1000 );
        }
        else{
            return hashContainer->entries[ hashedKey ]->key == key;
        }
    }

    return 0;
}

Comments (0)

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2017. Vantasy World is a project developed by Vantasy Online. Privacy Policy.