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