1 /*****************************************************************************
2 * tree.c : Playlist tree walking functions
3 *****************************************************************************
4 * Copyright (C) 1999-2007 VLC authors and VideoLAN
7 * Authors: Clément Stenac <zorglub@videolan.org>
9 * This program is free software; you can redistribute it and/or modify it
10 * under the terms of the GNU Lesser General Public License as published by
11 * the Free Software Foundation; either version 2.1 of the License, or
12 * (at your option) any later version.
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU Lesser General Public License for more details.
19 * You should have received a copy of the GNU Lesser General Public License
20 * along with this program; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
22 *****************************************************************************/
27 #include <vlc_common.h>
29 #include "vlc_playlist.h"
30 #include "playlist_internal.h"
32 /************************************************************************
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
);
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
);
48 * Create a playlist node
50 * \param p_playlist the playlist
51 * \param psz_name the name of the node
52 * \param p_parent the parent node to attach to or NULL if no attach
53 * \param i_pos position of the node in the parent, PLAYLIST_END to append to end.
54 * \param p_flags miscellaneous flags
55 * \param p_input the input_item to attach to or NULL if it has to be created
56 * \return the new node
58 playlist_item_t
* playlist_NodeCreate( playlist_t
*p_playlist
,
60 playlist_item_t
*p_parent
, int i_pos
,
63 input_item_t
*p_new_input
;
64 playlist_item_t
*p_item
;
67 if( !psz_name
) psz_name
= _("Undefined");
69 p_new_input
= input_item_NewExt( NULL
, psz_name
, -1, ITEM_TYPE_NODE
,
73 p_item
= playlist_ItemNewFromInput( p_playlist
, p_new_input
);
74 input_item_Release( p_new_input
);
76 if( p_item
== NULL
) return NULL
;
78 playlist_NodeInsert( p_parent
, p_item
, i_pos
);
79 playlist_SendAddNotify( p_playlist
, p_item
);
81 p_item
->i_flags
|= i_flags
;
87 * Remove all the children of a node and removes the node
89 * \param p_playlist the playlist
90 * \param p_root the node
92 void playlist_NodeDelete( playlist_t
*p_playlist
, playlist_item_t
*p_root
)
94 playlist_NodeDeleteExplicit( p_playlist
, p_root
,
95 PLAYLIST_DELETE_STOP_IF_CURRENT
);
98 void playlist_NodeDeleteExplicit( playlist_t
*p_playlist
,
99 playlist_item_t
*p_root
, int flags
)
103 /* Delete the node */
104 if( p_root
->i_flags
& PLAYLIST_RO_FLAG
&&
105 !( flags
& PLAYLIST_DELETE_FORCE
) )
108 /* Delete the children */
109 for( int i
= p_root
->i_children
- 1 ; i
>= 0; i
-- )
110 playlist_NodeDeleteExplicit( p_playlist
,
111 p_root
->pp_children
[i
], flags
| PLAYLIST_DELETE_FORCE
);
113 pl_priv(p_playlist
)->b_reset_currently_playing
= true;
116 var_SetAddress( p_playlist
, "playlist-item-deleted", p_root
);
118 if( p_root
->i_children
== -1 ) {
119 ARRAY_BSEARCH( p_playlist
->items
,->i_id
, int, p_root
->i_id
, i
);
121 ARRAY_REMOVE( p_playlist
->items
, i
);
124 if( get_current_status_item( p_playlist
) == p_root
)
126 /* a deleted item cannot be currently playing */
127 set_current_status_item( p_playlist
, NULL
);
129 if( flags
& PLAYLIST_DELETE_STOP_IF_CURRENT
)
130 playlist_Control( p_playlist
, PLAYLIST_STOP
, pl_Locked
);
133 for( i
= 0; i
< p_playlist
->current
.i_size
; i
++ )
134 if( p_playlist
->current
.p_elems
[i
] == p_root
)
135 ARRAY_REMOVE( p_playlist
->current
, i
);
136 for( i
= 0; i
< p_playlist
->current
.i_size
; i
++ )
137 assert( p_playlist
->current
.p_elems
[i
] != p_root
);
139 PL_DEBUG( "deleting item `%s'", p_root
->p_input
->psz_name
);
141 /* Remove the item from its parent */
142 playlist_item_t
*p_parent
= p_root
->p_parent
;
143 if( p_parent
!= NULL
)
144 TAB_REMOVE(p_parent
->i_children
, p_parent
->pp_children
, p_root
);
146 playlist_ItemRelease( p_playlist
, p_root
);
149 int playlist_NodeInsert( playlist_item_t
*p_parent
, playlist_item_t
*p_item
,
152 assert( p_parent
&& p_parent
->i_children
!= -1 );
153 if( i_position
== -1 ) i_position
= p_parent
->i_children
;
154 assert( i_position
<= p_parent
->i_children
);
156 TAB_INSERT(p_parent
->i_children
, p_parent
->pp_children
,
158 p_item
->p_parent
= p_parent
;
160 /* Inherit special flags from parent (sd cases) */
161 if( ( p_parent
->i_flags
& PLAYLIST_NO_INHERIT_FLAG
) == 0 )
162 p_item
->i_flags
|= (p_parent
->i_flags
& PLAYLIST_RO_FLAG
);
168 * Search a child of a node by its name
170 * \note The playlist must be locked, and the result is only valid until the
171 * playlist is unlocked.
173 * \param p_node the node
174 * \param psz_search the name of the child to search
175 * \return the child item or NULL if not found or error
177 playlist_item_t
*playlist_ChildSearchName( playlist_item_t
*p_node
,
178 const char *psz_search
)
182 if( p_node
->i_children
< 0 )
186 for( i
= 0 ; i
< p_node
->i_children
; i
++ )
188 if( !strcmp( p_node
->pp_children
[i
]->p_input
->psz_name
, psz_search
) )
190 return p_node
->pp_children
[i
];
196 /**********************************************************************
197 * Tree walking functions
198 **********************************************************************/
200 * Finds the next item to play
202 * \param p_playlist the playlist
203 * \param p_root the root node
204 * \param p_item the previous item (NULL if none )
205 * \return the next item to play, or NULL if none found
207 playlist_item_t
*playlist_GetNextLeaf( playlist_t
*p_playlist
,
208 playlist_item_t
*p_root
,
209 playlist_item_t
*p_item
,
210 bool b_ena
, bool b_unplayed
)
213 playlist_item_t
*p_next
;
215 assert( p_root
&& p_root
->i_children
!= -1 );
217 PL_DEBUG2( "finding next of %s within %s",
218 PLI_NAME( p_item
), PLI_NAME( p_root
) );
220 /* Now, walk the tree until we find a suitable next item */
224 bool b_ena_ok
= true, b_unplayed_ok
= true;
225 p_next
= GetNextItem( p_playlist
, p_root
, p_next
);
226 if( !p_next
|| p_next
== p_root
)
228 if( p_next
->i_children
== -1 )
230 if( b_ena
&& p_next
->i_flags
& PLAYLIST_DBL_FLAG
)
232 if( b_unplayed
&& p_next
->i_nb_played
!= 0 )
233 b_unplayed_ok
= false;
234 if( b_ena_ok
&& b_unplayed_ok
) break;
237 if( p_next
== NULL
) PL_DEBUG2( "at end of node" );
241 /************************************************************************
242 * Following functions are local
243 ***********************************************************************/
246 * Get the next item in the tree
247 * If p_item is NULL, return the first child of root
249 playlist_item_t
*GetNextItem( playlist_t
*p_playlist
,
250 playlist_item_t
*p_root
,
251 playlist_item_t
*p_item
)
253 /* If the item is NULL, return the firt child of root */
256 if( p_root
->i_children
> 0 )
257 return p_root
->pp_children
[0];
262 /* Node with children, get the first one */
263 if( p_item
->i_children
> 0 )
264 return p_item
->pp_children
[0];
266 playlist_item_t
* p_parent
= p_item
->p_parent
;
267 for( int i
= 0 ; i
< p_parent
->i_children
; i
++ )
269 if( p_parent
->pp_children
[i
] == p_item
)
271 // Return the next children
272 if( i
+ 1 < p_parent
->i_children
)
273 return p_parent
->pp_children
[i
+1];
274 // We are the least one, so try to have uncles
277 PL_DEBUG2( "Current item is the last of the node,"
278 "looking for uncle from %s",
279 p_parent
->p_input
->psz_name
);
280 if( p_parent
== p_root
)
282 PL_DEBUG2( "already at root" );
286 return GetNextUncle( p_playlist
, p_item
, p_root
);
293 playlist_item_t
*GetNextUncle( playlist_t
*p_playlist
, playlist_item_t
*p_item
,
294 playlist_item_t
*p_root
)
296 playlist_item_t
*p_parent
= p_item
->p_parent
;
297 playlist_item_t
*p_grandparent
;
298 bool b_found
= false;
302 if( p_parent
!= NULL
)
304 p_grandparent
= p_parent
->p_parent
;
305 while( p_grandparent
)
308 for( i
= 0 ; i
< p_grandparent
->i_children
; i
++ )
310 if( p_parent
== p_grandparent
->pp_children
[i
] )
312 PL_DEBUG2( "parent %s found as child %i of grandparent %s",
313 p_parent
->p_input
->psz_name
, i
,
314 p_grandparent
->p_input
->psz_name
);
319 if( b_found
&& i
+ 1 < p_grandparent
->i_children
)
321 return p_grandparent
->pp_children
[i
+1];
323 /* Not found at root */
324 if( p_grandparent
== p_root
)
330 p_parent
= p_grandparent
;
331 p_grandparent
= p_parent
->p_parent
;
335 /* We reached root */
339 playlist_item_t
*GetPrevUncle( playlist_t
*p_playlist
, playlist_item_t
*p_item
,
340 playlist_item_t
*p_root
)
342 playlist_item_t
*p_parent
= p_item
->p_parent
;
343 playlist_item_t
*p_grandparent
;
344 bool b_found
= false;
348 if( p_parent
!= NULL
)
350 p_grandparent
= p_parent
->p_parent
;
354 for( i
= p_grandparent
->i_children
-1 ; i
>= 0; i
-- )
356 if( p_parent
== p_grandparent
->pp_children
[i
] )
362 if( b_found
&& i
- 1 > 0 )
364 return p_grandparent
->pp_children
[i
-1];
366 /* Not found at root */
367 if( p_grandparent
== p_root
)
373 p_parent
= p_grandparent
;
374 p_grandparent
= p_parent
->p_parent
;
378 /* We reached root */
383 /* Recursively search the tree for previous item */
384 playlist_item_t
*GetPrevItem( playlist_t
*p_playlist
,
385 playlist_item_t
*p_root
,
386 playlist_item_t
*p_item
)
388 playlist_item_t
*p_parent
;
391 /* Node with children, get the last one */
392 if( p_item
&& p_item
->i_children
> 0 )
393 return p_item
->pp_children
[p_item
->i_children
- 1];
395 /* Last child of its parent ? */
397 p_parent
= p_item
->p_parent
;
400 msg_Err( p_playlist
, "Get the last one" );
404 for( i
= p_parent
->i_children
-1 ; i
>= 0 ; i
-- )
406 if( p_parent
->pp_children
[i
] == p_item
)
410 /* Was already the first sibling. Look for uncles */
411 PL_DEBUG2( "current item is the first of its node,"
412 "looking for uncle from %s",
413 p_parent
->p_input
->psz_name
);
414 if( p_parent
== p_root
)
416 PL_DEBUG2( "already at root" );
419 return GetPrevUncle( p_playlist
, p_item
, p_root
);
423 return p_parent
->pp_children
[i
-1];