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