git.sesse.net Git - vlc/blob - src/playlist/tree.c

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