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