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