vlc | branch: master | Rémi Denis-Courmont <r...@remlab.net> | Fri Nov 18 22:09:42 2016 +0200| [303001492a85db6fdf9611a7f3f1be6b9f397627] | committer: Rémi Denis-Courmont
playlist: use search trees for ID and input to item mapping Regarding input item look-ups, this reduces asymptotic complexity from linear to logarithmic time. Regarding ID look-ups, this reduces insertion and deletion time to logarithmic. Previously it degraded to linear time because of memcpy() and memmove() in ARRAY_APPEND and ARRAY_REMOVE macros. This removes the "all_items" array, and its missing error handlers. Finally, this adds support for allocating more than INT_MAX items during the entire lifetime of the VLC instance. (The maximum number of _concurrent_ items is still INT_MAX, but memory would probably run out before that is reached.) Note: Item deletion still requires linear time. And playlist deletion still consequently requires quadractic time because of the "current" array. > http://git.videolan.org/gitweb.cgi/vlc.git/?a=commit;h=303001492a85db6fdf9611a7f3f1be6b9f397627 --- src/playlist/engine.c | 3 --- src/playlist/item.c | 54 +++++++++++++++++++++++++++++++++++++++- src/playlist/playlist_internal.h | 2 -- src/playlist/search.c | 46 ---------------------------------- src/playlist/tree.c | 5 ---- 5 files changed, 53 insertions(+), 57 deletions(-) diff --git a/src/playlist/engine.c b/src/playlist/engine.c index d86ac30..dc5eff2 100644 --- a/src/playlist/engine.c +++ b/src/playlist/engine.c @@ -225,7 +225,6 @@ playlist_t *playlist_Create( vlc_object_t *p_parent ) pl_priv(p_playlist)->p_input = NULL; ARRAY_INIT( p_playlist->items ); - ARRAY_INIT( p->all_items ); ARRAY_INIT( p_playlist->current ); p_playlist->i_current_index = 0; @@ -336,8 +335,6 @@ void playlist_Destroy( playlist_t *p_playlist ) vlc_cond_destroy( &p_sys->signal ); vlc_mutex_destroy( &p_sys->lock ); - ARRAY_RESET( p_sys->all_items ); - ARRAY_RESET( p_playlist->items ); ARRAY_RESET( p_playlist->current ); diff --git a/src/playlist/item.c b/src/playlist/item.c index 5d56956..4231cb9 100644 --- a/src/playlist/item.c +++ b/src/playlist/item.c @@ -375,6 +375,59 @@ void playlist_ItemRelease( playlist_t *p_playlist, playlist_item_t *p_item ) } /** + * Finds a playlist item by ID. + * + * Searches for a playlist item with the given ID. + * + * \note The playlist must be locked, and the result is only valid until the + * playlist is unlocked. + * + * \warning If an item with the given ID is deleted, it is unlikely but + * possible that another item will get the same ID. This can result in + * mismatches. + * Where holding a reference to an input item is a viable option, then + * playlist_ItemGetByInput() should be used instead - to avoid this issue. + * + * @param p_playlist the playlist + * @param id ID to look for + * @return the matching item or NULL if not found + */ +playlist_item_t *playlist_ItemGetById( playlist_t *p_playlist , int id ) +{ + playlist_private_t *p = pl_priv(p_playlist); + playlist_item_t key, **pp; + + PL_ASSERT_LOCKED; + key.i_id = id; + pp = tfind( &key, &p->id_tree, playlist_ItemCmpId ); + return (pp != NULL) ? *pp : NULL; +} + +/** + * Finds a playlist item by input item. + * + * Searches for a playlist item for the given input item. + * + * \note The playlist must be locked, and the result is only valid until the + * playlist is unlocked. + * + * \param p_playlist the playlist + * \param item input item to look for + * \return the playlist item or NULL on failure + */ +playlist_item_t *playlist_ItemGetByInput( playlist_t * p_playlist, + const input_item_t *item ) +{ + playlist_private_t *p = pl_priv(p_playlist); + playlist_item_t key, **pp; + + PL_ASSERT_LOCKED; + key.p_input = (input_item_t *)item; + pp = tfind( &key, &p->input_tree, playlist_ItemCmpInput ); + return (pp != NULL) ? *pp : NULL; +} + +/** * Clear the playlist * * \param p_playlist playlist object @@ -780,7 +833,6 @@ static void AddItem( playlist_t *p_playlist, playlist_item_t *p_item, { PL_ASSERT_LOCKED; ARRAY_APPEND(p_playlist->items, p_item); - ARRAY_APPEND(pl_priv(p_playlist)->all_items, p_item); playlist_NodeInsert( p_playlist, p_item, p_node, i_pos ); playlist_SendAddNotify( p_playlist, p_item, diff --git a/src/playlist/playlist_internal.h b/src/playlist/playlist_internal.h index 1113f26..1395466 100644 --- a/src/playlist/playlist_internal.h +++ b/src/playlist/playlist_internal.h @@ -53,8 +53,6 @@ typedef struct playlist_private_t to playlist item mapping */ void *id_tree; /**< Search tree for item ID to item mapping */ - playlist_item_array_t all_items; /**< Array of items and nodes */ - vlc_sd_internal_t **pp_sds; int i_sds; /**< Number of service discovery modules */ input_thread_t * p_input; /**< the input thread associated diff --git a/src/playlist/search.c b/src/playlist/search.c index 0853b92..ee09ca8 100644 --- a/src/playlist/search.c +++ b/src/playlist/search.c @@ -34,52 +34,6 @@ * Item search functions ***************************************************************************/ -/** - * Search a playlist item by its playlist_item id. - * The playlist have to be locked - * @param p_playlist: the playlist - * @param i_id: the id to find - * @return the item or NULL on failure - */ -playlist_item_t* playlist_ItemGetById( playlist_t * p_playlist , int i_id ) -{ - int i; - PL_ASSERT_LOCKED; - ARRAY_BSEARCH( pl_priv(p_playlist)->all_items,->i_id, int, i_id, i ); - if( i != -1 ) - return ARRAY_VAL( pl_priv(p_playlist)->all_items, i ); - else - return NULL; -} - -/** - * Search an item by its input_item_t - * The playlist have to be locked - * @param p_playlist: the playlist - * @param p_item: the input_item_t to find - * @return the item, or NULL on failure - */ -playlist_item_t* playlist_ItemGetByInput( playlist_t * p_playlist, - const input_item_t *p_item ) -{ - PL_ASSERT_LOCKED; - if( get_current_status_item( p_playlist ) && - get_current_status_item( p_playlist )->p_input == p_item ) - { - return get_current_status_item( p_playlist ); - } - /** \todo Check if this is always incremental and whether we can bsearch */ - for( int i = 0 ; i < pl_priv(p_playlist)->all_items.i_size; i++ ) - { - if( ARRAY_VAL(pl_priv(p_playlist)->all_items, i)->p_input == p_item ) - { - return ARRAY_VAL(pl_priv(p_playlist)->all_items, i); - } - } - return NULL; -} - - /*************************************************************************** * Live search handling ***************************************************************************/ diff --git a/src/playlist/tree.c b/src/playlist/tree.c index 2496c8f..4ff5a7d 100644 --- a/src/playlist/tree.c +++ b/src/playlist/tree.c @@ -74,8 +74,6 @@ playlist_item_t * playlist_NodeCreate( playlist_t *p_playlist, if( p_item == NULL ) return NULL; p_item->i_children = 0; - ARRAY_APPEND(pl_priv(p_playlist)->all_items, p_item); - if( p_parent != NULL ) playlist_NodeInsert( p_playlist, p_item, p_parent, i_pos ); playlist_SendAddNotify( p_playlist, p_item, @@ -109,9 +107,6 @@ void playlist_NodeDelete( playlist_t *p_playlist, playlist_item_t *p_root, int i; var_SetAddress( p_playlist, "playlist-item-deleted", p_root ); - ARRAY_BSEARCH( pl_priv(p_playlist)->all_items, ->i_id, int, p_root->i_id, i ); - if( i != -1 ) - ARRAY_REMOVE( pl_priv(p_playlist)->all_items, i ); if( p_root->i_children == -1 ) { ARRAY_BSEARCH( p_playlist->items,->i_id, int, p_root->i_id, i ); _______________________________________________ vlc-commits mailing list vlc-commits@videolan.org https://mailman.videolan.org/listinfo/vlc-commits
