tree.c 20.3 KB
Newer Older
1
2
3
/*****************************************************************************
 * tree.c : Playlist tree walking functions
 *****************************************************************************
4
 * Copyright (C) 1999-2007 the VideoLAN team
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 * $Id$
 *
 * Authors: Clément Stenac <zorglub@videolan.org>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
 *****************************************************************************/
23
24
25
26
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif

27
#include <vlc/vlc.h>
28
#include <assert.h>
29
#include "vlc_playlist.h"
30
#include "playlist_internal.h"
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

/************************************************************************
 * Local prototypes
 ************************************************************************/
playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
                               playlist_item_t *p_root );
playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
                               playlist_item_t *p_root );

playlist_item_t *GetNextItem( playlist_t *p_playlist,
                              playlist_item_t *p_root,
                              playlist_item_t *p_item );
playlist_item_t *GetPrevItem( playlist_t *p_playlist,
                              playlist_item_t *p_item,
                              playlist_item_t *p_root );

/**
 * Create a playlist node
 *
 * \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
56
 * \return the new node
 */
57
58
playlist_item_t * playlist_NodeCreate( playlist_t *p_playlist,
                                       const char *psz_name,
59
60
                                       playlist_item_t *p_parent, int i_flags,
                                       input_item_t *p_input )
61
{
62
    input_item_t *p_new_input;
63
64
    playlist_item_t *p_item;

65
    if( !psz_name ) psz_name = _("Undefined");
66
67
68
69
70
71

    if( !p_input )
        p_new_input = input_ItemNewWithType( VLC_OBJECT(p_playlist), NULL,
                                        psz_name, 0, NULL, -1, ITEM_TYPE_NODE );
    p_item = playlist_ItemNewFromInput( VLC_OBJECT(p_playlist),
                                        p_input ? p_input : p_new_input );
72
73
    if( !p_input )
        vlc_gc_decref( p_new_input );
74

zorglub's avatar
zorglub committed
75
    if( p_item == NULL )  return NULL;
76
    p_item->i_children = 0;
zorglub's avatar
zorglub committed
77
78

    ARRAY_APPEND(p_playlist->all_items, p_item);
79
80
81
82

    if( p_parent != NULL )
        playlist_NodeAppend( p_playlist, p_item, p_parent );
    playlist_SendAddNotify( p_playlist, p_item->i_id,
83
84
                            p_parent ? p_parent->i_id : -1,
                            !( i_flags & PLAYLIST_NO_REBUILD ));
85
86
87
88
89
90
91
92
93
94
95
96
97
98
    return p_item;
}

/**
 * Remove all the children of a node
 *
 * This function must be entered with the playlist lock
 *
 * \param p_playlist the playlist
 * \param p_root the node
 * \param b_delete_items do we have to delete the children items ?
 * \return VLC_SUCCESS or an error
 */
int playlist_NodeEmpty( playlist_t *p_playlist, playlist_item_t *p_root,
99
                        bool b_delete_items )
100
101
102
103
104
105
106
107
108
109
110
111
112
{
    int i;
    if( p_root->i_children == -1 )
    {
        return VLC_EGENERIC;
    }

    /* Delete the children */
    for( i =  p_root->i_children-1 ; i >= 0 ;i-- )
    {
        if( p_root->pp_children[i]->i_children > -1 )
        {
            playlist_NodeDelete( p_playlist, p_root->pp_children[i],
113
                                 b_delete_items , false );
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
        }
        else if( b_delete_items )
        {
            /* Delete the item here */
            playlist_DeleteFromItemId( p_playlist,
                                       p_root->pp_children[i]->i_id );
        }
    }
    return VLC_SUCCESS;
}

/**
 * Remove all the children of a node and removes the node
 *
 * \param p_playlist the playlist
 * \param p_root the node
 * \param b_delete_items do we have to delete the children items ?
 * \return VLC_SUCCESS or an error
 */
int playlist_NodeDelete( playlist_t *p_playlist, playlist_item_t *p_root,
134
                         bool b_delete_items, bool b_force )
