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