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 $
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
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.
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.
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 *****************************************************************************/
28 /*****************************************************************************
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
37 static uint64_t DoHash ( const char *, int );
39 #define DARRAY p_dict->p_entries
40 #define DSIZE p_dict->i_entries
44 DECMALLOC_NULL( p_dict, dict_t );
45 p_dict->i_entries = 0;
46 p_dict->p_entries = NULL;
50 void vlc_DictClear( dict_t *p_dict )
53 for( i = 0 ; i< DSIZE; i++ )
55 FREE( DARRAY[i].psz_string );
61 void vlc_DictInsert( dict_t *p_dict, int i_int, const char *psz_string,
64 uint64_t i_hash = DoHash( psz_string, i_int );
67 /* Find a free slot */
68 if( DSIZE == 0 || i_hash <= DARRAY[0].i_hash )
70 else if( i_hash >= DARRAY[DSIZE-1].i_hash )
74 int i_low = 0, i_high = DSIZE;
75 while( i_low != i_high )
77 int i_mid = (i_low + i_high)/2;
78 if( DARRAY[i_mid].i_hash < i_hash )
80 if( DARRAY[i_mid].i_hash > i_hash )
85 DARRAY = realloc( DARRAY, (DSIZE + 1) * sizeof( dict_entry_t ) );
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;
94 DARRAY[i_new].psz_string = strdup( psz_string );
96 DARRAY[i_new].psz_string = NULL;
97 DARRAY[i_new].p_data = p_data;
100 void * vlc_DictGet( dict_t *p_dict, int i_int, const char *psz_string )
102 int i_new = vlc_DictLookup( p_dict, i_int, psz_string );
104 return DARRAY[i_new].p_data;
108 int vlc_DictLookup( dict_t *p_dict, int i_int, const char *psz_string )
112 if( DSIZE == 0 ) return -1;
114 i_hash = DoHash( psz_string, i_int );
115 BSEARCH( p_dict->p_entries, p_dict->i_entries, .i_hash, uint64_t,
117 if( i_pos == -1 ) return -1;
119 /* Hash found, let's check it looks like the entry */
120 if( !strcmp( psz_string, DARRAY[i_pos].psz_string ) )
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-- )
128 if( !strcmp( psz_string, DARRAY[i].psz_string ) &&
129 DARRAY[i].i_int == i_int )
132 for( i = i_pos + 1 ; i < DSIZE && i_hash == DARRAY[i].i_hash ; i++ )
134 if( !strcmp( psz_string, DARRAY[i].psz_string ) &&
135 DARRAY[i].i_int == i_int )
138 /* Hash found, but entry not found (quite strange !) */
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 )
157 i_hash += *psz_string++;
158 i_hash += i_hash << 10;
159 i_hash ^= i_hash >> 8;
162 return i_hash + ( (uint64_t)i_int << 32 );