git.maemo.org Git - mardrone/blob - mardrone/ARDrone_SDK_Version_1_8_20110726/ARDroneLib/VP_SDK/ATcodec/ATcodec_Tree.c

   1 /**
   2  * @file ATcodec_tree.c
   3  * @author aurelien.morelle@parrot.com
   4  * @date 2007/08/20
   5  * modified on 2010/07/19 by stephane.piskorski.ext@parrot.fr (bug fix+comments)
   6  */
   7
   8 #include <VP_Os/vp_os_types.h>
   9 #include <VP_Os/vp_os_assert.h>
  10 #include <VP_Os/vp_os_print.h>
  11 #include <VP_Os/vp_os_malloc.h>
  12 #include <ATcodec/ATcodec_Tree.h>
  13 #include <ATcodec/ATcodec_api.h>
  14 #include <ATcodec/ATcodec_Buffer.h>
  15 #include <ATcodec/ATcodec.h>
  16
  17
  18 /* \todo Remove nodes fields initializations that are not necessary in each function */
  19
  20
  21
  22
  23 static void
  24 ATcodec_Tree_Node_init(ATcodec_Tree_Node_t *node)
  25 {
  26   VP_OS_ASSERT(node);
  27
  28   node->data = -1;
  29   node->depth = 0;
  30   node->nb_sons = 0;
  31   vp_os_memset(node->sons,0,sizeof(node->sons));
  32   node->strkey = 0;
  33   node->type = ATCODEC_TREE_NODE_TYPE_EMPTY;
  34
  35 }
  36
  37
  38
  39 /********************************************************************\r
  40  * @brief Initialises the AT command search tree.\r
  41  * @param[in] tree The tree to initialise.\r
  42 */
  43 void
  44 ATcodec_Tree_init(ATcodec_Tree_t *tree, size_t leaf_size, int nb_start)
  45 {
  46   ATcodec_Tree_Node_t s_node;
  47
  48   VP_OS_ASSERT(tree);
  49
  50   ATcodec_Buffer_init(&tree->leaves, leaf_size, nb_start);
  51   ATcodec_Buffer_init(&tree->strs, sizeof(char), nb_start);
  52   ATcodec_Buffer_init(&tree->sons, sizeof(ATcodec_Tree_Node_t), nb_start);
  53
  54   ATcodec_Tree_Node_init(&s_node);
  55   tree->root = tree->sons.nbElements;
  56   ATcodec_Buffer_pushElement(&tree->sons, &s_node);
  57 }
  58
  59
  60
  61
  62 /********************************************************************\r
  63  * @param[in] tree Tree in which the node is inserted.\r
  64  * @brief Creates a new node in the tree.\r
  65 */
  66 static int
  67 ATcodec_Tree_Node_insert(ATcodec_Tree_t *tree, ATCODEC_TREE_NODE_TYPE type, int depth, int str_index, int data, ATcodec_Tree_Node_t *father, int son_index)
  68 {
  69         /* The new node's value */
  70         ATcodec_Tree_Node_t s_node;
  71         /* Index of the new node inside the tree's nodes list */
  72         int node_index;
  73
  74   /* Clears the new node */
  75         vp_os_memset(&s_node,0,sizeof(s_node));
  76
  77   node_index = tree->sons.nbElements;
  78   if(father)
  79     father->sons[son_index] = node_index;
  80
  81   s_node.type = type;
  82   s_node.depth = depth;
  83   s_node.strkey = str_index;
  84   s_node.data = data;
  85
  86   ATcodec_Buffer_pushElement(&tree->sons, &s_node);
  87
  88   return node_index;
  89 }
  90
  91
  92
  93 /********************************************************************\r
  94  * @param[in] tree Tree in which the command is inserted.\r
  95  * @brief Inserts an AT command string in the tree.\r
  96 */
  97 static int
  98 ATcodec_Tree_Node_search(ATcodec_Tree_t *tree, char *str)
  99 {
 100   ATcodec_Tree_Node_t *node;
 101   int searching = 1;
 102   int depth = 0;
 103   int str_index;
 104   int node_index = -1;
 105   int temp_data;
 106   int father_index;
 107
 108   VP_OS_ASSERT(str);
 109   VP_OS_ASSERT(*str);
 110   VP_OS_ASSERT(tree);
 111
 112   str_index = tree->strs.nbElements;
 113
 114   /* Adds the new string to the list of commands */
 115   ATcodec_Buffer_pushElements(&tree->strs, str, strlen(str)+1);
 116
 117   /* !! WARNING !! this pointer might be invalid after inserting an element in the tree */
 118   node = ATcodec_Tree_Node_get(tree, tree->root);
 119
 120   while(searching)
 121   {
 122       switch(node->type)
 123         {
 124
 125         /* Tree is empty -> we insert the string as the only element */
 126         case ATCODEC_TREE_NODE_TYPE_EMPTY:
 127           {
 128             /* Initialise the root element */
 129                         node->type = ATCODEC_TREE_NODE_TYPE_LEAF;
 130                         node->depth = depth;
 131                         node->strkey = str_index; /* str_index = place of the newly inserted string */
 132                         node_index = 0;
 133                 /* Stop the search */
 134                         searching = 0;
 135           }
 136           break;
 137
 138     /*
 139         Parse an intermediate node, which means that previously inserted
 140         command strings began with the same characters.
 141         */
 142         case ATCODEC_TREE_NODE_TYPE_NODE:
 143           {
 144                   /* Gets the node representing the next character of the command string */
 145                          node_index = node->sons[(int)*str];
 146
 147                  /* If there is no such node, the remaining part of the string is stored in the
 148                  tree as a terminal node (a leaf of the tree).*/
 149                          if(node_index == -1)
 150                           {
 151                                 node_index = ATcodec_Tree_Node_insert(tree,
 152                                                                                                                 ATCODEC_TREE_NODE_TYPE_LEAF,
 153                                                                                                                 depth+1,
 154                                                                                                                 str_index, /* str_index = place of the newly inserted string */
 155                                                                                                                 /*data*/-1,
 156                                                                                                                 /*father*/node,
 157                                                                                                                 /*index*/(int)*(str));
 158                                 searching = 0;
 159                           }
 160                  /* Otherwise, we get the node representing this character and continue scanning the tree.*/
 161                          node = ATcodec_Tree_Node_get(tree, node_index);
 162                      depth++;
 163                          str++;
 164           }
 165           break;
 166
 167         /*
 168         Scanning arrives on a leaf -> this leaf must be split to store the two
 169         possible command-string endings.
 170         */
 171         case ATCODEC_TREE_NODE_TYPE_LEAF:
 172           {
 173                 /*
 174                 Retrieves the already-stored string.
 175                 We have to insert as many additional intermediate nodes as there are common
 176                 characters in the two string remainders.
 177                 Two terminal leaves will then be added to store the parts of those strings which differ.
 178                 */
 179             char *leaf_str = (char *)ATcodec_Buffer_getElement(&tree->strs, node->strkey);
 180             int i;
 181
 182             /* As far as strings endings are the same, insert the intermediate nodes  ...*/
 183                 while(*str && *str == leaf_str[depth])
 184               {
 185                         /* Change the current leaf node to an intermediate node and initialises the list of sons. */
 186                           node->type = ATCODEC_TREE_NODE_TYPE_NODE;
 187                           for(i = 0 ; i < AT_CODEC_TREE_MAX_SONS ; i++) {  node->sons[i] = -1; }
 188
 189                                 /* Create a new leaf */
 190                                 node_index = ATcodec_Tree_Node_insert(tree,
 191                                                                                                          /*node type*/ATCODEC_TREE_NODE_TYPE_LEAF,
 192                                                                                                          /*node depth*/depth+1,
 193                                                                                                          /*str_index*/node->strkey, /* Points to the old command-string by default */
 194                                                                                                          /*data*/node->data,
 195                                                                                                          /*father*/node,
 196                                                                                                          /*son_index*/(int)leaf_str[depth]);
 197                                 depth++;
 198
 199                                 node = ATcodec_Tree_Node_get(tree, node_index);
 200                                 str++;
 201               }
 202
 203                 /* If the new string was in fact a subpart of the old one ...*/
 204                 if(*str == leaf_str[depth])
 205               {
 206                    /* Change the leaf to a multileaves */
 207                         node->type = ATCODEC_TREE_NODE_TYPE_MULTILEAVES;
 208                         node->nb_sons = 2;
 209                         temp_data = node->data;
 210                         node->data = -1;
 211                         father_index = node_index;
 212
 213                         /* Insert a leaf for the old longer string */
 214                         node_index = ATcodec_Tree_Node_insert(tree,
 215                                                                                                         ATCODEC_TREE_NODE_TYPE_LEAF,
 216                                                                                                         ++depth,
 217                                                                                                         node->strkey,
 218                                                                                                         temp_data,
 219                                                                                                         /*father*/node,
 220                                                                                                         /*son_index*/0);
 221
 222                         /* Pointer 'node' is invalid from here because it points
 223                         to a buffer which might have been resized by 'ATcodec_Tree_Node_insert'.
 224                         We fetch a valid address computed from the index.*/
 225                         node = ATcodec_Tree_Node_get(tree,father_index);
 226
 227                         /* Insert a leaf for the new, shorter string */
 228                         node_index = ATcodec_Tree_Node_insert(tree,
 229                                                                                                         ATCODEC_TREE_NODE_TYPE_LEAF,
 230                                                                                                         depth,
 231                                                                                                         str_index,
 232                                                                                                         /*data*/-1,
 233                                                                                                         /*father*/node,
 234                                                                                                         /*son_index*/1);
 235               }
 236
 237                 /* If the two strings have different endings ...*/
 238                 else
 239               {
 240                         /* The old leaf becomes an intermediate node with two daughter leaves */
 241                         node->type = ATCODEC_TREE_NODE_TYPE_NODE;
 242                         for(i = 0 ; i < AT_CODEC_TREE_MAX_SONS ; i++) { node->sons[i] = -1; }
 243                         father_index = node_index;
 244
 245                         /* Recreate a leaf for the old command string */
 246                         node_index = ATcodec_Tree_Node_insert(tree,
 247                                                                                                         ATCODEC_TREE_NODE_TYPE_LEAF,
 248                                                                                                         node->depth+1,
 249                                                                                                         node->strkey, /* strkey was propagated from the original leaf */
 250                                                                                                         node->data, /* keeps the data of the old command string */
 251                                                                                                         /*father*/node,
 252                                                                                                         /*son_index*/(int)leaf_str[depth]
 253                                                                                         );
 254
 255                         /* Pointer 'node' is invalid from here because it points
 256                         to a buffer which might have been resized by 'ATcodec_Tree_Node_insert'.
 257                         We fetch a valid address computed from the index.*/
 258                         node = ATcodec_Tree_Node_get(tree,father_index);
 259
 260
 261                         //node->sons[(int)leaf_str[depth]] = node_index;
 262
 263                         /* Create a new leaf for the new command string */
 264                         node_index = ATcodec_Tree_Node_insert(tree,
 265                                                                                                         ATCODEC_TREE_NODE_TYPE_LEAF,
 266                                                                                                         node->depth+1,
 267                                                                                                         str_index, /* str_index = place of the newly inserted string */
 268                                                                                                         -1, /* data is initialised later in the ATcodec_Tree_insert function */
 269                                                                                                         /*father*/node,
 270                                                                                                         /*son_index*/(int)*str);
 271               }
 272
 273                 searching = 0;
 274           }
 275           break;
 276
 277   /*
 278   If there are already at leat two several end-of-command-strings starting with the current character,
 279   these are represented by a 'multileaves' node and we just add a new son to this node.
 280   */
 281         case ATCODEC_TREE_NODE_TYPE_MULTILEAVES:
 282           {
 283             node_index = ATcodec_Tree_Node_insert(tree,
 284                                                                                                 ATCODEC_TREE_NODE_TYPE_LEAF,
 285                                                                                                 ++depth,
 286                                                                                                 str_index, /* str_index = place of the newly inserted string */
 287                                                                                                 /*data*/-1, /* data is initialised later in the ATcodec_Tree_insert function */
 288                                                                                                 /*father*/node,
 289                                                                                                 /*son_index*/node->nb_sons++
 290                                                                                 );
 291             searching = 0;
 292           }
 293           break;
 294         }
 295     }
 296
 297   return node_index;
 298 }
 299
 300
 301 /********************************************************************\r
 302  * @param[in] tree Tree in which the command is inserted.\r
 303  * @brief Inserts an AT command string in the AT tree with its associated parameters.\r
 304 */
 305 int
 306 ATcodec_Tree_insert(ATcodec_Tree_t *tree, char *str, void *data)
 307 {
 308   ATcodec_Tree_Node_t *node;
 309   int node_i;
 310
 311   VP_OS_ASSERT(tree);
 312
 313   /*
 314   Insert the 'command part' (until the '=' symbol, without parameter)
 315   in the search tree.
 316   */
 317           node_i = ATcodec_Tree_Node_search(tree, str);
 318           node = ATcodec_Tree_Node_get(tree, node_i);
 319           node->data = tree->leaves.nbElements;
 320   /* Stores the string containing the parameters */
 321           ATcodec_Buffer_pushElement(&tree->leaves, data);
 322
 323   return node_i;
 324 }
 325
 326
 327 \r
 328 /********************************************************************\r
 329  * @param[in] tree Tree from which the node is retrieved.\r
 330  * @param[in] node Index of the node whose pointer is to be returned.\r
 331  * @brief Gets a pointer the node-th node of the tree.\r
 332  * @return Pointer to the asked node.\r
 333  * Be extremely careful not to use this pointer anymore after a tree->sons buffer resize.\r
 334 */
 335 ATcodec_Tree_Node_t *
 336 ATcodec_Tree_Node_get(ATcodec_Tree_t *tree, int node)
 337 {
 338   ATcodec_Tree_Node_t * res = (ATcodec_Tree_Node_t *)ATcodec_Buffer_getElement(&tree->sons, node);
 339   return res;
 340 }
 341
 342
 343 #define AT_CODEC_PRINT_NODE_CHAR_CASE(CARAC_SRC,STR_DST) \
 344   case CARAC_SRC:                                        \
 345     PRINT(STR_DST);                                      \
 346     break
 347
 348 #define AT_CODEC_PRINT_NODE_CHAR(CARAC)                  \
 349   switch(CARAC)                                          \
 350   {                                                      \
 351     AT_CODEC_PRINT_NODE_CHAR_CASE('\r',"<CR>");          \
 352     AT_CODEC_PRINT_NODE_CHAR_CASE('\n',"<LF>");          \
 353     AT_CODEC_PRINT_NODE_CHAR_CASE('\0',"<\\0>");         \
 354     AT_CODEC_PRINT_NODE_CHAR_CASE(' ',"< >");            \
 355     default:                                             \
 356       PRINT("%c", CARAC);                                \
 357       break;                                             \
 358   }
 359
 360 void
 361 ATcodec_Tree_Node_print(ATcodec_Tree_t *tree, ATcodec_Tree_Node_t *node)
 362 {
 363 #ifdef ATCODEC_DEBUG
 364   static int tab = 0;
 365   int i, j;
 366   char *sta;
 367
 368   if(node->type == ATCODEC_TREE_NODE_TYPE_LEAF)
 369     {
 370          /* Get the end-of-command-string stored on the leaf */
 371       sta = ATcodec_Buffer_getElement(&tree->strs, node->strkey);
 372       for(j = 0 ; j < tab ; j++)
 373         ATCODEC_PRINT(" . ");
 374       do
 375         {
 376           /* Print the end-of-command-string */
 377           AT_CODEC_PRINT_NODE_CHAR(*sta);
 378         }
 379       while(*sta++);
 380       ATCODEC_PRINT("\"\n");
 381     }
 382   else if(node->type == ATCODEC_TREE_NODE_TYPE_NODE)
 383     {
 384       /* For each possible character of the ascii map, check if a command-string is stored. */
 385                 for(i = 0 ; i < AT_CODEC_TREE_MAX_SONS ; i++)
 386            {
 387                 if(node->sons[i] != -1)
 388             {
 389               for(j = 0 ; j < tab ; j++)
 390                 ATCODEC_PRINT(" . ");
 391               AT_CODEC_PRINT_NODE_CHAR((char)i);
 392               ATCODEC_PRINT("\n");
 393               tab++;
 394               ATcodec_Tree_Node_print(tree, ATcodec_Tree_Node_get(tree, node->sons[i]));
 395               tab--;
 396             }
 397         }
 398     }
 399   else if(node->type == ATCODEC_TREE_NODE_TYPE_MULTILEAVES)
 400     {
 401       for(i = 0 ; i < node->nb_sons ; i++)
 402         {
 403           tab++;
 404           ATcodec_Tree_Node_print(tree, ATcodec_Tree_Node_get(tree, node->sons[i]));
 405           tab--;
 406         }
 407     }
 408 #endif // > ATCODEC_DEBUG
 409 }
 410
 411
 412 void
 413 ATcodec_Tree_print(ATcodec_Tree_t *tree)
 414 {
 415 #ifdef ATCODEC_DEBUG
 416   ATcodec_Tree_Node_print(tree, ATcodec_Tree_Node_get(tree, tree->root));
 417 #endif // > ATCODEC_DEBUG
 418 }
 419