src/playlist/tree.c

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