Trie.h

Go to the documentation of this file.

#ifndef TRIE_H
#define TRIE_H

#include <stdlib.h>

#include "Spinlock.h"


#ifdef __cplusplus
extern "C" {
#endif


struct Trie_node
{
        void *payload;

        size_t size;
        MALP_Spinlock lock;
        
        /* From ascii 32 to ascii 126 */
        struct Trie_node *children[94];
};


struct Trie_node * Trie_node_init_empty();
struct Trie_node * Trie_node_init_noalloc( void *payload, size_t size );
void Trie_node_release( struct Trie_node * tn );

int Trie_node_set( struct Trie_node *tn, void *payload, size_t size );
void Trie_node_free_payload( struct Trie_node * tn );


struct Trie
{
        struct Trie_node *root;
};

static inline struct Trie_node * Trie_acquire_node( struct Trie *tr, char *key )
{
        struct Trie_node *current = tr->root;
        struct Trie_node *prev = NULL;
        
        if(!key)
                return NULL;

        do
        {
                /* From ascii 32 to ascii 126 */
                if( *key < 32 || 126 < *key )
                {
                        return NULL;
                }
                
                MALP_Spinlock_lock(&current->lock);
                
                int val = *key - 32;
                
                if( !current->children[ val ] )
                {
                        current->children[ val ] = Trie_node_init_empty();
                }
                
                prev = current;
                current = current->children[ val ];
                                
                MALP_Spinlock_unlock(&prev->lock);
                
                key++;
        }while( *key );
        
        return current;
}

static inline void Trie_relax_node( struct Trie_node *tn )
{
        if( tn )
                MALP_Spinlock_unlock(&tn->lock);
}


int Trie_init( struct Trie *tr );
int Trie_release( struct Trie *tr );


int Trie_set( struct Trie *tr, char *key, void *payload, size_t size );

static inline struct Trie_node * Trie_get( struct Trie *tr, char *key )
{
        struct Trie_node *ret = Trie_acquire_node( tr, key );
        
        if( !ret->payload )
        {
                Trie_relax_node( ret );
                return NULL;
        }
        
        return ret;
}


int Trie_set_no_alloc( struct Trie *tr, char *key, void *payload, size_t size );
void Trie_delete( struct Trie *tr, char *key );


#ifdef __cplusplus
}
#endif

#endif