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