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