include/vlc_arrays.h

   1 /*****************************************************************************
   2  * vlc_arrays.h : Arrays and data structures handling
   3  *****************************************************************************
   4  * Copyright (C) 1999-2004 VLC authors and VideoLAN
   5  * $Id$
   6  *
   7  * Authors: Samuel Hocevar <sam@zoy.org>
   8  *          Clément Stenac <zorglub@videolan.org>
   9  *
  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.
  14  *
  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.
  19  *
  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  *****************************************************************************/
  24
  25 #ifndef VLC_ARRAYS_H_
  26 #define VLC_ARRAYS_H_
  27
  28 /**
  29  * \file
  30  * This file defines functions, structures and macros for handling arrays in vlc
  31  */
  32
  33 /* realloc() that never fails *if* downsizing */
  34 static inline void *realloc_down( void *ptr, size_t size )
  35 {
  36     void *ret = realloc( ptr, size );
  37     return ret ? ret : ptr;
  38 }
  39
  40 /**
  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).
  46  */
  47 static inline void *realloc_or_free( void *p, size_t sz )
  48 {
  49     void *n = realloc(p,sz);
  50     if( !n )
  51         free(p);
  52     return n;
  53 }
  54
  55 #define TAB_INIT( count, tab )                  \
  56   do {                                          \
  57     (count) = 0;                                \
  58     (tab) = NULL;                               \
  59   } while(0)
  60
  61 #define TAB_CLEAN( count, tab )                 \
  62   do {                                          \
  63     free( tab );                                \
  64     (count)= 0;                                 \
  65     (tab)= NULL;                                \
  66   } while(0)
  67
  68 #define TAB_APPEND_CAST( cast, count, tab, p )             \
  69   do {                                          \
  70     if( (count) > 0 )                           \
  71         (tab) = cast realloc( tab, sizeof( *(tab) ) * ( (count) + 1 ) ); \
  72     else                                        \
  73         (tab) = cast malloc( sizeof( *(tab) ) );    \
  74     if( !(tab) ) abort();                       \
  75     (tab)[count] = (p);                         \
  76     (count)++;                                  \
  77   } while(0)
  78
  79 #define TAB_APPEND( count, tab, p )             \
  80     TAB_APPEND_CAST( , count, tab, p )
  81
  82 #define TAB_FIND( count, tab, p, idx )          \
  83   do {                                          \
  84     for( (idx) = 0; (idx) < (count); (idx)++ )  \
  85         if( (tab)[(idx)] == (p) )               \
  86             break;                              \
  87     if( (idx) >= (count) )                      \
  88         (idx) = -1;                             \
  89   } while(0)
  90
  91
  92 #define TAB_ERASE( count, tab, index )      \
  93   do {                                      \
  94         if( (count) > 1 )                   \
  95             memmove( (tab) + (index),       \
  96                      (tab) + (index) + 1,   \
  97                      ((count) - (index) - 1 ) * sizeof( *(tab) ) );\
  98         (count)--;                          \
  99         if( (count) == 0 )                  \
 100         {                                   \
 101             free( tab );                    \
 102             (tab) = NULL;                   \
 103         }                                   \
 104   } while(0)
 105
 106 #define TAB_REMOVE( count, tab, p )             \
 107   do {                                          \
 108         int i_index;                            \
 109         TAB_FIND( count, tab, p, i_index );     \
 110         if( i_index >= 0 )                      \
 111             TAB_ERASE( count, tab, i_index );   \
 112   } while(0)
 113
 114 #define TAB_INSERT_CAST( cast, count, tab, p, index ) do { \
 115     if( (count) > 0 )                           \
 116         (tab) = cast realloc( tab, sizeof( *(tab) ) * ( (count) + 1 ) ); \
 117     else                                        \
 118         (tab) = cast malloc( sizeof( *(tab) ) );       \
 119     if( !(tab) ) abort();                       \
 120     if( (count) - (index) > 0 )                 \
 121         memmove( (tab) + (index) + 1,           \
 122                  (tab) + (index),               \
 123                  ((count) - (index)) * sizeof( *(tab) ) );\
 124     (tab)[(index)] = (p);                       \
 125     (count)++;                                  \
 126 } while(0)
 127
 128 #define TAB_INSERT( count, tab, p, index )      \
 129     TAB_INSERT_CAST( , count, tab, p, index )
 130
 131 /**
 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
 139  */
 140 #define BSEARCH( entries, count, elem, zetype, key, answer ) \
 141    do {  \
 142     int low = 0, high = count - 1;   \
 143     answer = -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 ) \
 148             low = mid + 1; \
 149         else if ( mid_val > key ) \
 150             high = mid -1;  \
 151         else    \
 152         {   \
 153             answer = mid;  break;   \
 154         }\
 155     } \
 156  } while(0)
 157
 158
 159 /************************************************************************
 160  * Dynamic arrays with progressive allocation
 161  ************************************************************************/
 162
 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();                                         \
 169 }
 170
 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) )                    \
 176 }
 177
 178 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
 179
 180 /* API */
 181 #define DECL_ARRAY(type) struct {                                           \
 182     int i_alloc;                                                            \
 183     int i_size;                                                             \
 184     type *p_elems;                                                          \
 185 }
 186
 187 #define TYPEDEF_ARRAY(type, name) typedef DECL_ARRAY(type) name;
 188
 189 #define ARRAY_INIT(array)                                                   \
 190   do {                                                                      \
 191     (array).i_alloc = 0;                                                    \
 192     (array).i_size = 0;                                                     \
 193     (array).p_elems = NULL;                                                 \
 194   } while(0)
 195
 196 #define ARRAY_RESET(array)                                                  \
 197   do {                                                                      \
 198     (array).i_alloc = 0;                                                    \
 199     (array).i_size = 0;                                                     \
 200     free( (array).p_elems ); (array).p_elems = NULL;                        \
 201   } while(0)
 202
 203 #define ARRAY_APPEND(array, elem)                                           \
 204   do {                                                                      \
 205     _ARRAY_GROW1(array);                                                    \
 206     (array).p_elems[(array).i_size] = elem;                                 \
 207     (array).i_size++;                                                       \
 208   } while(0)
 209
 210 #define ARRAY_INSERT(array,elem,pos)                                        \
 211   do {                                                                      \
 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) );       \
 216     }                                                                       \
 217     (array).p_elems[pos] = elem;                                            \
 218     (array).i_size++;                                                       \
 219   } while(0)
 220
 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);                            \
 224     }                                                                       \
 225 }
 226
 227 #define ARRAY_FIND(array, p, idx)                                           \
 228   TAB_FIND((array).i_size, (array).p_elems, p, idx)
 229
 230 #define ARRAY_REMOVE(array,pos)                                             \
 231   do {                                                                      \
 232     if( (array).i_size - (pos) - 1 )                                        \
 233     {                                                                       \
 234         memmove( (array).p_elems + (pos), (array).p_elems + (pos) + 1,      \
 235                  ( (array).i_size - (pos) - 1 ) *sizeof(*(array).p_elems) );\
 236     }                                                                       \
 237     (array).i_size--;                                                       \
 238     _ARRAY_SHRINK(array);                                                   \
 239   } while(0)
 240
 241 #define ARRAY_VAL(array, pos) array.p_elems[pos]
 242
 243 #define ARRAY_BSEARCH(array, elem, zetype, key, answer) \
 244     BSEARCH( (array).p_elems, (array).i_size, elem, zetype, key, answer)
 245
 246 /* append ##item to index variable name to avoid variable shadowing warnings for
 247  * nested loops */
 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)
 253
 254
 255 /************************************************************************
 256  * Dynamic arrays with progressive allocation (Preferred API)
 257  ************************************************************************/
 258 typedef struct vlc_array_t
 259 {
 260     size_t i_count;
 261     void ** pp_elems;
 262 } vlc_array_t;
 263
 264 static inline void vlc_array_init( vlc_array_t * p_array )
 265 {
 266     p_array->i_count = 0;
 267     p_array->pp_elems = NULL;
 268 }
 269
 270 static inline void vlc_array_clear( vlc_array_t * p_array )
 271 {
 272     free( p_array->pp_elems );
 273     vlc_array_init( p_array );
 274 }
 275
 276 /* Read */
 277 static inline size_t vlc_array_count( vlc_array_t * p_array )
 278 {
 279     return p_array->i_count;
 280 }
 281
 282 #ifndef __cplusplus
 283 # define vlc_array_item_at_index(ar, idx) \
 284     _Generic((ar), \
 285         const vlc_array_t *: ((ar)->pp_elems[idx]), \
 286         vlc_array_t *: ((ar)->pp_elems[idx]))
 287 #else
 288 static inline void *vlc_array_item_at_index( vlc_array_t *ar, size_t idx )
 289 {
 290     return ar->pp_elems[idx];
 291 }
 292
 293 static inline const void *vlc_array_item_at_index( const vlc_array_t *ar,
 294                                                    size_t idx )
 295 {
 296     return ar->pp_elems[idx];
 297 }
 298 #endif
 299
 300 static inline ssize_t vlc_array_index_of_item( const vlc_array_t *ar,
 301                                                const void *elem )
 302 {
 303     for( size_t i = 0; i < ar->i_count; i++ )
 304     {
 305         if( ar->pp_elems[i] == elem )
 306             return i;
 307     }
 308     return -1;
 309 }
 310
 311 /* Write */
 312 static inline int vlc_array_insert( vlc_array_t *ar, void *elem, int idx )
 313 {
 314     void **pp = (void **)realloc( ar->pp_elems,
 315                                   sizeof( void * ) * (ar->i_count + 1) );
 316     if( unlikely(pp == NULL) )
 317         return -1;
 318
 319     size_t tail = ar->i_count - idx;
 320     if( tail > 0 )
 321         memmove( pp + idx + 1, pp + idx, sizeof( void * ) * tail );
 322
 323     pp[idx] = elem;
 324     ar->i_count++;
 325     ar->pp_elems = pp;
 326     return 0;
 327 }
 328
 329 static inline void vlc_array_insert_or_abort( vlc_array_t *ar, void *elem, int idx )
 330 {
 331     if( vlc_array_insert( ar, elem, idx ) )
 332         abort();
 333 }
 334
 335 static inline int vlc_array_append( vlc_array_t *ar, void *elem )
 336 {
 337     void **pp = (void **)realloc( ar->pp_elems,
 338                                   sizeof( void * ) * (ar->i_count + 1) );
 339     if( unlikely(pp == NULL) )
 340         return -1;
 341
 342     pp[ar->i_count++] = elem;
 343     ar->pp_elems = pp;
 344     return 0;
 345 }
 346
 347 static inline void vlc_array_append_or_abort( vlc_array_t *ar, void *elem )
 348 {
 349     if( vlc_array_append( ar, elem ) != 0 )
 350         abort();
 351 }
 352
 353 static inline void vlc_array_remove( vlc_array_t *ar, size_t idx )
 354 {
 355     void **pp = ar->pp_elems;
 356     size_t tail = ar->i_count - idx - 1;
 357
 358     if( tail > 0 )
 359         memmove( pp + idx, pp + idx + 1, sizeof( void * ) * tail );
 360
 361     ar->i_count--;
 362
 363     if( ar->i_count > 0 )
 364     {
 365         pp = (void **)realloc( pp, sizeof( void * ) * ar->i_count );
 366         if( likely(pp != NULL) )
 367             ar->pp_elems = pp;
 368     }
 369     else
 370     {
 371         free( pp );
 372         ar->pp_elems = NULL;
 373     }
 374 }
 375
 376
 377 /************************************************************************
 378  * Dictionaries
 379  ************************************************************************/
 380
 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.
 384  */
 385 static inline uint64_t DictHash( const char *psz_string, int hashsize )
 386 {
 387     uint64_t i_hash = 0;
 388     if( psz_string )
 389     {
 390         while( *psz_string )
 391         {
 392             i_hash += *psz_string++;
 393             i_hash += i_hash << 10;
 394             i_hash ^= i_hash >> 8;
 395         }
 396     }
 397     return i_hash % hashsize;
 398 }
 399
 400 typedef struct vlc_dictionary_entry_t
 401 {
 402     char *   psz_key;
 403     void *   p_value;
 404     struct vlc_dictionary_entry_t * p_next;
 405 } vlc_dictionary_entry_t;
 406
 407 typedef struct vlc_dictionary_t
 408 {
 409     int i_size;
 410     vlc_dictionary_entry_t ** p_entries;
 411 } vlc_dictionary_t;
 412
 413 static void * const kVLCDictionaryNotFound = NULL;
 414
 415 static inline void vlc_dictionary_init( vlc_dictionary_t * p_dict, int i_size )
 416 {
 417     p_dict->p_entries = NULL;
 418
 419     if( i_size > 0 )
 420     {
 421         p_dict->p_entries = (vlc_dictionary_entry_t **)calloc( i_size, sizeof(*p_dict->p_entries) );
 422         if( !p_dict->p_entries )
 423             i_size = 0;
 424     }
 425     p_dict->i_size = i_size;
 426 }
 427
 428 static inline void vlc_dictionary_clear( vlc_dictionary_t * p_dict,
 429                                          void ( * pf_free )( void * p_data, void * p_obj ),
 430                                          void * p_obj )
 431 {
 432     if( p_dict->p_entries )
 433     {
 434         for( int i = 0; i < p_dict->i_size; i++ )
 435         {
 436             vlc_dictionary_entry_t * p_current, * p_next;
 437             p_current = p_dict->p_entries[i];
 438             while( p_current )
 439             {
 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 );
 444                 free( p_current );
 445                 p_current = p_next;
 446             }
 447         }
 448         free( p_dict->p_entries );
 449         p_dict->p_entries = NULL;
 450     }
 451     p_dict->i_size = 0;
 452 }
 453
 454 static inline int
 455 vlc_dictionary_has_key( const vlc_dictionary_t * p_dict, const char * psz_key )
 456 {
 457     if( !p_dict->p_entries )
 458         return 0;
 459
 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 )
 463     {
 464         if( !strcmp( psz_key, p_entry->psz_key ) )
 465             break;
 466     }
 467     return p_entry != NULL;
 468 }
 469
 470 static inline void *
 471 vlc_dictionary_value_for_key( const vlc_dictionary_t * p_dict, const char * psz_key )
 472 {
 473     if( !p_dict->p_entries )
 474         return kVLCDictionaryNotFound;
 475
 476     int i_pos = DictHash( psz_key, p_dict->i_size );
 477     vlc_dictionary_entry_t * p_entry = p_dict->p_entries[i_pos];
 478
 479     if( !p_entry )
 480         return kVLCDictionaryNotFound;
 481
 482     /* Make sure we return the right item. (Hash collision) */
 483     do {
 484         if( !strcmp( psz_key, p_entry->psz_key ) )
 485             return p_entry->p_value;
 486         p_entry = p_entry->p_next;
 487     } while( p_entry );
 488
 489     return kVLCDictionaryNotFound;
 490 }
 491
 492 static inline int
 493 vlc_dictionary_keys_count( const vlc_dictionary_t * p_dict )
 494 {
 495     vlc_dictionary_entry_t * p_entry;
 496     int i, count = 0;
 497
 498     if( !p_dict->p_entries )
 499         return 0;
 500
 501     for( i = 0; i < p_dict->i_size; i++ )
 502     {
 503         for( p_entry = p_dict->p_entries[i]; p_entry; p_entry = p_entry->p_next ) count++;
 504     }
 505     return count;
 506 }
 507
 508 static inline bool
 509 vlc_dictionary_is_empty( const vlc_dictionary_t * p_dict )
 510 {
 511     if( p_dict->p_entries )
 512         for( int i = 0; i < p_dict->i_size; i++ )
 513             if( p_dict->p_entries[i] )
 514                 return false;
 515     return true;
 516 }
 517
 518 static inline char **
 519 vlc_dictionary_all_keys( const vlc_dictionary_t * p_dict )
 520 {
 521     vlc_dictionary_entry_t * p_entry;
 522     char ** ppsz_ret;
 523     int i, count = vlc_dictionary_keys_count( p_dict );
 524
 525     ppsz_ret = (char**)malloc(sizeof(char *) * (count + 1));
 526     if( unlikely(!ppsz_ret) )
 527         return NULL;
 528
 529     count = 0;
 530     for( i = 0; i < p_dict->i_size; i++ )
 531     {
 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 );
 534     }
 535     ppsz_ret[count] = NULL;
 536     return ppsz_ret;
 537 }
 538
 539 static inline void
 540 vlc_dictionary_insert_impl_( vlc_dictionary_t * p_dict, const char * psz_key,
 541                              void * p_value, bool rebuild )
 542 {
 543     if( !p_dict->p_entries )
 544         vlc_dictionary_init( p_dict, 1 );
 545
 546     int i_pos = DictHash( psz_key, p_dict->i_size );
 547     vlc_dictionary_entry_t * p_entry;
 548
 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;
 554     if( rebuild )
 555     {
 556         /* Count how many items there was */
 557         int count;
 558         for( count = 1; p_entry->p_next; count++ )
 559             p_entry = p_entry->p_next;
 560         if( count > 3 ) /* XXX: this need tuning */
 561         {
 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 */
 565             int i;
 566             vlc_dictionary_init( &new_dict, i_new_size );
 567             for( i = 0; i < p_dict->i_size; i++ )
 568             {
 569                 p_entry = p_dict->p_entries[i];
 570                 while( p_entry )
 571                 {
 572                     vlc_dictionary_insert_impl_( &new_dict, p_entry->psz_key,
 573                                              p_entry->p_value,
 574                                              false /* To avoid multiple rebuild loop */);
 575                     p_entry = p_entry->p_next;
 576                 }
 577             }
 578
 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;
 582         }
 583     }
 584 }
 585
 586 static inline void
 587 vlc_dictionary_insert( vlc_dictionary_t * p_dict, const char * psz_key, void * p_value )
 588 {
 589     vlc_dictionary_insert_impl_( p_dict, psz_key, p_value, true );
 590 }
 591
 592 static inline void
 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 ),
 595                                      void * p_obj )
 596 {
 597     if( !p_dict->p_entries )
 598         return;
 599
 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;
 603
 604     if( !p_entry )
 605         return; /* Not found, nothing to do */
 606
 607     /* Hash collision */
 608     p_prev = NULL;
 609     do {
 610         if( !strcmp( psz_key, p_entry->psz_key ) )
 611         {
 612             if( pf_free != NULL )
 613                 ( * pf_free )( p_entry->p_value, p_obj );
 614             if( !p_prev )
 615                 p_dict->p_entries[i_pos] = p_entry->p_next;
 616             else
 617                 p_prev->p_next = p_entry->p_next;
 618             free( p_entry->psz_key );
 619             free( p_entry );
 620             return;
 621         }
 622         p_prev = p_entry;
 623         p_entry = p_entry->p_next;
 624     } while( p_entry );
 625
 626     /* No key was found */
 627 }
 628
 629 #ifdef __cplusplus
 630 // C++ helpers
 631 template <typename T>
 632 void vlc_delete_all( T &container )
 633 {
 634     typename T::iterator it = container.begin();
 635     while ( it != container.end() )
 636     {
 637         delete *it;
 638         ++it;
 639     }
 640     container.clear();
 641 }
 642
 643 #endif
 644
 645 #endif