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

   1 /*****************************************************************************
   2  * tree.c : Playlist tree walking functions
   3  *****************************************************************************
   4  * Copyright (C) 1999-2004 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 #include <vlc/vlc.h>
  24 #include <assert.h>
  25 #include <vlc/input.h>
  26 #include "vlc_playlist.h"
  27
  28 /************************************************************************
  29  * Local prototypes
  30  ************************************************************************/
  31 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
  32                                playlist_item_t *p_root );
  33 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
  34                                playlist_item_t *p_root );
  35
  36 playlist_item_t *GetNextItem( playlist_t *p_playlist,
  37                               playlist_item_t *p_root,
  38                               playlist_item_t *p_item );
  39 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
  40                               playlist_item_t *p_item,
  41                               playlist_item_t *p_root );
  42
  43 /**
  44  * Create a playlist node
  45  *
  46  * \param p_playlist the playlist
  47  * \paam psz_name the name of the node
  48  * \param p_parent the parent node to attach to or NULL if no attach
  49  * \return the new node
  50  */
  51 playlist_item_t * playlist_NodeCreate( playlist_t *p_playlist, char *psz_name,
  52                                        playlist_item_t *p_parent )
  53 {
  54     input_item_t *p_input;
  55     playlist_item_t *p_item;
  56
  57     if( !psz_name ) psz_name = _("Undefined");
  58     p_input = input_ItemNewWithType( VLC_OBJECT(p_playlist), NULL, psz_name,
  59                                      0, NULL, -1, ITEM_TYPE_NODE );
  60     p_input->i_id = ++p_playlist->i_last_input_id;
  61     p_item = playlist_ItemNewFromInput( VLC_OBJECT(p_playlist), p_input );
  62     p_item->i_children = 0;
  63
  64     if( p_item == NULL )
  65     {
  66         return NULL;
  67     }
  68     INSERT_ELEM( p_playlist->pp_all_items,
  69                  p_playlist->i_all_size,
  70                  p_playlist->i_all_size,
  71                  p_item );
  72
  73     if( p_parent != NULL )
  74     {
  75         playlist_NodeAppend( p_playlist, p_item, p_parent );
  76     }
  77
  78     playlist_SendAddNotify( p_playlist, p_item->i_id,
  79                             p_parent ? p_parent->i_id : -1 );
  80     return p_item;
  81 }
  82
  83 /**
  84  * Remove all the children of a node
  85  *
  86  * This function must be entered with the playlist lock
  87  *
  88  * \param p_playlist the playlist
  89  * \param p_root the node
  90  * \param b_delete_items do we have to delete the children items ?
  91  * \return VLC_SUCCESS or an error
  92  */
  93 int playlist_NodeEmpty( playlist_t *p_playlist, playlist_item_t *p_root,
  94                         vlc_bool_t b_delete_items )
  95 {
  96     int i;
  97     if( p_root->i_children == -1 )
  98     {
  99         return VLC_EGENERIC;
 100     }
 101
 102     /* Delete the children */
 103     for( i =  p_root->i_children-1 ; i >= 0 ;i-- )
 104     {
 105         if( p_root->pp_children[i]->i_children > -1 )
 106         {
 107             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
 108                                  b_delete_items , VLC_FALSE );
 109         }
 110         else if( b_delete_items )
 111         {
 112             /* Delete the item here */
 113             playlist_DeleteFromItemId( p_playlist,
 114                                        p_root->pp_children[i]->i_id );
 115         }
 116     }
 117     return VLC_SUCCESS;
 118 }
 119
 120 /**
 121  * Remove all the children of a node and removes the node
 122  *
 123  * \param p_playlist the playlist
 124  * \param p_root the node
 125  * \param b_delete_items do we have to delete the children items ?
 126  * \return VLC_SUCCESS or an error
 127  */
 128 int playlist_NodeDelete( playlist_t *p_playlist, playlist_item_t *p_root,
 129                          vlc_bool_t b_delete_items, vlc_bool_t b_force )
 130 {
 131     int i;
 132
 133     if( p_root->i_children == -1 )
 134     {
 135         return VLC_EGENERIC;
 136     }
 137
 138     /* Delete the children */
 139     for( i =  p_root->i_children - 1 ; i >= 0; i-- )
 140     {
 141         if( p_root->pp_children[i]->i_children > -1 )
 142         {
 143             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
 144                                  b_delete_items , b_force );
 145         }
 146         else if( b_delete_items )
 147         {
 148             playlist_DeleteFromItemId( p_playlist,
 149                                        p_root->pp_children[i]->i_id );
 150         }
 151     }
 152     /* Delete the node */
 153     if( p_root->i_flags & PLAYLIST_RO_FLAG && !b_force )
 154     {
 155     }
 156     else
 157     {
 158         var_SetInteger( p_playlist, "item-deleted", p_root->p_input->i_id );
 159         for( i = 0 ; i< p_playlist->i_all_size; i ++ )
 160         {
 161             if( p_playlist->pp_all_items[i]->p_input->i_id ==
 162                                p_root->p_input->i_id )
 163             {
 164                 REMOVE_ELEM( p_playlist->pp_all_items, p_playlist->i_all_size,
 165                              i );
 166                 break;
 167             }
 168         }
 169
 170         /* Remove the item from its parent */
 171         if( p_root->p_parent )
 172         {
 173             playlist_NodeRemoveItem( p_playlist, p_root, p_root->p_parent );
 174         }
 175
 176         playlist_ItemDelete( 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    assert( p_parent && p_parent->i_children != -1 );
 203    if( i_position == -1 ) i_position = p_parent->i_children ;
 204
 205    INSERT_ELEM( p_parent->pp_children,
 206                 p_parent->i_children,
 207                 i_position,
 208                 p_item );
 209    p_item->p_parent = p_parent;
 210    return VLC_SUCCESS;
 211 }
 212
 213 /**
 214  * Deletes an item from the children of a node
 215  *
 216  * \param p_playlist the playlist
 217  * \param p_item the item to remove
 218  * \param p_parent the parent node
 219  * \return VLC_SUCCESS or an error
 220  */
 221 int playlist_NodeRemoveItem( playlist_t *p_playlist,
 222                         playlist_item_t *p_item,
 223                         playlist_item_t *p_parent )
 224 {
 225    int i;
 226    for( i= 0; i< p_parent->i_children ; i++ )
 227    {
 228        if( p_parent->pp_children[i] == p_item )
 229        {
 230            REMOVE_ELEM( p_parent->pp_children, p_parent->i_children, i );
 231        }
 232    }
 233
 234    return VLC_SUCCESS;
 235 }
 236
 237
 238 /**
 239  * Count the children of a node
 240  *
 241  * \param p_playlist the playlist
 242  * \param p_node the node
 243  * \return the number of children
 244  */
 245 int playlist_NodeChildrenCount( playlist_t *p_playlist, playlist_item_t*p_node)
 246 {
 247     int i;
 248     int i_nb = 0;
 249     if( p_node->i_children == -1 )
 250         return 0;
 251
 252     for( i=0 ; i< p_node->i_children;i++ )
 253     {
 254         if( p_node->pp_children[i]->i_children == -1 )
 255             i_nb++;
 256         else
 257             i_nb += playlist_NodeChildrenCount( p_playlist,
 258                                                 p_node->pp_children[i] );
 259     }
 260     return i_nb;
 261 }
 262
 263 /**
 264  * Search a child of a node by its name
 265  *
 266  * \param p_node the node
 267  * \param psz_search the name of the child to search
 268  * \return the child item or NULL if not found or error
 269  */
 270 playlist_item_t *playlist_ChildSearchName( playlist_item_t *p_node,
 271                                            const char *psz_search )
 272 {
 273     int i;
 274
 275     if( p_node->i_children < 0 )
 276     {
 277          return NULL;
 278     }
 279     for( i = 0 ; i< p_node->i_children; i++ )
 280     {
 281         if( !strcmp( p_node->pp_children[i]->p_input->psz_name, psz_search ) )
 282         {
 283             return p_node->pp_children[i];
 284         }
 285     }
 286     return NULL;
 287 }
 288
 289
 290 void playlist_NodesCreateForSD( playlist_t *p_playlist, char *psz_name,
 291                                 playlist_item_t **pp_node_cat,
 292                                 playlist_item_t **pp_node_one )
 293 {
 294     *pp_node_cat = playlist_NodeCreate( p_playlist, psz_name,
 295                                         p_playlist->p_root_category );
 296     (*pp_node_cat)->i_flags |= PLAYLIST_RO_FLAG;
 297     (*pp_node_cat)->i_flags |= PLAYLIST_SKIP_FLAG;
 298
 299     *pp_node_one = playlist_NodeCreate( p_playlist, psz_name,
 300                                         p_playlist->p_root_onelevel );
 301     (*pp_node_one)->i_flags |= PLAYLIST_RO_FLAG;
 302     (*pp_node_one)->i_flags |= PLAYLIST_SKIP_FLAG;
 303
 304     (*pp_node_one)->p_input->i_id = (*pp_node_cat)->p_input->i_id;
 305 }
 306
 307 playlist_item_t * playlist_GetPreferredNode( playlist_t *p_playlist,
 308                                              playlist_item_t *p_node )
 309 {
 310     int i;
 311     if( p_node->p_parent == p_playlist->p_root_category )
 312     {
 313         if( p_playlist->b_always_tree ||
 314             p_node->p_input->b_prefers_tree ) return p_node;
 315         for( i = 0 ; i< p_playlist->p_root_onelevel->i_children; i++ )
 316         {
 317             if( p_playlist->p_root_onelevel->pp_children[i]->p_input->i_id ==
 318                     p_node->p_input->i_id )
 319                 return p_playlist->p_root_onelevel->pp_children[i];
 320         }
 321     }
 322     else if( p_node->p_parent == p_playlist->p_root_onelevel )
 323     {
 324         if( p_playlist->b_never_tree || !p_node->p_input->b_prefers_tree )
 325             return p_node;
 326         for( i = 0 ; i< p_playlist->p_root_category->i_children; i++ )
 327         {
 328             if( p_playlist->p_root_category->pp_children[i]->p_input->i_id ==
 329                     p_node->p_input->i_id )
 330                 return p_playlist->p_root_category->pp_children[i];
 331         }
 332     }
 333     return NULL;
 334 }
 335
 336 /**********************************************************************
 337  * Tree walking functions
 338  **********************************************************************/
 339
 340 playlist_item_t *playlist_GetLastLeaf(playlist_t *p_playlist,
 341                                       playlist_item_t *p_root )
 342 {
 343     int i;
 344     playlist_item_t *p_item;
 345     for ( i = p_root->i_children - 1; i >= 0; i-- )
 346     {
 347         if( p_root->pp_children[i]->i_children == -1 )
 348             return p_root->pp_children[i];
 349         else if( p_root->pp_children[i]->i_children > 0)
 350         {
 351              p_item = playlist_GetLastLeaf( p_playlist,
 352                                             p_root->pp_children[i] );
 353             if ( p_item != NULL )
 354                 return p_item;
 355         }
 356         else if( i == 0 )
 357             return NULL;
 358     }
 359     return NULL;
 360 }
 361
 362 int playlist_GetAllEnabledChildren( playlist_t *p_playlist,
 363                                     playlist_item_t *p_node,
 364                                     playlist_item_t ***ppp_items )
 365 {
 366     int i_count = 0;
 367     playlist_item_t *p_next = NULL;
 368     while( 1 )
 369     {
 370         p_next = playlist_GetNextLeaf( p_playlist, p_node,
 371                                        p_next, VLC_TRUE, VLC_TRUE );
 372         if( p_next )
 373             INSERT_ELEM( *ppp_items, i_count, i_count, p_next );
 374         else
 375             break;
 376     }
 377     return i_count;
 378 }
 379
 380 /**
 381  * Finds the next item to play
 382  *
 383  * \param p_playlist the playlist
 384  * \param p_root the root node
 385  * \param p_item the previous item  (NULL if none )
 386  * \return the next item to play, or NULL if none found
 387  */
 388 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
 389                                        playlist_item_t *p_root,
 390                                        playlist_item_t *p_item,
 391                                        vlc_bool_t b_ena, vlc_bool_t b_unplayed )
 392 {
 393     playlist_item_t *p_next;
 394
 395     assert( p_root && p_root->i_children != -1 );
 396
 397 #ifdef PLAYLIST_DEBUG
 398     if( p_item != NULL )
 399         msg_Dbg( p_playlist, "finding next of %s within %s",
 400                         p_item->p_input->psz_name,  p_root->p_input->psz_name );
 401     else
 402         msg_Dbg( p_playlist, "finding something to play within %s",
 403                          p_root->p_input->psz_name );
 404 #endif
 405
 406     /* Now, walk the tree until we find a suitable next item */
 407     p_next = p_item;
 408     while( 1 )
 409     {
 410         vlc_bool_t b_ena_ok = VLC_TRUE, b_unplayed_ok = VLC_TRUE;
 411         p_next = GetNextItem( p_playlist, p_root, p_next );
 412         if( !p_next || p_next == p_root )
 413             break;
 414         if( p_next->i_children == -1 )
 415         {
 416             if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
 417                 b_ena_ok = VLC_FALSE;
 418             if( b_unplayed && p_next->p_input->i_nb_played != 0 )
 419                 b_unplayed_ok = VLC_FALSE;
 420             if( b_ena_ok && b_unplayed_ok ) break;
 421         }
 422     }
 423 #ifdef PLAYLIST_DEBUG
 424     if( p_next == NULL )
 425         msg_Dbg( p_playlist, "At end of node" );
 426 #endif
 427     return p_next;
 428 }
 429
 430 /**
 431  * Finds the previous item to play
 432  *
 433  * \param p_playlist the playlist
 434  * \param p_root the root node
 435  * \param p_item the previous item  (NULL if none )
 436  * \return the next item to play, or NULL if none found
 437  */
 438 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
 439                                        playlist_item_t *p_root,
 440                                        playlist_item_t *p_item,
 441                                        vlc_bool_t b_ena, vlc_bool_t b_unplayed )
 442 {
 443     playlist_item_t *p_prev;
 444
 445 #ifdef PLAYLIST_DEBUG
 446     if( p_item != NULL )
 447         msg_Dbg( p_playlist, "finding previous of %s within %s",
 448                         p_item->p_input->psz_name,  p_root->p_input->psz_name );
 449     else
 450         msg_Dbg( p_playlist, "finding previous to play within %s",
 451                          p_root->p_input->psz_name );
 452 #endif
 453     assert( p_root && p_root->i_children != -1 );
 454
 455     /* Now, walk the tree until we find a suitable previous item */
 456     p_prev = p_item;
 457     while( 1 )
 458     {
 459         vlc_bool_t b_ena_ok = VLC_TRUE, b_unplayed_ok = VLC_TRUE;
 460         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
 461         if( !p_prev || p_prev == p_root )
 462             break;
 463         if( p_prev->i_children == -1 )
 464         {
 465             if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
 466                 b_ena_ok = VLC_FALSE;
 467             if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
 468                 b_unplayed_ok = VLC_FALSE;
 469             if( b_ena_ok && b_unplayed_ok ) break;
 470         }
 471     }
 472 #ifdef PLAYLIST_DEBUG
 473     if( p_prev == NULL )
 474         msg_Dbg( p_playlist, "At beginning of node" );
 475 #endif
 476     return p_prev;
 477 }
 478
 479 /************************************************************************
 480  * Following functions are local
 481  ***********************************************************************/
 482
 483 /**
 484  * Get the next item in the tree
 485  * If p_item is NULL, return the first child of root
 486  **/
 487 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 488                               playlist_item_t *p_root,
 489                               playlist_item_t *p_item )
 490 {
 491     playlist_item_t *p_parent;
 492     int i;
 493
 494     /* Node with children, get the first one */
 495     if( p_item && p_item->i_children > 0 )
 496         return p_item->pp_children[0];
 497
 498     if( p_item != NULL )
 499         p_parent = p_item->p_parent;
 500     else
 501         p_parent = p_root;
 502
 503     for( i= 0 ; i < p_parent->i_children ; i++ )
 504     {
 505         if( p_item == NULL || p_parent->pp_children[i] == p_item )
 506         {
 507             if( p_item == NULL )
 508                 i = -1;
 509
 510             if( i+1 >= p_parent->i_children )
 511             {
 512                 /* Was already the last sibling. Look for uncles */
 513                 PL_DEBUG( "Current item is the last of the node,"
 514                           "looking for uncle from %s",
 515                            p_parent->p_input->psz_name );
 516
 517                 if( p_parent == p_root )
 518                 {
 519                     PL_DEBUG( "already at root" );
 520                     return NULL;
 521                 }
 522                 return GetNextUncle( p_playlist, p_item, p_root );
 523             }
 524             else
 525             {
 526                 return  p_parent->pp_children[i+1];
 527             }
 528         }
 529     }
 530     msg_Err( p_playlist, "I should not be here" );
 531     return NULL;
 532 }
 533
 534 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 535                                playlist_item_t *p_root )
 536 {
 537     playlist_item_t *p_parent = p_item->p_parent;
 538     playlist_item_t *p_grandparent;
 539     vlc_bool_t b_found = VLC_FALSE;
 540
 541     if( p_parent != NULL )
 542     {
 543         p_grandparent = p_parent->p_parent;
 544         while( 1 )
 545         {
 546             int i;
 547             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 548             {
 549                 if( p_parent == p_grandparent->pp_children[i] )
 550                 {
 551                     PL_DEBUG( "parent %s found as child %i of grandparent %s",
 552                               p_parent->p_input->psz_name, i,
 553                               p_grandparent->p_input->psz_name );
 554                     b_found = VLC_TRUE;
 555                     break;
 556                 }
 557             }
 558             if( b_found && i + 1 < p_grandparent->i_children )
 559             {
 560                     return p_grandparent->pp_children[i+1];
 561             }
 562             /* Not found at root */
 563             if( p_grandparent == p_root )
 564             {
 565                 return NULL;
 566             }
 567             else
 568             {
 569                 p_parent = p_grandparent;
 570                 p_grandparent = p_parent->p_parent;
 571             }
 572         }
 573     }
 574     /* We reached root */
 575     return NULL;
 576 }
 577
 578 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 579                                playlist_item_t *p_root )
 580 {
 581     playlist_item_t *p_parent = p_item->p_parent;
 582     playlist_item_t *p_grandparent;
 583     vlc_bool_t b_found = VLC_FALSE;
 584
 585     if( p_parent != NULL )
 586     {
 587         p_grandparent = p_parent->p_parent;
 588         while( 1 )
 589         {
 590             int i;
 591             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
 592             {
 593                 if( p_parent == p_grandparent->pp_children[i] )
 594                 {
 595                     b_found = VLC_TRUE;
 596                     break;
 597                 }
 598             }
 599             if( b_found && i - 1 > 0 )
 600             {
 601                 return p_grandparent->pp_children[i-1];
 602             }
 603             /* Not found at root */
 604             if( p_grandparent == p_root )
 605             {
 606                 return NULL;
 607             }
 608             else
 609             {
 610                 p_parent = p_grandparent;
 611                 p_grandparent = p_parent->p_parent;
 612             }
 613         }
 614     }
 615     /* We reached root */
 616     return NULL;
 617 }
 618
 619
 620 /* Recursively search the tree for previous item */
 621 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
 622                               playlist_item_t *p_root,
 623                               playlist_item_t *p_item )
 624 {
 625     playlist_item_t *p_parent;
 626     int i;
 627
 628     /* Node with children, get the last one */
 629     if( p_item && p_item->i_children > 0 )
 630         return p_item->pp_children[p_item->i_children - 1];
 631
 632     /* Last child of its parent ? */
 633     if( p_item != NULL )
 634         p_parent = p_item->p_parent;
 635     else
 636     {
 637         msg_Err( p_playlist, "Get the last one" );
 638         abort();
 639     };
 640
 641     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
 642     {
 643         if( p_parent->pp_children[i] == p_item )
 644         {
 645             if( i-1 < 0 )
 646             {
 647                 /* Was already the first sibling. Look for uncles */
 648                 PL_DEBUG( "Current item is the first of the node,"
 649                           "looking for uncle from %s",
 650                           p_parent->p_input->psz_name );
 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     msg_Err( p_playlist, "I should not be here" );
 660     return NULL;
 661 }
 662
 663 /* Dump the contents of a node */
 664 void playlist_NodeDump( playlist_t *p_playlist, playlist_item_t *p_item,
 665                         int i_level )
 666 {
 667     char str[512];
 668     int i;
 669
 670     if( i_level == 1 )
 671     {
 672         msg_Dbg( p_playlist, "%s (%i)",
 673                         p_item->p_input->psz_name, p_item->i_children );
 674     }
 675
 676     if( p_item->i_children == -1 )
 677     {
 678         return;
 679     }
 680
 681     for( i = 0; i< p_item->i_children; i++ )
 682     {
 683         memset( str, 32, 512 );
 684         sprintf( str + 2 * i_level , "%s (%i)",
 685                                 p_item->pp_children[i]->p_input->psz_name,
 686                                 p_item->pp_children[i]->i_children );
 687         msg_Dbg( p_playlist, "%s",str );
 688         if( p_item->pp_children[i]->i_children >= 0 )
 689         {
 690             playlist_NodeDump( p_playlist, p_item->pp_children[i],
 691                               i_level + 1 );
 692         }
 693     }
 694     return;
 695 }