Lemz_SwCtrlStmProj/App/tlst/tree_list.c

#define TREE_LIST_C
#include "my_assert.h"
#include "app/tlst/tree_list.h"

#if TREE_LIST_DEEP_ENABLE
// @tree_list_foreach
// Tree-List iteration function
// Walks the specified node seaching for derived nodes. Each node found is passed to the specified
// by user function @fcall with the specified user dependent context @ctx
// Function walks the current node while @fcall returns 'true', and returns current node immediately as
// far as @fcall returns 'false'. The function returns NULL if @fcall never returns 'false'.
// @ref_node - the tree node to walk in;
// @fcall - user defined function callback;
// @ctx - user defined function context;
// Returns: tree-list node in case @fcall have returned 'false', or NULL otherwise.
const sTreeList_t * tree_list_foreach( const sTreeList_t * ref_node, fTreeListForEach_t fcall, void * ctx )
{
    for( const sTreeList_t * iter = ref_node->c_list; NULL != iter; ++iter )
    {
         if( ! fcall( iter, ctx ) )
         {
             return iter;
         }
    }

    return NULL;
}
#endif

// @tree_list_search
// Search in the tree list @in for the node specified by @key using
// ... the compare function @fcmp.
// @in - the tree list to search in, shall not be NULL;
// @search_key - the node key to search for, shall not be NULL;
// @fcmp - nodes comparator, shall not be NULL; 
// @def_node - the default node to be returned if no node found by @search_key, can be NULL;
// Returns: the node pointer if found, @def_node otherwise.
// Note: The list @in shall be terminated by DECLARE_TREE_LIST_LAST() element.
const sTreeList_t * tree_list_search( const sTreeList_t * in,
                                      const void * search_key,
                                      fTreeListComparer_t fcmp,
                                      const sTreeList_t * def_node )
{
    my_assert( in );
    my_assert( search_key );
    my_assert( fcmp );

    for( const sTreeList_t * iter = in->list; NULL != iter; ++iter )
    {
         if( NULL == iter->key )
         {
             break;
         }
         else
         if( fcmp( iter->key, search_key ) )
         {
             return iter;
         }
    }

    return def_node;
}

#if TREE_LIST_DEEP_ENABLE
// @sTreeListSearchDeepCtx_t
// Internal context structure for @tree_list_search_deep
typedef struct
{
   const void * v_nextkey;                // next key to search
   const void * v_ret_node;               // found node
   #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
   const void * v_ret_pnode;              // parent of found node
   #endif
   const sTreeList_t * def_node;          // this node is considered as default
   const sTreeListSearchDeep_FSet_t * fs; // @fs parameter in 'tree_list_search_deep' function
   void * user_ctx;                       // user context
}
sTreeListSearchDeepCtx_t;


// @tl_search_deep_iterator
// Internal function.
// A @tree_list_foreach routine callback in @tree_list_search_deep_int implementation
// Modifies on return:
// [true]:
// - none
// [false]:
// - ctx->v_ret_node
static bool tl_search_deep_iterator( const sTreeList_t * node, void * _ctx )
{
    sTreeListSearchDeepCtx_t * ctx = (sTreeListSearchDeepCtx_t*)_ctx;

    my_assert( ctx->fs );
    my_assert( ctx->fs->fcmp );    
    my_assert( ctx->v_nextkey );

    (void)ctx->v_ret_node;         // keep value, do not touch
    #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
    (void)ctx->v_ret_pnode;        // keep value, do not touch
    #endif

    if( NULL == node->key )        // end-of-list [DECLARE_TREE_LIST_LAST] 
    {
        (void)ctx->v_ret_node;
        #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
        (void)ctx->v_ret_pnode;
        #endif
        return false;              // terminate walking
    }
    else
    if( ctx->fs->fcmp( node->key, ctx->v_nextkey ) )
    {
        #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
        // check if user agree the result
        if( ctx->fs->fagree( node, ctx->v_ret_pnode, ctx->user_ctx ) )
        {
        #endif
        ctx->v_ret_node = node;    // found
        #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
        (void)ctx->v_ret_pnode;    // keep value, do not touch
        #endif
        return false;              // terminate walking
        #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
        } // if not then continue searching
        #endif
    }

    // Check if no default node is assigned yet;
    // Check if the default node detector function is specified;
    // Check if the node is consideted as default;
    if( (NULL == ctx->def_node) && (NULL != ctx->fs->fisdef) && ctx->fs->fisdef( node, ctx->user_ctx ) )
    {
        ctx->def_node = node; // current node is the default node
    }

    (void)ctx->v_ret_node;
    #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
    (void)ctx->v_ret_pnode;
    #endif
    return true; // continue walking
}

