---

dt_node_impl.c

Go to the documentation of this file.

#include "dt_node.h"

#include "dt_node_impl.h"

#include <assert.h>
#include <stdlib.h>
#include <string.h>


#ifndef NDEBUG

  unsigned dt_node_instance_count = 0;
#endif



dt_bool dt_node_is_valid( dt_node const* node )
{
   if( ! node ) return 0;

   if( node->refs <= 0 )
      return 0;

   switch( node->kind )
   {
   default:             return 0;
   case dt_leaf_node:   break;
   case dt_arr_node: {
         if( (node->buf.strEnd - node->buf.begin)%sizeof(arr_item) ) return 0;
         break;
      }
   case dt_rec_node: {
         if( (node->buf.strEnd - node->buf.begin)%sizeof(rec_item) ) return 0;
         break;
      }
   }
   return 1;
}


dt_node* dt_make_leaf( dt_byte const* begin, size_t len )
{
   dt_node* ans = (dt_node*)malloc(sizeof(dt_node));
   if( !! ans )
   {
      ans->kind = dt_leaf_node;
      ans->refs = 1;
      if( dt_buf_init_data( & ans->buf, begin, len ) )
      {
#ifndef NDEBUG
         ++ dt_node_instance_count;
#endif
         return ans;
      }
      free(ans);
   }
   return 00;
}

dt_node* dt_make_rec()
{
   dt_node* ans = (dt_node*)malloc(sizeof(dt_node));
   if( !! ans )
   {
      ans->kind = dt_rec_node;
      ans->refs = 1;
      if( dt_buf_init( & ans->buf ) )
      {
#ifndef NDEBUG
         ++ dt_node_instance_count;
#endif
         return ans;
      }
      free(ans);
   }
   return 00;
}

dt_node* dt_make_arr()
{
   dt_node* ans = (dt_node*)malloc(sizeof(dt_node));
   if( !! ans )
   {
      ans->kind = dt_arr_node;
      ans->refs = 1;
      if( dt_buf_init( & ans->buf ) )
      {
#ifndef NDEBUG
         ++ dt_node_instance_count;
#endif
         return ans;
      }
      free(ans);
   }
   return 00;
}


void dt_node_addref( dt_node* node )
{
   if( ! node ) return;

   assert( dt_node_is_valid(node) );
   ++ node->refs;
   assert( node->refs != 0 ); /* not looping around... */
}

void dt_node_release( dt_node* node )
{
   if( ! node ) return;

   assert( dt_node_is_valid(node) );

   if( 0 < --node->refs )
      return;
   switch( node->kind )
   {
   default:             assert( 00 ); return;
   case dt_leaf_node:   break;
   case dt_arr_node: {
         arr_item *scan, *end;
         assert( (node->buf.strEnd - node->buf.begin)%sizeof(arr_item) == 0 );
         scan = (arr_item*)node->buf.begin;
         end  = (arr_item*)node->buf.strEnd;
         for(  ; scan != end ; ++scan )
            dt_node_release( *scan );            
      }
      break;
   case dt_rec_node: {
         rec_item *scan, *end;
         assert( (node->buf.strEnd - node->buf.begin)%sizeof(rec_item) == 0 );
         scan = (rec_item*)node->buf.begin;
         end  = (rec_item*)node->buf.strEnd;
         for(  ; scan != end ; ++scan )
         {
            free( scan->key );
            dt_node_release( scan->node );   
         }         
      }
      break;
   }
   dt_buf_free( & node->buf );
   free( node );
#ifndef NDEBUG
   -- dt_node_instance_count;
#endif
}

enum dt_node_kind dt_node_get_kind( dt_node* node )
{
   assert( dt_node_is_valid(node) );
   return node->kind;
}


dt_bool dt_leaf_get_data( dt_node const* node, dt_byte const** begin, size_t* len )
{
   if( ! node ) return 0;

   assert( dt_node_is_valid(node) );

   if( node->kind != dt_leaf_node )
      return 0;
   *begin = node->buf.begin;
   *len   = node->buf.strEnd - *begin;
   return 1;
}


size_t dt_arr_get_size( dt_node const* arr )
{
   if( ! arr  ||  arr->kind != dt_arr_node  )
      return 0;

   assert( dt_node_is_valid(arr) );

   return (arr->buf.strEnd - arr->buf.begin) / sizeof(arr_item);
}

dt_node* dt_arr_get( dt_node const* arr, unsigned ind )
{
   if( ! arr ) return 00;

   assert( dt_node_is_valid(arr) );

   if(   arr->kind != dt_arr_node
      || ind >= (arr->buf.strEnd - arr->buf.begin)/sizeof(arr_item)
      ) return 00;
   return ((arr_item*)arr->buf.begin)[ind];
}

