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