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         playlist_ItemDelete( p_root );
 183     }
 184     return VLC_SUCCESS;
 185 }
 186
 187
 188 /**
 189  * Adds an item to the children of a node
 190  *
 191  * \param p_playlist the playlist
 192  * \param p_item the item to append
 193  * \param p_parent the parent node
 194  * \return VLC_SUCCESS or an error
 195  */
 196 int playlist_NodeAppend( playlist_t *p_playlist,
 197                          playlist_item_t *p_item,
 198                          playlist_item_t *p_parent )
 199 {
 200     return playlist_NodeInsert( p_playlist, p_item, p_parent, -1 );
 201 }
 202
 203 int playlist_NodeInsert( playlist_t *p_playlist,
 204                          playlist_item_t *p_item,
 205                          playlist_item_t *p_parent,
 206                          int i_position )
 207 {
 208    assert( p_parent && p_parent->i_children != -1 );
 209    if( i_position == -1 ) i_position = p_parent->i_children ;
 210
 211    INSERT_ELEM( p_parent->pp_children,
 212                 p_parent->i_children,
 213                 i_position,
 214                 p_item );
 215    p_item->p_parent = p_parent;
 216    return VLC_SUCCESS;
 217 }
 218
 219 /**
 220  * Deletes an item from the children of a node
 221  *
 222  * \param p_playlist the playlist
 223  * \param p_item the item to remove
 224  * \param p_parent the parent node
 225  * \return VLC_SUCCESS or an error
 226  */
 227 int playlist_NodeRemoveItem( playlist_t *p_playlist,
 228                         playlist_item_t *p_item,
 229                         playlist_item_t *p_parent )
 230 {
 231    int i;
 232    for( i= 0; i< p_parent->i_children ; i++ )
 233    {
 234        if( p_parent->pp_children[i] == p_item )
 235        {
 236            REMOVE_ELEM( p_parent->pp_children, p_parent->i_children, i );
 237        }
 238    }
 239
 240    return VLC_SUCCESS;
 241 }
 242
 243
 244 /**
 245  * Count the children of a node
 246  *
 247  * \param p_playlist the playlist
 248  * \param p_node the node
 249  * \return the number of children
 250  */
 251 int playlist_NodeChildrenCount( playlist_t *p_playlist, playlist_item_t*p_node)
 252 {
 253     int i;
 254     int i_nb = 0;
 255     if( p_node->i_children == -1 )
 256         return 0;
 257
 258     for( i=0 ; i< p_node->i_children;i++ )
 259     {
 260         if( p_node->pp_children[i]->i_children == -1 )
 261             i_nb++;
 262         else
 263             i_nb += playlist_NodeChildrenCount( p_playlist,
 264                                                 p_node->pp_children[i] );
 265     }
 266     return i_nb;
 267 }
 268
 269 /**
 270  * Search a child of a node by its name
 271  *
 272  * \param p_node the node
 273  * \param psz_search the name of the child to search
 274  * \return the child item or NULL if not found or error
 275  */
 276 playlist_item_t *playlist_ChildSearchName( playlist_item_t *p_node,
 277                                            const char *psz_search )
 278 {
 279     int i;
 280
 281     if( p_node->i_children < 0 )
 282     {
 283          return NULL;
 284     }
 285     for( i = 0 ; i< p_node->i_children; i++ )
 286     {
 287         if( !strcmp( p_node->pp_children[i]->p_input->psz_name, psz_search ) )
 288         {
 289             return p_node->pp_children[i];
 290         }
 291     }
 292     return NULL;
 293 }
 294
 295
 296 void playlist_NodesCreateForSD( playlist_t *p_playlist, char *psz_name,
 297                                 playlist_item_t **pp_node_cat,
 298                                 playlist_item_t **pp_node_one )
 299 {
 300     *pp_node_cat = playlist_NodeCreate( p_playlist, psz_name,
 301                                         p_playlist->p_root_category );
 302     (*pp_node_cat)->i_flags |= PLAYLIST_RO_FLAG;
 303     (*pp_node_cat)->i_flags |= PLAYLIST_SKIP_FLAG;
 304
 305     *pp_node_one = playlist_NodeCreate( p_playlist, psz_name,
 306                                         p_playlist->p_root_onelevel );
 307     (*pp_node_one)->i_flags |= PLAYLIST_RO_FLAG;
 308     (*pp_node_one)->i_flags |= PLAYLIST_SKIP_FLAG;
 309 }
 310
 311
 312 /**********************************************************************
 313  * Tree walking functions
 314  **********************************************************************/
 315
 316 playlist_item_t *playlist_GetLastLeaf(playlist_t *p_playlist,
 317                                       playlist_item_t *p_root )
 318 {
 319     int i;
 320     playlist_item_t *p_item;
 321     for ( i = p_root->i_children - 1; i >= 0; i-- )
 322     {
 323         if( p_root->pp_children[i]->i_children == -1 )
 324             return p_root->pp_children[i];
 325         else if( p_root->pp_children[i]->i_children > 0)
 326         {
 327              p_item = playlist_GetLastLeaf( p_playlist,
 328                                             p_root->pp_children[i] );
 329             if ( p_item != NULL )
 330                 return p_item;
 331         }
 332         else if( i == 0 )
 333             return NULL;
 334     }
 335     return NULL;
 336 }
 337
 338 /**
 339  * Finds the next item to play
 340  *
 341  * \param p_playlist the playlist
 342  * \param p_root the root node
 343  * \param p_item the previous item  (NULL if none )
 344  * \return the next item to play, or NULL if none found
 345  */
 346 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
 347                                        playlist_item_t *p_root,
 348                                        playlist_item_t *p_item )
 349 {
 350     playlist_item_t *p_next;
 351
 352 #ifdef PLAYLIST_DEBUG
 353     if( p_item != NULL )
 354         msg_Dbg( p_playlist, "finding next of %s within %s",
 355                         p_item->p_input->psz_name,  p_root->p_input->psz_name );
 356     else
 357         msg_Dbg( p_playlist, "finding something to play within %s",
 358                          p_root->p_input->psz_name );
 359 #endif
 360
 361     assert( p_root && p_root->i_children != -1 );
 362
 363     /* Now, walk the tree until we find a suitable next item */
 364     p_next = p_item;
 365     do
 366     {
 367         p_next = GetNextItem( p_playlist, p_root, p_next );
 368     } while ( p_next && p_next != p_root && p_next->i_children != -1 );
 369
 370 #ifdef PLAYLIST_DEBUG
 371     if( p_next == NULL )
 372         msg_Dbg( p_playlist, "At end of node" );
 373 #endif
 374     return p_next;
 375 }
 376
 377 playlist_item_t *playlist_GetNextEnabledLeaf( playlist_t *p_playlist,
 378                                               playlist_item_t *p_root,
 379                                               playlist_item_t *p_item )
 380 {
 381     playlist_item_t *p_next;
 382
 383 #ifdef PLAYLIST_DEBUG
 384     if( p_item != NULL )
 385         msg_Dbg( p_playlist, "finding next of %s within %s",
 386                         p_item->p_input->psz_name,  p_root->p_input->psz_name );
 387     else
 388         msg_Dbg( p_playlist, "finding something to play within %s",
 389                          p_root->p_input->psz_name );
 390 #endif
 391
 392     assert( p_root && p_root->i_children != -1 );
 393
 394     /* Now, walk the tree until we find a suitable next item */
 395     p_next = p_item;
 396     do
 397     {
 398         p_next = GetNextItem( p_playlist, p_root, p_next );
 399     } while ( p_next && p_next != p_root &&
 400               !( p_next->i_children == -1 &&
 401               !(p_next->i_flags & PLAYLIST_DBL_FLAG) ) );
 402
 403 #ifdef PLAYLIST_DEBUG
 404     if( p_next == NULL )
 405         msg_Dbg( p_playlist, "At end of node" );
 406 #endif
 407     return p_next;
 408 }
 409
 410 /**
 411  * Finds the previous item to play
 412  *
 413  * \param p_playlist the playlist
 414  * \param p_root the root node
 415  * \param p_item the previous item  (NULL if none )
 416  * \return the next item to play, or NULL if none found
 417  */
 418 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
 419                                        playlist_item_t *p_root,
 420                                        playlist_item_t *p_item )
 421 {
 422     playlist_item_t *p_prev;
 423
 424 #ifdef PLAYLIST_DEBUG
 425     if( p_item != NULL )
 426         msg_Dbg( p_playlist, "finding previous of %s within %s",
 427                         p_item->p_input->psz_name,  p_root->p_input->psz_name );
 428     else
 429         msg_Dbg( p_playlist, "finding previous to play within %s",
 430                          p_root->p_input->psz_name );
 431 #endif
 432     assert( p_root && p_root->i_children != -1 );
 433
 434     /* Now, walk the tree until we find a suitable previous item */
 435     p_prev = p_item;
 436     do
 437     {
 438         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
 439     } while ( p_prev && p_prev != p_root && p_prev->i_children != -1 );
 440
 441 #ifdef PLAYLIST_DEBUG
 442     if( p_prev == NULL )
 443         msg_Dbg( p_playlist, "At beginning of node" );
 444 #endif
 445     return p_prev;
 446 }
 447
 448 /************************************************************************
 449  * Following functions are local
 450  ***********************************************************************/
 451
 452 /**
 453  * Get the next item in the tree
 454  * If p_item is NULL, return the first child of root
 455  **/
 456 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 457                               playlist_item_t *p_root,
 458                               playlist_item_t *p_item )
 459 {
 460     playlist_item_t *p_parent;
 461     int i;
 462
 463     /* Node with children, get the first one */
 464     if( p_item && p_item->i_children > 0 )
 465         return p_item->pp_children[0];
 466
 467     if( p_item != NULL )
 468         p_parent = p_item->p_parent;
 469     else
 470         p_parent = p_root;
 471
 472     for( i= 0 ; i < p_parent->i_children ; i++ )
 473     {
 474         if( p_item == NULL || p_parent->pp_children[i] == p_item )
 475         {
 476             if( p_item == NULL )
 477                 i = -1;
 478
 479             if( i+1 >= p_parent->i_children )
 480             {
 481                 /* Was already the last sibling. Look for uncles */
 482 #ifdef PLAYLIST_DEBUG
 483                 msg_Dbg( p_playlist, "Current item is the last of the node,"
 484                                      "looking for uncle from %s",
 485                                      p_parent->p_input->psz_name );
 486 #endif
 487                 if( p_parent == p_root )
 488                 {
 489 #ifdef PLAYLIST_DEBUG
 490                     msg_Dbg( p_playlist, "Already at root" );
 491                     return NULL;
 492 #endif
 493                 }
 494                 return GetNextUncle( p_playlist, p_item, p_root );
 495             }
 496             else
 497             {
 498                 return  p_parent->pp_children[i+1];
 499             }
 500         }
 501     }
 502     msg_Err( p_playlist, "I should not be here" );
 503     return NULL;
 504 }
 505
 506 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 507                                playlist_item_t *p_root )
 508 {
 509     playlist_item_t *p_parent = p_item->p_parent;
 510     playlist_item_t *p_grandparent;
 511     vlc_bool_t b_found = VLC_FALSE;
 512
 513     if( p_parent != NULL )
 514     {
 515         p_grandparent = p_parent->p_parent;
 516         while( 1 )
 517         {
 518             int i;
 519             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 520             {
 521                 if( p_parent == p_grandparent->pp_children[i] )
 522                 {
 523 #ifdef PLAYLIST_DEBUG
 524                     msg_Dbg( p_playlist, "parent %s found as child %i of "
 525                                     "grandparent %s",
 526                                     p_parent->p_input->psz_name, i,
 527                                     p_grandparent->p_input->psz_name );
 528 #endif
 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 #ifdef PLAYLIST_DEBUG
 624                 msg_Dbg( p_playlist, "Current item is the first of the node,"
 625                                      "looking for uncle from %s",
 626                                      p_parent->p_input->psz_name );
 627 #endif
 628                 return GetPrevUncle( p_playlist, p_item, p_root );
 629             }
 630             else
 631             {
 632                 return p_parent->pp_children[i-1];
 633             }
 634         }
 635     }
 636     msg_Err( p_playlist, "I should not be here" );
 637     return NULL;
 638 }
 639
 640 /* Dump the contents of a node */
 641 void playlist_NodeDump( playlist_t *p_playlist, playlist_item_t *p_item,
 642                         int i_level )
 643 {
 644     char str[512];
 645     int i;
 646
 647     if( i_level == 1 )
 648     {
 649         msg_Dbg( p_playlist, "%s (%i)",
 650                         p_item->p_input->psz_name, p_item->i_children );
 651     }
 652
 653     if( p_item->i_children == -1 )
 654     {
 655         return;
 656     }
 657
 658     for( i = 0; i< p_item->i_children; i++ )
 659     {
 660         memset( str, 32, 512 );
 661         sprintf( str + 2 * i_level , "%s (%i)",
 662                                 p_item->pp_children[i]->p_input->psz_name,
 663                                 p_item->pp_children[i]->i_children );
 664         msg_Dbg( p_playlist, "%s",str );
 665         if( p_item->pp_children[i]->i_children >= 0 )
 666         {
 667             playlist_NodeDump( p_playlist, p_item->pp_children[i],
 668                               i_level + 1 );
 669         }
 670     }
 671     return;
 672 }