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