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