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 /**
 406  * Finds the next item to play
 407  *
 408  * \param p_playlist the playlist
 409  * \param p_root the root node
 410  * \param p_item the previous item  (NULL if none )
 411  * \return the next item to play, or NULL if none found
 412  */
 413 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
 414                                        playlist_item_t *p_root,
 415                                        playlist_item_t *p_item,
 416                                        bool b_ena, bool b_unplayed )
 417 {
 418     PL_ASSERT_LOCKED;
 419     playlist_item_t *p_next;
 420
 421     assert( p_root && p_root->i_children != -1 );
 422
 423     PL_DEBUG2( "finding next of %s within %s",
 424                PLI_NAME( p_item ), PLI_NAME( p_root ) );
 425
 426     /* Now, walk the tree until we find a suitable next item */
 427     p_next = p_item;
 428     while( 1 )
 429     {
 430         bool b_ena_ok = true, b_unplayed_ok = true;
 431         p_next = GetNextItem( p_playlist, p_root, p_next );
 432         if( !p_next || p_next == p_root )
 433             break;
 434         if( p_next->i_children == -1 )
 435         {
 436             if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
 437                 b_ena_ok = false;
 438             if( b_unplayed && p_next->p_input->i_nb_played != 0 )
 439                 b_unplayed_ok = false;
 440             if( b_ena_ok && b_unplayed_ok ) break;
 441         }
 442     }
 443     if( p_next == NULL ) PL_DEBUG2( "at end of node" );
 444     return p_next;
 445 }
 446
 447 /**
 448  * Finds the previous item to play
 449  *
 450  * \param p_playlist the playlist
 451  * \param p_root the root node
 452  * \param p_item the previous item  (NULL if none )
 453  * \return the next item to play, or NULL if none found
 454  */
 455 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
 456                                        playlist_item_t *p_root,
 457                                        playlist_item_t *p_item,
 458                                        bool b_ena, bool b_unplayed )
 459 {
 460     PL_ASSERT_LOCKED;
 461     playlist_item_t *p_prev;
 462
 463     PL_DEBUG2( "finding previous os %s within %s", PLI_NAME( p_item ),
 464                                                    PLI_NAME( p_root ) );
 465     assert( p_root && p_root->i_children != -1 );
 466
 467     /* Now, walk the tree until we find a suitable previous item */
 468     p_prev = p_item;
 469     while( 1 )
 470     {
 471         bool b_ena_ok = true, b_unplayed_ok = true;
 472         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
 473         if( !p_prev || p_prev == p_root )
 474             break;
 475         if( p_prev->i_children == -1 )
 476         {
 477             if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
 478                 b_ena_ok = false;
 479             if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
 480                 b_unplayed_ok = false;
 481             if( b_ena_ok && b_unplayed_ok ) break;
 482         }
 483     }
 484     if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
 485     return p_prev;
 486 }
 487
 488 /************************************************************************
 489  * Following functions are local
 490  ***********************************************************************/
 491
 492 /**
 493  * Get the next item in the tree
 494  * If p_item is NULL, return the first child of root
 495  **/
 496 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 497                               playlist_item_t *p_root,
 498                               playlist_item_t *p_item )
 499 {
 500     playlist_item_t *p_parent;
 501     int i;
 502
 503     /* Node with children, get the first one */
 504     if( p_item && p_item->i_children > 0 )
 505         return p_item->pp_children[0];
 506
 507     if( p_item != NULL )
 508         p_parent = p_item->p_parent;
 509     else
 510         p_parent = p_root;
 511     for( i= 0 ; i < p_parent->i_children ; i++ )
 512     {
 513         if( p_item == NULL || p_parent->pp_children[i] == p_item )
 514         {
 515             if( p_item == NULL )
 516                 i = -1;
 517
 518             if( i+1 >= p_parent->i_children )
 519             {
 520                 /* Was already the last sibling. Look for uncles */
 521                 PL_DEBUG2( "Current item is the last of the node,"
 522                            "looking for uncle from %s",
 523                             p_parent->p_input->psz_name );
 524
 525                 if( p_parent == p_root )
 526                 {
 527                     PL_DEBUG2( "already at root" );
 528                     return NULL;
 529                 }
 530                 return GetNextUncle( p_playlist, p_item, p_root );
 531             }
 532             else
 533             {
 534                 return  p_parent->pp_children[i+1];
 535             }
 536         }
 537     }
 538     return NULL;
 539 }
 540
 541 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 542                                playlist_item_t *p_root )
 543 {
 544     playlist_item_t *p_parent = p_item->p_parent;
 545     playlist_item_t *p_grandparent;
 546     bool b_found = false;
 547
 548     (void)p_playlist;
 549
 550     if( p_parent != NULL )
 551     {
 552         p_grandparent = p_parent->p_parent;
 553         while( p_grandparent )
 554         {
 555             int i;
 556             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 557             {
 558                 if( p_parent == p_grandparent->pp_children[i] )
 559                 {
 560                     PL_DEBUG2( "parent %s found as child %i of grandparent %s",
 561                                p_parent->p_input->psz_name, i,
 562                                p_grandparent->p_input->psz_name );
 563                     b_found = true;
 564                     break;
 565                 }
 566             }
 567             if( b_found && i + 1 < p_grandparent->i_children )
 568             {
 569                     return p_grandparent->pp_children[i+1];
 570             }
 571             /* Not found at root */
 572             if( p_grandparent == p_root )
 573             {
 574                 return NULL;
 575             }
 576             else
 577             {
 578                 p_parent = p_grandparent;
 579                 p_grandparent = p_parent->p_parent;
 580             }
 581         }
 582     }
 583     /* We reached root */
 584     return NULL;
 585 }
 586
 587 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 588                                playlist_item_t *p_root )
 589 {
 590     playlist_item_t *p_parent = p_item->p_parent;
 591     playlist_item_t *p_grandparent;
 592     bool b_found = false;
 593
 594     (void)p_playlist;
 595
 596     if( p_parent != NULL )
 597     {
 598         p_grandparent = p_parent->p_parent;
 599         while( 1 )
 600         {
 601             int i;
 602             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
 603             {
 604                 if( p_parent == p_grandparent->pp_children[i] )
 605                 {
 606                     b_found = true;
 607                     break;
 608                 }
 609             }
 610             if( b_found && i - 1 > 0 )
 611             {
 612                 return p_grandparent->pp_children[i-1];
 613             }
 614             /* Not found at root */
 615             if( p_grandparent == p_root )
 616             {
 617                 return NULL;
 618             }
 619             else
 620             {
 621                 p_parent = p_grandparent;
 622                 p_grandparent = p_parent->p_parent;
 623             }
 624         }
 625     }
 626     /* We reached root */
 627     return NULL;
 628 }
 629
 630
 631 /* Recursively search the tree for previous item */
 632 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
 633                               playlist_item_t *p_root,
 634                               playlist_item_t *p_item )
 635 {
 636     playlist_item_t *p_parent;
 637     int i;
 638
 639     /* Node with children, get the last one */
 640     if( p_item && p_item->i_children > 0 )
 641         return p_item->pp_children[p_item->i_children - 1];
 642
 643     /* Last child of its parent ? */
 644     if( p_item != NULL )
 645         p_parent = p_item->p_parent;
 646     else
 647     {
 648         msg_Err( p_playlist, "Get the last one" );
 649         abort();
 650     };
 651
 652     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
 653     {
 654         if( p_parent->pp_children[i] == p_item )
 655         {
 656             if( i-1 < 0 )
 657             {
 658                /* Was already the first sibling. Look for uncles */
 659                 PL_DEBUG2( "current item is the first of its node,"
 660                            "looking for uncle from %s",
 661                            p_parent->p_input->psz_name );
 662                 if( p_parent == p_root )
 663                 {
 664                     PL_DEBUG2( "already at root" );
 665                     return NULL;
 666                 }
 667                 return GetPrevUncle( p_playlist, p_item, p_root );
 668             }
 669             else
 670             {
 671                 return p_parent->pp_children[i-1];
 672             }
 673         }
 674     }
 675     return NULL;
 676 }