135
{
136
137
    int i;

138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
    if( p_root->i_children == -1 )
    {
        return VLC_EGENERIC;
    }

    /* Delete the children */
    for( i =  p_root->i_children - 1 ; i >= 0; i-- )
    {
        if( p_root->pp_children[i]->i_children > -1 )
        {
            playlist_NodeDelete( p_playlist, p_root->pp_children[i],
                                 b_delete_items , b_force );
        }
        else if( b_delete_items )
        {
            playlist_DeleteFromItemId( p_playlist,
                                       p_root->pp_children[i]->i_id );
        }
    }
    /* Delete the node */
    if( p_root->i_flags & PLAYLIST_RO_FLAG && !b_force )
    {
    }
    else
    {
zorglub's avatar
zorglub committed
163
        int i;
164
        var_SetInteger( p_playlist, "item-deleted", p_root->i_id );
165
166
        ARRAY_BSEARCH( p_playlist->all_items, ->i_id, int,
                       p_root->i_id, i );
zorglub's avatar
zorglub committed
167
168
        if( i != -1 )
            ARRAY_REMOVE( p_playlist->all_items, i );
169
170
171
172
173

        /* Remove the item from its parent */
        if( p_root->p_parent )
            playlist_NodeRemoveItem( p_playlist, p_root, p_root->p_parent );

174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
        playlist_ItemDelete( p_root );
    }
    return VLC_SUCCESS;
}


/**
 * Adds an item to the children of a node
 *
 * \param p_playlist the playlist
 * \param p_item the item to append
 * \param p_parent the parent node
 * \return VLC_SUCCESS or an error
 */
int playlist_NodeAppend( playlist_t *p_playlist,
                         playlist_item_t *p_item,
                         playlist_item_t *p_parent )
{
    return playlist_NodeInsert( p_playlist, p_item, p_parent, -1 );
}

int playlist_NodeInsert( playlist_t *p_playlist,
                         playlist_item_t *p_item,
                         playlist_item_t *p_parent,
                         int i_position )
{
200
   (void)p_playlist;
201
   assert( p_parent && p_parent->i_children != -1 );
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
   if( i_position == -1 ) i_position = p_parent->i_children ;

   INSERT_ELEM( p_parent->pp_children,
                p_parent->i_children,
                i_position,
                p_item );
   p_item->p_parent = p_parent;
   return VLC_SUCCESS;
}

/**
 * Deletes an item from the children of a node
 *
 * \param p_playlist the playlist
 * \param p_item the item to remove
 * \param p_parent the parent node
 * \return VLC_SUCCESS or an error
 */
int playlist_NodeRemoveItem( playlist_t *p_playlist,
                        playlist_item_t *p_item,
                        playlist_item_t *p_parent )
{
224
225
226
   (void)p_playlist;

   for(int i= 0; i< p_parent->i_children ; i++ )
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
   {
       if( p_parent->pp_children[i] == p_item )
       {
           REMOVE_ELEM( p_parent->pp_children, p_parent->i_children, i );
       }
   }

   return VLC_SUCCESS;
}


/**
 * Count the children of a node
 *
 * \param p_playlist the playlist
 * \param p_node the node
 * \return the number of children
 */
int playlist_NodeChildrenCount( playlist_t *p_playlist, playlist_item_t*p_node)
{
    int i;
    int i_nb = 0;
249

250
251
252
    if( p_node->i_children == -1 )
        return 0;

253
    i_nb = p_node->i_children;
254
255
256
    for( i=0 ; i< p_node->i_children;i++ )
    {
        if( p_node->pp_children[i]->i_children == -1 )
Jean-Paul Saman's avatar
Jean-Paul Saman committed
257
            break;
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
        else
            i_nb += playlist_NodeChildrenCount( p_playlist,
                                                p_node->pp_children[i] );
    }
    return i_nb;
}

/**
 * Search a child of a node by its name
 *
 * \param p_node the node
 * \param psz_search the name of the child to search
 * \return the child item or NULL if not found or error
 */
playlist_item_t *playlist_ChildSearchName( playlist_item_t *p_node,
                                           const char *psz_search )
{
    int i;

    if( p_node->i_children < 0 )
    {
         return NULL;
    }
    for( i = 0 ; i< p_node->i_children; i++ )
    {
        if( !strcmp( p_node->pp_children[i]->p_input->psz_name, psz_search ) )
        {
            return p_node->pp_children[i];
        }
    }
    return NULL;
}

