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

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