1 /*****************************************************************************
2 * vlc_arrays.h : Arrays and data structures handling
3 *****************************************************************************
4 * Copyright (C) 1999-2004 VLC authors and VideoLAN
7 * Authors: Samuel Hocevar <sam@zoy.org>
8 * Clément Stenac <zorglub@videolan.org>
10 * This program is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU Lesser General Public License as published by
12 * the Free Software Foundation; either version 2.1 of the License, or
13 * (at your option) any later version.
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU Lesser General Public License for more details.
20 * You should have received a copy of the GNU Lesser General Public License
21 * along with this program; if not, write to the Free Software Foundation,
22 * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
23 *****************************************************************************/
30 * This file defines functions, structures and macros for handling arrays in vlc
33 /* realloc() that never fails *if* downsizing */
34 static inline void *realloc_down( void *ptr
, size_t size
)
36 void *ret
= realloc( ptr
, size
);
37 return ret
? ret
: ptr
;
41 * This wrapper around realloc() will free the input pointer when
42 * realloc() returns NULL. The use case ptr = realloc(ptr, newsize) will
43 * cause a memory leak when ptr pointed to a heap allocation before,
44 * leaving the buffer allocated but unreferenced. vlc_realloc() is a
45 * drop-in replacement for that use case (and only that use case).
47 static inline void *realloc_or_free( void *p
, size_t sz
)
49 void *n
= realloc(p
,sz
);
55 #define TAB_INIT( count, tab ) \
61 #define TAB_CLEAN( count, tab ) \
68 #define TAB_APPEND_CAST( cast, count, tab, p ) \
71 (tab) = cast realloc( tab, sizeof( *(tab) ) * ( (count) + 1 ) ); \
73 (tab) = cast malloc( sizeof( *(tab) ) ); \
74 if( !(tab) ) abort(); \
79 #define TAB_APPEND( count, tab, p ) \
80 TAB_APPEND_CAST( , count, tab, p )
82 #define TAB_FIND( count, tab, p, idx ) \
84 for( (idx) = 0; (idx) < (count); (idx)++ ) \
85 if( (tab)[(idx)] == (p) ) \
87 if( (idx) >= (count) ) \
92 #define TAB_ERASE( count, tab, index ) \
95 memmove( (tab) + (index), \
96 (tab) + (index) + 1, \
97 ((count) - (index) - 1 ) * sizeof( *(tab) ) );\
106 #define TAB_REMOVE( count, tab, p ) \
109 TAB_FIND( count, tab, p, i_index ); \
111 TAB_ERASE( count, tab, i_index ); \
114 #define TAB_INSERT_CAST( cast, count, tab, p, index ) do { \
116 (tab) = cast realloc( tab, sizeof( *(tab) ) * ( (count) + 1 ) ); \
118 (tab) = cast malloc( sizeof( *(tab) ) ); \
119 if( !(tab) ) abort(); \
120 if( (count) - (index) > 0 ) \
121 memmove( (tab) + (index) + 1, \
123 ((count) - (index)) * sizeof( *(tab) ) );\
124 (tab)[(index)] = (p); \
128 #define TAB_INSERT( count, tab, p, index ) \
129 TAB_INSERT_CAST( , count, tab, p, index )
132 * Binary search in a sorted array. The key must be comparable by < and >
133 * \param entries array of entries
134 * \param count number of entries
135 * \param elem key to check within an entry (like .id, or ->i_id)
136 * \param zetype type of the key
137 * \param key value of the key
138 * \param answer index of answer within the array. -1 if not found
140 #define BSEARCH( entries, count, elem, zetype, key, answer ) \
142 int low = 0, high = count - 1; \
144 while( low <= high ) {\
145 int mid = ((unsigned int)low + (unsigned int)high) >> 1;\
146 zetype mid_val = entries[mid] elem;\
147 if( mid_val < key ) \
149 else if ( mid_val > key ) \
153 answer = mid; break; \
159 /************************************************************************
160 * Dynamic arrays with progressive allocation
161 ************************************************************************/
163 /* Internal functions */
164 #define _ARRAY_ALLOC(array, newsize) { \
165 (array).i_alloc = newsize; \
166 (array).p_elems = realloc( (array).p_elems, (array).i_alloc * \
167 sizeof(*(array).p_elems) ); \
168 if( !(array).p_elems ) abort(); \
171 #define _ARRAY_GROW1(array) { \
172 if( (array).i_alloc < 10 ) \
173 _ARRAY_ALLOC(array, 10 ) \
174 else if( (array).i_alloc == (array).i_size ) \
175 _ARRAY_ALLOC(array, (int)((array).i_alloc * 1.5) ) \
178 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
181 #define DECL_ARRAY(type) struct { \
187 #define TYPEDEF_ARRAY(type, name) typedef DECL_ARRAY(type) name;
189 #define ARRAY_INIT(array) \
191 (array).i_alloc = 0; \
192 (array).i_size = 0; \
193 (array).p_elems = NULL; \
196 #define ARRAY_RESET(array) \
198 (array).i_alloc = 0; \
199 (array).i_size = 0; \
200 free( (array).p_elems ); (array).p_elems = NULL; \
203 #define ARRAY_APPEND(array, elem) \
205 _ARRAY_GROW1(array); \
206 (array).p_elems[(array).i_size] = elem; \
210 #define ARRAY_INSERT(array,elem,pos) \
212 _ARRAY_GROW1(array); \
213 if( (array).i_size - (pos) ) { \
214 memmove( (array).p_elems + (pos) + 1, (array).p_elems + (pos), \
215 ((array).i_size-(pos)) * sizeof(*(array).p_elems) ); \
217 (array).p_elems[pos] = elem; \
221 #define _ARRAY_SHRINK(array) { \
222 if( (array).i_size > 10 && (array).i_size < (int)((array).i_alloc / 1.5) ) { \
223 _ARRAY_ALLOC(array, (array).i_size + 5); \
227 #define ARRAY_FIND(array, p, idx) \
228 TAB_FIND((array).i_size, (array).p_elems, p, idx)
230 #define ARRAY_REMOVE(array,pos) \
232 if( (array).i_size - (pos) - 1 ) \
234 memmove( (array).p_elems + (pos), (array).p_elems + (pos) + 1, \
235 ( (array).i_size - (pos) - 1 ) *sizeof(*(array).p_elems) );\
238 _ARRAY_SHRINK(array); \
241 #define ARRAY_VAL(array, pos) array.p_elems[pos]
243 #define ARRAY_BSEARCH(array, elem, zetype, key, answer) \
244 BSEARCH( (array).p_elems, (array).i_size, elem, zetype, key, answer)
246 /* append ##item to index variable name to avoid variable shadowing warnings for
248 #define ARRAY_FOREACH(item, array) \
249 for (int array_index_##item = 0; \
250 array_index_##item < (array).i_size && \
251 ((item) = (array).p_elems[array_index_##item], 1); \
252 ++array_index_##item)
255 /************************************************************************
256 * Dynamic arrays with progressive allocation (Preferred API)
257 ************************************************************************/
258 typedef struct vlc_array_t
264 static inline void vlc_array_init( vlc_array_t
* p_array
)
266 p_array
->i_count
= 0;
267 p_array
->pp_elems
= NULL
;
270 static inline void vlc_array_clear( vlc_array_t
* p_array
)
272 free( p_array
->pp_elems
);
273 vlc_array_init( p_array
);
277 static inline size_t vlc_array_count( vlc_array_t
* p_array
)
279 return p_array
->i_count
;
283 # define vlc_array_item_at_index(ar, idx) \
285 const vlc_array_t *: ((ar)->pp_elems[idx]), \
286 vlc_array_t *: ((ar)->pp_elems[idx]))
288 static inline void *vlc_array_item_at_index( vlc_array_t
*ar
, size_t idx
)
290 return ar
->pp_elems
[idx
];
293 static inline const void *vlc_array_item_at_index( const vlc_array_t
*ar
,
296 return ar
->pp_elems
[idx
];
300 static inline ssize_t
vlc_array_index_of_item( const vlc_array_t
*ar
,
303 for( size_t i
= 0; i
< ar
->i_count
; i
++ )
305 if( ar
->pp_elems
[i
] == elem
)
312 static inline int vlc_array_insert( vlc_array_t
*ar
, void *elem
, int idx
)
314 void **pp
= (void **)realloc( ar
->pp_elems
,
315 sizeof( void * ) * (ar
->i_count
+ 1) );
316 if( unlikely(pp
== NULL
) )
319 size_t tail
= ar
->i_count
- idx
;
321 memmove( pp
+ idx
+ 1, pp
+ idx
, sizeof( void * ) * tail
);
329 static inline void vlc_array_insert_or_abort( vlc_array_t
*ar
, void *elem
, int idx
)
331 if( vlc_array_insert( ar
, elem
, idx
) )
335 static inline int vlc_array_append( vlc_array_t
*ar
, void *elem
)
337 void **pp
= (void **)realloc( ar
->pp_elems
,
338 sizeof( void * ) * (ar
->i_count
+ 1) );
339 if( unlikely(pp
== NULL
) )
342 pp
[ar
->i_count
++] = elem
;
347 static inline void vlc_array_append_or_abort( vlc_array_t
*ar
, void *elem
)
349 if( vlc_array_append( ar
, elem
) != 0 )
353 static inline void vlc_array_remove( vlc_array_t
*ar
, size_t idx
)
355 void **pp
= ar
->pp_elems
;
356 size_t tail
= ar
->i_count
- idx
- 1;
359 memmove( pp
+ idx
, pp
+ idx
+ 1, sizeof( void * ) * tail
);
363 if( ar
->i_count
> 0 )
365 pp
= (void **)realloc( pp
, sizeof( void * ) * ar
->i_count
);
366 if( likely(pp
!= NULL
) )
377 /************************************************************************
379 ************************************************************************/
381 /* This function is not intended to be crypto-secure, we only want it to be
382 * fast and not suck too much. This one is pretty fast and did 0 collisions
383 * in wenglish's dictionary.
385 static inline uint64_t DictHash( const char *psz_string
, int hashsize
)
392 i_hash
+= *psz_string
++;
393 i_hash
+= i_hash
<< 10;
394 i_hash
^= i_hash
>> 8;
397 return i_hash
% hashsize
;
400 typedef struct vlc_dictionary_entry_t
404 struct vlc_dictionary_entry_t
* p_next
;
405 } vlc_dictionary_entry_t
;
407 typedef struct vlc_dictionary_t
410 vlc_dictionary_entry_t
** p_entries
;
413 static void * const kVLCDictionaryNotFound
= NULL
;
415 static inline void vlc_dictionary_init( vlc_dictionary_t
* p_dict
, int i_size
)
417 p_dict
->p_entries
= NULL
;
421 p_dict
->p_entries
= (vlc_dictionary_entry_t
**)calloc( i_size
, sizeof(*p_dict
->p_entries
) );
422 if( !p_dict
->p_entries
)
425 p_dict
->i_size
= i_size
;
428 static inline void vlc_dictionary_clear( vlc_dictionary_t
* p_dict
,
429 void ( * pf_free
)( void * p_data
, void * p_obj
),
432 if( p_dict
->p_entries
)
434 for( int i
= 0; i
< p_dict
->i_size
; i
++ )
436 vlc_dictionary_entry_t
* p_current
, * p_next
;
437 p_current
= p_dict
->p_entries
[i
];
440 p_next
= p_current
->p_next
;
441 if( pf_free
!= NULL
)
442 ( * pf_free
)( p_current
->p_value
, p_obj
);
443 free( p_current
->psz_key
);
448 free( p_dict
->p_entries
);
449 p_dict
->p_entries
= NULL
;
455 vlc_dictionary_has_key( const vlc_dictionary_t
* p_dict
, const char * psz_key
)
457 if( !p_dict
->p_entries
)
460 int i_pos
= DictHash( psz_key
, p_dict
->i_size
);
461 const vlc_dictionary_entry_t
* p_entry
= p_dict
->p_entries
[i_pos
];
462 for( ; p_entry
!= NULL
; p_entry
= p_entry
->p_next
)
464 if( !strcmp( psz_key
, p_entry
->psz_key
) )
467 return p_entry
!= NULL
;
471 vlc_dictionary_value_for_key( const vlc_dictionary_t
* p_dict
, const char * psz_key
)
473 if( !p_dict
->p_entries
)
474 return kVLCDictionaryNotFound
;
476 int i_pos
= DictHash( psz_key
, p_dict
->i_size
);
477 vlc_dictionary_entry_t
* p_entry
= p_dict
->p_entries
[i_pos
];
480 return kVLCDictionaryNotFound
;
482 /* Make sure we return the right item. (Hash collision) */
484 if( !strcmp( psz_key
, p_entry
->psz_key
) )
485 return p_entry
->p_value
;
486 p_entry
= p_entry
->p_next
;
489 return kVLCDictionaryNotFound
;
493 vlc_dictionary_keys_count( const vlc_dictionary_t
* p_dict
)
495 vlc_dictionary_entry_t
* p_entry
;
498 if( !p_dict
->p_entries
)
501 for( i
= 0; i
< p_dict
->i_size
; i
++ )
503 for( p_entry
= p_dict
->p_entries
[i
]; p_entry
; p_entry
= p_entry
->p_next
) count
++;
509 vlc_dictionary_is_empty( const vlc_dictionary_t
* p_dict
)
511 if( p_dict
->p_entries
)
512 for( int i
= 0; i
< p_dict
->i_size
; i
++ )
513 if( p_dict
->p_entries
[i
] )
518 static inline char **
519 vlc_dictionary_all_keys( const vlc_dictionary_t
* p_dict
)
521 vlc_dictionary_entry_t
* p_entry
;
523 int i
, count
= vlc_dictionary_keys_count( p_dict
);
525 ppsz_ret
= (char**)malloc(sizeof(char *) * (count
+ 1));
526 if( unlikely(!ppsz_ret
) )
530 for( i
= 0; i
< p_dict
->i_size
; i
++ )
532 for( p_entry
= p_dict
->p_entries
[i
]; p_entry
; p_entry
= p_entry
->p_next
)
533 ppsz_ret
[count
++] = strdup( p_entry
->psz_key
);
535 ppsz_ret
[count
] = NULL
;
540 vlc_dictionary_insert_impl_( vlc_dictionary_t
* p_dict
, const char * psz_key
,
541 void * p_value
, bool rebuild
)
543 if( !p_dict
->p_entries
)
544 vlc_dictionary_init( p_dict
, 1 );
546 int i_pos
= DictHash( psz_key
, p_dict
->i_size
);
547 vlc_dictionary_entry_t
* p_entry
;
549 p_entry
= (vlc_dictionary_entry_t
*)malloc(sizeof(*p_entry
));
550 p_entry
->psz_key
= strdup( psz_key
);
551 p_entry
->p_value
= p_value
;
552 p_entry
->p_next
= p_dict
->p_entries
[i_pos
];
553 p_dict
->p_entries
[i_pos
] = p_entry
;
556 /* Count how many items there was */
558 for( count
= 1; p_entry
->p_next
; count
++ )
559 p_entry
= p_entry
->p_next
;
560 if( count
> 3 ) /* XXX: this need tuning */
562 /* Here it starts to be not good, rebuild a bigger dictionary */
563 struct vlc_dictionary_t new_dict
;
564 int i_new_size
= ( (p_dict
->i_size
+2) * 3) / 2; /* XXX: this need tuning */
566 vlc_dictionary_init( &new_dict
, i_new_size
);
567 for( i
= 0; i
< p_dict
->i_size
; i
++ )
569 p_entry
= p_dict
->p_entries
[i
];
572 vlc_dictionary_insert_impl_( &new_dict
, p_entry
->psz_key
,
574 false /* To avoid multiple rebuild loop */);
575 p_entry
= p_entry
->p_next
;
579 vlc_dictionary_clear( p_dict
, NULL
, NULL
);
580 p_dict
->i_size
= new_dict
.i_size
;
581 p_dict
->p_entries
= new_dict
.p_entries
;
587 vlc_dictionary_insert( vlc_dictionary_t
* p_dict
, const char * psz_key
, void * p_value
)
589 vlc_dictionary_insert_impl_( p_dict
, psz_key
, p_value
, true );
593 vlc_dictionary_remove_value_for_key( const vlc_dictionary_t
* p_dict
, const char * psz_key
,
594 void ( * pf_free
)( void * p_data
, void * p_obj
),
597 if( !p_dict
->p_entries
)
600 int i_pos
= DictHash( psz_key
, p_dict
->i_size
);
601 vlc_dictionary_entry_t
* p_entry
= p_dict
->p_entries
[i_pos
];
602 vlc_dictionary_entry_t
* p_prev
;
605 return; /* Not found, nothing to do */
610 if( !strcmp( psz_key
, p_entry
->psz_key
) )
612 if( pf_free
!= NULL
)
613 ( * pf_free
)( p_entry
->p_value
, p_obj
);
615 p_dict
->p_entries
[i_pos
] = p_entry
->p_next
;
617 p_prev
->p_next
= p_entry
->p_next
;
618 free( p_entry
->psz_key
);
623 p_entry
= p_entry
->p_next
;
626 /* No key was found */
631 template <typename T
>
632 void vlc_delete_all( T
&container
)
634 typename
T::iterator it
= container
.begin();
635 while ( it
!= container
.end() )