src/misc/variables.c

   1 /*****************************************************************************
   2  * variables.c: routines for object variables handling
   3  *****************************************************************************
   4  * Copyright (C) 2002 VideoLAN
   5  * $Id: variables.c,v 1.2 2002/10/14 16:46:56 sam Exp $
   6  *
   7  * Authors: Samuel Hocevar <sam@zoy.org>
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation; either version 2 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA.
  22  *****************************************************************************/
  23
  24 /*****************************************************************************
  25  * Preamble
  26  *****************************************************************************/
  27 #include <vlc/vlc.h>
  28
  29 #ifdef HAVE_STDLIB_H
  30 #   include <stdlib.h>                                          /* realloc() */
  31 #endif
  32
  33 /*****************************************************************************
  34  * Local prototypes
  35  *****************************************************************************/
  36 static u32 HashString     ( const char * );
  37 static int Insert         ( variable_t *, int, const char * );
  38 static int InsertInner    ( variable_t *, int, u32 );
  39 static int Lookup         ( variable_t *, int, const char * );
  40 static int LookupInner    ( variable_t *, int, u32 );
  41
  42 /*****************************************************************************
  43  * var_Create: initialize a vlc variable
  44  *****************************************************************************
  45  * We hash the given string and insert it into the sorted list. The insertion
  46  * may require slow memory copies, but think about what we gain in the log(n)
  47  * lookup phase when setting/getting the variable value!
  48  *****************************************************************************/
  49 int __var_Create( vlc_object_t *p_this, const char *psz_name, int i_type )
  50 {
  51     int i_new;
  52
  53     vlc_mutex_lock( &p_this->var_lock );
  54
  55     if( (p_this->i_vars & 15) == 15 )
  56     {
  57         p_this->p_vars = realloc( p_this->p_vars,
  58                                   (p_this->i_vars+17) * sizeof(variable_t) );
  59     }
  60
  61     i_new = Insert( p_this->p_vars, p_this->i_vars, psz_name );
  62
  63     memmove( p_this->p_vars + i_new + 1,
  64              p_this->p_vars + i_new,
  65              (p_this->i_vars - i_new) * sizeof(variable_t) );
  66
  67     p_this->p_vars[i_new].i_hash = HashString( psz_name );
  68     p_this->p_vars[i_new].psz_name = strdup( psz_name );
  69
  70     p_this->p_vars[i_new].i_type = i_type;
  71     memset( &p_this->p_vars[i_new].val, 0, sizeof(vlc_value_t) );
  72
  73     p_this->p_vars[i_new].b_set = VLC_FALSE;
  74     p_this->p_vars[i_new].b_active = VLC_TRUE;
  75
  76     p_this->i_vars++;
  77
  78     vlc_mutex_unlock( &p_this->var_lock );
  79
  80     return VLC_SUCCESS;
  81 }
  82
  83 /*****************************************************************************
  84  * var_Destroy: destroy a vlc variable
  85  *****************************************************************************
  86  * Look for the variable and destroy it if it is found. As in var_Create we
  87  * do a call to memmove() but we have performance counterparts elsewhere.
  88  *****************************************************************************/
  89 int __var_Destroy( vlc_object_t *p_this, const char *psz_name )
  90 {
  91     int i_del;
  92
  93     vlc_mutex_lock( &p_this->var_lock );
  94
  95     i_del = Lookup( p_this->p_vars, p_this->i_vars, psz_name );
  96
  97     if( i_del < 0 )
  98     {
  99         msg_Err( p_this, "variable %s was not found", psz_name );
 100         vlc_mutex_unlock( &p_this->var_lock );
 101         return VLC_ENOVAR;
 102     }
 103
 104     /* Free value if needed */
 105     switch( p_this->p_vars[i_del].i_type )
 106     {
 107         case VLC_VAR_STRING:
 108         case VLC_VAR_MODULE:
 109         case VLC_VAR_FILE:
 110             if( p_this->p_vars[i_del].b_set
 111                  && p_this->p_vars[i_del].val.psz_string )
 112             {
 113                 free( p_this->p_vars[i_del].val.psz_string );
 114             }
 115             break;
 116     }
 117
 118     free( p_this->p_vars[i_del].psz_name );
 119
 120     memmove( p_this->p_vars + i_del,
 121              p_this->p_vars + i_del + 1,
 122              (p_this->i_vars - i_del - 1) * sizeof(variable_t) );
 123
 124     if( (p_this->i_vars & 15) == 0 )
 125     {
 126         p_this->p_vars = realloc( p_this->p_vars,
 127                           (p_this->i_vars) * sizeof( variable_t ) );
 128     }
 129
 130     p_this->i_vars--;
 131
 132     vlc_mutex_unlock( &p_this->var_lock );
 133
 134     return VLC_SUCCESS;
 135 }
 136
 137 /*****************************************************************************
 138  * var_Type: request a variable's type, 0 if not found
 139  *****************************************************************************
 140  *
 141  *****************************************************************************/
 142 int __var_Type( vlc_object_t *p_this, const char *psz_name )
 143 {
 144     int i_var, i_type;
 145
 146     vlc_mutex_lock( &p_this->var_lock );
 147
 148     i_var = Lookup( p_this->p_vars, p_this->i_vars, psz_name );
 149
 150     if( i_var < 0 )
 151     {
 152         vlc_mutex_unlock( &p_this->var_lock );
 153         return 0;
 154     }
 155
 156     i_type = p_this->p_vars[i_var].i_type;
 157
 158     vlc_mutex_unlock( &p_this->var_lock );
 159
 160     return i_type;
 161 }
 162
 163 /*****************************************************************************
 164  * var_Set: set a variable's value
 165  *****************************************************************************
 166  *
 167  *****************************************************************************/
 168 int __var_Set( vlc_object_t *p_this, const char *psz_name, vlc_value_t val )
 169 {
 170     int i_var;
 171
 172     vlc_mutex_lock( &p_this->var_lock );
 173
 174     i_var = Lookup( p_this->p_vars, p_this->i_vars, psz_name );
 175
 176     if( i_var < 0 )
 177     {
 178         vlc_mutex_unlock( &p_this->var_lock );
 179         return VLC_ENOVAR;
 180     }
 181
 182     /* Duplicate value if needed */
 183     switch( p_this->p_vars[i_var].i_type )
 184     {
 185         case VLC_VAR_STRING:
 186         case VLC_VAR_MODULE:
 187         case VLC_VAR_FILE:
 188             if( p_this->p_vars[i_var].b_set
 189                  && p_this->p_vars[i_var].val.psz_string )
 190             {
 191                 free( p_this->p_vars[i_var].val.psz_string );
 192             }
 193             if( val.psz_string )
 194             {
 195                 val.psz_string = strdup( val.psz_string );
 196             }
 197             break;
 198     }
 199
 200     p_this->p_vars[i_var].val = val;
 201     p_this->p_vars[i_var].b_set = VLC_TRUE;
 202
 203     /* XXX: callback stuff will go here */
 204
 205     vlc_mutex_unlock( &p_this->var_lock );
 206
 207     return VLC_SUCCESS;
 208 }
 209
 210 /*****************************************************************************
 211  * var_Get: get a variable's value
 212  *****************************************************************************
 213  *
 214  *****************************************************************************/
 215 int __var_Get( vlc_object_t *p_this, const char *psz_name, vlc_value_t *p_val )
 216 {
 217     int i_var;
 218
 219     vlc_mutex_lock( &p_this->var_lock );
 220
 221     i_var = Lookup( p_this->p_vars, p_this->i_vars, psz_name );
 222
 223     if( i_var < 0 )
 224     {
 225         vlc_mutex_unlock( &p_this->var_lock );
 226         return VLC_ENOVAR;
 227     }
 228
 229     if( !p_this->p_vars[i_var].b_set )
 230     {
 231         vlc_mutex_unlock( &p_this->var_lock );
 232         return VLC_EBADVAR;
 233     }
 234
 235     /* Some variables trigger special behaviour. */
 236     switch( p_this->p_vars[i_var].i_type )
 237     {
 238         case VLC_VAR_COMMAND:
 239             if( p_this->p_vars[i_var].b_set )
 240             {
 241                 int i_ret = ((int (*) (vlc_object_t *, char *, char *))
 242                                 p_this->p_vars[i_var].val.p_address) (
 243                                     p_this,
 244                                     p_this->p_vars[i_var].psz_name,
 245                                     p_val->psz_string );
 246                 vlc_mutex_unlock( &p_this->var_lock );
 247                 return i_ret;
 248             }
 249             break;
 250     }
 251
 252     /* Really set the variable */
 253     *p_val = p_this->p_vars[i_var].val;
 254
 255     /* Duplicate value if needed */
 256     switch( p_this->p_vars[i_var].i_type )
 257     {
 258         case VLC_VAR_STRING:
 259         case VLC_VAR_MODULE:
 260         case VLC_VAR_FILE:
 261             if( p_val->psz_string )
 262             {
 263                 p_val->psz_string = strdup( p_val->psz_string );
 264             }
 265             break;
 266     }
 267
 268     vlc_mutex_unlock( &p_this->var_lock );
 269
 270     return VLC_SUCCESS;
 271 }
 272
 273 /* Following functions are local */
 274
 275 /*****************************************************************************
 276  * HashString: our cool hash function
 277  *****************************************************************************
 278  * This function is not intended to be crypto-secure, we only want it to be
 279  * fast and not suck too much. This one is pretty fast and did 0 collisions
 280  * in wenglish's dictionary.
 281  *****************************************************************************/
 282 static u32 HashString( const char *psz_string )
 283 {
 284     u32 i_hash = 0;
 285
 286     while( *psz_string )
 287     {
 288         i_hash += *psz_string++;
 289         i_hash += i_hash << 10;
 290         i_hash ^= i_hash >> 8;
 291     }
 292
 293     return i_hash;
 294 }
 295
 296 /*****************************************************************************
 297  * Insert: find an empty slot to insert a new variable
 298  *****************************************************************************
 299  * We use a recursive inner function indexed on the hash. This function does
 300  * nothing in the rare cases where a collision may occur, see Lookup()
 301  * to see how we handle them.
 302  * XXX: does this really need to be written recursively?
 303  *****************************************************************************/
 304 static int Insert( variable_t *p_vars, int i_count, const char *psz_name )
 305 {
 306     if( i_count == 0 )
 307     {
 308         return 0;
 309     }
 310
 311     return InsertInner( p_vars, i_count, HashString( psz_name ) );
 312 }
 313
 314 static int InsertInner( variable_t *p_vars, int i_count, u32 i_hash )
 315 {
 316     int i_middle;
 317
 318     if( i_hash <= p_vars[0].i_hash )
 319     {
 320         return 0;
 321     }
 322
 323     if( i_hash >= p_vars[i_count - 1].i_hash )
 324     {
 325         return i_count;
 326     }
 327
 328     i_middle = i_count / 2;
 329
 330     /* We know that 0 < i_middle */
 331     if( i_hash < p_vars[i_middle].i_hash )
 332     {
 333         return InsertInner( p_vars, i_middle, i_hash );
 334     }
 335
 336     /* We know that i_middle + 1 < i_count */
 337     if( i_hash > p_vars[i_middle + 1].i_hash )
 338     {
 339         return i_middle + 1 + InsertInner( p_vars + i_middle + 1,
 340                                            i_count - i_middle - 1,
 341                                            i_hash );
 342     }
 343
 344     return i_middle + 1;
 345 }
 346
 347 /*****************************************************************************
 348  * Lookup: find an existing variable given its name
 349  *****************************************************************************
 350  * We use a recursive inner function indexed on the hash. Care is taken of
 351  * possible hash collisions.
 352  * XXX: does this really need to be written recursively?
 353  *****************************************************************************/
 354 static int Lookup( variable_t *p_vars, int i_count, const char *psz_name )
 355 {
 356     u32 i_hash;
 357     int i, i_pos;
 358
 359     if( i_count == 0 )
 360     {
 361         return -1;
 362     }
 363
 364     i_hash = HashString( psz_name );
 365
 366     i_pos = LookupInner( p_vars, i_count, i_hash );
 367
 368     /* Hash not found */
 369     if( i_hash != p_vars[i_pos].i_hash )
 370     {
 371         return -1;
 372     }
 373
 374     /* Hash found, entry found */
 375     if( !strcmp( psz_name, p_vars[i_pos].psz_name ) )
 376     {
 377         return i_pos;
 378     }
 379
 380     /* Hash collision! This should be very rare, but we cannot guarantee
 381      * it will never happen. Just do an exhaustive search amongst all
 382      * entries with the same hash. */
 383     for( i = i_pos - 1 ; i > 0 && i_hash == p_vars[i].i_hash ; i-- )
 384     {
 385         if( !strcmp( psz_name, p_vars[i].psz_name ) )
 386         {
 387             return i;
 388         }
 389     }
 390
 391     for( i = i_pos + 1 ; i < i_count && i_hash == p_vars[i].i_hash ; i++ )
 392     {
 393         if( !strcmp( psz_name, p_vars[i].psz_name ) )
 394         {
 395             return i;
 396         }
 397     }
 398
 399     /* Hash found, but entry not found */
 400     return -1;
 401 }
 402
 403 static int LookupInner( variable_t *p_vars, int i_count, u32 i_hash )
 404 {
 405     int i_middle;
 406
 407     if( i_hash <= p_vars[0].i_hash )
 408     {
 409         return 0;
 410     }
 411
 412     if( i_hash >= p_vars[i_count-1].i_hash )
 413     {
 414         return i_count - 1;
 415     }
 416
 417     i_middle = i_count / 2;
 418
 419     /* We know that 0 < i_middle */
 420     if( i_hash < p_vars[i_middle].i_hash )
 421     {
 422         return LookupInner( p_vars, i_middle, i_hash );
 423     }
 424
 425     /* We know that i_middle + 1 < i_count */
 426     if( i_hash > p_vars[i_middle].i_hash )
 427     {
 428         return i_middle + LookupInner( p_vars + i_middle,
 429                                        i_count - i_middle,
 430                                        i_hash );
 431     }
 432
 433     return i_middle;
 434 }
 435