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 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( VLC_OBJECT(p_playlist), NULL,
  71                                         psz_name, 0, NULL, 0, -1, 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     int i;
 145
 146     /* Delete the children */
 147     for( i = p_root->i_children - 1 ; i >= 0; i-- )
 148     {
 149         if( b_delete_items || p_root->pp_children[i]->i_children > -1 )
 150         {
 151             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
 152                                  b_delete_items, b_force );
 153         }
 154     }
 155     /* Delete the node */
 156     if( p_root->i_flags & PLAYLIST_RO_FLAG && !b_force )
 157     {
 158     }
 159     else
 160     {
 161         pl_priv(p_playlist)->b_reset_currently_playing = true;
 162
 163         int i;
 164         var_SetInteger( p_playlist, "playlist-item-deleted", p_root->i_id );
 165         ARRAY_BSEARCH( p_playlist->all_items, ->i_id, int,
 166                        p_root->i_id, i );
 167         if( i != -1 )
 168             ARRAY_REMOVE( p_playlist->all_items, i );
 169
 170         if( p_root->i_children == -1 ) {
 171             ARRAY_BSEARCH( p_playlist->items,->i_id, int, p_root->i_id, i );
 172             if( i != -1 )
 173                 ARRAY_REMOVE( p_playlist->items, i );
 174         }
 175
 176         /* Check if it is the current item */
 177         if( get_current_status_item( p_playlist ) == p_root )
 178         {
 179             /* Stop */
 180             playlist_Control( p_playlist, PLAYLIST_STOP, pl_Locked );
 181             msg_Info( p_playlist, "stopping playback" );
 182             /* This item can't be the next one to be played ! */
 183             set_current_status_item( p_playlist, NULL );
 184         }
 185
 186         ARRAY_BSEARCH( p_playlist->current,->i_id, int, p_root->i_id, i );
 187         if( i != -1 )
 188             ARRAY_REMOVE( p_playlist->current, i );
 189
 190         PL_DEBUG( "deleting item `%s'", p_root->p_input->psz_name );
 191
 192         /* Remove the item from its parent */
 193         if( p_root->p_parent )
 194             playlist_NodeRemoveItem( p_playlist, p_root, p_root->p_parent );
 195
 196         playlist_ItemRelease( p_root );
 197     }
 198     return VLC_SUCCESS;
 199 }
 200
 201
 202 /**
 203  * Adds an item to the children of a node
 204  *
 205  * \param p_playlist the playlist
 206  * \param p_item the item to append
 207  * \param p_parent the parent node
 208  * \return VLC_SUCCESS or an error
 209  */
 210 int playlist_NodeAppend( playlist_t *p_playlist,
 211                          playlist_item_t *p_item,
 212                          playlist_item_t *p_parent )
 213 {
 214     return playlist_NodeInsert( p_playlist, p_item, p_parent, -1 );
 215 }
 216
 217 int playlist_NodeInsert( playlist_t *p_playlist,
 218                          playlist_item_t *p_item,
 219                          playlist_item_t *p_parent,
 220                          int i_position )
 221 {
 222     PL_ASSERT_LOCKED;
 223     (void)p_playlist;
 224     assert( p_parent && p_parent->i_children != -1 );
 225     if( i_position == -1 ) i_position = p_parent->i_children ;
 226     assert( i_position <= p_parent->i_children);
 227
 228     INSERT_ELEM( p_parent->pp_children,
 229                  p_parent->i_children,
 230                  i_position,
 231                  p_item );
 232     p_item->p_parent = p_parent;
 233     return VLC_SUCCESS;
 234 }
 235
 236 /**
 237  * Deletes an item from the children of a node
 238  *
 239  * \param p_playlist the playlist
 240  * \param p_item the item to remove
 241  * \param p_parent the parent node
 242  * \return VLC_SUCCESS or an error
 243  */
 244 int playlist_NodeRemoveItem( playlist_t *p_playlist,
 245                         playlist_item_t *p_item,
 246                         playlist_item_t *p_parent )
 247 {
 248     PL_ASSERT_LOCKED;
 249     (void)p_playlist;
 250
 251     int ret = VLC_EGENERIC;
 252
 253     for(int i= 0; i< p_parent->i_children ; i++ )
 254     {
 255         if( p_parent->pp_children[i] == p_item )
 256         {
 257             REMOVE_ELEM( p_parent->pp_children, p_parent->i_children, i );
 258             ret = VLC_SUCCESS;
 259         }
 260     }
 261
 262     if( ret == VLC_SUCCESS ) {
 263         assert( p_item->p_parent == p_parent );
 264         p_item->p_parent = NULL;
 265     }
 266
 267     return ret;
 268 }
 269
 270 /**
 271  * Search a child of a node by its name
 272  *
 273  * \param p_node the node
 274  * \param psz_search the name of the child to search
 275  * \return the child item or NULL if not found or error
 276  */
 277 playlist_item_t *playlist_ChildSearchName( playlist_item_t *p_node,
 278                                            const char *psz_search )
 279 {
 280     playlist_t * p_playlist = p_node->p_playlist; /* For assert_locked */
 281     PL_ASSERT_LOCKED;
 282     int i;
 283
 284     if( p_node->i_children < 0 )
 285     {
 286          return NULL;
 287     }
 288     for( i = 0 ; i< p_node->i_children; i++ )
 289     {
 290         if( !strcmp( p_node->pp_children[i]->p_input->psz_name, psz_search ) )
 291         {
 292             return p_node->pp_children[i];
 293         }
 294     }
 295     return NULL;
 296 }
 297
 298 /**********************************************************************
 299  * Tree walking functions
 300  **********************************************************************/
 301 /**
 302  * Finds the next item to play
 303  *
 304  * \param p_playlist the playlist
 305  * \param p_root the root node
 306  * \param p_item the previous item  (NULL if none )
 307  * \return the next item to play, or NULL if none found
 308  */
 309 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
 310                                        playlist_item_t *p_root,
 311                                        playlist_item_t *p_item,
 312                                        bool b_ena, bool b_unplayed )
 313 {
 314     PL_ASSERT_LOCKED;
 315     playlist_item_t *p_next;
 316
 317     assert( p_root && p_root->i_children != -1 );
 318
 319     PL_DEBUG2( "finding next of %s within %s",
 320                PLI_NAME( p_item ), PLI_NAME( p_root ) );
 321
 322     /* Now, walk the tree until we find a suitable next item */
 323     p_next = p_item;
 324     while( 1 )
 325     {
 326         bool b_ena_ok = true, b_unplayed_ok = true;
 327         p_next = GetNextItem( p_playlist, p_root, p_next );
 328         if( !p_next || p_next == p_root )
 329             break;
 330         if( p_next->i_children == -1 )
 331         {
 332             if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
 333                 b_ena_ok = false;
 334             if( b_unplayed && p_next->p_input->i_nb_played != 0 )
 335                 b_unplayed_ok = false;
 336             if( b_ena_ok && b_unplayed_ok ) break;
 337         }
 338     }
 339     if( p_next == NULL ) PL_DEBUG2( "at end of node" );
 340     return p_next;
 341 }
 342
 343 /**
 344  * Finds the previous item to play
 345  *
 346  * \param p_playlist the playlist
 347  * \param p_root the root node
 348  * \param p_item the previous item  (NULL if none )
 349  * \return the next item to play, or NULL if none found
 350  */
 351 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
 352                                        playlist_item_t *p_root,
 353                                        playlist_item_t *p_item,
 354                                        bool b_ena, bool b_unplayed )
 355 {
 356     PL_ASSERT_LOCKED;
 357     playlist_item_t *p_prev;
 358
 359     PL_DEBUG2( "finding previous of %s within %s", PLI_NAME( p_item ),
 360                                                    PLI_NAME( p_root ) );
 361     assert( p_root && p_root->i_children != -1 );
 362
 363     /* Now, walk the tree until we find a suitable previous item */
 364     p_prev = p_item;
 365     while( 1 )
 366     {
 367         bool b_ena_ok = true, b_unplayed_ok = true;
 368         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
 369         if( !p_prev || p_prev == p_root )
 370             break;
 371         if( p_prev->i_children == -1 )
 372         {
 373             if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
 374                 b_ena_ok = false;
 375             if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
 376                 b_unplayed_ok = false;
 377             if( b_ena_ok && b_unplayed_ok ) break;
 378         }
 379     }
 380     if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
 381     return p_prev;
 382 }
 383
 384 /************************************************************************
 385  * Following functions are local
 386  ***********************************************************************/
 387
 388 /**
 389  * Get the next item in the tree
 390  * If p_item is NULL, return the first child of root
 391  **/
 392 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 393                               playlist_item_t *p_root,
 394                               playlist_item_t *p_item )
 395 {
 396     /* If the item is NULL, return the firt child of root */
 397     if( p_item == NULL )
 398     {
 399         if( p_root->i_children > 0 )
 400             return p_root->pp_children[0];
 401         else
 402             return NULL;
 403     }
 404
 405     /* Node with children, get the first one */
 406     if( p_item->i_children > 0 )
 407         return p_item->pp_children[0];
 408
 409     playlist_item_t* p_parent = p_item->p_parent;
 410     for( int i = 0 ; i < p_parent->i_children ; i++ )
 411     {
 412         if( p_parent->pp_children[i] == p_item )
 413         {
 414             // Return the next children
 415             if( i + 1 < p_parent->i_children )
 416                 return p_parent->pp_children[i+1];
 417             // We are the least one, so try to have uncles
 418             else
 419             {
 420                 PL_DEBUG2( "Current item is the last of the node,"
 421                            "looking for uncle from %s",
 422                             p_parent->p_input->psz_name );
 423                 if( p_parent == p_root )
 424                 {
 425                     PL_DEBUG2( "already at root" );
 426                     return NULL;
 427                 }
 428                 else
 429                     return GetNextUncle( p_playlist, p_item, p_root );
 430             }
 431         }
 432     }
 433     return NULL;
 434 }
 435
 436 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 437                                playlist_item_t *p_root )
 438 {
 439     playlist_item_t *p_parent = p_item->p_parent;
 440     playlist_item_t *p_grandparent;
 441     bool b_found = false;
 442
 443     (void)p_playlist;
 444
 445     if( p_parent != NULL )
 446     {
 447         p_grandparent = p_parent->p_parent;
 448         while( p_grandparent )
 449         {
 450             int i;
 451             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 452             {
 453                 if( p_parent == p_grandparent->pp_children[i] )
 454                 {
 455                     PL_DEBUG2( "parent %s found as child %i of grandparent %s",
 456                                p_parent->p_input->psz_name, i,
 457                                p_grandparent->p_input->psz_name );
 458                     b_found = true;
 459                     break;
 460                 }
 461             }
 462             if( b_found && i + 1 < p_grandparent->i_children )
 463             {
 464                     return p_grandparent->pp_children[i+1];
 465             }
 466             /* Not found at root */
 467             if( p_grandparent == p_root )
 468             {
 469                 return NULL;
 470             }
 471             else
 472             {
 473                 p_parent = p_grandparent;
 474                 p_grandparent = p_parent->p_parent;
 475             }
 476         }
 477     }
 478     /* We reached root */
 479     return NULL;
 480 }
 481
 482 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 483                                playlist_item_t *p_root )
 484 {
 485     playlist_item_t *p_parent = p_item->p_parent;
 486     playlist_item_t *p_grandparent;
 487     bool b_found = false;
 488
 489     (void)p_playlist;
 490
 491     if( p_parent != NULL )
 492     {
 493         p_grandparent = p_parent->p_parent;
 494         while( 1 )
 495         {
 496             int i;
 497             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
 498             {
 499                 if( p_parent == p_grandparent->pp_children[i] )
 500                 {
 501                     b_found = true;
 502                     break;
 503                 }
 504             }
 505             if( b_found && i - 1 > 0 )
 506             {
 507                 return p_grandparent->pp_children[i-1];
 508             }
 509             /* Not found at root */
 510             if( p_grandparent == p_root )
 511             {
 512                 return NULL;
 513             }
 514             else
 515             {
 516                 p_parent = p_grandparent;
 517                 p_grandparent = p_parent->p_parent;
 518             }
 519         }
 520     }
 521     /* We reached root */
 522     return NULL;
 523 }
 524
 525
 526 /* Recursively search the tree for previous item */
 527 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
 528                               playlist_item_t *p_root,
 529                               playlist_item_t *p_item )
 530 {
 531     playlist_item_t *p_parent;
 532     int i;
 533
 534     /* Node with children, get the last one */
 535     if( p_item && p_item->i_children > 0 )
 536         return p_item->pp_children[p_item->i_children - 1];
 537
 538     /* Last child of its parent ? */
 539     if( p_item != NULL )
 540         p_parent = p_item->p_parent;
 541     else
 542     {
 543         msg_Err( p_playlist, "Get the last one" );
 544         abort();
 545     };
 546
 547     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
 548     {
 549         if( p_parent->pp_children[i] == p_item )
 550         {
 551             if( i-1 < 0 )
 552             {
 553                /* Was already the first sibling. Look for uncles */
 554                 PL_DEBUG2( "current item is the first of its node,"
 555                            "looking for uncle from %s",
 556                            p_parent->p_input->psz_name );
 557                 if( p_parent == p_root )
 558                 {
 559                     PL_DEBUG2( "already at root" );
 560                     return NULL;
 561                 }
 562                 return GetPrevUncle( p_playlist, p_item, p_root );
 563             }
 564             else
 565             {
 566                 return p_parent->pp_children[i-1];
 567             }
 568         }
 569     }
 570     return NULL;
 571 }