291
292
/**
 * Create a pair of nodes in the category and onelevel trees.
293
 * They share the same input item.
294
295
296
297
298
299
 * \param p_playlist the playlist
 * \param psz_name the name of the nodes
 * \param pp_node_cat pointer to return the node in category tree
 * \param pp_node_one pointer to return the node in onelevel tree
 * \param b_for_sd For Services Discovery ? (make node read-only and unskipping)
 */
Rémi Denis-Courmont's avatar
Rémi Denis-Courmont committed
300
void playlist_NodesPairCreate( playlist_t *p_playlist, const char *psz_name,
301
302
                               playlist_item_t **pp_node_cat,
                               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
309
                                        p_playlist->p_root_onelevel, 0,
                                        (*pp_node_cat)->p_input );
310
311
312
313
314
315
316
    if( b_for_sd )
    {
        (*pp_node_cat)->i_flags |= PLAYLIST_RO_FLAG;
        (*pp_node_cat)->i_flags |= PLAYLIST_SKIP_FLAG;
        (*pp_node_one)->i_flags |= PLAYLIST_RO_FLAG;
        (*pp_node_one)->i_flags |= PLAYLIST_SKIP_FLAG;
    }
317
318
}

319
320
/**
 * Get the node in the preferred tree from a node in one of category
321
 * or onelevel tree.
322
 */
323
324
325
326
327
328
playlist_item_t * playlist_GetPreferredNode( playlist_t *p_playlist,
                                             playlist_item_t *p_node )
{
    int i;
    if( p_node->p_parent == p_playlist->p_root_category )
    {
329
        if( p_playlist->b_tree )
330
            return p_node;
331
332
333
334
335
336
337
338
339
        for( i = 0 ; i< p_playlist->p_root_onelevel->i_children; i++ )
        {
            if( p_playlist->p_root_onelevel->pp_children[i]->p_input->i_id ==
                    p_node->p_input->i_id )
                return p_playlist->p_root_onelevel->pp_children[i];
        }
    }
    else if( p_node->p_parent == p_playlist->p_root_onelevel )
    {
340
        if( !p_playlist->b_tree )
341
342
343
344
345
346
347
348
349
350
            return p_node;
        for( i = 0 ; i< p_playlist->p_root_category->i_children; i++ )
        {
            if( p_playlist->p_root_category->pp_children[i]->p_input->i_id ==
                    p_node->p_input->i_id )
                return p_playlist->p_root_category->pp_children[i];
        }
    }
    return NULL;
}
351

352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
/**********************************************************************
 * Tree walking functions
 **********************************************************************/

playlist_item_t *playlist_GetLastLeaf(playlist_t *p_playlist,
                                      playlist_item_t *p_root )
{
    int i;
    playlist_item_t *p_item;
    for ( i = p_root->i_children - 1; i >= 0; i-- )
    {
        if( p_root->pp_children[i]->i_children == -1 )
            return p_root->pp_children[i];
        else if( p_root->pp_children[i]->i_children > 0)
        {
             p_item = playlist_GetLastLeaf( p_playlist,
                                            p_root->pp_children[i] );
            if ( p_item != NULL )
                return p_item;
        }
        else if( i == 0 )
            return NULL;
    }
    return NULL;
}

zorglub's avatar
zorglub committed
378
379
380
381
382
383
384
385
386
int playlist_GetAllEnabledChildren( playlist_t *p_playlist,
                                    playlist_item_t *p_node,
                                    playlist_item_t ***ppp_items )
{
    int i_count = 0;
    playlist_item_t *p_next = NULL;
    while( 1 )
    {
        p_next = playlist_GetNextLeaf( p_playlist, p_node,
387
                                       p_next, true, false );
zorglub's avatar
zorglub committed
388
389
390
391
392
393
394
395
        if( p_next )
            INSERT_ELEM( *ppp_items, i_count, i_count, p_next );
        else
            break;
    }
    return i_count;
}

