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
  82     if( i_hash <= p_array[0].i_hash )
  83     {
  84         return 0;
  85     }
  86
  87     if( i_hash >= p_array[i_count - 1].i_hash )
  88     {
  89         return i_count;
  90     }
  91
  92     i_middle = i_count / 2;
  93
  94     /* We know that 0 < i_middle */
  95     if( i_hash < p_array[i_middle].i_hash )
  96     {
  97         return FindSlot( p_array, i_middle, i_hash );
  98     }
  99
 100     /* We know that i_middle + 1 < i_count */
 101     if( i_hash > p_array[i_middle + 1].i_hash )
 102     {
 103         return i_middle + 1 + FindSlot( p_array + i_middle + 1,
 104                                         i_count - i_middle - 1,
 105                                         i_hash );
 106     }
 107
 108     return i_middle + 1;
 109 }
 110
 111 /*****************************************************************************
 112  * Lookup: find an existing variable given its name and id
 113  *****************************************************************************
 114  * We use a recursive inner function indexed on the hash. Care is taken of
 115  * possible hash collisions.
 116  * XXX: does this really need to be written recursively?
 117  *****************************************************************************/
 118 int vlc_HashLookup( hashtable_entry_t *p_array, int i_count,
 119                     int i_id, const char *psz_name )
 120 {
 121     uint64_t i_hash;
 122     int i, i_pos;
 123
 124     if( i_count == 0 )
 125     {
 126         return -1;
 127     }
 128
 129     i_hash = HashString( psz_name, i_id );
 130
 131     i_pos = LookupInner( p_array, i_count, i_hash );
 132
 133     /* Hash not found */
 134     if( i_hash != p_array[i_pos].i_hash )
 135     {
 136         return -1;
 137     }
 138
 139     /* Hash found, let's check it looks like the entry
 140      * We don't check the whole entry, this could lead to bad surprises :( */
 141     if( psz_name[0] == p_array[i].psz_name[0] )
 142     {
 143         return i_pos;
 144     }
 145
 146     /* Hash collision! This should be very rare, but we cannot guarantee
 147      * it will never happen. Just do an exhaustive search amongst all
 148      * entries with the same hash. */
 149     for( i = i_pos - 1 ; i > 0 && i_hash == p_array[i].i_hash ; i-- )
 150     {
 151         if( !strcmp( psz_name, p_array[i].psz_name ) && p_array[i].i_id == i_id )
 152         {
 153             return i;
 154         }
 155     }
 156
 157     for( i = i_pos + 1 ; i < i_count && i_hash == p_array[i].i_hash ; i++ )
 158     {
 159         if( !strcmp( psz_name, p_array[i].psz_name ) && p_array[i].i_id == i_id )
 160         {
 161             return i;
 162         }
 163     }
 164
 165     /* Hash found, but entry not found */
 166     return -1;
 167 }
 168
 169 static int LookupInner( hashtable_entry_t *p_array, int i_count, uint64_t i_hash )
 170 {
 171     int i_middle;
 172
 173     if( i_hash <= p_array[0].i_hash )
 174     {
 175         return 0;
 176     }
 177
 178     if( i_hash >= p_array[i_count-1].i_hash )
 179     {
 180         return i_count - 1;
 181     }
 182
 183     i_middle = i_count / 2;
 184
 185     /* We know that 0 < i_middle */
 186     if( i_hash < p_array[i_middle].i_hash )
 187     {
 188         return LookupInner( p_array, i_middle, i_hash );
 189     }
 190
 191     /* We know that i_middle + 1 < i_count */
 192     if( i_hash > p_array[i_middle].i_hash )
 193     {
 194         return i_middle + LookupInner( p_array + i_middle,
 195                                        i_count - i_middle,
 196                                        i_hash );
 197     }
 198
 199     return i_middle;
 200 }
 201
 202
 203 /*****************************************************************************
 204  * HashString: our cool hash function
 205  *****************************************************************************
 206  * This function is not intended to be crypto-secure, we only want it to be
 207  * fast and not suck too much. This one is pretty fast and did 0 collisions
 208  * in wenglish's dictionary.
 209  *****************************************************************************/
 210 static uint64_t HashString( const char *psz_string, int i_id )
 211 {
 212     uint64_t i_hash = 0;
 213
 214     while( *psz_string )
 215     {
 216         i_hash += *psz_string++;
 217         i_hash += i_hash << 10;
 218         i_hash ^= i_hash >> 8;
 219     }
 220
 221     i_hash += ( (uint64_t)i_id << 32 );
 222
 223     return i_hash;
 224 }