src/playlist_legacy/tree.c

   1 /*****************************************************************************
   2  * tree.c : Playlist tree walking functions
   3  *****************************************************************************
   4  * Copyright (C) 1999-2007 VLC authors and VideoLAN
   5  *
   6  * Authors: Clément Stenac <zorglub@videolan.org>
   7  *
   8  * This program is free software; you can redistribute it and/or modify it
   9  * under the terms of the GNU Lesser General Public License as published by
  10  * the Free Software Foundation; either version 2.1 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * This program is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  16  * GNU Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public License
  19  * along with this program; if not, write to the Free Software Foundation,
  20  * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  21  *****************************************************************************/
  22 #ifdef HAVE_CONFIG_H
  23 # include "config.h"
  24 #endif
  25
  26 #include <vlc_common.h>
  27 #include <assert.h>
  28 #include "vlc_playlist_legacy.h"
  29 #include "playlist_internal.h"
  30
  31 /************************************************************************
  32  * Local prototypes
  33  ************************************************************************/
  34 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
  35                                playlist_item_t *p_root );
  36 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
  37                                playlist_item_t *p_root );
  38
  39 playlist_item_t *GetNextItem( playlist_t *p_playlist,
  40                               playlist_item_t *p_root,
  41                               playlist_item_t *p_item );
  42 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
  43                               playlist_item_t *p_item,
  44                               playlist_item_t *p_root );
  45
  46 /**
  47  * Create a playlist node
  48  *
  49  * \param p_playlist the playlist
  50  * \param psz_name the name of the node
  51  * \param p_parent the parent node to attach to or NULL if no attach
  52  * \param i_pos position of the node in the parent, PLAYLIST_END to append to end.
  53  * \param p_flags miscellaneous flags
  54  * \param p_input the input_item to attach to or NULL if it has to be created
  55  * \return the new node
  56  */
  57 playlist_item_t * playlist_NodeCreate( playlist_t *p_playlist,
  58                                        const char *psz_name,
  59                                        playlist_item_t *p_parent, int i_pos,
  60                                        int i_flags )
  61 {
  62     input_item_t *p_new_input;
  63     playlist_item_t *p_item;
  64
  65     PL_ASSERT_LOCKED;
  66     if( !psz_name ) psz_name = _("Undefined");
  67
  68     p_new_input = input_item_NewExt( NULL, psz_name, INPUT_DURATION_UNSET, ITEM_TYPE_NODE,
  69                                      ITEM_NET_UNKNOWN );
  70     if( !p_new_input )
  71         return NULL;
  72     p_item = playlist_ItemNewFromInput( p_playlist, p_new_input );
  73     input_item_Release( p_new_input );
  74
  75     if( p_item == NULL )  return NULL;
  76
  77     playlist_NodeInsert( p_parent, p_item, i_pos );
  78     playlist_SendAddNotify( p_playlist, p_item );
  79
  80     p_item->i_flags |= i_flags;
  81
  82     return p_item;
  83 }
  84
  85 /**
  86  * Remove all the children of a node and removes the node
  87  *
  88  * \param p_playlist the playlist
  89  * \param p_root the node
  90  */
  91 void playlist_NodeDelete( playlist_t *p_playlist, playlist_item_t *p_root )
  92 {
  93     playlist_NodeDeleteExplicit( p_playlist, p_root,
  94         PLAYLIST_DELETE_STOP_IF_CURRENT );
  95 }
  96
  97 void playlist_NodeDeleteExplicit( playlist_t *p_playlist,
  98     playlist_item_t *p_root, int flags )
  99 {
 100     PL_ASSERT_LOCKED;
 101
 102     /* Delete the node */
 103     if( p_root->i_flags & PLAYLIST_RO_FLAG &&
 104         !( flags & PLAYLIST_DELETE_FORCE ) )
 105         return;
 106
 107     /* Delete the children */
 108     for( int i = p_root->i_children - 1 ; i >= 0; i-- )
 109         playlist_NodeDeleteExplicit( p_playlist,
 110             p_root->pp_children[i], flags | PLAYLIST_DELETE_FORCE );
 111
 112     pl_priv(p_playlist)->b_reset_currently_playing = true;
 113
 114     int i;
 115     var_SetAddress( p_playlist, "playlist-item-deleted", p_root );
 116
 117     if( p_root->i_children == -1 ) {
 118         ARRAY_BSEARCH( p_playlist->items,->i_id, int, p_root->i_id, i );
 119         if( i != -1 )
 120             ARRAY_REMOVE( p_playlist->items, i );
 121     }
 122
 123     if( get_current_status_item( p_playlist ) == p_root )
 124     {
 125         /* a deleted item cannot be currently playing */
 126         set_current_status_item( p_playlist, NULL );
 127
 128         if( flags & PLAYLIST_DELETE_STOP_IF_CURRENT )
 129             playlist_Control( p_playlist, PLAYLIST_STOP, pl_Locked );
 130     }
 131
 132     for( i = 0; i < p_playlist->current.i_size; i++ )
 133         if( p_playlist->current.p_elems[i] == p_root )
 134             ARRAY_REMOVE( p_playlist->current, i );
 135     for( i = 0; i < p_playlist->current.i_size; i++ )
 136         assert( p_playlist->current.p_elems[i] != p_root );
 137
 138     PL_DEBUG( "deleting item `%s'", p_root->p_input->psz_name );
 139
 140     /* Remove the item from its parent */
 141     playlist_item_t *p_parent = p_root->p_parent;
 142     if( p_parent != NULL )
 143         TAB_REMOVE(p_parent->i_children, p_parent->pp_children, p_root);
 144
 145     playlist_ItemRelease( p_playlist, p_root );
 146 }
 147
 148 int playlist_NodeInsert( playlist_item_t *p_parent, playlist_item_t *p_item,
 149                          int i_position )
 150 {
 151     assert( p_parent && p_parent->i_children != -1 );
 152     if( i_position == -1 ) i_position = p_parent->i_children ;
 153     assert( i_position <= p_parent->i_children);
 154
 155     TAB_INSERT(p_parent->i_children, p_parent->pp_children,
 156                p_item, i_position);
 157     p_item->p_parent = p_parent;
 158
 159     /* Inherit special flags from parent (sd cases) */
 160     if( ( p_parent->i_flags & PLAYLIST_NO_INHERIT_FLAG ) == 0 )
 161         p_item->i_flags |= (p_parent->i_flags & PLAYLIST_RO_FLAG);
 162
 163     return VLC_SUCCESS;
 164 }
 165
 166 /**
 167  * Search a child of a node by its name
 168  *
 169  * \note The playlist must be locked, and the result is only valid until the
 170  * playlist is unlocked.
 171  *
 172  * \param p_node the node
 173  * \param psz_search the name of the child to search
 174  * \return the child item or NULL if not found or error
 175  */
 176 playlist_item_t *playlist_ChildSearchName( playlist_item_t *p_node,
 177                                            const char *psz_search )
 178 {
 179     int i;
 180
 181     if( p_node->i_children < 0 )
 182     {
 183          return NULL;
 184     }
 185     for( i = 0 ; i< p_node->i_children; i++ )
 186     {
 187         if( !strcmp( p_node->pp_children[i]->p_input->psz_name, psz_search ) )
 188         {
 189             return p_node->pp_children[i];
 190         }
 191     }
 192     return NULL;
 193 }
 194
 195 /**********************************************************************
 196  * Tree walking functions
 197  **********************************************************************/
 198 /**
 199  * Finds the next item to play
 200  *
 201  * \param p_playlist the playlist
 202  * \param p_root the root node
 203  * \param p_item the previous item  (NULL if none )
 204  * \return the next item to play, or NULL if none found
 205  */
 206 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
 207                                        playlist_item_t *p_root,
 208                                        playlist_item_t *p_item,
 209                                        bool b_ena, bool b_unplayed )
 210 {
 211     PL_ASSERT_LOCKED;
 212     playlist_item_t *p_next;
 213
 214     assert( p_root && p_root->i_children != -1 );
 215
 216     PL_DEBUG2( "finding next of %s within %s",
 217                PLI_NAME( p_item ), PLI_NAME( p_root ) );
 218
 219     /* Now, walk the tree until we find a suitable next item */
 220     p_next = p_item;
 221     while( 1 )
 222     {
 223         bool b_ena_ok = true, b_unplayed_ok = true;
 224         p_next = GetNextItem( p_playlist, p_root, p_next );
 225         if( !p_next || p_next == p_root )
 226             break;
 227         if( p_next->i_children == -1 )
 228         {
 229             if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
 230                 b_ena_ok = false;
 231             if( b_unplayed && p_next->i_nb_played != 0 )
 232                 b_unplayed_ok = false;
 233             if( b_ena_ok && b_unplayed_ok ) break;
 234         }
 235     }
 236     if( p_next == NULL ) PL_DEBUG2( "at end of node" );
 237     return p_next;
 238 }
 239
 240 /************************************************************************
 241  * Following functions are local
 242  ***********************************************************************/
 243
 244 /**
 245  * Get the next item in the tree
 246  * If p_item is NULL, return the first child of root
 247  **/
 248 playlist_item_t *GetNextItem( playlist_t *p_playlist,
 249                               playlist_item_t *p_root,
 250                               playlist_item_t *p_item )
 251 {
 252     /* If the item is NULL, return the firt child of root */
 253     if( p_item == NULL )
 254     {
 255         if( p_root->i_children > 0 )
 256             return p_root->pp_children[0];
 257         else
 258             return NULL;
 259     }
 260
 261     /* Node with children, get the first one */
 262     if( p_item->i_children > 0 )
 263         return p_item->pp_children[0];
 264
 265     playlist_item_t* p_parent = p_item->p_parent;
 266     for( int i = 0 ; i < p_parent->i_children ; i++ )
 267     {
 268         if( p_parent->pp_children[i] == p_item )
 269         {
 270             // Return the next children
 271             if( i + 1 < p_parent->i_children )
 272                 return p_parent->pp_children[i+1];
 273             // We are the least one, so try to have uncles
 274             else
 275             {
 276                 PL_DEBUG2( "Current item is the last of the node,"
 277                            "looking for uncle from %s",
 278                             p_parent->p_input->psz_name );
 279                 if( p_parent == p_root )
 280                 {
 281                     PL_DEBUG2( "already at root" );
 282                     return NULL;
 283                 }
 284                 else
 285                     return GetNextUncle( p_playlist, p_item, p_root );
 286             }
 287         }
 288     }
 289     return NULL;
 290 }
 291
 292 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 293                                playlist_item_t *p_root )
 294 {
 295     playlist_item_t *p_parent = p_item->p_parent;
 296     playlist_item_t *p_grandparent;
 297     bool b_found = false;
 298
 299     (void)p_playlist;
 300
 301     if( p_parent != NULL )
 302     {
 303         p_grandparent = p_parent->p_parent;
 304         while( p_grandparent )
 305         {
 306             int i;
 307             for( i = 0 ; i< p_grandparent->i_children ; i++ )
 308             {
 309                 if( p_parent == p_grandparent->pp_children[i] )
 310                 {
 311                     PL_DEBUG2( "parent %s found as child %i of grandparent %s",
 312                                p_parent->p_input->psz_name, i,
 313                                p_grandparent->p_input->psz_name );
 314                     b_found = true;
 315                     break;
 316                 }
 317             }
 318             if( b_found && i + 1 < p_grandparent->i_children )
 319             {
 320                     return p_grandparent->pp_children[i+1];
 321             }
 322             /* Not found at root */
 323             if( p_grandparent == p_root )
 324             {
 325                 return NULL;
 326             }
 327             else
 328             {
 329                 p_parent = p_grandparent;
 330                 p_grandparent = p_parent->p_parent;
 331             }
 332         }
 333     }
 334     /* We reached root */
 335     return NULL;
 336 }
 337
 338 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
 339                                playlist_item_t *p_root )
 340 {
 341     playlist_item_t *p_parent = p_item->p_parent;
 342     playlist_item_t *p_grandparent;
 343     bool b_found = false;
 344
 345     (void)p_playlist;
 346
 347     if( p_parent != NULL )
 348     {
 349         p_grandparent = p_parent->p_parent;
 350         while( 1 )
 351         {
 352             int i;
 353             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
 354             {
 355                 if( p_parent == p_grandparent->pp_children[i] )
 356                 {
 357                     b_found = true;
 358                     break;
 359                 }
 360             }
 361             if( b_found && i - 1 > 0 )
 362             {
 363                 return p_grandparent->pp_children[i-1];
 364             }
 365             /* Not found at root */
 366             if( p_grandparent == p_root )
 367             {
 368                 return NULL;
 369             }
 370             else
 371             {
 372                 p_parent = p_grandparent;
 373                 p_grandparent = p_parent->p_parent;
 374             }
 375         }
 376     }
 377     /* We reached root */
 378     return NULL;
 379 }
 380
 381
 382 /* Recursively search the tree for previous item */
 383 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
 384                               playlist_item_t *p_root,
 385                               playlist_item_t *p_item )
 386 {
 387     playlist_item_t *p_parent;
 388     int i;
 389
 390     /* Node with children, get the last one */
 391     if( p_item && p_item->i_children > 0 )
 392         return p_item->pp_children[p_item->i_children - 1];
 393
 394     /* Last child of its parent ? */
 395     if( p_item != NULL )
 396         p_parent = p_item->p_parent;
 397     else
 398     {
 399         msg_Err( p_playlist, "Get the last one" );
 400         abort();
 401     };
 402
 403     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
 404     {
 405         if( p_parent->pp_children[i] == p_item )
 406         {
 407             if( i-1 < 0 )
 408             {
 409                /* Was already the first sibling. Look for uncles */
 410                 PL_DEBUG2( "current item is the first of its node,"
 411                            "looking for uncle from %s",
 412                            p_parent->p_input->psz_name );
 413                 if( p_parent == p_root )
 414                 {
 415                     PL_DEBUG2( "already at root" );
 416                     return NULL;
 417                 }
 418                 return GetPrevUncle( p_playlist, p_item, p_root );
 419             }
 420             else
 421             {
 422                 return p_parent->pp_children[i-1];
 423             }
 424         }
 425     }
 426     return NULL;
 427 }