// @tree_list_search_deep_int
// Internal function.
// Extended search for a key chain in the tree-list.
// @ref_node - base node, root, the node to start search from;
// @fs - functional set, see @sTreeListSearchDeep_FSet_t:
//  - fnext: user-defined abstract routine to retrieve next key in the chain;
//  - fcmp: user-defined abstract predicate to compare nodes;
//  - fisdef: user-defined predicate to determine if the node is the "default" node;
//  - freclim: user-defined abstract routine to limit recursive calls, see @fTreeListSearchDeepRecursiveLimiter_t;
// @v_nextkey_override - override key to search, shall be NULL to use @fs->fnext, or this value will be used;
// @user_ctx - user-dependent context, will be passed to routines in functional set @fs;
// Returns:
//  NON NULL: found node;
//  NULL: node not found;
static const sTreeList_t * tree_list_search_deep_int( const sTreeList_t * ref_node, 
                                                      const sTreeListSearchDeep_FSet_t * fs,
                                                      const void * v_nextkey_override,
                                                      void * user_ctx )
{
   const sTreeList_t * found = NULL;

   my_assert( ref_node );
   my_assert( fs );   
   my_assert( fs->fnext );
   my_assert( fs->fcmp );

   sTreeListSearchDeepCtx_t ctx = { 
    .v_nextkey = v_nextkey_override,
    .v_ret_node = NULL,
    .def_node = NULL,
    .fs = fs,
    .user_ctx = user_ctx,
   };

   do
   {
       if( NULL == v_nextkey_override )
       {
           // get next key to search in the tree list
           ctx.v_nextkey = fs->fnext( user_ctx );
       }
       else
       {
           // use predefined key to search
           (void)ctx.v_nextkey;
       }

       // check if there no next key
       if( NULL == ctx.v_nextkey ) break; // invalid key

       ctx.v_ret_node = NULL;
       #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
       ctx.v_ret_pnode = ref_node;
       #endif
       ctx.def_node = NULL;

       // search for the key in tree list
       if( NULL != tree_list_foreach( ref_node, tl_search_deep_iterator, &ctx ) )
       {
           // not found?
           if( NULL == ctx.v_ret_node )
           {
               // try the default node if possible
               if( NULL != ctx.def_node )
               {
                   // search recursevely (support optional/default nodes):
                   // - specify the default node found as root node;
                   // - pass the same function set (@fs);
                   // - override the key to search (do not use @fs->fnext);
                   // - limit recursive calls by user defined way;
                   #if TREE_LIST_RECURSIVE_LIMIT_ENABLE
                   bool possbile_call = true;
                   // check if recursive call is possible:
                   if( NULL != fs->freclim )
                   {
                       possbile_call = fs->freclim( true, user_ctx );  // enter recursive call
                   }
                   if( possbile_call )
                   {
                       found = tree_list_search_deep_int( ctx.def_node, fs, ctx.v_nextkey, user_ctx ); 
                   }
                   if( NULL != fs->freclim )
                   {
                       fs->freclim( false, user_ctx ); // leave recursive call
                   }
                   #else
                   found = tree_list_search_deep_int( ctx.def_node, fs, ctx.v_nextkey, user_ctx ); 
                   #endif 
               }
               else
               {
                   // assign NULL due to the element not found
                   found = NULL;
                   #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
                   (void)ctx.v_ret_pnode;
                   #endif
               }
           }
           else
           {
               // assign the element found
               found = ctx.v_ret_node;
               #if TREE_LIST_DEEP_PARENT_SEARCH_ENABLE
               (void)ctx.v_ret_pnode;
               #endif
           }

           if( NULL == found )
           {
               break; // not found
           }
           else
           {
               if( NULL != v_nextkey_override )
               {
                   v_nextkey_override = NULL;
               }
           }
       }
       else break; // end-of-list, element not found

       ref_node = found; // found, go next key in the chain
   }
   while( NULL != found );

   return found;
}

// @tree_list_search_deep_int
// Extended search for a key chain in the tree-list.
// @ref_node - base node, root, the node to start search from;
// @fs - functional set, see @sTreeListSearchDeep_FSet_t:
//  - fnext: user-defined abstract routine to retrieve next key in the chain;
//  - fcmp: user-defined abstract predicate to compare nodes;
//  - fisdef: user-defined predicate to determine if the node is the "default" node;
//  - freclim: user-defined abstract routine to limit recursive calls, see @fTreeListSearchDeepRecursiveLimiter_t;
// @user_ctx - user-dependent context, will be passed to routines in functional set @fs;
// Returns:
//  NON NULL: found node;
//  NULL: node not found;
const sTreeList_t * tree_list_search_deep( const sTreeList_t * ref_node, 
                                           const sTreeListSearchDeep_FSet_t * fs,
                                           void * user_ctx )
{
   return tree_list_search_deep_int( ref_node, fs, NULL, user_ctx );
}
#endif