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

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