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_item_NewWithType( 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     PL_ASSERT_LOCKED;
 283     int i;
 284
 285     if( p_node->i_children < 0 )
 286     {
 287          return NULL;
 288     }
 289     for( i = 0 ; i< p_node->i_children; i++ )
 290     {
 291         if( !strcmp( p_node->pp_children[i]->p_input->psz_name, psz_search ) )
 292         {
 293             return p_node->pp_children[i];
 294         }
 295     }
 296     return NULL;
 297 }
 298
 299 /**
 300  * Create a pair of nodes in the category and onelevel trees.
 301  * They share the same input item.
 302  * \param p_playlist the playlist
 303  * \param psz_name the name of the nodes
 304  * \param pp_node_cat pointer to return the node in category tree
 305  * \param pp_node_one pointer to return the node in onelevel tree
 306  * \param b_for_sd For Services Discovery ? (make node read-only and unskipping)
 307  */
 308 void playlist_NodesPairCreate( playlist_t *p_playlist, const char *psz_name,
 309                                playlist_item_t **pp_node_cat,
 310                                playlist_item_t **pp_node_one,
 311                                bool b_for_sd )
 312 {
 313     PL_ASSERT_LOCKED;
 314     *pp_node_cat = playlist_NodeCreate( p_playlist, psz_name,
 315                                         p_playlist->p_root_category, 0, NULL );
 316     *pp_node_one = playlist_NodeCreate( p_playlist, psz_name,
 317                                         p_playlist->p_root_onelevel, 0,
 318                                         (*pp_node_cat)->p_input );
 319     if( b_for_sd )
 320     {
 321         (*pp_node_cat)->i_flags |= PLAYLIST_RO_FLAG;
 322         (*pp_node_cat)->i_flags |= PLAYLIST_SKIP_FLAG;
 323         (*pp_node_one)->i_flags |= PLAYLIST_RO_FLAG;
 324         (*pp_node_one)->i_flags |= PLAYLIST_SKIP_FLAG;
 325     }
 326 }
 327
 328 /**
 329  * Get the node in the preferred tree from a node in one of category
 330  * or onelevel tree.
 331  */
 332 playlist_item_t * playlist_GetPreferredNode( playlist_t *p_playlist,
 333                                              playlist_item_t *p_node )
 334 {
 335     PL_ASSERT_LOCKED;
 336     int i;
 337     if( p_node->p_parent == p_playlist->p_root_category )
 338     {
 339         if( p_playlist->b_tree || p_node->p_input->b_prefers_tree )
 340             return p_node;
 341         for( i = 0 ; i< p_playlist->p_root_onelevel->i_children; i++ )
 342         {
 343             if( p_playlist->p_root_onelevel->pp_children[i]->p_input->i_id ==
 344                     p_node->p_input->i_id )
 345                 return p_playlist->p_root_onelevel->pp_children[i];
 346         }
 347     }
 348     else if( p_node->p_parent == p_playlist->p_root_onelevel )
 349     {
 350         if( !p_playlist->b_tree || !p_node->p_input->b_prefers_tree )
 351             return p_node;
 352         for( i = 0 ; i< p_playlist->p_root_category->i_children; i++ )
 353         {
 354             if( p_playlist->p_root_category->pp_children[i]->p_input->i_id ==
 355                     p_node->p_input->i_id )
 356                 return p_playlist->p_root_category->pp_children[i];
 357         }
 358     }
 359     return NULL;
 360 }
 361
 362 /**********************************************************************
 363  * Tree walking functions
 364  **********************************************************************/
 365
 366 playlist_item_t *playlist_GetLastLeaf(playlist_t *p_playlist,
 367                                       playlist_item_t *p_root )
 368 {
 369     PL_ASSERT_LOCKED;
 370     int i;
 371     playlist_item_t *p_item;
 372     for ( i = p_root->i_children - 1; i >= 0; i-- )
 373     {
 374         if( p_root->pp_children[i]->i_children == -1 )
 375             return p_root->pp_children[i];
 376         else if( p_root->pp_children[i]->i_children > 0)
 377         {
 378              p_item = playlist_GetLastLeaf( p_playlist,
 379                                             p_root->pp_children[i] );
 380             if ( p_item != NULL )
 381                 return p_item;
 382         }
 383         else if( i == 0 )
 384             return NULL;
 385     }
 386     return NULL;
 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                                        bool b_ena, bool b_unplayed )
 401 {
 402     PL_ASSERT_LOCKED;
 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         bool b_ena_ok = true, b_unplayed_ok = 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 = false;
 422             if( b_unplayed && p_next->p_input->i_nb_played != 0 )
 423                 b_unplayed_ok = 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                                        bool b_ena, bool b_unplayed )
 443 {
 444     PL_ASSERT_LOCKED;
 445     playlist_item_t *p_prev;
 446
 447     PL_DEBUG2( "finding previous os %s within %s", PLI_NAME( p_item ),
 448                                                    PLI_NAME( p_root ) );
 449     assert( p_root && p_root->i_children != -1 );
 450
 451     /* Now, walk the tree until we find a suitable previous item */
 452     p_prev = p_item;
 453     while( 1 )
 454     {
 455         bool b_ena_ok = true, b_unplayed_ok = true;
 456         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
 457         if( !p_prev || p_prev == p_root )
 458             break;
 459         if( p_prev->i_children == -1 )
 460         {
 461             if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
 462                 b_ena_ok = false;
 463             if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
 464                 b_unplayed_ok = false;
 465             if( b_ena_ok && b_unplayed_ok ) break;
 466         }
 467     }
 468     if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
 469     return p_prev;
 470 }
 471
 472 /************************************************************************
 473  * Following functions are local
 474  ***********************************************************************/
 475
 476 /**
 477  * Get the next item in the tree
 478  * If p_item is NULL, return the first child of root
 479  **/
 480 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 481                               playlist_item_t *p_root,
 482                               playlist_item_t *p_item )
 483 {
 484     playlist_item_t *p_parent;
 485     int i;
 486
 487     /* Node with children, get the first one */
 488     if( p_item && p_item->i_children > 0 )
 489         return p_item->pp_children[0];
 490
 491     if( p_item != NULL )
 492         p_parent = p_item->p_parent;
 493     else
 494         p_parent = p_root;
 495     for( i= 0 ; i < p_parent->i_children ; i++ )
 496     {
 497         if( p_item == NULL || p_parent->pp_children[i] == p_item )
 498         {
 499             if( p_item == NULL )
 500                 i = -1;
 501
 502             if( i+1 >= p_parent->i_children )
 503             {
 504                 /* Was already the last sibling. Look for uncles */
 505                 PL_DEBUG2( "Current item is the last of the node,"
 506                            "looking for uncle from %s",
 507                             p_parent->p_input->psz_name );
 508
 509                 if( p_parent == p_root )
 510                 {
 511                     PL_DEBUG2( "already at root" );
 512                     return NULL;
 513                 }
 514                 return GetNextUncle( p_playlist, p_item, p_root );
 515             }
 516             else
 517             {
 518                 return  p_parent->pp_children[i+1];
 519             }
 520         }
 521     }
 522     return NULL;
 523 }
 524
 525 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 526                                playlist_item_t *p_root )
 527 {
 528     playlist_item_t *p_parent = p_item->p_parent;
 529     playlist_item_t *p_grandparent;
 530     bool b_found = false;
 531
 532     (void)p_playlist;
 533
 534     if( p_parent != NULL )
 535     {
 536         p_grandparent = p_parent->p_parent;
 537         while( p_grandparent )
 538         {
 539             int i;
 540             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 541             {
 542                 if( p_parent == p_grandparent->pp_children[i] )
 543                 {
 544                     PL_DEBUG2( "parent %s found as child %i of grandparent %s",
 545                                p_parent->p_input->psz_name, i,
 546                                p_grandparent->p_input->psz_name );
 547                     b_found = true;
 548                     break;
 549                 }
 550             }
 551             if( b_found && i + 1 < p_grandparent->i_children )
 552             {
 553                     return p_grandparent->pp_children[i+1];
 554             }
 555             /* Not found at root */
 556             if( p_grandparent == p_root )
 557             {
 558                 return NULL;
 559             }
 560             else
 561             {
 562                 p_parent = p_grandparent;
 563                 p_grandparent = p_parent->p_parent;
 564             }
 565         }
 566     }
 567     /* We reached root */
 568     return NULL;
 569 }
 570
 571 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 572                                playlist_item_t *p_root )
 573 {
 574     playlist_item_t *p_parent = p_item->p_parent;
 575     playlist_item_t *p_grandparent;
 576     bool b_found = false;
 577
 578     (void)p_playlist;
 579
 580     if( p_parent != NULL )
 581     {
 582         p_grandparent = p_parent->p_parent;
 583         while( 1 )
 584         {
 585             int i;
 586             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
 587             {
 588                 if( p_parent == p_grandparent->pp_children[i] )
 589                 {
 590                     b_found = true;
 591                     break;
 592                 }
 593             }
 594             if( b_found && i - 1 > 0 )
 595             {
 596                 return p_grandparent->pp_children[i-1];
 597             }
 598             /* Not found at root */
 599             if( p_grandparent == p_root )
 600             {
 601                 return NULL;
 602             }
 603             else
 604             {
 605                 p_parent = p_grandparent;
 606                 p_grandparent = p_parent->p_parent;
 607             }
 608         }
 609     }
 610     /* We reached root */
 611     return NULL;
 612 }
 613
 614
 615 /* Recursively search the tree for previous item */
 616 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
 617                               playlist_item_t *p_root,
 618                               playlist_item_t *p_item )
 619 {
 620     playlist_item_t *p_parent;
 621     int i;
 622
 623     /* Node with children, get the last one */
 624     if( p_item && p_item->i_children > 0 )
 625         return p_item->pp_children[p_item->i_children - 1];
 626
 627     /* Last child of its parent ? */
 628     if( p_item != NULL )
 629         p_parent = p_item->p_parent;
 630     else
 631     {
 632         msg_Err( p_playlist, "Get the last one" );
 633         abort();
 634     };
 635
 636     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
 637     {
 638         if( p_parent->pp_children[i] == p_item )
 639         {
 640             if( i-1 < 0 )
 641             {
 642                /* Was already the first sibling. Look for uncles */
 643                 PL_DEBUG2( "current item is the first of its node,"
 644                            "looking for uncle from %s",
 645                            p_parent->p_input->psz_name );
 646                 if( p_parent == p_root )
 647                 {
 648                     PL_DEBUG2( "already at root" );
 649                     return NULL;
 650                 }
 651                 return GetPrevUncle( p_playlist, p_item, p_root );
 652             }
 653             else
 654             {
 655                 return p_parent->pp_children[i-1];
 656             }
 657         }
 658     }
 659     return NULL;
 660 }