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