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 #ifdef PLAYLIST_DEBUG
 358     if( p_item != NULL )
 359         msg_Dbg( p_playlist, "finding next of %s within %s",
 360                         p_item->p_input->psz_name,  p_root->p_input->psz_name );
 361     else
 362         msg_Dbg( p_playlist, "finding something to play within %s",
 363                          p_root->p_input->psz_name );
 364 #endif
 365
 366     assert( p_root && p_root->i_children != -1 );
 367
 368     /* Now, walk the tree until we find a suitable next item */
 369     p_next = p_item;
 370     do
 371     {
 372         p_next = GetNextItem( p_playlist, p_root, p_next );
 373     } while ( p_next && p_next != p_root && p_next->i_children != -1 );
 374
 375 #ifdef PLAYLIST_DEBUG
 376     if( p_next == NULL )
 377         msg_Dbg( p_playlist, "At end of node" );
 378 #endif
 379     return p_next;
 380 }
 381
 382 playlist_item_t *playlist_GetNextEnabledLeaf( playlist_t *p_playlist,
 383                                               playlist_item_t *p_root,
 384                                               playlist_item_t *p_item )
 385 {
 386     playlist_item_t *p_next;
 387
 388 #ifdef PLAYLIST_DEBUG
 389     if( p_item != NULL )
 390         msg_Dbg( p_playlist, "finding next of %s within %s",
 391                         p_item->p_input->psz_name,  p_root->p_input->psz_name );
 392     else
 393         msg_Dbg( p_playlist, "finding something to play within %s",
 394                          p_root->p_input->psz_name );
 395 #endif
 396
 397     assert( p_root && p_root->i_children != -1 );
 398
 399     /* Now, walk the tree until we find a suitable next item */
 400     p_next = p_item;
 401     do
 402     {
 403         p_next = GetNextItem( p_playlist, p_root, p_next );
 404     } while ( p_next && p_next != p_root &&
 405               !( p_next->i_children == -1 &&
 406               !(p_next->i_flags & PLAYLIST_DBL_FLAG) ) );
 407
 408 #ifdef PLAYLIST_DEBUG
 409     if( p_next == NULL )
 410         msg_Dbg( p_playlist, "At end of node" );
 411 #endif
 412     return p_next;
 413 }
 414
 415 /**
 416  * Finds the previous item to play
 417  *
 418  * \param p_playlist the playlist
 419  * \param p_root the root node
 420  * \param p_item the previous item  (NULL if none )
 421  * \return the next item to play, or NULL if none found
 422  */
 423 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
 424                                        playlist_item_t *p_root,
 425                                        playlist_item_t *p_item )
 426 {
 427     playlist_item_t *p_prev;
 428
 429 #ifdef PLAYLIST_DEBUG
 430     if( p_item != NULL )
 431         msg_Dbg( p_playlist, "finding previous of %s within %s",
 432                         p_item->p_input->psz_name,  p_root->p_input->psz_name );
 433     else
 434         msg_Dbg( p_playlist, "finding previous to play within %s",
 435                          p_root->p_input->psz_name );
 436 #endif
 437     assert( p_root && p_root->i_children != -1 );
 438
 439     /* Now, walk the tree until we find a suitable previous item */
 440     p_prev = p_item;
 441     do
 442     {
 443         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
 444     } while ( p_prev && p_prev != p_root && p_prev->i_children != -1 );
 445
 446 #ifdef PLAYLIST_DEBUG
 447     if( p_prev == NULL )
 448         msg_Dbg( p_playlist, "At beginning of node" );
 449 #endif
 450     return p_prev;
 451 }
 452
 453 /************************************************************************
 454  * Following functions are local
 455  ***********************************************************************/
 456
 457 /**
 458  * Get the next item in the tree
 459  * If p_item is NULL, return the first child of root
 460  **/
 461 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 462                               playlist_item_t *p_root,
 463                               playlist_item_t *p_item )
 464 {
 465     playlist_item_t *p_parent;
 466     int i;
 467
 468     /* Node with children, get the first one */
 469     if( p_item && p_item->i_children > 0 )
 470         return p_item->pp_children[0];
 471
 472     if( p_item != NULL )
 473         p_parent = p_item->p_parent;
 474     else
 475         p_parent = p_root;
 476
 477     for( i= 0 ; i < p_parent->i_children ; i++ )
 478     {
 479         if( p_item == NULL || p_parent->pp_children[i] == p_item )
 480         {
 481             if( p_item == NULL )
 482                 i = -1;
 483
 484             if( i+1 >= p_parent->i_children )
 485             {
 486                 /* Was already the last sibling. Look for uncles */
 487                 PL_DEBUG( "Current item is the last of the node,"
 488                           "looking for uncle from %s",
 489                            p_parent->p_input->psz_name );
 490
 491                 if( p_parent == p_root )
 492                 {
 493                     PL_DEBUG( "already at root" );
 494                     return NULL;
 495                 }
 496                 return GetNextUncle( p_playlist, p_item, p_root );
 497             }
 498             else
 499             {
 500                 return  p_parent->pp_children[i+1];
 501             }
 502         }
 503     }
 504     msg_Err( p_playlist, "I should not be here" );
 505     return NULL;
 506 }
 507
 508 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 509                                playlist_item_t *p_root )
 510 {
 511     playlist_item_t *p_parent = p_item->p_parent;
 512     playlist_item_t *p_grandparent;
 513     vlc_bool_t b_found = VLC_FALSE;
 514
 515     if( p_parent != NULL )
 516     {
 517         p_grandparent = p_parent->p_parent;
 518         while( 1 )
 519         {
 520             int i;
 521             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 522             {
 523                 if( p_parent == p_grandparent->pp_children[i] )
 524                 {
 525                     PL_DEBUG( "parent %s found as child %i of grandparent %s",
 526                               p_parent->p_input->psz_name, i,
 527                               p_grandparent->p_input->psz_name );
 528                     b_found = VLC_TRUE;
 529                     break;
 530                 }
 531             }
 532             if( b_found && i + 1 < p_grandparent->i_children )
 533             {
 534                     return p_grandparent->pp_children[i+1];
 535             }
 536             /* Not found at root */
 537             if( p_grandparent == p_root )
 538             {
 539                 return NULL;
 540             }
 541             else
 542             {
 543                 p_parent = p_grandparent;
 544                 p_grandparent = p_parent->p_parent;
 545             }
 546         }
 547     }
 548     /* We reached root */
 549     return NULL;
 550 }
 551
 552 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 553                                playlist_item_t *p_root )
 554 {
 555     playlist_item_t *p_parent = p_item->p_parent;
 556     playlist_item_t *p_grandparent;
 557     vlc_bool_t b_found = VLC_FALSE;
 558
 559     if( p_parent != NULL )
 560     {
 561         p_grandparent = p_parent->p_parent;
 562         while( 1 )
 563         {
 564             int i;
 565             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
 566             {
 567                 if( p_parent == p_grandparent->pp_children[i] )
 568                 {
 569                     b_found = VLC_TRUE;
 570                     break;
 571                 }
 572             }
 573             if( b_found && i - 1 > 0 )
 574             {
 575                 return p_grandparent->pp_children[i-1];
 576             }
 577             /* Not found at root */
 578             if( p_grandparent == p_root )
 579             {
 580                 return NULL;
 581             }
 582             else
 583             {
 584                 p_parent = p_grandparent;
 585                 p_grandparent = p_parent->p_parent;
 586             }
 587         }
 588     }
 589     /* We reached root */
 590     return NULL;
 591 }
 592
 593
 594 /* Recursively search the tree for previous item */
 595 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
 596                               playlist_item_t *p_root,
 597                               playlist_item_t *p_item )
 598 {
 599     playlist_item_t *p_parent;
 600     int i;
 601
 602     /* Node with children, get the last one */
 603     if( p_item && p_item->i_children > 0 )
 604         return p_item->pp_children[p_item->i_children - 1];
 605
 606     /* Last child of its parent ? */
 607     if( p_item != NULL )
 608         p_parent = p_item->p_parent;
 609     else
 610     {
 611         msg_Err( p_playlist, "Get the last one" );
 612         abort();
 613     };
 614
 615     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
 616     {
 617         if( p_parent->pp_children[i] == p_item )
 618         {
 619             if( i-1 < 0 )
 620             {
 621                 /* Was already the first sibling. Look for uncles */
 622                 PL_DEBUG( "Current item is the first of the node,"
 623                           "looking for uncle from %s",
 624                           p_parent->p_input->psz_name );
 625                 return GetPrevUncle( p_playlist, p_item, p_root );
 626             }
 627             else
 628             {
 629                 return p_parent->pp_children[i-1];
 630             }
 631         }
 632     }
 633     msg_Err( p_playlist, "I should not be here" );
 634     return NULL;
 635 }
 636
 637 /* Dump the contents of a node */
 638 void playlist_NodeDump( playlist_t *p_playlist, playlist_item_t *p_item,
 639                         int i_level )
 640 {
 641     char str[512];
 642     int i;
 643
 644     if( i_level == 1 )
 645     {
 646         msg_Dbg( p_playlist, "%s (%i)",
 647                         p_item->p_input->psz_name, p_item->i_children );
 648     }
 649
 650     if( p_item->i_children == -1 )
 651     {
 652         return;
 653     }
 654
 655     for( i = 0; i< p_item->i_children; i++ )
 656     {
 657         memset( str, 32, 512 );
 658         sprintf( str + 2 * i_level , "%s (%i)",
 659                                 p_item->pp_children[i]->p_input->psz_name,
 660                                 p_item->pp_children[i]->i_children );
 661         msg_Dbg( p_playlist, "%s",str );
 662         if( p_item->pp_children[i]->i_children >= 0 )
 663         {
 664             playlist_NodeDump( p_playlist, p_item->pp_children[i],
 665                               i_level + 1 );
 666         }
 667     }
 668     return;
 669 }