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