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