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

   1 /*****************************************************************************
   2  * hashtables.c: Hash tables 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 /*****************************************************************************
  26  * Preamble
  27  *****************************************************************************/
  28 #include <vlc/vlc.h>
  29
  30 static uint64_t HashString    ( const char *, int );
  31 static int      FindSlot      ( hashtable_entry_t *, int, uint64_t );
  32 static int      LookupInner   ( hashtable_entry_t *, int, uint64_t );
  33
  34
  35
  36 void vlc_HashInsert( hashtable_entry_t **pp_array, int *pi_count, int i_id,
  37                      const char *psz_name, void *p_data )
  38 {
  39     hashtable_entry_t *p_new;
  40     int64_t i_hash = HashString( psz_name, i_id );
  41     int i_new = FindSlot( *pp_array, *pi_count, i_hash );
  42
  43     *pp_array = realloc( *pp_array, ( *pi_count + 2) * sizeof( hashtable_entry_t ) );
  44
  45     memmove( *pp_array + i_new + 1 , *pp_array + i_new, ( *pi_count - i_new ) *
  46                 sizeof( hashtable_entry_t ) );
  47     (*pi_count)++;
  48
  49     p_new = &((*pp_array)[i_new]);
  50     p_new->i_hash = i_hash;
  51     p_new->i_id = i_id;
  52     p_new->psz_name = strdup( psz_name );
  53     p_new->p_data = p_data;
  54
  55 }
  56
  57 void * vlc_HashRetrieve( hashtable_entry_t *p_array, int i_count, int i_id,
  58                          const char *psz_name )
  59 {
  60     int i_new = vlc_HashLookup( p_array, i_count, i_id, psz_name );
  61
  62     if( i_new >=  0 && i_new < i_count )
  63     {
  64         return p_array[i_new].p_data;
  65     }
  66     return NULL;
  67 }
  68
  69 /*****************************************************************************
  70  * FindSlot: find an empty slot to insert a new variable
  71  *****************************************************************************
  72  * We use a recursive inner function indexed on the hash. This function does
  73  * nothing in the rare cases where a collision may occur, see Lookup()
  74  * to see how we handle them.
  75  * XXX: does this really need to be written recursively?
  76  *****************************************************************************/
  77 static int FindSlot( hashtable_entry_t *p_array, int i_count, uint64_t i_hash )
  78 {
  79     int i_middle;
  80
  81     if( i_count == 0 || i_hash <= p_array[0].i_hash )
  82     {
  83         return 0;
  84     }
  85
  86     if( i_hash >= p_array[i_count - 1].i_hash )
  87     {
  88         return i_count;
  89     }
  90
  91     i_middle = i_count / 2;
  92
  93     /* We know that 0 < i_middle */
  94     if( i_hash < p_array[i_middle].i_hash )
  95     {
  96         return FindSlot( p_array, i_middle, i_hash );
  97     }
  98
  99     /* We know that i_middle + 1 < i_count */
 100     if( i_hash > p_array[i_middle + 1].i_hash )
 101     {
 102         return i_middle + 1 + FindSlot( p_array + i_middle + 1,
 103                                         i_count - i_middle - 1,
 104                                         i_hash );
 105     }
 106
 107     return i_middle + 1;
 108 }
 109
 110 /*****************************************************************************
 111  * Lookup: find an existing variable given its name and id
 112  *****************************************************************************
 113  * We use a recursive inner function indexed on the hash. Care is taken of
 114  * possible hash collisions.
 115  * XXX: does this really need to be written recursively?
 116  *****************************************************************************/
 117 int vlc_HashLookup( hashtable_entry_t *p_array, int i_count,
 118                     int i_id, const char *psz_name )
 119 {
 120     uint64_t i_hash;
 121     int i, i_pos;
 122
 123     if( i_count == 0 )
 124     {
 125         return -1;
 126     }
 127
 128     i_hash = HashString( psz_name, i_id );
 129
 130     i_pos = LookupInner( p_array, i_count, i_hash );
 131
 132     /* Hash not found */
 133     if( i_hash != p_array[i_pos].i_hash )
 134     {
 135         return -1;
 136     }
 137
 138     /* Hash found, let's check it looks like the entry
 139      * We don't check the whole entry, this could lead to bad surprises :( */
 140     if( psz_name[0] == p_array[i_pos].psz_name[0] )
 141     {
 142         return i_pos;
 143     }
 144
 145     /* Hash collision! This should be very rare, but we cannot guarantee
 146      * it will never happen. Just do an exhaustive search amongst all
 147      * entries with the same hash. */
 148     for( i = i_pos - 1 ; i > 0 && i_hash == p_array[i].i_hash ; i-- )
 149     {
 150         if( !strcmp( psz_name, p_array[i].psz_name ) && p_array[i].i_id == i_id )
 151         {
 152             return i;
 153         }
 154     }
 155
 156     for( i = i_pos + 1 ; i < i_count && i_hash == p_array[i].i_hash ; i++ )
 157     {
 158         if( !strcmp( psz_name, p_array[i].psz_name ) && p_array[i].i_id == i_id )
 159         {
 160             return i;
 161         }
 162     }
 163
 164     /* Hash found, but entry not found */
 165     return -1;
 166 }
 167
 168 static int LookupInner( hashtable_entry_t *p_array, int i_count, uint64_t i_hash )
 169 {
 170     int i_middle;
 171
 172     if( i_hash <= p_array[0].i_hash )
 173     {
 174         return 0;
 175     }
 176
 177     if( i_hash >= p_array[i_count-1].i_hash )
 178     {
 179         return i_count - 1;
 180     }
 181
 182     i_middle = i_count / 2;
 183
 184     /* We know that 0 < i_middle */
 185     if( i_hash < p_array[i_middle].i_hash )
 186     {
 187         return LookupInner( p_array, i_middle, i_hash );
 188     }
 189
 190     /* We know that i_middle + 1 < i_count */
 191     if( i_hash > p_array[i_middle].i_hash )
 192     {
 193         return i_middle + LookupInner( p_array + i_middle,
 194                                        i_count - i_middle,
 195                                        i_hash );
 196     }
 197
 198     return i_middle;
 199 }
 200
 201
 202 /*****************************************************************************
 203  * HashString: our cool hash function
 204  *****************************************************************************
 205  * This function is not intended to be crypto-secure, we only want it to be
 206  * fast and not suck too much. This one is pretty fast and did 0 collisions
 207  * in wenglish's dictionary.
 208  *****************************************************************************/
 209 static uint64_t HashString( const char *psz_string, int i_id )
 210 {
 211     uint64_t i_hash = 0;
 212
 213     while( *psz_string )
 214     {
 215         i_hash += *psz_string++;
 216         i_hash += i_hash << 10;
 217         i_hash ^= i_hash >> 8;
 218     }
 219
 220     i_hash += ( (uint64_t)i_id << 32 );
 221
 222     return i_hash;
 223 }