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  * Finds the next item to play
 338  *
 339  * \param p_playlist the playlist
 340  * \param p_root the root node
 341  * \param p_item the previous item  (NULL if none )
 342  * \return the next item to play, or NULL if none found
 343  */
 344 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
 345                                        playlist_item_t *p_root,
 346                                        playlist_item_t *p_item,
 347                                        bool b_ena, bool b_unplayed )
 348 {
 349     PL_ASSERT_LOCKED;
 350     playlist_item_t *p_next;
 351
 352     assert( p_root && p_root->i_children != -1 );
 353
 354     PL_DEBUG2( "finding next of %s within %s",
 355                PLI_NAME( p_item ), PLI_NAME( p_root ) );
 356
 357     /* Now, walk the tree until we find a suitable next item */
 358     p_next = p_item;
 359     while( 1 )
 360     {
 361         bool b_ena_ok = true, b_unplayed_ok = true;
 362         p_next = GetNextItem( p_playlist, p_root, p_next );
 363         if( !p_next || p_next == p_root )
 364             break;
 365         if( p_next->i_children == -1 )
 366         {
 367             if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
 368                 b_ena_ok = false;
 369             if( b_unplayed && p_next->p_input->i_nb_played != 0 )
 370                 b_unplayed_ok = false;
 371             if( b_ena_ok && b_unplayed_ok ) break;
 372         }
 373     }
 374     if( p_next == NULL ) PL_DEBUG2( "at end of node" );
 375     return p_next;
 376 }
 377
 378 /**
 379  * Finds the previous item to play
 380  *
 381  * \param p_playlist the playlist
 382  * \param p_root the root node
 383  * \param p_item the previous item  (NULL if none )
 384  * \return the next item to play, or NULL if none found
 385  */
 386 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
 387                                        playlist_item_t *p_root,
 388                                        playlist_item_t *p_item,
 389                                        bool b_ena, bool b_unplayed )
 390 {
 391     PL_ASSERT_LOCKED;
 392     playlist_item_t *p_prev;
 393
 394     PL_DEBUG2( "finding previous of %s within %s", PLI_NAME( p_item ),
 395                                                    PLI_NAME( p_root ) );
 396     assert( p_root && p_root->i_children != -1 );
 397
 398     /* Now, walk the tree until we find a suitable previous item */
 399     p_prev = p_item;
 400     while( 1 )
 401     {
 402         bool b_ena_ok = true, b_unplayed_ok = true;
 403         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
 404         if( !p_prev || p_prev == p_root )
 405             break;
 406         if( p_prev->i_children == -1 )
 407         {
 408             if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
 409                 b_ena_ok = false;
 410             if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
 411                 b_unplayed_ok = false;
 412             if( b_ena_ok && b_unplayed_ok ) break;
 413         }
 414     }
 415     if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
 416     return p_prev;
 417 }
 418
 419 /************************************************************************
 420  * Following functions are local
 421  ***********************************************************************/
 422
 423 /**
 424  * Get the next item in the tree
 425  * If p_item is NULL, return the first child of root
 426  **/
 427 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 428                               playlist_item_t *p_root,
 429                               playlist_item_t *p_item )
 430 {
 431     /* If the item is NULL, return the firt child of root */
 432     if( p_item == NULL )
 433     {
 434         if( p_root->i_children > 0 )
 435             return p_root->pp_children[0];
 436         else
 437             return NULL;
 438     }
 439
 440     /* Node with children, get the first one */
 441     if( p_item->i_children > 0 )
 442         return p_item->pp_children[0];
 443
 444     playlist_item_t* p_parent = p_item->p_parent;
 445     for( int i = 0 ; i < p_parent->i_children ; i++ )
 446     {
 447         if( p_parent->pp_children[i] == p_item )
 448         {
 449             // Return the next children
 450             if( i + 1 < p_parent->i_children )
 451                 return p_parent->pp_children[i+1];
 452             // We are the least one, so try to have uncles
 453             else
 454             {
 455                 PL_DEBUG2( "Current item is the last of the node,"
 456                            "looking for uncle from %s",
 457                             p_parent->p_input->psz_name );
 458                 if( p_parent == p_root )
 459                 {
 460                     PL_DEBUG2( "already at root" );
 461                     return NULL;
 462                 }
 463                 else
 464                     return GetNextUncle( p_playlist, p_item, p_root );
 465             }
 466         }
 467     }
 468     return NULL;
 469 }
 470
 471 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 472                                playlist_item_t *p_root )
 473 {
 474     playlist_item_t *p_parent = p_item->p_parent;
 475     playlist_item_t *p_grandparent;
 476     bool b_found = false;
 477
 478     (void)p_playlist;
 479
 480     if( p_parent != NULL )
 481     {
 482         p_grandparent = p_parent->p_parent;
 483         while( p_grandparent )
 484         {
 485             int i;
 486             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 487             {
 488                 if( p_parent == p_grandparent->pp_children[i] )
 489                 {
 490                     PL_DEBUG2( "parent %s found as child %i of grandparent %s",
 491                                p_parent->p_input->psz_name, i,
 492                                p_grandparent->p_input->psz_name );
 493                     b_found = true;
 494                     break;
 495                 }
 496             }
 497             if( b_found && i + 1 < p_grandparent->i_children )
 498             {
 499                     return p_grandparent->pp_children[i+1];
 500             }
 501             /* Not found at root */
 502             if( p_grandparent == p_root )
 503             {
 504                 return NULL;
 505             }
 506             else
 507             {
 508                 p_parent = p_grandparent;
 509                 p_grandparent = p_parent->p_parent;
 510             }
 511         }
 512     }
 513     /* We reached root */
 514     return NULL;
 515 }
 516
 517 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 518                                playlist_item_t *p_root )
 519 {
 520     playlist_item_t *p_parent = p_item->p_parent;
 521     playlist_item_t *p_grandparent;
 522     bool b_found = false;
 523
 524     (void)p_playlist;
 525
 526     if( p_parent != NULL )
 527     {
 528         p_grandparent = p_parent->p_parent;
 529         while( 1 )
 530         {
 531             int i;
 532             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
 533             {
 534                 if( p_parent == p_grandparent->pp_children[i] )
 535                 {
 536                     b_found = true;
 537                     break;
 538                 }
 539             }
 540             if( b_found && i - 1 > 0 )
 541             {
 542                 return p_grandparent->pp_children[i-1];
 543             }
 544             /* Not found at root */
 545             if( p_grandparent == p_root )
 546             {
 547                 return NULL;
 548             }
 549             else
 550             {
 551                 p_parent = p_grandparent;
 552                 p_grandparent = p_parent->p_parent;
 553             }
 554         }
 555     }
 556     /* We reached root */
 557     return NULL;
 558 }
 559
 560
 561 /* Recursively search the tree for previous item */
 562 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
 563                               playlist_item_t *p_root,
 564                               playlist_item_t *p_item )
 565 {
 566     playlist_item_t *p_parent;
 567     int i;
 568
 569     /* Node with children, get the last one */
 570     if( p_item && p_item->i_children > 0 )
 571         return p_item->pp_children[p_item->i_children - 1];
 572
 573     /* Last child of its parent ? */
 574     if( p_item != NULL )
 575         p_parent = p_item->p_parent;
 576     else
 577     {
 578         msg_Err( p_playlist, "Get the last one" );
 579         abort();
 580     };
 581
 582     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
 583     {
 584         if( p_parent->pp_children[i] == p_item )
 585         {
 586             if( i-1 < 0 )
 587             {
 588                /* Was already the first sibling. Look for uncles */
 589                 PL_DEBUG2( "current item is the first of its node,"
 590                            "looking for uncle from %s",
 591                            p_parent->p_input->psz_name );
 592                 if( p_parent == p_root )
 593                 {
 594                     PL_DEBUG2( "already at root" );
 595                     return NULL;
 596                 }
 597                 return GetPrevUncle( p_playlist, p_item, p_root );
 598             }
 599             else
 600             {
 601                 return p_parent->pp_children[i-1];
 602             }
 603         }
 604     }
 605     return NULL;
 606 }