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/vlc.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;
  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( VLC_OBJECT(p_playlist),
  71                                         p_input ? p_input : p_new_input );
  72     if( !p_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     int i;
 102     if( p_root->i_children == -1 )
 103     {
 104         return VLC_EGENERIC;
 105     }
 106
 107     /* Delete the children */
 108     for( i =  p_root->i_children-1 ; i >= 0 ;i-- )
 109     {
 110         if( p_root->pp_children[i]->i_children > -1 )
 111         {
 112             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
 113                                  b_delete_items , false );
 114         }
 115         else if( b_delete_items )
 116         {
 117             /* Delete the item here */
 118             playlist_DeleteFromItemId( p_playlist,
 119                                        p_root->pp_children[i]->i_id );
 120         }
 121     }
 122     return VLC_SUCCESS;
 123 }
 124
 125 /**
 126  * Remove all the children of a node and removes the node
 127  *
 128  * \param p_playlist the playlist
 129  * \param p_root the node
 130  * \param b_delete_items do we have to delete the children items ?
 131  * \return VLC_SUCCESS or an error
 132  */
 133 int playlist_NodeDelete( playlist_t *p_playlist, playlist_item_t *p_root,
 134                          bool b_delete_items, bool b_force )
 135 {
 136     int i;
 137
 138     if( p_root->i_children == -1 )
 139     {
 140         return VLC_EGENERIC;
 141     }
 142
 143     /* Delete the children */
 144     for( i =  p_root->i_children - 1 ; i >= 0; i-- )
 145     {
 146         if( p_root->pp_children[i]->i_children > -1 )
 147         {
 148             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
 149                                  b_delete_items , b_force );
 150         }
 151         else if( b_delete_items )
 152         {
 153             playlist_DeleteFromItemId( p_playlist,
 154                                        p_root->pp_children[i]->i_id );
 155         }
 156     }
 157     /* Delete the node */
 158     if( p_root->i_flags & PLAYLIST_RO_FLAG && !b_force )
 159     {
 160     }
 161     else
 162     {
 163         int i;
 164         var_SetInteger( p_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         /* Remove the item from its parent */
 171         if( p_root->p_parent )
 172             playlist_NodeRemoveItem( p_playlist, p_root, p_root->p_parent );
 173
 174         playlist_ItemDelete( p_root );
 175     }
 176     return VLC_SUCCESS;
 177 }
 178
 179
 180 /**
 181  * Adds an item to the children of a node
 182  *
 183  * \param p_playlist the playlist
 184  * \param p_item the item to append
 185  * \param p_parent the parent node
 186  * \return VLC_SUCCESS or an error
 187  */
 188 int playlist_NodeAppend( playlist_t *p_playlist,
 189                          playlist_item_t *p_item,
 190                          playlist_item_t *p_parent )
 191 {
 192     return playlist_NodeInsert( p_playlist, p_item, p_parent, -1 );
 193 }
 194
 195 int playlist_NodeInsert( playlist_t *p_playlist,
 196                          playlist_item_t *p_item,
 197                          playlist_item_t *p_parent,
 198                          int i_position )
 199 {
 200    (void)p_playlist;
 201    assert( p_parent && p_parent->i_children != -1 );
 202    if( i_position == -1 ) i_position = p_parent->i_children ;
 203
 204    INSERT_ELEM( p_parent->pp_children,
 205                 p_parent->i_children,
 206                 i_position,
 207                 p_item );
 208    p_item->p_parent = p_parent;
 209    return VLC_SUCCESS;
 210 }
 211
 212 /**
 213  * Deletes an item from the children of a node
 214  *
 215  * \param p_playlist the playlist
 216  * \param p_item the item to remove
 217  * \param p_parent the parent node
 218  * \return VLC_SUCCESS or an error
 219  */
 220 int playlist_NodeRemoveItem( playlist_t *p_playlist,
 221                         playlist_item_t *p_item,
 222                         playlist_item_t *p_parent )
 223 {
 224    (void)p_playlist;
 225
 226    for(int i= 0; i< p_parent->i_children ; i++ )
 227    {
 228        if( p_parent->pp_children[i] == p_item )
 229        {
 230            REMOVE_ELEM( p_parent->pp_children, p_parent->i_children, i );
 231        }
 232    }
 233
 234    return VLC_SUCCESS;
 235 }
 236
 237
 238 /**
 239  * Count the children of a node
 240  *
 241  * \param p_playlist the playlist
 242  * \param p_node the node
 243  * \return the number of children
 244  */
 245 int playlist_NodeChildrenCount( playlist_t *p_playlist, playlist_item_t*p_node)
 246 {
 247     int i;
 248     int i_nb = 0;
 249
 250     if( p_node->i_children == -1 )
 251         return 0;
 252
 253     i_nb = p_node->i_children;
 254     for( i=0 ; i< p_node->i_children;i++ )
 255     {
 256         if( p_node->pp_children[i]->i_children == -1 )
 257             break;
 258         else
 259             i_nb += playlist_NodeChildrenCount( p_playlist,
 260                                                 p_node->pp_children[i] );
 261     }
 262     return i_nb;
 263 }
 264
 265 /**
 266  * Search a child of a node by its name
 267  *
 268  * \param p_node the node
 269  * \param psz_search the name of the child to search
 270  * \return the child item or NULL if not found or error
 271  */
 272 playlist_item_t *playlist_ChildSearchName( playlist_item_t *p_node,
 273                                            const char *psz_search )
 274 {
 275     int i;
 276
 277     if( p_node->i_children < 0 )
 278     {
 279          return NULL;
 280     }
 281     for( i = 0 ; i< p_node->i_children; i++ )
 282     {
 283         if( !strcmp( p_node->pp_children[i]->p_input->psz_name, psz_search ) )
 284         {
 285             return p_node->pp_children[i];
 286         }
 287     }
 288     return NULL;
 289 }
 290
 291 /**
 292  * Create a pair of nodes in the category and onelevel trees.
 293  * They share the same input item.
 294  * \param p_playlist the playlist
 295  * \param psz_name the name of the nodes
 296  * \param pp_node_cat pointer to return the node in category tree
 297  * \param pp_node_one pointer to return the node in onelevel tree
 298  * \param b_for_sd For Services Discovery ? (make node read-only and unskipping)
 299  */
 300 void playlist_NodesPairCreate( playlist_t *p_playlist, const char *psz_name,
 301                                playlist_item_t **pp_node_cat,
 302                                playlist_item_t **pp_node_one,
 303                                bool b_for_sd )
 304 {
 305     *pp_node_cat = playlist_NodeCreate( p_playlist, psz_name,
 306                                         p_playlist->p_root_category, 0, NULL );
 307     *pp_node_one = playlist_NodeCreate( p_playlist, psz_name,
 308                                         p_playlist->p_root_onelevel, 0,
 309                                         (*pp_node_cat)->p_input );
 310     if( b_for_sd )
 311     {
 312         (*pp_node_cat)->i_flags |= PLAYLIST_RO_FLAG;
 313         (*pp_node_cat)->i_flags |= PLAYLIST_SKIP_FLAG;
 314         (*pp_node_one)->i_flags |= PLAYLIST_RO_FLAG;
 315         (*pp_node_one)->i_flags |= PLAYLIST_SKIP_FLAG;
 316     }
 317 }
 318
 319 /**
 320  * Get the node in the preferred tree from a node in one of category
 321  * or onelevel tree.
 322  * For example, for the SAP node, it will return the node in the category
 323  * tree if --playlist-tree is not set to never, because the SAP node prefers
 324  * category
 325  */
 326 playlist_item_t * playlist_GetPreferredNode( playlist_t *p_playlist,
 327                                              playlist_item_t *p_node )
 328 {
 329     int i;
 330     if( p_node->p_parent == p_playlist->p_root_category )
 331     {
 332         if( p_playlist->b_always_tree ||
 333             p_node->p_input->b_prefers_tree ) return p_node;
 334         for( i = 0 ; i< p_playlist->p_root_onelevel->i_children; i++ )
 335         {
 336             if( p_playlist->p_root_onelevel->pp_children[i]->p_input->i_id ==
 337                     p_node->p_input->i_id )
 338                 return p_playlist->p_root_onelevel->pp_children[i];
 339         }
 340     }
 341     else if( p_node->p_parent == p_playlist->p_root_onelevel )
 342     {
 343         if( p_playlist->b_never_tree || !p_node->p_input->b_prefers_tree )
 344             return p_node;
 345         for( i = 0 ; i< p_playlist->p_root_category->i_children; i++ )
 346         {
 347             if( p_playlist->p_root_category->pp_children[i]->p_input->i_id ==
 348                     p_node->p_input->i_id )
 349                 return p_playlist->p_root_category->pp_children[i];
 350         }
 351     }
 352     return NULL;
 353 }
 354
 355 /**********************************************************************
 356  * Tree walking functions
 357  **********************************************************************/
 358
 359 playlist_item_t *playlist_GetLastLeaf(playlist_t *p_playlist,
 360                                       playlist_item_t *p_root )
 361 {
 362     int i;
 363     playlist_item_t *p_item;
 364     for ( i = p_root->i_children - 1; i >= 0; i-- )
 365     {
 366         if( p_root->pp_children[i]->i_children == -1 )
 367             return p_root->pp_children[i];
 368         else if( p_root->pp_children[i]->i_children > 0)
 369         {
 370              p_item = playlist_GetLastLeaf( p_playlist,
 371                                             p_root->pp_children[i] );
 372             if ( p_item != NULL )
 373                 return p_item;
 374         }
 375         else if( i == 0 )
 376             return NULL;
 377     }
 378     return NULL;
 379 }
 380
 381 int playlist_GetAllEnabledChildren( playlist_t *p_playlist,
 382                                     playlist_item_t *p_node,
 383                                     playlist_item_t ***ppp_items )
 384 {
 385     int i_count = 0;
 386     playlist_item_t *p_next = NULL;
 387     while( 1 )
 388     {
 389         p_next = playlist_GetNextLeaf( p_playlist, p_node,
 390                                        p_next, true, false );
 391         if( p_next )
 392             INSERT_ELEM( *ppp_items, i_count, i_count, p_next );
 393         else
 394             break;
 395     }
 396     return i_count;
 397 }
 398
 399 /**
 400  * Finds the next item to play
 401  *
 402  * \param p_playlist the playlist
 403  * \param p_root the root node
 404  * \param p_item the previous item  (NULL if none )
 405  * \return the next item to play, or NULL if none found
 406  */
 407 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
 408                                        playlist_item_t *p_root,
 409                                        playlist_item_t *p_item,
 410                                        bool b_ena, bool b_unplayed )
 411 {
 412     playlist_item_t *p_next;
 413
 414     assert( p_root && p_root->i_children != -1 );
 415
 416     PL_DEBUG2( "finding next of %s within %s",
 417                PLI_NAME( p_item ), PLI_NAME( p_root ) );
 418
 419     /* Now, walk the tree until we find a suitable next item */
 420     p_next = p_item;
 421     while( 1 )
 422     {
 423         bool b_ena_ok = true, b_unplayed_ok = true;
 424         p_next = GetNextItem( p_playlist, p_root, p_next );
 425         if( !p_next || p_next == p_root )
 426             break;
 427         if( p_next->i_children == -1 )
 428         {
 429             if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
 430                 b_ena_ok = false;
 431             if( b_unplayed && p_next->p_input->i_nb_played != 0 )
 432                 b_unplayed_ok = false;
 433             if( b_ena_ok && b_unplayed_ok ) break;
 434         }
 435     }
 436     if( p_next == NULL ) PL_DEBUG2( "at end of node" );
 437     return p_next;
 438 }
 439
 440 /**
 441  * Finds the previous item to play
 442  *
 443  * \param p_playlist the playlist
 444  * \param p_root the root node
 445  * \param p_item the previous item  (NULL if none )
 446  * \return the next item to play, or NULL if none found
 447  */
 448 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
 449                                        playlist_item_t *p_root,
 450                                        playlist_item_t *p_item,
 451                                        bool b_ena, bool b_unplayed )
 452 {
 453     playlist_item_t *p_prev;
 454
 455     PL_DEBUG2( "finding previous os %s within %s", PLI_NAME( p_item ),
 456                                                    PLI_NAME( p_root ) );
 457     assert( p_root && p_root->i_children != -1 );
 458
 459     /* Now, walk the tree until we find a suitable previous item */
 460     p_prev = p_item;
 461     while( 1 )
 462     {
 463         bool b_ena_ok = true, b_unplayed_ok = true;
 464         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
 465         if( !p_prev || p_prev == p_root )
 466             break;
 467         if( p_prev->i_children == -1 )
 468         {
 469             if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
 470                 b_ena_ok = false;
 471             if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
 472                 b_unplayed_ok = false;
 473             if( b_ena_ok && b_unplayed_ok ) break;
 474         }
 475     }
 476     if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
 477     return p_prev;
 478 }
 479
 480 /************************************************************************
 481  * Following functions are local
 482  ***********************************************************************/
 483
 484 /**
 485  * Get the next item in the tree
 486  * If p_item is NULL, return the first child of root
 487  **/
 488 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 489                               playlist_item_t *p_root,
 490                               playlist_item_t *p_item )
 491 {
 492     playlist_item_t *p_parent;
 493     int i;
 494
 495     /* Node with children, get the first one */
 496     if( p_item && p_item->i_children > 0 )
 497         return p_item->pp_children[0];
 498
 499     if( p_item != NULL )
 500         p_parent = p_item->p_parent;
 501     else
 502         p_parent = p_root;
 503     for( i= 0 ; i < p_parent->i_children ; i++ )
 504     {
 505         if( p_item == NULL || p_parent->pp_children[i] == p_item )
 506         {
 507             if( p_item == NULL )
 508                 i = -1;
 509
 510             if( i+1 >= p_parent->i_children )
 511             {
 512                 /* Was already the last sibling. Look for uncles */
 513                 PL_DEBUG2( "Current item is the last of the node,"
 514                            "looking for uncle from %s",
 515                             p_parent->p_input->psz_name );
 516
 517                 if( p_parent == p_root )
 518                 {
 519                     PL_DEBUG2( "already at root" );
 520                     return NULL;
 521                 }
 522                 return GetNextUncle( p_playlist, p_item, p_root );
 523             }
 524             else
 525             {
 526                 return  p_parent->pp_children[i+1];
 527             }
 528         }
 529     }
 530     return NULL;
 531 }
 532
 533 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 534                                playlist_item_t *p_root )
 535 {
 536     playlist_item_t *p_parent = p_item->p_parent;
 537     playlist_item_t *p_grandparent;
 538     bool b_found = false;
 539
 540     (void)p_playlist;
 541
 542     if( p_parent != NULL )
 543     {
 544         p_grandparent = p_parent->p_parent;
 545         while( p_grandparent )
 546         {
 547             int i;
 548             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 549             {
 550                 if( p_parent == p_grandparent->pp_children[i] )
 551                 {
 552                     PL_DEBUG2( "parent %s found as child %i of grandparent %s",
 553                                p_parent->p_input->psz_name, i,
 554                                p_grandparent->p_input->psz_name );
 555                     b_found = true;
 556                     break;
 557                 }
 558             }
 559             if( b_found && i + 1 < p_grandparent->i_children )
 560             {
 561                     return p_grandparent->pp_children[i+1];
 562             }
 563             /* Not found at root */
 564             if( p_grandparent == p_root )
 565             {
 566                 return NULL;
 567             }
 568             else
 569             {
 570                 p_parent = p_grandparent;
 571                 p_grandparent = p_parent->p_parent;
 572             }
 573         }
 574     }
 575     /* We reached root */
 576     return NULL;
 577 }
 578
 579 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 580                                playlist_item_t *p_root )
 581 {
 582     playlist_item_t *p_parent = p_item->p_parent;
 583     playlist_item_t *p_grandparent;
 584     bool b_found = false;
 585
 586     (void)p_playlist;
 587
 588     if( p_parent != NULL )
 589     {
 590         p_grandparent = p_parent->p_parent;
 591         while( 1 )
 592         {
 593             int i;
 594             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
 595             {
 596                 if( p_parent == p_grandparent->pp_children[i] )
 597                 {
 598                     b_found = true;
 599                     break;
 600                 }
 601             }
 602             if( b_found && i - 1 > 0 )
 603             {
 604                 return p_grandparent->pp_children[i-1];
 605             }
 606             /* Not found at root */
 607             if( p_grandparent == p_root )
 608             {
 609                 return NULL;
 610             }
 611             else
 612             {
 613                 p_parent = p_grandparent;
 614                 p_grandparent = p_parent->p_parent;
 615             }
 616         }
 617     }
 618     /* We reached root */
 619     return NULL;
 620 }
 621
 622
 623 /* Recursively search the tree for previous item */
 624 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
 625                               playlist_item_t *p_root,
 626                               playlist_item_t *p_item )
 627 {
 628     playlist_item_t *p_parent;
 629     int i;
 630
 631     /* Node with children, get the last one */
 632     if( p_item && p_item->i_children > 0 )
 633         return p_item->pp_children[p_item->i_children - 1];
 634
 635     /* Last child of its parent ? */
 636     if( p_item != NULL )
 637         p_parent = p_item->p_parent;
 638     else
 639     {
 640         msg_Err( p_playlist, "Get the last one" );
 641         abort();
 642     };
 643
 644     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
 645     {
 646         if( p_parent->pp_children[i] == p_item )
 647         {
 648             if( i-1 < 0 )
 649             {
 650                /* Was already the first sibling. Look for uncles */
 651                 PL_DEBUG2( "current item is the first of its node,"
 652                            "looking for uncle from %s",
 653                            p_parent->p_input->psz_name );
 654                 if( p_parent == p_root )
 655                 {
 656                     PL_DEBUG2( "already at root" );
 657                     return NULL;
 658                 }
 659                 return GetPrevUncle( p_playlist, p_item, p_root );
 660             }
 661             else
 662             {
 663                 return p_parent->pp_children[i-1];
 664             }
 665         }
 666     }
 667     return NULL;
 668 }