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, 0, -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, "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  * Search a child of a node by its name
 244  *
 245  * \param p_node the node
 246  * \param psz_search the name of the child to search
 247  * \return the child item or NULL if not found or error
 248  */
 249 playlist_item_t *playlist_ChildSearchName( playlist_item_t *p_node,
 250                                            const char *psz_search )
 251 {
 252     playlist_t * p_playlist = p_node->p_playlist; /* For assert_locked */
 253     PL_ASSERT_LOCKED;
 254     int i;
 255
 256     if( p_node->i_children < 0 )
 257     {
 258          return NULL;
 259     }
 260     for( i = 0 ; i< p_node->i_children; i++ )
 261     {
 262         if( !strcmp( p_node->pp_children[i]->p_input->psz_name, psz_search ) )
 263         {
 264             return p_node->pp_children[i];
 265         }
 266     }
 267     return NULL;
 268 }
 269
 270 /**
 271  * Create a pair of nodes in the category and onelevel trees.
 272  * They share the same input item.
 273  * \param p_playlist the playlist
 274  * \param psz_name the name of the nodes
 275  * \param pp_node_cat pointer to return the node in category tree
 276  * \param pp_node_one pointer to return the node in onelevel tree
 277  * \param b_for_sd For Services Discovery ? (make node read-only and unskipping)
 278  */
 279 void playlist_NodesPairCreate( playlist_t *p_playlist, const char *psz_name,
 280                                playlist_item_t **pp_node_cat,
 281                                playlist_item_t **pp_node_one,
 282                                bool b_for_sd )
 283 {
 284     PL_ASSERT_LOCKED;
 285     *pp_node_cat = playlist_NodeCreate( p_playlist, psz_name,
 286                                         p_playlist->p_root_category, 0, NULL );
 287     *pp_node_one = playlist_NodeCreate( p_playlist, psz_name,
 288                                         p_playlist->p_root_onelevel, 0,
 289                                         (*pp_node_cat)->p_input );
 290     if( b_for_sd )
 291     {
 292         (*pp_node_cat)->i_flags |= PLAYLIST_RO_FLAG;
 293         (*pp_node_cat)->i_flags |= PLAYLIST_SKIP_FLAG;
 294         (*pp_node_one)->i_flags |= PLAYLIST_RO_FLAG;
 295         (*pp_node_one)->i_flags |= PLAYLIST_SKIP_FLAG;
 296     }
 297 }
 298
 299 /**
 300  * Get the node in the preferred tree from a node in one of category
 301  * or onelevel tree.
 302  */
 303 playlist_item_t * playlist_GetPreferredNode( playlist_t *p_playlist,
 304                                              playlist_item_t *p_node )
 305 {
 306     PL_ASSERT_LOCKED;
 307     int i;
 308     if( p_node->p_parent == p_playlist->p_root_category )
 309     {
 310         if( pl_priv(p_playlist)->b_tree || p_node->p_input->b_prefers_tree )
 311             return p_node;
 312         for( i = 0 ; i< p_playlist->p_root_onelevel->i_children; i++ )
 313         {
 314             if( p_playlist->p_root_onelevel->pp_children[i]->p_input ==
 315                     p_node->p_input )
 316                 return p_playlist->p_root_onelevel->pp_children[i];
 317         }
 318     }
 319     else if( p_node->p_parent == p_playlist->p_root_onelevel )
 320     {
 321         if( !pl_priv(p_playlist)->b_tree || !p_node->p_input->b_prefers_tree )
 322             return p_node;
 323         for( i = 0 ; i< p_playlist->p_root_category->i_children; i++ )
 324         {
 325             if( p_playlist->p_root_category->pp_children[i]->p_input ==
 326                     p_node->p_input )
 327                 return p_playlist->p_root_category->pp_children[i];
 328         }
 329     }
 330     return NULL;
 331 }
 332
 333 /**********************************************************************
 334  * Tree walking functions
 335  **********************************************************************/
 336
 337 playlist_item_t *playlist_GetLastLeaf(playlist_t *p_playlist,
 338                                       playlist_item_t *p_root )
 339 {
 340     PL_ASSERT_LOCKED;
 341     int i;
 342     playlist_item_t *p_item;
 343     for ( i = p_root->i_children - 1; i >= 0; i-- )
 344     {
 345         if( p_root->pp_children[i]->i_children == -1 )
 346             return p_root->pp_children[i];
 347         else if( p_root->pp_children[i]->i_children > 0)
 348         {
 349              p_item = playlist_GetLastLeaf( p_playlist,
 350                                             p_root->pp_children[i] );
 351             if ( p_item != NULL )
 352                 return p_item;
 353         }
 354         else if( i == 0 )
 355             return NULL;
 356     }
 357     return NULL;
 358 }
 359
 360 /**
 361  * Finds the next item to play
 362  *
 363  * \param p_playlist the playlist
 364  * \param p_root the root node
 365  * \param p_item the previous item  (NULL if none )
 366  * \return the next item to play, or NULL if none found
 367  */
 368 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
 369                                        playlist_item_t *p_root,
 370                                        playlist_item_t *p_item,
 371                                        bool b_ena, bool b_unplayed )
 372 {
 373     PL_ASSERT_LOCKED;
 374     playlist_item_t *p_next;
 375
 376     assert( p_root && p_root->i_children != -1 );
 377
 378     PL_DEBUG2( "finding next of %s within %s",
 379                PLI_NAME( p_item ), PLI_NAME( p_root ) );
 380
 381     /* Now, walk the tree until we find a suitable next item */
 382     p_next = p_item;
 383     while( 1 )
 384     {
 385         bool b_ena_ok = true, b_unplayed_ok = true;
 386         p_next = GetNextItem( p_playlist, p_root, p_next );
 387         if( !p_next || p_next == p_root )
 388             break;
 389         if( p_next->i_children == -1 )
 390         {
 391             if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
 392                 b_ena_ok = false;
 393             if( b_unplayed && p_next->p_input->i_nb_played != 0 )
 394                 b_unplayed_ok = false;
 395             if( b_ena_ok && b_unplayed_ok ) break;
 396         }
 397     }
 398     if( p_next == NULL ) PL_DEBUG2( "at end of node" );
 399     return p_next;
 400 }
 401
 402 /**
 403  * Finds the previous item to play
 404  *
 405  * \param p_playlist the playlist
 406  * \param p_root the root node
 407  * \param p_item the previous item  (NULL if none )
 408  * \return the next item to play, or NULL if none found
 409  */
 410 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
 411                                        playlist_item_t *p_root,
 412                                        playlist_item_t *p_item,
 413                                        bool b_ena, bool b_unplayed )
 414 {
 415     PL_ASSERT_LOCKED;
 416     playlist_item_t *p_prev;
 417
 418     PL_DEBUG2( "finding previous os %s within %s", PLI_NAME( p_item ),
 419                                                    PLI_NAME( p_root ) );
 420     assert( p_root && p_root->i_children != -1 );
 421
 422     /* Now, walk the tree until we find a suitable previous item */
 423     p_prev = p_item;
 424     while( 1 )
 425     {
 426         bool b_ena_ok = true, b_unplayed_ok = true;
 427         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
 428         if( !p_prev || p_prev == p_root )
 429             break;
 430         if( p_prev->i_children == -1 )
 431         {
 432             if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
 433                 b_ena_ok = false;
 434             if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
 435                 b_unplayed_ok = false;
 436             if( b_ena_ok && b_unplayed_ok ) break;
 437         }
 438     }
 439     if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
 440     return p_prev;
 441 }
 442
 443 /************************************************************************
 444  * Following functions are local
 445  ***********************************************************************/
 446
 447 /**
 448  * Get the next item in the tree
 449  * If p_item is NULL, return the first child of root
 450  **/
 451 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 452                               playlist_item_t *p_root,
 453                               playlist_item_t *p_item )
 454 {
 455     /* If the item is NULL, return the firt child of root */
 456     if( p_item == NULL )
 457     {
 458         if( p_root->i_children > 0 )
 459             return p_root->pp_children[0];
 460         else
 461             return NULL;
 462     }
 463
 464     /* Node with children, get the first one */
 465     if( p_item->i_children > 0 )
 466         return p_item->pp_children[0];
 467
 468     playlist_item_t* p_parent = p_item->p_parent;
 469     for( int i = 0 ; i < p_parent->i_children ; i++ )
 470     {
 471         if( p_parent->pp_children[i] == p_item )
 472         {
 473             // Return the next children
 474             if( i + 1 < p_parent->i_children )
 475                 return p_parent->pp_children[i+1];
 476             // We are the least one, so try to have uncles
 477             else
 478             {
 479                 PL_DEBUG2( "Current item is the last of the node,"
 480                            "looking for uncle from %s",
 481                             p_parent->p_input->psz_name );
 482                 if( p_parent == p_root )
 483                 {
 484                     PL_DEBUG2( "already at root" );
 485                     return NULL;
 486                 }
 487                 else
 488                     return GetNextUncle( p_playlist, p_item, p_root );
 489             }
 490         }
 491     }
 492     return NULL;
 493 }
 494
 495 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 496                                playlist_item_t *p_root )
 497 {
 498     playlist_item_t *p_parent = p_item->p_parent;
 499     playlist_item_t *p_grandparent;
 500     bool b_found = false;
 501
 502     (void)p_playlist;
 503
 504     if( p_parent != NULL )
 505     {
 506         p_grandparent = p_parent->p_parent;
 507         while( p_grandparent )
 508         {
 509             int i;
 510             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 511             {
 512                 if( p_parent == p_grandparent->pp_children[i] )
 513                 {
 514                     PL_DEBUG2( "parent %s found as child %i of grandparent %s",
 515                                p_parent->p_input->psz_name, i,
 516                                p_grandparent->p_input->psz_name );
 517                     b_found = true;
 518                     break;
 519                 }
 520             }
 521             if( b_found && i + 1 < p_grandparent->i_children )
 522             {
 523                     return p_grandparent->pp_children[i+1];
 524             }
 525             /* Not found at root */
 526             if( p_grandparent == p_root )
 527             {
 528                 return NULL;
 529             }
 530             else
 531             {
 532                 p_parent = p_grandparent;
 533                 p_grandparent = p_parent->p_parent;
 534             }
 535         }
 536     }
 537     /* We reached root */
 538     return NULL;
 539 }
 540
 541 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 542                                playlist_item_t *p_root )
 543 {
 544     playlist_item_t *p_parent = p_item->p_parent;
 545     playlist_item_t *p_grandparent;
 546     bool b_found = false;
 547
 548     (void)p_playlist;
 549
 550     if( p_parent != NULL )
 551     {
 552         p_grandparent = p_parent->p_parent;
 553         while( 1 )
 554         {
 555             int i;
 556             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
 557             {
 558                 if( p_parent == p_grandparent->pp_children[i] )
 559                 {
 560                     b_found = true;
 561                     break;
 562                 }
 563             }
 564             if( b_found && i - 1 > 0 )
 565             {
 566                 return p_grandparent->pp_children[i-1];
 567             }
 568             /* Not found at root */
 569             if( p_grandparent == p_root )
 570             {
 571                 return NULL;
 572             }
 573             else
 574             {
 575                 p_parent = p_grandparent;
 576                 p_grandparent = p_parent->p_parent;
 577             }
 578         }
 579     }
 580     /* We reached root */
 581     return NULL;
 582 }
 583
 584
 585 /* Recursively search the tree for previous item */
 586 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
 587                               playlist_item_t *p_root,
 588                               playlist_item_t *p_item )
 589 {
 590     playlist_item_t *p_parent;
 591     int i;
 592
 593     /* Node with children, get the last one */
 594     if( p_item && p_item->i_children > 0 )
 595         return p_item->pp_children[p_item->i_children - 1];
 596
 597     /* Last child of its parent ? */
 598     if( p_item != NULL )
 599         p_parent = p_item->p_parent;
 600     else
 601     {
 602         msg_Err( p_playlist, "Get the last one" );
 603         abort();
 604     };
 605
 606     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
 607     {
 608         if( p_parent->pp_children[i] == p_item )
 609         {
 610             if( i-1 < 0 )
 611             {
 612                /* Was already the first sibling. Look for uncles */
 613                 PL_DEBUG2( "current item is the first of its node,"
 614                            "looking for uncle from %s",
 615                            p_parent->p_input->psz_name );
 616                 if( p_parent == p_root )
 617                 {
 618                     PL_DEBUG2( "already at root" );
 619                     return NULL;
 620                 }
 621                 return GetPrevUncle( p_playlist, p_item, p_root );
 622             }
 623             else
 624             {
 625                 return p_parent->pp_children[i-1];
 626             }
 627         }
 628     }
 629     return NULL;
 630 }