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