tree.c 20.1 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_common.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 = NULL;
63 64
    playlist_item_t *p_item;

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

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

Clément Stenac's avatar
Clément Stenac committed
75
    if( p_item == NULL )  return NULL;
76
    p_item->i_children = 0;
Clément Stenac's avatar
Clément Stenac 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
    PL_ASSERT_LOCKED;
102 103 104 105 106 107 108 109 110 111 112 113
    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],
114
                                 b_delete_items , false );
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
        }
        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,
135
                         bool b_delete_items, bool b_force )
136
{
137
    PL_ASSERT_LOCKED;
138 139
    int i;

140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164
    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
    {
Clément Stenac's avatar
Clément Stenac committed
165
        int i;
166
        var_SetInteger( p_playlist, "item-deleted", p_root->i_id );
167 168
        ARRAY_BSEARCH( p_playlist->all_items, ->i_id, int,
                       p_root->i_id, i );
Clément Stenac's avatar
Clément Stenac committed
169 170
        if( i != -1 )
            ARRAY_REMOVE( p_playlist->all_items, i );
171 172 173 174 175

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

176
        playlist_ItemRelease( p_root );
177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201
    }
    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 )
{
202
    PL_ASSERT_LOCKED;
203
   (void)p_playlist;
204
   assert( p_parent && p_parent->i_children != -1 );
205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226
   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 )
{
227
    PL_ASSERT_LOCKED;
228 229 230
   (void)p_playlist;

   for(int i= 0; i< p_parent->i_children ; i++ )
231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250
   {
       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)
{
251
    PL_ASSERT_LOCKED;
252 253
    int i;
    int i_nb = 0;
254

255 256 257
    if( p_node->i_children == -1 )
        return 0;

258
    i_nb = p_node->i_children;
259 260 261
    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
262
            break;
263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279
        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 )
{
280 281
    playlist_t * p_playlist = p_node->p_playlist; /* For assert_locked */
    PL_ASSERT_LOCKED;
282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297
    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;
}

298 299
/**
 * Create a pair of nodes in the category and onelevel trees.
300
 * They share the same input item.
301 302 303 304 305 306
 * \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
307
void playlist_NodesPairCreate( playlist_t *p_playlist, const char *psz_name,
308 309
                               playlist_item_t **pp_node_cat,
                               playlist_item_t **pp_node_one,
310
                               bool b_for_sd )
311
{
312
    PL_ASSERT_LOCKED;
313
    *pp_node_cat = playlist_NodeCreate( p_playlist, psz_name,
314
                                        p_playlist->p_root_category, 0, NULL );
315
    *pp_node_one = playlist_NodeCreate( p_playlist, psz_name,
316 317
                                        p_playlist->p_root_onelevel, 0,
                                        (*pp_node_cat)->p_input );
318 319 320 321 322 323 324
    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;
    }
325 326
}

327 328
/**
 * Get the node in the preferred tree from a node in one of category
329
 * or onelevel tree.
330
 */
331 332 333
playlist_item_t * playlist_GetPreferredNode( playlist_t *p_playlist,
                                             playlist_item_t *p_node )
{
334
    PL_ASSERT_LOCKED;
335 336 337
    int i;
    if( p_node->p_parent == p_playlist->p_root_category )
    {
338
        if( p_playlist->b_tree )
339
            return p_node;
340 341 342 343 344 345 346 347 348
        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 )
    {
349
        if( !p_playlist->b_tree )
350 351 352 353 354 355 356 357 358 359
            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;
}
360

361 362 363 364 365 366 367
/**********************************************************************
 * Tree walking functions
 **********************************************************************/

playlist_item_t *playlist_GetLastLeaf(playlist_t *p_playlist,
                                      playlist_item_t *p_root )
{
368
    PL_ASSERT_LOCKED;
369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397
    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;
}

/**
 * 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,
398
                                       playlist_item_t *p_item,
399
                                       bool b_ena, bool b_unplayed )
400
{
401
    PL_ASSERT_LOCKED;
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",
               PLI_NAME( p_item ), PLI_NAME( p_root ) );
408 409 410

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

446 447
    PL_DEBUG2( "finding previous os %s within %s", PLI_NAME( p_item ),
                                                   PLI_NAME( p_root ) );
448
    assert( p_root && p_root->i_children != -1 );
449 450 451

    /* Now, walk the tree until we find a suitable previous item */
    p_prev = p_item;
452
    while( 1 )
453
    {
454
        bool b_ena_ok = true, b_unplayed_ok = true;
455
        p_prev = GetPrevItem( p_playlist, p_root, p_prev );
456 457 458 459 460
        if( !p_prev || p_prev == p_root )
            break;
        if( p_prev->i_children == -1 )
        {
            if( b_ena && p_prev->i_flags & PLAYLIST_DBL_FLAG )
461
                b_ena_ok = false;
462
            if( b_unplayed && p_prev->p_input->i_nb_played != 0 )
463
                b_unplayed_ok = false;
464 465 466
            if( b_ena_ok && b_unplayed_ok ) break;
        }
    }
467
    if( p_prev == NULL ) PL_DEBUG2( "at beginning of node" );
468 469 470 471 472 473 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
    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 */
504 505 506
                PL_DEBUG2( "Current item is the last of the node,"
                           "looking for uncle from %s",
                            p_parent->p_input->psz_name );
507

508 509
                if( p_parent == p_root )
                {
510
                    PL_DEBUG2( "already at root" );
511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528
                    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;
529
    bool b_found = false;
530

531 532
    (void)p_playlist;

533 534 535
    if( p_parent != NULL )
    {
        p_grandparent = p_parent->p_parent;
Rafaël Carré's avatar
Rafaël Carré committed
536
        while( p_grandparent )
537 538 539 540 541 542
        {
            int i;
            for( i = 0 ; i< p_grandparent->i_children ; i++ )
            {
                if( p_parent == p_grandparent->pp_children[i] )
                {
543 544 545
                    PL_DEBUG2( "parent %s found as child %i of grandparent %s",
                               p_parent->p_input->psz_name, i,
                               p_grandparent->p_input->psz_name );
546
                    b_found = true;
547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574
                    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;
575
    bool b_found = false;
576

577 578
    (void)p_playlist;

579 580 581 582 583 584 585 586 587 588
    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] )
                {
589
                    b_found = true;
590 591 592 593 594 595 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
                    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 )
            {
Clément Stenac's avatar
Clément Stenac committed
641
               /* Was already the first sibling. Look for uncles */
642 643 644
                PL_DEBUG2( "current item is the first of its node,"
                           "looking for uncle from %s",
                           p_parent->p_input->psz_name );
Clément Stenac's avatar
Clément Stenac committed
645 646
                if( p_parent == p_root )
                {
647
                    PL_DEBUG2( "already at root" );
Clément Stenac's avatar
Clément Stenac committed
648 649
                    return NULL;
                }
650 651 652 653 654 655 656 657 658 659
                return GetPrevUncle( p_playlist, p_item, p_root );
            }
            else
            {
                return p_parent->pp_children[i-1];
            }
        }
    }
    return NULL;
}