32ef051be5999cde7fcacc6e3b6441df2ac441f2
[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 playlist_item_t *playlist_GetLastLeaf(playlist_t *p_playlist,
338                                       playlist_item_t *p_root )
339 {
340     PL_ASSERT_LOCKED;
341     int i;
342     playlist_item_t *p_item;
343     for ( i = p_root->i_children - 1; i >= 0; i-- )
344     {
345         if( p_root->pp_children[i]->i_children == -1 )
346             return p_root->pp_children[i];
347         else if( p_root->pp_children[i]->i_children > 0)
348         {
349              p_item = playlist_GetLastLeaf( p_playlist,
350                                             p_root->pp_children[i] );
351             if ( p_item != NULL )
352                 return p_item;
353         }
354         else if( i == 0 )
355             return NULL;
356     }
357     return NULL;
358 }
359
360 /**
361  * Finds the next item to play
362  *
363  * \param p_playlist the playlist
364  * \param p_root the root node
365  * \param p_item the previous item  (NULL if none )
366  * \return the next item to play, or NULL if none found
367  */
368 playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
369                                        playlist_item_t *p_root,
370                                        playlist_item_t *p_item,
371                                        bool b_ena, bool b_unplayed )
372 {
373     PL_ASSERT_LOCKED;
374     playlist_item_t *p_next;
375
376     assert( p_root && p_root->i_children != -1 );
377
378     PL_DEBUG2( "finding next of %s within %s",
379                PLI_NAME( p_item ), PLI_NAME( p_root ) );
380
381     /* Now, walk the tree until we find a suitable next item */
382     p_next = p_item;
383     while( 1 )
384     {
385         bool b_ena_ok = true, b_unplayed_ok = true;
386         p_next = GetNextItem( p_playlist, p_root, p_next );
387         if( !p_next || p_next == p_root )
388             break;
389         if( p_next->i_children == -1 )
390         {
391             if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
392                 b_ena_ok = false;
393             if( b_unplayed && p_next->p_input->i_nb_played != 0 )
394                 b_unplayed_ok = false;
395             if( b_ena_ok && b_unplayed_ok ) break;
396         }
397     }
398     if( p_next == NULL ) PL_DEBUG2( "at end of node" );
399     return p_next;
400 }
401
402 /**
403  * Finds the previous item to play
404  *
405  * \param p_playlist the playlist
406  * \param p_root the root node
407  * \param p_item the previous item  (NULL if none )
408  * \return the next item to play, or NULL if none found
409  */
410 playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
411                                        playlist_item_t *p_root,
412                                        playlist_item_t *p_item,
413                                        bool b_ena, bool b_unplayed )
414 {
415     PL_ASSERT_LOCKED;
416     playlist_item_t *p_prev;
417
418     PL_DEBUG2( "finding previous os %s within %s", PLI_NAME( p_item ),
419                                                    PLI_NAME( p_root ) );
420     assert( p_root && p_root->i_children != -1 );
421
422     /* Now, walk the tree until we find a suitable previous item */
423     p_prev = p_item;
424     while( 1 )
425     {
426         bool b_ena_ok = true, b_unplayed_ok = true;
427         p_prev = GetPrevItem( p_playlist, p_root, p_prev );
428         if( !p_prev || p_prev == p_root )
429             break;
430         if( p_prev->i_children == -1 )
431         {
432             if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
433                 b_ena_ok = false;
434             if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
435                 b_unplayed_ok = false;
436             if( b_ena_ok && b_unplayed_ok ) break;
437         }
438     }
439     if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
440     return p_prev;
441 }
442
443 /************************************************************************
444  * Following functions are local
445  ***********************************************************************/
446
447 /**
448  * Get the next item in the tree
449  * If p_item is NULL, return the first child of root
450  **/
451 playlist_item_t *GetNextItem( playlist_t *p_playlist,
452                               playlist_item_t *p_root,
453                               playlist_item_t *p_item )
454 {
455     /* If the item is NULL, return the firt child of root */
456     if( p_item == NULL )
457     {
458         if( p_root->i_children > 0 )
459             return p_root->pp_children[0];
460         else
461             return NULL;
462     }
463
464     /* Node with children, get the first one */
465     if( p_item->i_children > 0 )
466         return p_item->pp_children[0];
467
468     playlist_item_t* p_parent = p_item->p_parent;
469     for( int i = 0 ; i < p_parent->i_children ; i++ )
470     {
471         if( p_parent->pp_children[i] == p_item )
472         {
473             // Return the next children
474             if( i + 1 < p_parent->i_children )
475                 return p_parent->pp_children[i+1];
476             // We are the least one, so try to have uncles
477             else
478             {
479                 PL_DEBUG2( "Current item is the last of the node,"
480                            "looking for uncle from %s",
481                             p_parent->p_input->psz_name );
482                 if( p_parent == p_root )
483                 {
484                     PL_DEBUG2( "already at root" );
485                     return NULL;
486                 }
487                 else
488                     return GetNextUncle( p_playlist, p_item, p_root );
489             }
490         }
491     }
492     return NULL;
493 }
494
495 playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
496                                playlist_item_t *p_root )
497 {
498     playlist_item_t *p_parent = p_item->p_parent;
499     playlist_item_t *p_grandparent;
500     bool b_found = false;
501
502     (void)p_playlist;
503
504     if( p_parent != NULL )
505     {
506         p_grandparent = p_parent->p_parent;
507         while( p_grandparent )
508         {
509             int i;
510             for( i = 0 ; i< p_grandparent->i_children ; i++ )
511             {
512                 if( p_parent == p_grandparent->pp_children[i] )
513                 {
514                     PL_DEBUG2( "parent %s found as child %i of grandparent %s",
515                                p_parent->p_input->psz_name, i,
516                                p_grandparent->p_input->psz_name );
517                     b_found = true;
518                     break;
519                 }
520             }
521             if( b_found && i + 1 < p_grandparent->i_children )
522             {
523                     return p_grandparent->pp_children[i+1];
524             }
525             /* Not found at root */
526             if( p_grandparent == p_root )
527             {
528                 return NULL;
529             }
530             else
531             {
532                 p_parent = p_grandparent;
533                 p_grandparent = p_parent->p_parent;
534             }
535         }
536     }
537     /* We reached root */
538     return NULL;
539 }
540
541 playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
542                                playlist_item_t *p_root )
543 {
544     playlist_item_t *p_parent = p_item->p_parent;
545     playlist_item_t *p_grandparent;
546     bool b_found = false;
547
548     (void)p_playlist;
549
550     if( p_parent != NULL )
551     {
552         p_grandparent = p_parent->p_parent;
553         while( 1 )
554         {
555             int i;
556             for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
557             {
558                 if( p_parent == p_grandparent->pp_children[i] )
559                 {
560                     b_found = true;
561                     break;
562                 }
563             }
564             if( b_found && i - 1 > 0 )
565             {
566                 return p_grandparent->pp_children[i-1];
567             }
568             /* Not found at root */
569             if( p_grandparent == p_root )
570             {
571                 return NULL;
572             }
573             else
574             {
575                 p_parent = p_grandparent;
576                 p_grandparent = p_parent->p_parent;
577             }
578         }
579     }
580     /* We reached root */
581     return NULL;
582 }
583
584
585 /* Recursively search the tree for previous item */
586 playlist_item_t *GetPrevItem( playlist_t *p_playlist,
587                               playlist_item_t *p_root,
588                               playlist_item_t *p_item )
589 {
590     playlist_item_t *p_parent;
591     int i;
592
593     /* Node with children, get the last one */
594     if( p_item && p_item->i_children > 0 )
595         return p_item->pp_children[p_item->i_children - 1];
596
597     /* Last child of its parent ? */
598     if( p_item != NULL )
599         p_parent = p_item->p_parent;
600     else
601     {
602         msg_Err( p_playlist, "Get the last one" );
603         abort();
604     };
605
606     for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
607     {
608         if( p_parent->pp_children[i] == p_item )
609         {
610             if( i-1 < 0 )
611             {
612                /* Was already the first sibling. Look for uncles */
613                 PL_DEBUG2( "current item is the first of its node,"
614                            "looking for uncle from %s",
615                            p_parent->p_input->psz_name );
616                 if( p_parent == p_root )
617                 {
618                     PL_DEBUG2( "already at root" );
619                     return NULL;
620                 }
621                 return GetPrevUncle( p_playlist, p_item, p_root );
622             }
623             else
624             {
625                 return p_parent->pp_children[i-1];
626             }
627         }
628     }
629     return NULL;
630 }