Trie.c

Go to the documentation of this file.

#include "Trie.h"

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

struct Trie_node * Trie_node_init_empty()
{
        struct Trie_node * ret = malloc( sizeof( struct Trie_node ) );
        
        if( !ret )
        {
                perror("malloc");
                return NULL;
        }
        
        memset( ret, 0, sizeof( struct Trie_node ) );

        return ret;
}

struct Trie_node * Trie_node_init_noalloc( void *payload, size_t size )
{
        struct Trie_node * ret = Trie_node_init_empty();
        
        if( !ret )
                return NULL;
        
        ret->payload = payload;
        ret->size = size;
        
        return ret;
}

int Trie_node_set( struct Trie_node *tn, void *payload, size_t size )
{
        if( tn->size != size )
        {
                tn->payload = realloc( tn->payload, size );
                
                if( !tn->payload )
                {
                        perror("realloc");
                        return 1;
                }
        }
        
        memcpy( tn->payload, payload, size );
        tn->size = size;
        
        return 0;
}

void Trie_node_free_payload( struct Trie_node * tn )
{
        if( !tn )
                return;
        
        free( tn->payload );
        tn->payload = NULL;
        tn->size = 0;
}


void Trie_node_release( struct Trie_node * tn )
{
        int i;
        
        MALP_Spinlock_trylock(&tn->lock);
        
        for( i = 0 ; i < 94 ; i++ )
        {
                if( tn->children[i] )
                        Trie_node_release( tn->children[i]  );
        }

        free( tn->payload );
        memset( tn, 0, sizeof( struct Trie_node ) );
        
        free( tn );
}


int Trie_init( struct Trie *tr )
{
        tr->root =  Trie_node_init_empty();
        return 0;
}

int Trie_release( struct Trie *tr )
{
        Trie_node_release( tr->root );
        tr->root = NULL;
        return 0;
}


int Trie_set( struct Trie *tr, char *key, void *payload, size_t size )
{
        struct Trie_node *tn = Trie_acquire_node( tr, key );
        
        if( !tn )
                return 1;
        
        if( Trie_node_set( tn, payload, size ) )
                return 1;
        
        Trie_relax_node( tn );
        
        return 0;
}

int Trie_set_no_alloc( struct Trie *tr, char *key, void *payload, size_t size )
{
        struct Trie_node *tn = Trie_acquire_node( tr, key );
        
        if( !tn )
                return 1;
        
        Trie_node_free_payload( tn );
        tn->payload = payload;
        tn->size = size;
        
        Trie_relax_node( tn );
        
        return 0;
}

int _Trie_delete( struct Trie_node *tn, char *key, int depth )
{
        if( !tn )
                return 0;
        
        MALP_Spinlock_lock(&tn->lock);
        
        char c = *key;
        
        key++;
        
        if( c == '\0' )
        {
                        
                // Found it at least clear the payload
                Trie_node_free_payload( tn );

                int i;
                
                for( i = 0 ; i < 94 ; i++ )
                {
                        if( tn->children[i] )
                        {
                                /* No children we are about to free the node*/
                                MALP_Spinlock_unlock(&tn->lock);
                                return 0;
                        }
                }
                
                
                return 1;
        }
        
        int val = c - 32;
        
        if( _Trie_delete( tn->children[ val ], key, depth + 1 ) && depth /* Make sure we do not clear the root */ )
        {
                /* If  node is a leaf we can even clear the node itself */
                Trie_node_release( tn->children[ val ] );
                tn->children[ val ] = NULL;
        }
        
        MALP_Spinlock_unlock(&tn->lock);
        return 0;
}


void Trie_delete( struct Trie *tr, char *key )
{
         _Trie_delete( tr->root, key, 0 );
}