396
397
398
399
400
401
402
403
404
405
/**
 * Finds the next item to play
 *
 * \param p_playlist the playlist
 * \param p_root the root node
 * \param p_item the previous item  (NULL if none )
 * \return the next item to play, or NULL if none found
 */
playlist_item_t *playlist_GetNextLeaf( playlist_t *p_playlist,
                                       playlist_item_t *p_root,
406
                                       playlist_item_t *p_item,
407
                                       bool b_ena, bool b_unplayed )
408
409
410
{
    playlist_item_t *p_next;

411
412
    assert( p_root && p_root->i_children != -1 );

413
414
    PL_DEBUG2( "finding next of %s within %s",
               PLI_NAME( p_item ), PLI_NAME( p_root ) );
415
416
417

    /* Now, walk the tree until we find a suitable next item */
    p_next = p_item;
418
    while( 1 )
419
    {
420
        bool b_ena_ok = true, b_unplayed_ok = true;
421
        p_next = GetNextItem( p_playlist, p_root, p_next );
422
423
424
425
426
        if( !p_next || p_next == p_root )
            break;
        if( p_next->i_children == -1 )
        {
            if( b_ena && p_next->i_flags & PLAYLIST_DBL_FLAG )
427
                b_ena_ok = false;
428
            if( b_unplayed && p_next->p_input->i_nb_played != 0 )
429
                b_unplayed_ok = false;
430
431
432
            if( b_ena_ok && b_unplayed_ok ) break;
        }
    }
433
    if( p_next == NULL ) PL_DEBUG2( "at end of node" );
434
435
436
437
438
439
440
441
442
443
444
445
446
    return p_next;
}

/**
 * Finds the previous item to play
 *
 * \param p_playlist the playlist
 * \param p_root the root node
 * \param p_item the previous item  (NULL if none )
 * \return the next item to play, or NULL if none found
 */
playlist_item_t *playlist_GetPrevLeaf( playlist_t *p_playlist,
                                       playlist_item_t *p_root,
447
                                       playlist_item_t *p_item,
448
                                       bool b_ena, bool b_unplayed )
449
450
451
{
    playlist_item_t *p_prev;

452
453
    PL_DEBUG2( "finding previous os %s within %s", PLI_NAME( p_item ),
                                                   PLI_NAME( p_root ) );
454
    assert( p_root && p_root->i_children != -1 );
455
456
457

    /* Now, walk the tree until we find a suitable previous item */
    p_prev = p_item;
458
    while( 1 )
459
    {
460
        bool b_ena_ok = true, b_unplayed_ok = true;
461
        p_prev = GetPrevItem( p_playlist, p_root, p_prev );
462
463
464
465
466
        if( !p_prev || p_prev == p_root )
            break;
        if( p_prev->i_children == -1 )
        {
            if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
467
                b_ena_ok = false;
468
            if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
469
                b_unplayed_ok = false;
470
471
472
            if( b_ena_ok && b_unplayed_ok ) break;
        }
    }
473
    if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
    return p_prev;
}

/************************************************************************
 * Following functions are local
 ***********************************************************************/

/**
 * Get the next item in the tree
 * If p_item is NULL, return the first child of root
 **/
playlist_item_t *GetNextItem( playlist_t *p_playlist,
                              playlist_item_t *p_root,
                              playlist_item_t *p_item )
{
    playlist_item_t *p_parent;
    int i;

    /* Node with children, get the first one */
    if( p_item && p_item->i_children > 0 )
        return p_item->pp_children[0];

    if( p_item != NULL )
        p_parent = p_item->p_parent;
    else
        p_parent = p_root;
    for( i= 0 ; i < p_parent->i_children ; i++ )
    {
        if( p_item == NULL || p_parent->pp_children[i] == p_item )
        {
            if( p_item == NULL )
                i = -1;

            if( i+1 >= p_parent->i_children )
            {
                /* Was already the last sibling. Look for uncles */
510
511
512
                PL_DEBUG2( "Current item is the last of the node,"
                           "looking for uncle from %s",
                            p_parent->p_input->psz_name );
zorglub's avatar
zorglub committed
513

514
515
                if( p_parent == p_root )
                {
516
                    PL_DEBUG2( "already at root" );
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
                    return NULL;
                }
                return GetNextUncle( p_playlist, p_item, p_root );
            }
            else
            {
                return  p_parent->pp_children[i+1];
            }
        }
    }
    return NULL;
}

