git.sesse.net Git - vlc/blob - src/misc/dict.c

   1 /*****************************************************************************
   2  * dict.c: Dictionnary handling
   3  *****************************************************************************
   4  * Copyright (C) 2002-2004 the VideoLAN team
   5  * $Id: variables.c 13991 2006-01-22 17:12:24Z zorglub $
   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
  11  * it under the terms of the GNU General Public License as published by
  12  * the Free Software Foundation; either version 2 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 General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; if not, write to the Free Software
  22  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
  23  *****************************************************************************/
  24
  25 #include <vlc/vlc.h>
  26 #include <assert.h>
  27
  28 /*****************************************************************************
  29  * Associative array
  30  *****************************************************************************
  31  * This is quite a weak implementation of an associative array.
  32  * It hashes the key and stores the entry in a sorted array that gets
  33  * reallocated to insert new entries (so, this is SLOW)
  34  * Lookup is done by using binary search on the array
  35  */
  36
  37 static uint64_t DoHash    ( const char *, int );
  38
  39 #define DARRAY p_dict->p_entries
  40 #define DSIZE p_dict->i_entries
  41
  42 dict_t *vlc_DictNew()
  43 {
  44     DECMALLOC_NULL( p_dict, dict_t );
  45     p_dict->i_entries = 0;
  46     p_dict->p_entries = NULL;
  47     return p_dict;
  48 }
  49
  50 void vlc_DictClear( dict_t *p_dict )
  51 {
  52     int i = 0;
  53     for( i = 0 ; i< DSIZE; i++ )
  54     {
  55         FREE( DARRAY[i].psz_string );
  56     }
  57     free( DARRAY );
  58     free( p_dict );
  59 }
  60
  61 void vlc_DictInsert( dict_t *p_dict, int i_int, const char *psz_string,
  62                      void *p_data )
  63 {
  64     uint64_t i_hash = DoHash( psz_string, i_int );
  65     int i_new;
  66
  67     /* Find a free slot */
  68     if( DSIZE == 0 || i_hash <= DARRAY[0].i_hash )
  69         i_new = 0;
  70     else if( i_hash >= DARRAY[DSIZE-1].i_hash )
  71         i_new = DSIZE;
  72     else
  73     {
  74         int i_low = 0, i_high = DSIZE;
  75         while( i_low != i_high )
  76         {
  77             int i_mid = (i_low + i_high)/2;
  78             if( DARRAY[i_mid].i_hash < i_hash )
  79                 i_low = i_mid + 1;
  80             if( DARRAY[i_mid].i_hash > i_hash )
  81                 i_high = i_low + 1;
  82         }
  83         i_new = i_low;
  84     }
  85     DARRAY = realloc( DARRAY, (DSIZE + 1) * sizeof( dict_entry_t ) );
  86     DSIZE++;
  87
  88     if( i_new != DSIZE -1 )
  89         memmove( DARRAY + i_new + 1 , DARRAY + i_new, ( DSIZE - i_new - 1 ) *
  90                     sizeof( dict_entry_t ) );
  91     DARRAY[i_new].i_hash = i_hash;
  92     DARRAY[i_new].i_int = i_int;
  93     if( psz_string )
  94         DARRAY[i_new].psz_string = strdup( psz_string );
  95     else
  96         DARRAY[i_new].psz_string = NULL;
  97     DARRAY[i_new].p_data = p_data;
  98 }
  99
 100 void * vlc_DictGet( dict_t *p_dict, int i_int, const char *psz_string )
 101 {
 102     int i_new = vlc_DictLookup( p_dict, i_int, psz_string );
 103     if( i_new >=  0 )
 104         return DARRAY[i_new].p_data;
 105     return NULL;
 106 }
 107
 108 int vlc_DictLookup( dict_t *p_dict, int i_int, const char *psz_string )
 109 {
 110     uint64_t i_hash;
 111     int i, i_pos;
 112     if( DSIZE == 0 ) return -1;
 113
 114     i_hash = DoHash( psz_string, i_int );
 115     BSEARCH( p_dict->p_entries, p_dict->i_entries, .i_hash, uint64_t,
 116              i_hash, i_pos );
 117     if( i_pos == -1 ) return -1;
 118
 119     /* Hash found, let's check it looks like the entry */
 120     if( !strcmp( psz_string, DARRAY[i_pos].psz_string ) )
 121         return i_pos;
 122
 123     /* Hash collision! This should be very rare, but we cannot guarantee
 124      * it will never happen. Just do an exhaustive search amongst all
 125      * entries with the same hash. */
 126     for( i = i_pos - 1 ; i > 0 && i_hash == DARRAY[i].i_hash ; i-- )
 127     {
 128         if( !strcmp( psz_string, DARRAY[i].psz_string ) &&
 129                    DARRAY[i].i_int == i_int )
 130             return i;
 131     }
 132     for( i = i_pos + 1 ; i < DSIZE && i_hash == DARRAY[i].i_hash ; i++ )
 133     {
 134          if( !strcmp( psz_string, DARRAY[i].psz_string ) &&
 135                    DARRAY[i].i_int == i_int )
 136             return i;
 137     }
 138     /* Hash found, but entry not found (quite strange !) */
 139     assert( 0 );
 140     return -1;
 141 }
 142
 143 /*****************************************************************************
 144  * DoHash: our cool hash function
 145  *****************************************************************************
 146  * This function is not intended to be crypto-secure, we only want it to be
 147  * fast and not suck too much. This one is pretty fast and did 0 collisions
 148  * in wenglish's dictionary.
 149  *****************************************************************************/
 150 static uint64_t DoHash( const char *psz_string, int i_int )
 151 {
 152     uint64_t i_hash = 0;
 153     if( psz_string )
 154     {
 155         while( *psz_string )
 156         {
 157             i_hash += *psz_string++;
 158             i_hash += i_hash << 10;
 159             i_hash ^= i_hash >> 8;
 160         }
 161     }
 162     return i_hash + ( (uint64_t)i_int << 32 );
 163 }