git.sesse.net Git - vlc/blob - src/playlist/tree.c

   1 /*****************************************************************************
   2  * tree.c : Playlist tree walking functions
   3  *****************************************************************************
   4  * Copyright (C) 1999-2007 the VideoLAN team
   5  * $Id$
   6  *
   7  * Authors: Clément Stenac <zorglub@videolan.org>
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation; either version 2 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  22  *****************************************************************************/
  23 #include <vlc/vlc.h>
  24 #include <assert.h>
  25 #include "vlc_playlist.h"
  26 #include "playlist_internal.h"
  27
  28 /************************************************************************
  29  * Local prototypes
  30  ************************************************************************/
  31 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
  32                                playlist_item_t *p_root );
  33 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
  34                                playlist_item_t *p_root );
  35
  36 playlist_item_t *GetNextItem( playlist_t *p_playlist,
  37                               playlist_item_t *p_root,
  38                               playlist_item_t *p_item );
  39 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
  40                               playlist_item_t *p_item,
  41                               playlist_item_t *p_root );
  42
  43 /**
  44  * Create a playlist node
  45  *
  46  * \param p_playlist the playlist
  47  * \paam psz_name the name of the node
  48  * \param p_parent the parent node to attach to or NULL if no attach
  49  * \param p_flags miscellaneous flags
  50  * \param p_input the input_item to attach to or NULL if it has to be created
  51  * \return the new node
  52  */
  53 playlist_item_t * playlist_NodeCreate( playlist_t *p_playlist,
  54                                        const char *psz_name,
  55                                        playlist_item_t *p_parent, int i_flags,
  56                                        input_item_t *p_input )
  57 {
  58     input_item_t *p_new_input;
  59     playlist_item_t *p_item;
  60
  61     if( !psz_name ) psz_name = _("Undefined");
  62
  63     if( !p_input )
  64         p_new_input = input_ItemNewWithType( VLC_OBJECT(p_playlist), NULL,
  65                                         psz_name, 0, NULL, -1, ITEM_TYPE_NODE );
  66     p_item = playlist_ItemNewFromInput( VLC_OBJECT(p_playlist),
  67                                         p_input ? p_input : p_new_input );
  68
  69     if( p_item == NULL )  return NULL;
  70     p_item->i_children = 0;
  71
  72     ARRAY_APPEND(p_playlist->all_items, p_item);
  73
  74     if( p_parent != NULL )
  75         playlist_NodeAppend( p_playlist, p_item, p_parent );
  76     playlist_SendAddNotify( p_playlist, p_item->i_id,
  77                             p_parent ? p_parent->i_id : -1,
  78                             !( i_flags & PLAYLIST_NO_REBUILD ));
  79     return p_item;
  80 }
  81
  82 /**
  83  * Remove all the children of a node
  84  *
  85  * This function must be entered with the playlist lock
  86  *
  87  * \param p_playlist the playlist
  88  * \param p_root the node
  89  * \param b_delete_items do we have to delete the children items ?
  90  * \return VLC_SUCCESS or an error
  91  */
  92 int playlist_NodeEmpty( playlist_t *p_playlist, playlist_item_t *p_root,
  93                         vlc_bool_t b_delete_items )
  94 {
  95     int i;
  96     if( p_root->i_children == -1 )
  97     {
  98         return VLC_EGENERIC;
  99     }
 100
 101     /* Delete the children */
 102     for( i =  p_root->i_children-1 ; i >= 0 ;i-- )
 103     {
 104         if( p_root->pp_children[i]->i_children > -1 )
 105         {
 106             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
 107                                  b_delete_items , VLC_FALSE );
 108         }
 109         else if( b_delete_items )
 110         {
 111             /* Delete the item here */
 112             playlist_DeleteFromItemId( p_playlist,
 113                                        p_root->pp_children[i]->i_id );
 114         }
 115     }
 116     return VLC_SUCCESS;
 117 }
 118
 119 /**
 120  * Remove all the children of a node and removes the node
 121  *
 122  * \param p_playlist the playlist
 123  * \param p_root the node
 124  * \param b_delete_items do we have to delete the children items ?
 125  * \return VLC_SUCCESS or an error
 126  */
 127 int playlist_NodeDelete( playlist_t *p_playlist, playlist_item_t *p_root,
 128                          vlc_bool_t b_delete_items, vlc_bool_t b_force )
 129 {
 130     int i;
 131
 132     if( p_root->i_children == -1 )
 133     {
 134         return VLC_EGENERIC;
 135     }
 136
 137     /* Delete the children */
 138     for( i =  p_root->i_children - 1 ; i >= 0; i-- )
 139     {
 140         if( p_root->pp_children[i]->i_children > -1 )
 141         {
 142             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
 143                                  b_delete_items , b_force );
 144         }
 145         else if( b_delete_items )
 146         {
 147             playlist_DeleteFromItemId( p_playlist,
 148                                        p_root->pp_children[i]->i_id );
 149         }
 150     }
 151     /* Delete the node */
 152     if( p_root->i_flags & PLAYLIST_RO_FLAG && !b_force )
 153     {
 154     }
 155     else
 156     {
 157         int i;
 158         var_SetInteger( p_playlist, "item-deleted", p_root->i_id );
 159         ARRAY_BSEARCH( p_playlist->all_items, ->i_id, int,
 160                        p_root->i_id, i );
 161         if( i != -1 )
 162             ARRAY_REMOVE( p_playlist->all_items, i );
 163
 164         /* Remove the item from its parent */
 165         if( p_root->p_parent )
 166             playlist_NodeRemoveItem( p_playlist, p_root, p_root->p_parent );
 167
 168         playlist_ItemDelete( p_root );
 169     }
 170     return VLC_SUCCESS;
 171 }
 172
 173
 174 /**
 175  * Adds an item to the children of a node
 176  *
 177  * \param p_playlist the playlist
 178  * \param p_item the item to append
 179  * \param p_parent the parent node
 180  * \return VLC_SUCCESS or an error
 181  */
 182 int playlist_NodeAppend( playlist_t *p_playlist,
 183                          playlist_item_t *p_item,
 184                          playlist_item_t *p_parent )
 185 {
 186     return playlist_NodeInsert( p_playlist, p_item, p_parent, -1 );
 187 }
 188
 189 int playlist_NodeInsert( playlist_t *p_playlist,
 190                          playlist_item_t *p_item,
 191                          playlist_item_t *p_parent,
 192                          int i_position )
 193 {
 194    (void)p_playlist;
 195    assert( p_parent && p_parent->i_children != -1 );
 196    if( i_position == -1 ) i_position = p_parent->i_children ;
 197
 198    INSERT_ELEM( p_parent->pp_children,
 199                 p_parent->i_children,
 200                 i_position,
 201                 p_item );
 202    p_item->p_parent = p_parent;
 203    return VLC_SUCCESS;
 204 }
 205
 206 /**
 207  * Deletes an item from the children of a node
 208  *
 209  * \param p_playlist the playlist
 210  * \param p_item the item to remove
 211  * \param p_parent the parent node
 212  * \return VLC_SUCCESS or an error
 213  */
 214 int playlist_NodeRemoveItem( playlist_t *p_playlist,
 215                         playlist_item_t *p_item,
 216                         playlist_item_t *p_parent )
 217 {
 218    (void)p_playlist;
 219
 220    for(int i= 0; i< p_parent->i_children ; i++ )
 221    {
 222        if( p_parent->pp_children[i] == p_item )
 223        {
 224            REMOVE_ELEM( p_parent->pp_children, p_parent->i_children, i );
 225        }
 226    }
 227
 228    return VLC_SUCCESS;
 229 }
 230
 231
 232 /**
 233  * Count the children of a node
 234  *
 235  * \param p_playlist the playlist
 236  * \param p_node the node
 237  * \return the number of children
 238  */
 239 int playlist_NodeChildrenCount( playlist_t *p_playlist, playlist_item_t*p_node)
 240 {
 241     int i;
 242     int i_nb = 0;
 243
 244     if( p_node->i_children == -1 )
 245         return 0;
 246
 247     i_nb = p_node->i_children;
 248     for( i=0 ; i< p_node->i_children;i++ )
 249     {
 250         if( p_node->pp_children[i]->i_children == -1 )
 251             break;
 252         else
 253             i_nb += playlist_NodeChildrenCount( p_playlist,
 254                                                 p_node->pp_children[i] );
 255     }
 256     return i_nb;
 257 }
 258
 259 /**
 260  * Search a child of a node by its name
 261  *
 262  * \param p_node the node
 263  * \param psz_search the name of the child to search
 264  * \return the child item or NULL if not found or error
 265  */
 266 playlist_item_t *playlist_ChildSearchName( playlist_item_t *p_node,
 267                                            const char *psz_search )
 268 {
 269     int i;
 270
 271     if( p_node->i_children < 0 )
 272     {
 273          return NULL;
 274     }
 275     for( i = 0 ; i< p_node->i_children; i++ )
 276     {
 277         if( !strcmp( p_node->pp_children[i]->p_input->psz_name, psz_search ) )
 278         {
 279             return p_node->pp_children[i];
 280         }
 281     }
 282     return NULL;
 283 }
 284
 285 /**
 286  * Create a pair of nodes in the category and onelevel trees.
 287  * They share the same input item.
 288  * \param p_playlist the playlist
 289  * \param psz_name the name of the nodes
 290  * \param pp_node_cat pointer to return the node in category tree
 291  * \param pp_node_one pointer to return the node in onelevel tree
 292  * \param b_for_sd For Services Discovery ? (make node read-only and unskipping)
 293  */
 294 void playlist_NodesPairCreate( playlist_t *p_playlist, const char *psz_name,
 295                                playlist_item_t **pp_node_cat,
 296                                playlist_item_t **pp_node_one,
 297                                vlc_bool_t b_for_sd )
 298 {
 299     *pp_node_cat = playlist_NodeCreate( p_playlist, psz_name,
 300                                         p_playlist->p_root_category, 0, NULL );
 301     *pp_node_one = playlist_NodeCreate( p_playlist, psz_name,
 302                                         p_playlist->p_root_onelevel, 0,
 303                                         (*pp_node_cat)->p_input );
 304     if( b_for_sd )
 305     {
 306         (*pp_node_cat)->i_flags |= PLAYLIST_RO_FLAG;
 307         (*pp_node_cat)->i_flags |= PLAYLIST_SKIP_FLAG;
 308         (*pp_node_one)->i_flags |= PLAYLIST_RO_FLAG;
 309         (*pp_node_one)->i_flags |= PLAYLIST_SKIP_FLAG;
 310     }
 311 }
 312
 313 /**
 314  * Get the node in the preferred tree from a node in one of category
 315  * or onelevel tree.
 316  * For example, for the SAP node, it will return the node in the category
 317  * tree if --playlist-tree is not set to never, because the SAP node prefers
 318  * category
 319  */
 320 playlist_item_t * playlist_GetPreferredNode( playlist_t *p_playlist,
 321                                              playlist_item_t *p_node )
 322 {
 323     int i;
 324     if( p_node->p_parent == p_playlist->p_root_category )
 325     {
 326         if( p_playlist->b_always_tree ||
 327             p_node->p_input->b_prefers_tree ) return p_node;
 328         for( i = 0 ; i< p_playlist->p_root_onelevel->i_children; i++ )
 329         {
 330             if( p_playlist->p_root_onelevel->pp_children[i]->p_input->i_id ==
 331                     p_node->p_input->i_id )
 332                 return p_playlist->p_root_onelevel->pp_children[i];
 333         }
 334     }
 335     else if( p_node->p_parent == p_playlist->p_root_onelevel )
 336     {
 337         if( p_playlist->b_never_tree || !p_node->p_input->b_prefers_tree )
 338             return p_node;
 339         for( i = 0 ; i< p_playlist->p_root_category->i_children; i++ )
 340         {
 341             if( p_playlist->p_root_category->pp_children[i]->p_input->i_id ==
 342                     p_node->p_input->i_id )
 343                 return p_playlist->p_root_category->pp_children[i];
 344         }
 345     }
 346     return NULL;
 347 }
 348
 349 /**********************************************************************
 350  * Tree walking functions
 351  **********************************************************************/
 352
 353 playlist_item_t *playlist_GetLastLeaf(playlist_t *p_playlist,
 354                                       playlist_item_t *p_root )
 355 {
 356     int i;
 357     playlist_item_t *p_item;
 358     for ( i = p_root->i_children - 1; i >= 0; i-- )
 359     {
 360         if( p_root->pp_children[i]->i_children == -1 )
 361             return p_root->pp_children[i];
 362         else if( p_root->pp_children[i]->i_children > 0)
 363         {
 364              p_item = playlist_GetLastLeaf( p_playlist,
 365                                             p_root->pp_children[i] );
 366             if ( p_item != NULL )
 367                 return p_item;
 368         }
 369         else if( i == 0 )
 370             return NULL;
 371     }
 372     return NULL;
 373 }
 374
 375 int playlist_GetAllEnabledChildren( playlist_t *p_playlist,
 376                                     playlist_item_t *p_node,
 377                                     playlist_item_t ***ppp_items )
 378 {
 379     int i_count = 0;
 380     playlist_item_t *p_next = NULL;
 381     while( 1 )
 382     {
 383         p_next = playlist_GetNextLeaf( p_playlist, p_node,
 384                                        p_next, VLC_TRUE, VLC_FALSE );
 385         if( p_next )
 386             INSERT_ELEM( *ppp_items, i_count, i_count, p_next );
 387         else
 388             break;
 389     }
 390     return i_count;
 391 }
 392
 393 /**
 394  * Finds the next item to play
 395  *
 396  * \param p_playlist the playlist
 397  * \param p_root the root node
 398  * \param p_item the previous item  (NULL if none )
 399  * \return the next item to play, or NULL if none found
 400  */
 401 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
 402                                        playlist_item_t *p_root,
 403                                        playlist_item_t *p_item,
 404                                        vlc_bool_t b_ena, vlc_bool_t b_unplayed )
 405 {
 406     playlist_item_t *p_next;
 407
 408     assert( p_root && p_root->i_children != -1 );
 409
 410     PL_DEBUG2( "finding next of %s within %s",
 411                PLI_NAME( p_item ), PLI_NAME( p_root ) );
 412
 413     /* Now, walk the tree until we find a suitable next item */
 414     p_next = p_item;
 415     while( 1 )
 416     {
 417         vlc_bool_t b_ena_ok = VLC_TRUE, b_unplayed_ok = VLC_TRUE;
 418         p_next = GetNextItem( p_playlist, p_root, p_next );
 419         if( !p_next || p_next == p_root )
 420             break;
 421         if( p_next->i_children == -1 )
 422         {
 423             if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
 424                 b_ena_ok = VLC_FALSE;
 425             if( b_unplayed && p_next->p_input->i_nb_played != 0 )
 426                 b_unplayed_ok = VLC_FALSE;
 427             if( b_ena_ok && b_unplayed_ok ) break;
 428         }
 429     }
 430     if( p_next == NULL ) PL_DEBUG2( "at end of node" );
 431     return p_next;
 432 }
 433
 434 /**
 435  * Finds the previous item to play
 436  *
 437  * \param p_playlist the playlist
 438  * \param p_root the root node
 439  * \param p_item the previous item  (NULL if none )
 440  * \return the next item to play, or NULL if none found
 441  */
 442 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
 443                                        playlist_item_t *p_root,
 444                                        playlist_item_t *p_item,
 445                                        vlc_bool_t b_ena, vlc_bool_t b_unplayed )
 446 {
 447     playlist_item_t *p_prev;
 448
 449     PL_DEBUG2( "finding previous os %s within %s", PLI_NAME( p_item ),
 450                                                    PLI_NAME( p_root ) );
 451     assert( p_root && p_root->i_children != -1 );
 452
 453     /* Now, walk the tree until we find a suitable previous item */
 454     p_prev = p_item;
 455     while( 1 )
 456     {
 457         vlc_bool_t b_ena_ok = VLC_TRUE, b_unplayed_ok = VLC_TRUE;
 458         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
 459         if( !p_prev || p_prev == p_root )
 460             break;
 461         if( p_prev->i_children == -1 )
 462         {
 463             if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
 464                 b_ena_ok = VLC_FALSE;
 465             if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
 466                 b_unplayed_ok = VLC_FALSE;
 467             if( b_ena_ok && b_unplayed_ok ) break;
 468         }
 469     }
 470     if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
 471     return p_prev;
 472 }
 473
 474 /************************************************************************
 475  * Following functions are local
 476  ***********************************************************************/
 477
 478 /**
 479  * Get the next item in the tree
 480  * If p_item is NULL, return the first child of root
 481  **/
 482 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 483                               playlist_item_t *p_root,
 484                               playlist_item_t *p_item )
 485 {
 486     playlist_item_t *p_parent;
 487     int i;
 488
 489     /* Node with children, get the first one */
 490     if( p_item && p_item->i_children > 0 )
 491         return p_item->pp_children[0];
 492
 493     if( p_item != NULL )
 494         p_parent = p_item->p_parent;
 495     else
 496         p_parent = p_root;
 497     for( i= 0 ; i < p_parent->i_children ; i++ )
 498     {
 499         if( p_item == NULL || p_parent->pp_children[i] == p_item )
 500         {
 501             if( p_item == NULL )
 502                 i = -1;
 503
 504             if( i+1 >= p_parent->i_children )
 505             {
 506                 /* Was already the last sibling. Look for uncles */
 507                 PL_DEBUG2( "Current item is the last of the node,"
 508                            "looking for uncle from %s",
 509                             p_parent->p_input->psz_name );
 510
 511                 if( p_parent == p_root )
 512                 {
 513                     PL_DEBUG2( "already at root" );
 514                     return NULL;
 515                 }
 516                 return GetNextUncle( p_playlist, p_item, p_root );
 517             }
 518             else
 519             {
 520                 return  p_parent->pp_children[i+1];
 521             }
 522         }
 523     }
 524     return NULL;
 525 }
 526
 527 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 528                                playlist_item_t *p_root )
 529 {
 530     playlist_item_t *p_parent = p_item->p_parent;
 531     playlist_item_t *p_grandparent;
 532     vlc_bool_t b_found = VLC_FALSE;
 533
 534     (void)p_playlist;
 535
 536     if( p_parent != NULL )
 537     {
 538         p_grandparent = p_parent->p_parent;
 539         while( p_grandparent )
 540         {
 541             int i;
 542             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 543             {
 544                 if( p_parent == p_grandparent->pp_children[i] )
 545                 {
 546                     PL_DEBUG2( "parent %s found as child %i of grandparent %s",
 547                                p_parent->p_input->psz_name, i,
 548                                p_grandparent->p_input->psz_name );
 549                     b_found = VLC_TRUE;
 550                     break;
 551                 }
 552             }
 553             if( b_found && i + 1 < p_grandparent->i_children )
 554             {
 555                     return p_grandparent->pp_children[i+1];
 556             }
 557             /* Not found at root */
 558             if( p_grandparent == p_root )
 559             {
 560                 return NULL;
 561             }
 562             else
 563             {
 564                 p_parent = p_grandparent;
 565                 p_grandparent = p_parent->p_parent;
 566             }
 567         }
 568     }
 569     /* We reached root */
 570     return NULL;
 571 }
 572
 573 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 574                                playlist_item_t *p_root )
 575 {
 576     playlist_item_t *p_parent = p_item->p_parent;
 577     playlist_item_t *p_grandparent;
 578     vlc_bool_t b_found = VLC_FALSE;
 579
 580     (void)p_playlist;
 581
 582     if( p_parent != NULL )
 583     {
 584         p_grandparent = p_parent->p_parent;
 585         while( 1 )
 586         {
 587             int i;
 588             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
 589             {
 590                 if( p_parent == p_grandparent->pp_children[i] )
 591                 {
 592                     b_found = VLC_TRUE;
 593                     break;
 594                 }
 595             }
 596             if( b_found && i - 1 > 0 )
 597             {
 598                 return p_grandparent->pp_children[i-1];
 599             }
 600             /* Not found at root */
 601             if( p_grandparent == p_root )
 602             {
 603                 return NULL;
 604             }
 605             else
 606             {
 607                 p_parent = p_grandparent;
 608                 p_grandparent = p_parent->p_parent;
 609             }
 610         }
 611     }
 612     /* We reached root */
 613     return NULL;
 614 }
 615
 616
 617 /* Recursively search the tree for previous item */
 618 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
 619                               playlist_item_t *p_root,
 620                               playlist_item_t *p_item )
 621 {
 622     playlist_item_t *p_parent;
 623     int i;
 624
 625     /* Node with children, get the last one */
 626     if( p_item && p_item->i_children > 0 )
 627         return p_item->pp_children[p_item->i_children - 1];
 628
 629     /* Last child of its parent ? */
 630     if( p_item != NULL )
 631         p_parent = p_item->p_parent;
 632     else
 633     {
 634         msg_Err( p_playlist, "Get the last one" );
 635         abort();
 636     };
 637
 638     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
 639     {
 640         if( p_parent->pp_children[i] == p_item )
 641         {
 642             if( i-1 < 0 )
 643             {
 644                /* Was already the first sibling. Look for uncles */
 645                 PL_DEBUG2( "current item is the first of its node,"
 646                            "looking for uncle from %s",
 647                            p_parent->p_input->psz_name );
 648                 if( p_parent == p_root )
 649                 {
 650                     PL_DEBUG2( "already at root" );
 651                     return NULL;
 652                 }
 653                 return GetPrevUncle( p_playlist, p_item, p_root );
 654             }
 655             else
 656             {
 657                 return p_parent->pp_children[i-1];
 658             }
 659         }
 660     }
 661     return NULL;
 662 }
 663
 664 /* Dump the contents of a node */
 665 void playlist_NodeDump( playlist_t *p_playlist, playlist_item_t *p_item,
 666                         int i_level )
 667 {
 668     char str[512];
 669     int i;
 670
 671     if( i_level == 1 )
 672     {
 673         msg_Dbg( p_playlist, "%s (%i)",
 674                         p_item->p_input->psz_name, p_item->i_children );
 675     }
 676
 677     if( p_item->i_children == -1 )
 678     {
 679         return;
 680     }
 681
 682     for( i = 0; i< p_item->i_children; i++ )
 683     {
 684         memset( str, 32, 512 );
 685         sprintf( str + 2 * i_level , "%s (%i)",
 686                                 p_item->pp_children[i]->p_input->psz_name,
 687                                 p_item->pp_children[i]->i_children );
 688         msg_Dbg( p_playlist, "%s",str );
 689         if( p_item->pp_children[i]->i_children >= 0 )
 690         {
 691             playlist_NodeDump( p_playlist, p_item->pp_children[i],
 692                               i_level + 1 );
 693         }
 694     }
 695     return;
 696 }