playlist_item_t *GetNextUncle( playlist_t *p_playlist, playlist_item_t *p_item,
                               playlist_item_t *p_root )
{
    playlist_item_t *p_parent = p_item->p_parent;
    playlist_item_t *p_grandparent;
535
    bool b_found = false;
536

537
538
    (void)p_playlist;

539
540
541
    if( p_parent != NULL )
    {
        p_grandparent = p_parent->p_parent;
Rafaël Carré's avatar
Rafaël Carré committed
542
        while( p_grandparent )
543
544
545
546
547
548
        {
            int i;
            for( i = 0 ; i< p_grandparent->i_children ; i++ )
            {
                if( p_parent == p_grandparent->pp_children[i] )
                {
549
550
551
                    PL_DEBUG2( "parent %s found as child %i of grandparent %s",
                               p_parent->p_input->psz_name, i,
                               p_grandparent->p_input->psz_name );
552
                    b_found = true;
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
                    break;
                }
            }
            if( b_found && i + 1 < p_grandparent->i_children )
            {
                    return p_grandparent->pp_children[i+1];
            }
            /* Not found at root */
            if( p_grandparent == p_root )
            {
                return NULL;
            }
            else
            {
                p_parent = p_grandparent;
                p_grandparent = p_parent->p_parent;
            }
        }
    }
    /* We reached root */
    return NULL;
}

playlist_item_t *GetPrevUncle( playlist_t *p_playlist, playlist_item_t *p_item,
                               playlist_item_t *p_root )
{
    playlist_item_t *p_parent = p_item->p_parent;
    playlist_item_t *p_grandparent;
581
    bool b_found = false;
582

583
584
    (void)p_playlist;

585
586
587
588
589
590
591
592
593
594
    if( p_parent != NULL )
    {
        p_grandparent = p_parent->p_parent;
        while( 1 )
        {
            int i;
            for( i = p_grandparent->i_children -1 ; i >= 0; i-- )
            {
                if( p_parent == p_grandparent->pp_children[i] )
                {
595
                    b_found = true;
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
                    break;
                }
            }
            if( b_found && i - 1 > 0 )
            {
                return p_grandparent->pp_children[i-1];
            }
            /* Not found at root */
            if( p_grandparent == p_root )
            {
                return NULL;
            }
            else
            {
                p_parent = p_grandparent;
                p_grandparent = p_parent->p_parent;
            }
        }
    }
    /* We reached root */
    return NULL;
}


/* Recursively search the tree for previous item */
playlist_item_t *GetPrevItem( playlist_t *p_playlist,
                              playlist_item_t *p_root,
                              playlist_item_t *p_item )
{
    playlist_item_t *p_parent;
    int i;

    /* Node with children, get the last one */
    if( p_item && p_item->i_children > 0 )
        return p_item->pp_children[p_item->i_children - 1];

    /* Last child of its parent ? */
    if( p_item != NULL )
        p_parent = p_item->p_parent;
    else
    {
        msg_Err( p_playlist, "Get the last one" );
        abort();
    };

    for( i = p_parent->i_children -1 ; i >= 0 ;  i-- )
    {
        if( p_parent->pp_children[i] == p_item )
        {
            if( i-1 < 0 )
            {
zorglub's avatar
zorglub committed
647
               /* Was already the first sibling. Look for uncles */
648
649
650
                PL_DEBUG2( "current item is the first of its node,"
                           "looking for uncle from %s",
                           p_parent->p_input->psz_name );
zorglub's avatar
zorglub committed
651
652
                if( p_parent == p_root )
                {
653
                    PL_DEBUG2( "already at root" );
zorglub's avatar
zorglub committed
654
655
                    return NULL;
                }
656
657
658
659
660
661
662
663
664
665
                return GetPrevUncle( p_playlist, p_item, p_root );
            }
            else
            {
                return p_parent->pp_children[i-1];
            }
        }
    }
    return NULL;
}