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