dt_bool dt_arr_put( dt_node* arr, unsigned ind, dt_node* item )
{
   arr_item* pos;
   
   if( ! item )
      return 0;
 
   assert( !arr || dt_node_is_valid(arr) );
   assert( dt_node_is_valid(item) );

   if(   ! arr
      || arr->kind != dt_arr_node
      || ind >= (arr->buf.strEnd - arr->buf.begin)/sizeof(arr_item)
      )
   {
      dt_node_release(item);
      return 0;
   }
   pos = ((arr_item*)arr->buf.begin) + ind;
   dt_node_release( *pos );
   *pos = item;
   return 1;
}

dt_bool dt_arr_append( dt_node* arr, dt_node* item )
{
   if( ! item ) return 0;
 
   assert( !arr || dt_node_is_valid(arr) );
   assert( dt_node_is_valid(item) );

   if(   !! arr  &&  arr->kind == dt_arr_node
      && dt_buf_append_data( & arr->buf, &item, sizeof(item) )
      ) return 1;

   dt_node_release( item );
   return 0;
}


size_t dt_rec_get_size( dt_node const* node )
{
   if( !node || node->kind != dt_rec_node )
      return 0;
   assert( dt_node_is_valid(node) );
   return  (node->buf.strEnd - node->buf.begin) / sizeof(rec_item);
}

static
int rec_key_cmp(dt_byte const* a, size_t la, dt_byte const* b, size_t lb)
{
   size_t l = (la<lb) ? la : lb;
   for(   ;  l--  ;  ++a, ++b  )
      if( *a != *b )
         return (*a<*b) ? -1 : +1;
   
   if( la!=lb ) return (la<lb) ? -1 : +1;
   return 0;
}

static
dt_bool rec_bsearch( rec_item* base, rec_item* end
                   , dt_byte const* key, size_t key_len
                   , rec_item** pos )
{
   size_t n = end-base;
   while( n > 0 )
   {
      size_t m = n/2;
      rec_item* mid = base+m;
      int cmp = rec_key_cmp( key,key_len, mid->key, mid->key_len );
      if( cmp==0 )
      {
         *pos = mid;
         return 1;
      }
      if( cmp<0 )
      {
         n = m;
      }
      else
      {
         ++m;
         base += m;
         n -= m;
      }
   }
   *pos = base;
   return 0;
}


dt_node*  dt_rec_get( dt_node const* rec, dt_byte const* key, size_t key_len )
{
   rec_item* pos;

   assert( !rec || dt_node_is_valid(rec) );

   if(   !! rec
      && ( !! key  || ! key_len )
      && rec->kind == dt_rec_node
      && rec_bsearch( (rec_item*)rec->buf.begin, (rec_item*)rec->buf.strEnd, key, key_len, &pos )
      )
      return pos->node;

   return 00;
}


dt_node*   dt_rec_sget( dt_node const* rec, char const* key )
{
   if( ! key )
      return 00;

   return dt_rec_get( rec, (dt_byte const*)key, strlen(key) );
}



dt_bool dt_rec_put( dt_node* rec
                  , dt_byte const* key, size_t key_len
                  , dt_node* item
                  )
{
   rec_item* pos;
   if( ! item ) return 0;
   if(   ! rec
      || ( !key && !!key_len )
      || rec->kind != dt_rec_node
      ) goto FAIL;
   
   assert( dt_node_is_valid(rec) );
   assert( dt_node_is_valid(item) );

   if( rec_bsearch( (rec_item*)rec->buf.begin, (rec_item*)rec->buf.strEnd, key, key_len, &pos ) )
   {
      dt_node_release( pos->node );
   }
   else
   {
      void*  alloc_key;
      
      /* Ensure that memory is available for new entry. */
      /*  WARN: recompute 'pos' from offset in case the buffer is reallocated */
      size_t rec_offs = pos - (rec_item*)rec->buf.begin;
      if( ! dt_buf_growth_reserve( & rec->buf, sizeof( rec_item ) ) )
         goto FAIL;
      pos = (rec_item*)rec->buf.begin + rec_offs;

      alloc_key = malloc(key_len);
      if( ! alloc_key )
         goto FAIL;

      memcpy( alloc_key, key, key_len );
      memmove( pos+1, pos, rec->buf.strEnd-(dt_byte*)pos );
      rec->buf.strEnd += sizeof(*pos);
      pos->key = alloc_key;
      pos->key_len = key_len;
   }
   pos->node = item;
   return 1;

FAIL:
   dt_node_release( item );
   return 0;
}


dt_bool dt_rec_sput( dt_node* rec, char const* key, dt_node* item )
{
   return dt_rec_put( rec, (dt_byte const*)key, !key ? 1 : strlen(key), item );
}



dt_node*  dt_rec_get_nth( dt_node* rec, unsigned ind
                        , dt_byte const** key, size_t* key_len
                        )
{
   rec_item* pos;
   assert( !rec || dt_node_is_valid(rec) );

   if(   ! rec
      || rec->kind != dt_rec_node
      || ind >= (rec->buf.strEnd - rec->buf.begin)/sizeof(rec_item)
      ) return 00;
   
   pos = (rec_item*)rec->buf.begin + ind;
   if( key     ) *key     = pos->key;
   if( key_len ) *key_len = pos->key_len;
   return pos->node;
}

---