src/playlist/tree.c

   1 /*****************************************************************************
   2  * tree.c : Playlist tree walking functions
   3  *****************************************************************************
   4  * Copyright (C) 1999-2007 VLC authors and VideoLAN
   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 it
  10  * under the terms of the GNU Lesser General Public License as published by
  11  * the Free Software Foundation; either version 2.1 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 Lesser General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU Lesser General Public License
  20  * along with this program; if not, write to the Free Software Foundation,
  21  * 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 i_pos position of the node in the parent, PLAYLIST_END to append to end.
  54  * \param p_flags miscellaneous flags
  55  * \param p_input the input_item to attach to or NULL if it has to be created
  56  * \return the new node
  57  */
  58 playlist_item_t * playlist_NodeCreate( playlist_t *p_playlist,
  59                                        const char *psz_name,
  60                                        playlist_item_t *p_parent, int i_pos,
  61                                        int i_flags, input_item_t *p_input )
  62 {
  63     input_item_t *p_new_input = NULL;
  64     playlist_item_t *p_item;
  65
  66     PL_ASSERT_LOCKED;
  67     if( !psz_name ) psz_name = _("Undefined");
  68
  69     if( !p_input )
  70         p_new_input = input_item_NewWithType( NULL, psz_name, 0, NULL, 0, -1,
  71                                               ITEM_TYPE_NODE );
  72     p_item = playlist_ItemNewFromInput( p_playlist,
  73                                         p_input ? p_input : p_new_input );
  74     if( p_new_input )
  75         vlc_gc_decref( p_new_input );
  76
  77     if( p_item == NULL )  return NULL;
  78     p_item->i_children = 0;
  79
  80     ARRAY_APPEND(p_playlist->all_items, p_item);
  81
  82     if( p_parent != NULL )
  83         playlist_NodeInsert( p_playlist, p_item, p_parent,
  84                              i_pos == PLAYLIST_END ? -1 : i_pos );
  85     playlist_SendAddNotify( p_playlist, p_item->i_id,
  86                             p_parent ? p_parent->i_id : -1,
  87                             !( i_flags & PLAYLIST_NO_REBUILD ));
  88
  89     p_item->i_flags |= i_flags;
  90
  91     return p_item;
  92 }
  93
  94 /**
  95  * Remove all the children of a node
  96  *
  97  * This function must be entered with the playlist lock
  98  *
  99  * \param p_playlist the playlist
 100  * \param p_root the node
 101  * \param b_delete_items do we have to delete the children items ?
 102  * \return VLC_SUCCESS or an error
 103  */
 104 int playlist_NodeEmpty( playlist_t *p_playlist, playlist_item_t *p_root,
 105                         bool b_delete_items )
 106 {
 107     PL_ASSERT_LOCKED;
 108     int i;
 109     if( p_root->i_children == -1 )
 110     {
 111         return VLC_EGENERIC;
 112     }
 113
 114     /* Delete the children */
 115     for( i =  p_root->i_children-1 ; i >= 0 ;i-- )
 116     {
 117         if( p_root->pp_children[i]->i_children > -1 )
 118         {
 119             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
 120                                  b_delete_items , false );
 121         }
 122         else if( b_delete_items )
 123         {
 124             /* Delete the item here */
 125             playlist_DeleteFromItemId( p_playlist,
 126                                        p_root->pp_children[i]->i_id );
 127         }
 128     }
 129     return VLC_SUCCESS;
 130 }
 131
 132 /**
 133  * Remove all the children of a node and removes the node
 134  *
 135  * \param p_playlist the playlist
 136  * \param p_root the node
 137  * \param b_delete_items do we have to delete the children items ?
 138  * \return VLC_SUCCESS or an error
 139  */
 140 int playlist_NodeDelete( playlist_t *p_playlist, playlist_item_t *p_root,
 141                          bool b_delete_items, bool b_force )
 142 {
 143     PL_ASSERT_LOCKED;
 144
 145     /* Delete the children */
 146     for( int i = p_root->i_children - 1 ; i >= 0; i-- )
 147         if( b_delete_items || p_root->pp_children[i]->i_children >= 0 )
 148             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
 149                                  b_delete_items, b_force );
 150
 151     /* Delete the node */
 152     if( p_root->i_flags & PLAYLIST_RO_FLAG && !b_force )
 153         return VLC_SUCCESS;
 154
 155     pl_priv(p_playlist)->b_reset_currently_playing = true;
 156
 157     int i;
 158     var_SetInteger( p_playlist, "playlist-item-deleted", p_root->i_id );
 159     ARRAY_BSEARCH( p_playlist->all_items, ->i_id, int, p_root->i_id, i );
 160     if( i != -1 )
 161         ARRAY_REMOVE( p_playlist->all_items, i );
 162
 163     if( p_root->i_children == -1 ) {
 164         ARRAY_BSEARCH( p_playlist->items,->i_id, int, p_root->i_id, i );
 165         if( i != -1 )
 166             ARRAY_REMOVE( p_playlist->items, i );
 167     }
 168
 169     /* Check if it is the current item */
 170     if( get_current_status_item( p_playlist ) == p_root )
 171     {
 172         /* Stop */
 173         playlist_Control( p_playlist, PLAYLIST_STOP, pl_Locked );
 174         msg_Info( p_playlist, "stopping playback" );
 175         /* This item can't be the next one to be played ! */
 176         set_current_status_item( p_playlist, NULL );
 177     }
 178
 179     ARRAY_BSEARCH( p_playlist->current,->i_id, int, p_root->i_id, i );
 180     if( i != -1 )
 181         ARRAY_REMOVE( p_playlist->current, i );
 182
 183     PL_DEBUG( "deleting item `%s'", p_root->p_input->psz_name );
 184
 185     /* Remove the item from its parent */
 186     if( p_root->p_parent )
 187         playlist_NodeRemoveItem( p_playlist, p_root, p_root->p_parent );
 188
 189     playlist_ItemRelease( p_root );
 190     return VLC_SUCCESS;
 191 }
 192
 193
 194 /**
 195  * Adds an item to the children of a node
 196  *
 197  * \param p_playlist the playlist
 198  * \param p_item the item to append
 199  * \param p_parent the parent node
 200  * \return VLC_SUCCESS or an error
 201  */
 202 int playlist_NodeAppend( playlist_t *p_playlist,
 203                          playlist_item_t *p_item,
 204                          playlist_item_t *p_parent )
 205 {
 206     return playlist_NodeInsert( p_playlist, p_item, p_parent, -1 );
 207 }
 208
 209 int playlist_NodeInsert( playlist_t *p_playlist,
 210                          playlist_item_t *p_item,
 211                          playlist_item_t *p_parent,
 212                          int i_position )
 213 {
 214     PL_ASSERT_LOCKED;
 215     (void)p_playlist;
 216     assert( p_parent && p_parent->i_children != -1 );
 217     if( i_position == -1 ) i_position = p_parent->i_children ;
 218     assert( i_position <= p_parent->i_children);
 219
 220     INSERT_ELEM( p_parent->pp_children,
 221                  p_parent->i_children,
 222                  i_position,
 223                  p_item );
 224     p_item->p_parent = p_parent;
 225     return VLC_SUCCESS;
 226 }
 227
 228 /**
 229  * Deletes an item from the children of a node
 230  *
 231  * \param p_playlist the playlist
 232  * \param p_item the item to remove
 233  * \param p_parent the parent node
 234  * \return VLC_SUCCESS or an error
 235  */
 236 int playlist_NodeRemoveItem( playlist_t *p_playlist,
 237                         playlist_item_t *p_item,
 238                         playlist_item_t *p_parent )
 239 {
 240     PL_ASSERT_LOCKED;
 241     (void)p_playlist;
 242
 243     int ret = VLC_EGENERIC;
 244
 245     for(int i= 0; i< p_parent->i_children ; i++ )
 246     {
 247         if( p_parent->pp_children[i] == p_item )
 248         {
 249             REMOVE_ELEM( p_parent->pp_children, p_parent->i_children, i );
 250             ret = VLC_SUCCESS;
 251         }
 252     }
 253
 254     if( ret == VLC_SUCCESS ) {
 255         assert( p_item->p_parent == p_parent );
 256         p_item->p_parent = NULL;
 257     }
 258
 259     return ret;
 260 }
 261
 262 /**
 263  * Search a child of a node by its name
 264  *
 265  * \param p_node the node
 266  * \param psz_search the name of the child to search
 267  * \return the child item or NULL if not found or error
 268  */
 269 playlist_item_t *playlist_ChildSearchName( playlist_item_t *p_node,
 270                                            const char *psz_search )
 271 {
 272     playlist_t * p_playlist = p_node->p_playlist; /* For assert_locked */
 273     PL_ASSERT_LOCKED;
 274     int i;
 275
 276     if( p_node->i_children < 0 )
 277     {
 278          return NULL;
 279     }
 280     for( i = 0 ; i< p_node->i_children; i++ )
 281     {
 282         if( !strcmp( p_node->pp_children[i]->p_input->psz_name, psz_search ) )
 283         {
 284             return p_node->pp_children[i];
 285         }
 286     }
 287     return NULL;
 288 }
 289
 290 /**********************************************************************
 291  * Tree walking functions
 292  **********************************************************************/
 293 /**
 294  * Finds the next item to play
 295  *
 296  * \param p_playlist the playlist
 297  * \param p_root the root node
 298  * \param p_item the previous item  (NULL if none )
 299  * \return the next item to play, or NULL if none found
 300  */
 301 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
 302                                        playlist_item_t *p_root,
 303                                        playlist_item_t *p_item,
 304                                        bool b_ena, bool b_unplayed )
 305 {
 306     PL_ASSERT_LOCKED;
 307     playlist_item_t *p_next;
 308
 309     assert( p_root && p_root->i_children != -1 );
 310
 311     PL_DEBUG2( "finding next of %s within %s",
 312                PLI_NAME( p_item ), PLI_NAME( p_root ) );
 313
 314     /* Now, walk the tree until we find a suitable next item */
 315     p_next = p_item;
 316     while( 1 )
 317     {
 318         bool b_ena_ok = true, b_unplayed_ok = true;
 319         p_next = GetNextItem( p_playlist, p_root, p_next );
 320         if( !p_next || p_next == p_root )
 321             break;
 322         if( p_next->i_children == -1 )
 323         {
 324             if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
 325                 b_ena_ok = false;
 326             if( b_unplayed && p_next->p_input->i_nb_played != 0 )
 327                 b_unplayed_ok = false;
 328             if( b_ena_ok && b_unplayed_ok ) break;
 329         }
 330     }
 331     if( p_next == NULL ) PL_DEBUG2( "at end of node" );
 332     return p_next;
 333 }
 334
 335 /**
 336  * Finds the previous item to play
 337  *
 338  * \param p_playlist the playlist
 339  * \param p_root the root node
 340  * \param p_item the previous item  (NULL if none )
 341  * \return the next item to play, or NULL if none found
 342  */
 343 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
 344                                        playlist_item_t *p_root,
 345                                        playlist_item_t *p_item,
 346                                        bool b_ena, bool b_unplayed )
 347 {
 348     PL_ASSERT_LOCKED;
 349     playlist_item_t *p_prev;
 350
 351     PL_DEBUG2( "finding previous of %s within %s", PLI_NAME( p_item ),
 352                                                    PLI_NAME( p_root ) );
 353     assert( p_root && p_root->i_children != -1 );
 354
 355     /* Now, walk the tree until we find a suitable previous item */
 356     p_prev = p_item;
 357     while( 1 )
 358     {
 359         bool b_ena_ok = true, b_unplayed_ok = true;
 360         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
 361         if( !p_prev || p_prev == p_root )
 362             break;
 363         if( p_prev->i_children == -1 )
 364         {
 365             if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
 366                 b_ena_ok = false;
 367             if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
 368                 b_unplayed_ok = false;
 369             if( b_ena_ok && b_unplayed_ok ) break;
 370         }
 371     }
 372     if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
 373     return p_prev;
 374 }
 375
 376 /************************************************************************
 377  * Following functions are local
 378  ***********************************************************************/
 379
 380 /**
 381  * Get the next item in the tree
 382  * If p_item is NULL, return the first child of root
 383  **/
 384 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 385                               playlist_item_t *p_root,
 386                               playlist_item_t *p_item )
 387 {
 388     /* If the item is NULL, return the firt child of root */
 389     if( p_item == NULL )
 390     {
 391         if( p_root->i_children > 0 )
 392             return p_root->pp_children[0];
 393         else
 394             return NULL;
 395     }
 396
 397     /* Node with children, get the first one */
 398     if( p_item->i_children > 0 )
 399         return p_item->pp_children[0];
 400
 401     playlist_item_t* p_parent = p_item->p_parent;
 402     for( int i = 0 ; i < p_parent->i_children ; i++ )
 403     {
 404         if( p_parent->pp_children[i] == p_item )
 405         {
 406             // Return the next children
 407             if( i + 1 < p_parent->i_children )
 408                 return p_parent->pp_children[i+1];
 409             // We are the least one, so try to have uncles
 410             else
 411             {
 412                 PL_DEBUG2( "Current item is the last of the node,"
 413                            "looking for uncle from %s",
 414                             p_parent->p_input->psz_name );
 415                 if( p_parent == p_root )
 416                 {
 417                     PL_DEBUG2( "already at root" );
 418                     return NULL;
 419                 }
 420                 else
 421                     return GetNextUncle( p_playlist, p_item, p_root );
 422             }
 423         }
 424     }
 425     return NULL;
 426 }
 427
 428 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 429                                playlist_item_t *p_root )
 430 {
 431     playlist_item_t *p_parent = p_item->p_parent;
 432     playlist_item_t *p_grandparent;
 433     bool b_found = false;
 434
 435     (void)p_playlist;
 436
 437     if( p_parent != NULL )
 438     {
 439         p_grandparent = p_parent->p_parent;
 440         while( p_grandparent )
 441         {
 442             int i;
 443             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 444             {
 445                 if( p_parent == p_grandparent->pp_children[i] )
 446                 {
 447                     PL_DEBUG2( "parent %s found as child %i of grandparent %s",
 448                                p_parent->p_input->psz_name, i,
 449                                p_grandparent->p_input->psz_name );
 450                     b_found = true;
 451                     break;
 452                 }
 453             }
 454             if( b_found && i + 1 < p_grandparent->i_children )
 455             {
 456                     return p_grandparent->pp_children[i+1];
 457             }
 458             /* Not found at root */
 459             if( p_grandparent == p_root )
 460             {
 461                 return NULL;
 462             }
 463             else
 464             {
 465                 p_parent = p_grandparent;
 466                 p_grandparent = p_parent->p_parent;
 467             }
 468         }
 469     }
 470     /* We reached root */
 471     return NULL;
 472 }
 473
 474 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 475                                playlist_item_t *p_root )
 476 {
 477     playlist_item_t *p_parent = p_item->p_parent;
 478     playlist_item_t *p_grandparent;
 479     bool b_found = false;
 480
 481     (void)p_playlist;
 482
 483     if( p_parent != NULL )
 484     {
 485         p_grandparent = p_parent->p_parent;
 486         while( 1 )
 487         {
 488             int i;
 489             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
 490             {
 491                 if( p_parent == p_grandparent->pp_children[i] )
 492                 {
 493                     b_found = true;
 494                     break;
 495                 }
 496             }
 497             if( b_found && i - 1 > 0 )
 498             {
 499                 return p_grandparent->pp_children[i-1];
 500             }
 501             /* Not found at root */
 502             if( p_grandparent == p_root )
 503             {
 504                 return NULL;
 505             }
 506             else
 507             {
 508                 p_parent = p_grandparent;
 509                 p_grandparent = p_parent->p_parent;
 510             }
 511         }
 512     }
 513     /* We reached root */
 514     return NULL;
 515 }
 516
 517
 518 /* Recursively search the tree for previous item */
 519 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
 520                               playlist_item_t *p_root,
 521                               playlist_item_t *p_item )
 522 {
 523     playlist_item_t *p_parent;
 524     int i;
 525
 526     /* Node with children, get the last one */
 527     if( p_item && p_item->i_children > 0 )
 528         return p_item->pp_children[p_item->i_children - 1];
 529
 530     /* Last child of its parent ? */
 531     if( p_item != NULL )
 532         p_parent = p_item->p_parent;
 533     else
 534     {
 535         msg_Err( p_playlist, "Get the last one" );
 536         abort();
 537     };
 538
 539     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
 540     {
 541         if( p_parent->pp_children[i] == p_item )
 542         {
 543             if( i-1 < 0 )
 544             {
 545                /* Was already the first sibling. Look for uncles */
 546                 PL_DEBUG2( "current item is the first of its node,"
 547                            "looking for uncle from %s",
 548                            p_parent->p_input->psz_name );
 549                 if( p_parent == p_root )
 550                 {
 551                     PL_DEBUG2( "already at root" );
 552                     return NULL;
 553                 }
 554                 return GetPrevUncle( p_playlist, p_item, p_root );
 555             }
 556             else
 557             {
 558                 return p_parent->pp_children[i-1];
 559             }
 560         }
 561     }
 562     return NULL;
 563 }