Remove unused function.
[vlc.git] / src / playlist / tree.c
1 /*****************************************************************************
2  * tree.c : Playlist tree walking functions
3  *****************************************************************************
4  * Copyright (C) 1999-2007 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 #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 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_flags,
60                                        input_item_t *p_input )
61 {
62     input_item_t *p_new_input = NULL;
63     playlist_item_t *p_item;
64
65     PL_ASSERT_LOCKED;
66     if( !psz_name ) psz_name = _("Undefined");
67
68     if( !p_input )
69         p_new_input = input_item_NewWithType( VLC_OBJECT(p_playlist), NULL,
70                                         psz_name, 0, NULL, 0, -1, ITEM_TYPE_NODE );
71     p_item = playlist_ItemNewFromInput( p_playlist,
72                                         p_input ? p_input : p_new_input );
73     if( p_new_input )
74         vlc_gc_decref( p_new_input );
75
76     if( p_item == NULL )  return NULL;
77     p_item->i_children = 0;
78
79     ARRAY_APPEND(p_playlist->all_items, p_item);
80
81     if( p_parent != NULL )
82         playlist_NodeAppend( p_playlist, p_item, p_parent );
83     playlist_SendAddNotify( p_playlist, p_item->i_id,
84                             p_parent ? p_parent->i_id : -1,
85                             !( i_flags & PLAYLIST_NO_REBUILD ));
86     return p_item;
87 }
88
89 /**
90  * Remove all the children of a node
91  *
92  * This function must be entered with the playlist lock
93  *
94  * \param p_playlist the playlist
95  * \param p_root the node
96  * \param b_delete_items do we have to delete the children items ?
97  * \return VLC_SUCCESS or an error
98  */
99 int playlist_NodeEmpty( playlist_t *p_playlist, playlist_item_t *p_root,
100                         bool b_delete_items )
101 {
102     PL_ASSERT_LOCKED;
103     int i;
104     if( p_root->i_children == -1 )
105     {
106         return VLC_EGENERIC;
107     }
108
109     /* Delete the children */
110     for( i =  p_root->i_children-1 ; i >= 0 ;i-- )
111     {
112         if( p_root->pp_children[i]->i_children > -1 )
113         {
114             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
115                                  b_delete_items , false );
116         }
117         else if( b_delete_items )
118         {
119             /* Delete the item here */
120             playlist_DeleteFromItemId( p_playlist,
121                                        p_root->pp_children[i]->i_id );
122         }
123     }
124     return VLC_SUCCESS;
125 }
126
127 /**
128  * Remove all the children of a node and removes the node
129  *
130  * \param p_playlist the playlist
131  * \param p_root the node
132  * \param b_delete_items do we have to delete the children items ?
133  * \return VLC_SUCCESS or an error
134  */
135 int playlist_NodeDelete( playlist_t *p_playlist, playlist_item_t *p_root,
136                          bool b_delete_items, bool b_force )
137 {
138     PL_ASSERT_LOCKED;
139     int i;
140
141     if( p_root->i_children == -1 )
142     {
143         return VLC_EGENERIC;
144     }
145
146     /* Delete the children */
147     for( i = p_root->i_children - 1 ; i >= 0; i-- )
148     {
149         if( p_root->pp_children[i]->i_children > -1 )
150         {
151             playlist_NodeDelete( p_playlist, p_root->pp_children[i],
152                                  b_delete_items , b_force );
153         }
154         else if( b_delete_items )
155         {
156             playlist_DeleteFromItemId( p_playlist,
157                                        p_root->pp_children[i]->i_id );
158         }
159     }
160     /* Delete the node */
161     if( p_root->i_flags & PLAYLIST_RO_FLAG && !b_force )
162     {
163     }
164     else
165     {
166         int i;
167         var_SetInteger( p_playlist, "playlist-item-deleted", p_root->i_id );
168         ARRAY_BSEARCH( p_playlist->all_items, ->i_id, int,
169                        p_root->i_id, i );
170         if( i != -1 )
171             ARRAY_REMOVE( p_playlist->all_items, i );
172
173         /* Remove the item from its parent */
174         if( p_root->p_parent )
175             playlist_NodeRemoveItem( p_playlist, p_root, p_root->p_parent );
176
177         playlist_ItemRelease( p_root );
178     }
179     return VLC_SUCCESS;
180 }
181
182
183 /**
184  * Adds an item to the children of a node
185  *
186  * \param p_playlist the playlist
187  * \param p_item the item to append
188  * \param p_parent the parent node
189  * \return VLC_SUCCESS or an error
190  */
191 int playlist_NodeAppend( playlist_t *p_playlist,
192                          playlist_item_t *p_item,
193                          playlist_item_t *p_parent )
194 {
195     return playlist_NodeInsert( p_playlist, p_item, p_parent, -1 );
196 }
197
198 int playlist_NodeInsert( playlist_t *p_playlist,
199                          playlist_item_t *p_item,
200                          playlist_item_t *p_parent,
201                          int i_position )
202 {
203     PL_ASSERT_LOCKED;
204    (void)p_playlist;
205    assert( p_parent && p_parent->i_children != -1 );
206    if( i_position == -1 ) i_position = p_parent->i_children ;
207
208    INSERT_ELEM( p_parent->pp_children,
209                 p_parent->i_children,
210                 i_position,
211                 p_item );
212    p_item->p_parent = p_parent;
213    return VLC_SUCCESS;
214 }
215
216 /**
217  * Deletes an item from the children of a node
218  *
219  * \param p_playlist the playlist
220  * \param p_item the item to remove
221  * \param p_parent the parent node
222  * \return VLC_SUCCESS or an error
223  */
224 int playlist_NodeRemoveItem( playlist_t *p_playlist,
225                         playlist_item_t *p_item,
226                         playlist_item_t *p_parent )
227 {
228     PL_ASSERT_LOCKED;
229    (void)p_playlist;
230
231    for(int i= 0; i< p_parent->i_children ; i++ )
232    {
233        if( p_parent->pp_children[i] == p_item )
234        {
235            REMOVE_ELEM( p_parent->pp_children, p_parent->i_children, i );
236        }
237    }
238
239    return VLC_SUCCESS;
240 }
241
242 /**
243  * Search a child of a node by its name
244  *
245  * \param p_node the node
246  * \param psz_search the name of the child to search
247  * \return the child item or NULL if not found or error
248  */
249 playlist_item_t *playlist_ChildSearchName( playlist_item_t *p_node,
250                                            const char *psz_search )
251 {
252     playlist_t * p_playlist = p_node->p_playlist; /* For assert_locked */
253     PL_ASSERT_LOCKED;
254     int i;
255
256     if( p_node->i_children < 0 )
257     {
258          return NULL;
259     }
260     for( i = 0 ; i< p_node->i_children; i++ )
261     {
262         if( !strcmp( p_node->pp_children[i]->p_input->psz_name, psz_search ) )
263         {
264             return p_node->pp_children[i];
265         }
266     }
267     return NULL;
268 }
269
270 /**
271  * Create a pair of nodes in the category and onelevel trees.
272  * They share the same input item.
273  * \param p_playlist the playlist
274  * \param psz_name the name of the nodes
275  * \param pp_node_cat pointer to return the node in category tree
276  * \param pp_node_one pointer to return the node in onelevel tree
277  * \param b_for_sd For Services Discovery ? (make node read-only and unskipping)
278  */
279 void playlist_NodesPairCreate( playlist_t *p_playlist, const char *psz_name,
280                                playlist_item_t **pp_node_cat,
281                                playlist_item_t **pp_node_one,
282                                bool b_for_sd )
283 {
284     PL_ASSERT_LOCKED;
285     *pp_node_cat = playlist_NodeCreate( p_playlist, psz_name,
286                                         p_playlist->p_root_category, 0, NULL );
287     *pp_node_one = playlist_NodeCreate( p_playlist, psz_name,
288                                         p_playlist->p_root_onelevel, 0,
289                                         (*pp_node_cat)->p_input );
290     if( b_for_sd )
291     {
292         (*pp_node_cat)->i_flags |= PLAYLIST_RO_FLAG;
293         (*pp_node_cat)->i_flags |= PLAYLIST_SKIP_FLAG;
294         (*pp_node_one)->i_flags |= PLAYLIST_RO_FLAG;
295         (*pp_node_one)->i_flags |= PLAYLIST_SKIP_FLAG;
296     }
297 }
298
299 /**
300  * Get the node in the preferred tree from a node in one of category
301  * or onelevel tree.
302  */
303 playlist_item_t * playlist_GetPreferredNode( playlist_t *p_playlist,
304                                              playlist_item_t *p_node )
305 {
306     PL_ASSERT_LOCKED;
307     int i;
308     if( p_node->p_parent == p_playlist->p_root_category )
309     {
310         if( pl_priv(p_playlist)->b_tree || p_node->p_input->b_prefers_tree )
311             return p_node;
312         for( i = 0 ; i< p_playlist->p_root_onelevel->i_children; i++ )
313         {
314             if( p_playlist->p_root_onelevel->pp_children[i]->p_input ==
315                     p_node->p_input )
316                 return p_playlist->p_root_onelevel->pp_children[i];
317         }
318     }
319     else if( p_node->p_parent == p_playlist->p_root_onelevel )
320     {
321         if( !pl_priv(p_playlist)->b_tree || !p_node->p_input->b_prefers_tree )
322             return p_node;
323         for( i = 0 ; i< p_playlist->p_root_category->i_children; i++ )
324         {
325             if( p_playlist->p_root_category->pp_children[i]->p_input ==
326                     p_node->p_input )
327                 return p_playlist->p_root_category->pp_children[i];
328         }
329     }
330     return NULL;
331 }
332
333 /**********************************************************************
334  * Tree walking functions
335  **********************************************************************/
336 /**
337  * Finds the next item to play
338  *
339  * \param p_playlist the playlist
340  * \param p_root the root node
341  * \param p_item the previous item  (NULL if none )
342  * \return the next item to play, or NULL if none found
343  */
344 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
345                                        playlist_item_t *p_root,
346                                        playlist_item_t *p_item,
347                                        bool b_ena, bool b_unplayed )
348 {
349     PL_ASSERT_LOCKED;
350     playlist_item_t *p_next;
351
352     assert( p_root && p_root->i_children != -1 );
353
354     PL_DEBUG2( "finding next of %s within %s",
355                PLI_NAME( p_item ), PLI_NAME( p_root ) );
356
357     /* Now, walk the tree until we find a suitable next item */
358     p_next = p_item;
359     while( 1 )
360     {
361         bool b_ena_ok = true, b_unplayed_ok = true;
362         p_next = GetNextItem( p_playlist, p_root, p_next );
363         if( !p_next || p_next == p_root )
364             break;
365         if( p_next->i_children == -1 )
366         {
367             if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
368                 b_ena_ok = false;
369             if( b_unplayed && p_next->p_input->i_nb_played != 0 )
370                 b_unplayed_ok = false;
371             if( b_ena_ok && b_unplayed_ok ) break;
372         }
373     }
374     if( p_next == NULL ) PL_DEBUG2( "at end of node" );
375     return p_next;
376 }
377
378 /**
379  * Finds the previous item to play
380  *
381  * \param p_playlist the playlist
382  * \param p_root the root node
383  * \param p_item the previous item  (NULL if none )
384  * \return the next item to play, or NULL if none found
385  */
386 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
387                                        playlist_item_t *p_root,
388                                        playlist_item_t *p_item,
389                                        bool b_ena, bool b_unplayed )
390 {
391     PL_ASSERT_LOCKED;
392     playlist_item_t *p_prev;
393
394     PL_DEBUG2( "finding previous of %s within %s", PLI_NAME( p_item ),
395                                                    PLI_NAME( p_root ) );
396     assert( p_root && p_root->i_children != -1 );
397
398     /* Now, walk the tree until we find a suitable previous item */
399     p_prev = p_item;
400     while( 1 )
401     {
402         bool b_ena_ok = true, b_unplayed_ok = true;
403         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
404         if( !p_prev || p_prev == p_root )
405             break;
406         if( p_prev->i_children == -1 )
407         {
408             if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
409                 b_ena_ok = false;
410             if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
411                 b_unplayed_ok = false;
412             if( b_ena_ok && b_unplayed_ok ) break;
413         }
414     }
415     if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
416     return p_prev;
417 }
418
419 /************************************************************************
420  * Following functions are local
421  ***********************************************************************/
422
423 /**
424  * Get the next item in the tree
425  * If p_item is NULL, return the first child of root
426  **/
427 playlist_item_t *GetNextItem( playlist_t *p_playlist,
428                               playlist_item_t *p_root,
429                               playlist_item_t *p_item )
430 {
431     /* If the item is NULL, return the firt child of root */
432     if( p_item == NULL )
433     {
434         if( p_root->i_children > 0 )
435             return p_root->pp_children[0];
436         else
437             return NULL;
438     }
439
440     /* Node with children, get the first one */
441     if( p_item->i_children > 0 )
442         return p_item->pp_children[0];
443
444     playlist_item_t* p_parent = p_item->p_parent;
445     for( int i = 0 ; i < p_parent->i_children ; i++ )
446     {
447         if( p_parent->pp_children[i] == p_item )
448         {
449             // Return the next children
450             if( i + 1 < p_parent->i_children )
451                 return p_parent->pp_children[i+1];
452             // We are the least one, so try to have uncles
453             else
454             {
455                 PL_DEBUG2( "Current item is the last of the node,"
456                            "looking for uncle from %s",
457                             p_parent->p_input->psz_name );
458                 if( p_parent == p_root )
459                 {
460                     PL_DEBUG2( "already at root" );
461                     return NULL;
462                 }
463                 else
464                     return GetNextUncle( p_playlist, p_item, p_root );
465             }
466         }
467     }
468     return NULL;
469 }
470
471 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
472                                playlist_item_t *p_root )
473 {
474     playlist_item_t *p_parent = p_item->p_parent;
475     playlist_item_t *p_grandparent;
476     bool b_found = false;
477
478     (void)p_playlist;
479
480     if( p_parent != NULL )
481     {
482         p_grandparent = p_parent->p_parent;
483         while( p_grandparent )
484         {
485             int i;
486             for( i = 0 ; i< p_grandparent->i_children ; i++ )
487             {
488                 if( p_parent == p_grandparent->pp_children[i] )
489                 {
490                     PL_DEBUG2( "parent %s found as child %i of grandparent %s",
491                                p_parent->p_input->psz_name, i,
492                                p_grandparent->p_input->psz_name );
493                     b_found = true;
494                     break;
495                 }
496             }
497             if( b_found && i + 1 < p_grandparent->i_children )
498             {
499                     return p_grandparent->pp_children[i+1];
500             }
501             /* Not found at root */
502             if( p_grandparent == p_root )
503             {
504                 return NULL;
505             }
506             else
507             {
508                 p_parent = p_grandparent;
509                 p_grandparent = p_parent->p_parent;
510             }
511         }
512     }
513     /* We reached root */
514     return NULL;
515 }
516
517 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
518                                playlist_item_t *p_root )
519 {
520     playlist_item_t *p_parent = p_item->p_parent;
521     playlist_item_t *p_grandparent;
522     bool b_found = false;
523
524     (void)p_playlist;
525
526     if( p_parent != NULL )
527     {
528         p_grandparent = p_parent->p_parent;
529         while( 1 )
530         {
531             int i;
532             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
533             {
534                 if( p_parent == p_grandparent->pp_children[i] )
535                 {
536                     b_found = true;
537                     break;
538                 }
539             }
540             if( b_found && i - 1 > 0 )
541             {
542                 return p_grandparent->pp_children[i-1];
543             }
544             /* Not found at root */
545             if( p_grandparent == p_root )
546             {
547                 return NULL;
548             }
549             else
550             {
551                 p_parent = p_grandparent;
552                 p_grandparent = p_parent->p_parent;
553             }
554         }
555     }
556     /* We reached root */
557     return NULL;
558 }
559
560
561 /* Recursively search the tree for previous item */
562 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
563                               playlist_item_t *p_root,
564                               playlist_item_t *p_item )
565 {
566     playlist_item_t *p_parent;
567     int i;
568
569     /* Node with children, get the last one */
570     if( p_item && p_item->i_children > 0 )
571         return p_item->pp_children[p_item->i_children - 1];
572
573     /* Last child of its parent ? */
574     if( p_item != NULL )
575         p_parent = p_item->p_parent;
576     else
577     {
578         msg_Err( p_playlist, "Get the last one" );
579         abort();
580     };
581
582     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
583     {
584         if( p_parent->pp_children[i] == p_item )
585         {
586             if( i-1 < 0 )
587             {
588                /* Was already the first sibling. Look for uncles */
589                 PL_DEBUG2( "current item is the first of its node,"
590                            "looking for uncle from %s",
591                            p_parent->p_input->psz_name );
592                 if( p_parent == p_root )
593                 {
594                     PL_DEBUG2( "already at root" );
595                     return NULL;
596                 }
597                 return GetPrevUncle( p_playlist, p_item, p_root );
598             }
599             else
600             {
601                 return p_parent->pp_children[i-1];
602             }
603         }
604     }
605     return NULL;
606 }