git.sesse.net Git - vlc/blob - 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.20 2003/03/09 19:25:08 gbazin 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  * Private types
  35  *****************************************************************************/
  36 struct callback_entry_t
  37 {
  38     vlc_callback_t pf_callback;
  39     void *         p_data;
  40 };
  41
  42 /*****************************************************************************
  43  * Local comparison functions, returns 0 if v == w, < 0 if v < w, > 0 if v > w
  44  *****************************************************************************/
  45 static int CmpBool( vlc_value_t v, vlc_value_t w ) { return v.b_bool ? w.b_bool ? 0 : 1 : w.b_bool ? -1 : 0; }
  46 static int CmpInt( vlc_value_t v, vlc_value_t w ) { return v.i_int == w.i_int ? 0 : v.i_int > w.i_int ? 1 : -1; }
  47 static int CmpString( vlc_value_t v, vlc_value_t w ) { return strcmp( v.psz_string, w.psz_string ); }
  48 static int CmpFloat( vlc_value_t v, vlc_value_t w ) { return v.f_float == w.f_float ? 0 : v.f_float > w.f_float ? 1 : -1; }
  49 static int CmpAddress( vlc_value_t v, vlc_value_t w ) { return v.p_address == w.p_address ? 0 : v.p_address > w.p_address ? 1 : -1; }
  50
  51 /*****************************************************************************
  52  * Local duplication functions, and local deallocation functions
  53  *****************************************************************************/
  54 static void DupDummy( vlc_value_t *p_val ) { (void)p_val; /* unused */ }
  55 static void DupString( vlc_value_t *p_val ) { p_val->psz_string = strdup( p_val->psz_string ); }
  56
  57 static void FreeDummy( vlc_value_t *p_val ) { (void)p_val; /* unused */ }
  58 static void FreeString( vlc_value_t *p_val ) { free( p_val->psz_string ); }
  59 static void FreeMutex( vlc_value_t *p_val ) { vlc_mutex_destroy( (vlc_mutex_t*)p_val->p_address ); free( p_val->p_address ); }
  60
  61 /*****************************************************************************
  62  * Local prototypes
  63  *****************************************************************************/
  64 static int      GetUnused   ( vlc_object_t *, const char * );
  65 static uint32_t HashString  ( const char * );
  66 static int      Insert      ( variable_t *, int, const char * );
  67 static int      InsertInner ( variable_t *, int, uint32_t );
  68 static int      Lookup      ( variable_t *, int, const char * );
  69 static int      LookupInner ( variable_t *, int, uint32_t );
  70
  71 static void     CheckValue  ( variable_t *, vlc_value_t * );
  72
  73 /*****************************************************************************
  74  * var_Create: initialize a vlc variable
  75  *****************************************************************************
  76  * We hash the given string and insert it into the sorted list. The insertion
  77  * may require slow memory copies, but think about what we gain in the log(n)
  78  * lookup phase when setting/getting the variable value!
  79  *****************************************************************************/
  80 int __var_Create( vlc_object_t *p_this, const char *psz_name, int i_type )
  81 {
  82     int i_new;
  83     variable_t *p_var;
  84
  85     vlc_mutex_lock( &p_this->var_lock );
  86
  87     /* FIXME: if the variable already exists, we don't duplicate it. But we
  88      * duplicate the lookups. It's not that serious, but if anyone finds some
  89      * time to rework Insert() so that only one lookup has to be done, feel
  90      * free to do so. */
  91     i_new = Lookup( p_this->p_vars, p_this->i_vars, psz_name );
  92
  93     if( i_new >= 0 )
  94     {
  95         /* If the types differ, variable creation failed. */
  96         if( i_type != p_this->p_vars[i_new].i_type )
  97         {
  98             vlc_mutex_unlock( &p_this->var_lock );
  99             return VLC_EBADVAR;
 100         }
 101
 102         p_this->p_vars[i_new].i_usage++;
 103         vlc_mutex_unlock( &p_this->var_lock );
 104         return VLC_SUCCESS;
 105     }
 106
 107     i_new = Insert( p_this->p_vars, p_this->i_vars, psz_name );
 108
 109     if( (p_this->i_vars & 15) == 15 )
 110     {
 111         p_this->p_vars = realloc( p_this->p_vars,
 112                                   (p_this->i_vars+17) * sizeof(variable_t) );
 113     }
 114
 115     memmove( p_this->p_vars + i_new + 1,
 116              p_this->p_vars + i_new,
 117              (p_this->i_vars - i_new) * sizeof(variable_t) );
 118
 119     p_this->i_vars++;
 120
 121     p_var = &p_this->p_vars[i_new];
 122
 123     p_var->i_hash = HashString( psz_name );
 124     p_var->psz_name = strdup( psz_name );
 125
 126     p_var->i_type = i_type;
 127     memset( &p_var->val, 0, sizeof(vlc_value_t) );
 128
 129     p_var->pf_dup = DupDummy;
 130     p_var->pf_free = FreeDummy;
 131
 132     p_var->i_usage = 1;
 133
 134     p_var->i_default = -1;
 135     p_var->choices.i_count = 0;
 136     p_var->choices.p_values = NULL;
 137
 138     p_var->b_incallback = VLC_FALSE;
 139     p_var->i_entries = 0;
 140     p_var->p_entries = NULL;
 141
 142     /* Always initialize the variable, even if it is a list variable; this
 143      * will lead to errors if the variable is not initialized, but it will
 144      * not cause crashes in the variable handling. */
 145     switch( i_type & VLC_VAR_TYPE )
 146     {
 147         case VLC_VAR_BOOL:
 148             p_var->pf_cmp = CmpBool;
 149             p_var->val.b_bool = VLC_FALSE;
 150             break;
 151         case VLC_VAR_INTEGER:
 152             p_var->pf_cmp = CmpInt;
 153             p_var->val.i_int = 0;
 154             break;
 155         case VLC_VAR_STRING:
 156         case VLC_VAR_MODULE:
 157         case VLC_VAR_FILE:
 158             p_var->pf_cmp = CmpString;
 159             p_var->pf_dup = DupString;
 160             p_var->pf_free = FreeString;
 161             p_var->val.psz_string = "";
 162             break;
 163         case VLC_VAR_FLOAT:
 164             p_var->pf_cmp = CmpFloat;
 165             p_var->val.f_float = 0.0;
 166             break;
 167         case VLC_VAR_TIME:
 168             /* FIXME: TODO */
 169             break;
 170         case VLC_VAR_ADDRESS:
 171             p_var->pf_cmp = CmpAddress;
 172             p_var->val.p_address = NULL;
 173             break;
 174         case VLC_VAR_MUTEX:
 175             p_var->pf_cmp = CmpAddress;
 176             p_var->pf_free = FreeMutex;
 177             p_var->val.p_address = malloc( sizeof(vlc_mutex_t) );
 178             vlc_mutex_init( p_this, (vlc_mutex_t*)p_var->val.p_address );
 179             break;
 180     }
 181
 182     /* Duplicate the default data we stored. */
 183     p_var->pf_dup( &p_var->val );
 184
 185     vlc_mutex_unlock( &p_this->var_lock );
 186
 187     return VLC_SUCCESS;
 188 }
 189
 190 /*****************************************************************************
 191  * var_Destroy: destroy a vlc variable
 192  *****************************************************************************
 193  * Look for the variable and destroy it if it is found. As in var_Create we
 194  * do a call to memmove() but we have performance counterparts elsewhere.
 195  *****************************************************************************/
 196 int __var_Destroy( vlc_object_t *p_this, const char *psz_name )
 197 {
 198     int i_var, i;
 199     variable_t *p_var;
 200
 201     vlc_mutex_lock( &p_this->var_lock );
 202
 203     i_var = GetUnused( p_this, psz_name );
 204     if( i_var < 0 )
 205     {
 206         vlc_mutex_unlock( &p_this->var_lock );
 207         return i_var;
 208     }
 209
 210     p_var = &p_this->p_vars[i_var];
 211
 212     if( p_var->i_usage > 1 )
 213     {
 214         p_var->i_usage--;
 215         vlc_mutex_unlock( &p_this->var_lock );
 216         return VLC_SUCCESS;
 217     }
 218
 219     /* Free value if needed */
 220     p_var->pf_free( &p_var->val );
 221
 222     /* Free choice list if needed */
 223     if( p_var->choices.i_count )
 224     {
 225         for( i = 0 ; i < p_var->choices.i_count ; i++ )
 226         {
 227             p_var->pf_free( &p_var->choices.p_values[i] );
 228         }
 229         free( p_var->choices.p_values );
 230     }
 231
 232     /* Free callbacks if needed */
 233     if( p_var->p_entries )
 234     {
 235         free( p_var->p_entries );
 236     }
 237
 238     free( p_var->psz_name );
 239
 240     memmove( p_this->p_vars + i_var,
 241              p_this->p_vars + i_var + 1,
 242              (p_this->i_vars - i_var - 1) * sizeof(variable_t) );
 243
 244     if( (p_this->i_vars & 15) == 0 )
 245     {
 246         p_this->p_vars = realloc( p_this->p_vars,
 247                           (p_this->i_vars) * sizeof( variable_t ) );
 248     }
 249
 250     p_this->i_vars--;
 251
 252     vlc_mutex_unlock( &p_this->var_lock );
 253
 254     return VLC_SUCCESS;
 255 }
 256
 257 /*****************************************************************************
 258  * var_Change: perform an action on a variable
 259  *****************************************************************************
 260  *
 261  *****************************************************************************/
 262 int __var_Change( vlc_object_t *p_this, const char *psz_name,
 263                   int i_action, vlc_value_t *p_val )
 264 {
 265     int i_var, i;
 266     variable_t *p_var;
 267
 268     vlc_mutex_lock( &p_this->var_lock );
 269
 270     i_var = Lookup( p_this->p_vars, p_this->i_vars, psz_name );
 271
 272     if( i_var < 0 )
 273     {
 274         vlc_mutex_unlock( &p_this->var_lock );
 275         return VLC_ENOVAR;
 276     }
 277
 278     p_var = &p_this->p_vars[i_var];
 279
 280     switch( i_action )
 281     {
 282         case VLC_VAR_SETMIN:
 283             if( p_var->i_type & VLC_VAR_HASMIN )
 284             {
 285                 p_var->pf_free( &p_var->min );
 286             }
 287             p_var->i_type |= VLC_VAR_HASMIN;
 288             p_var->min = *p_val;
 289             p_var->pf_dup( &p_var->min );
 290             CheckValue( p_var, &p_var->val );
 291             break;
 292         case VLC_VAR_SETMAX:
 293             if( p_var->i_type & VLC_VAR_HASMAX )
 294             {
 295                 p_var->pf_free( &p_var->max );
 296             }
 297             p_var->i_type |= VLC_VAR_HASMAX;
 298             p_var->max = *p_val;
 299             p_var->pf_dup( &p_var->max );
 300             CheckValue( p_var, &p_var->val );
 301             break;
 302         case VLC_VAR_SETSTEP:
 303             if( p_var->i_type & VLC_VAR_HASSTEP )
 304             {
 305                 p_var->pf_free( &p_var->step );
 306             }
 307             p_var->i_type |= VLC_VAR_HASSTEP;
 308             p_var->step = *p_val;
 309             p_var->pf_dup( &p_var->step );
 310             CheckValue( p_var, &p_var->val );
 311             break;
 312         case VLC_VAR_ADDCHOICE:
 313             /* FIXME: the list is sorted, dude. Use something cleverer. */
 314             for( i = p_var->choices.i_count ; i-- ; )
 315             {
 316                 if( p_var->pf_cmp( p_var->choices.p_values[i], *p_val ) < 0 )
 317                 {
 318                     break;
 319                 }
 320             }
 321
 322             /* The new place is i+1 */
 323             i++;
 324
 325             if( p_var->i_default >= i )
 326             {
 327                 p_var->i_default++;
 328             }
 329
 330             INSERT_ELEM( p_var->choices.p_values, p_var->choices.i_count,
 331                          i, *p_val );
 332             p_var->pf_dup( &p_var->choices.p_values[i] );
 333
 334             CheckValue( p_var, &p_var->val );
 335             break;
 336         case VLC_VAR_DELCHOICE:
 337             /* FIXME: the list is sorted, dude. Use something cleverer. */
 338             for( i = 0 ; i < p_var->choices.i_count ; i++ )
 339             {
 340                 if( p_var->pf_cmp( p_var->choices.p_values[i], *p_val ) == 0 )
 341                 {
 342                     break;
 343                 }
 344             }
 345
 346             if( i == p_var->choices.i_count )
 347             {
 348                 /* Not found */
 349                 vlc_mutex_unlock( &p_this->var_lock );
 350                 return VLC_EGENERIC;
 351             }
 352
 353             if( p_var->i_default > i )
 354             {
 355                 p_var->i_default--;
 356             }
 357             else if( p_var->i_default == i )
 358             {
 359                 p_var->i_default = -1;
 360             }
 361
 362             p_var->pf_free( &p_var->choices.p_values[i] );
 363             REMOVE_ELEM( p_var->choices.p_values, p_var->choices.i_count, i );
 364
 365             CheckValue( p_var, &p_var->val );
 366             break;
 367         case VLC_VAR_SETDEFAULT:
 368             /* FIXME: the list is sorted, dude. Use something cleverer. */
 369             for( i = 0 ; i < p_var->choices.i_count ; i++ )
 370             {
 371                 if( p_var->pf_cmp( p_var->choices.p_values[i], *p_val ) == 0 )
 372                 {
 373                     break;
 374                 }
 375             }
 376
 377             if( i == p_var->choices.i_count )
 378             {
 379                 /* Not found */
 380                 break;
 381             }
 382
 383             p_var->i_default = i;
 384             CheckValue( p_var, &p_var->val );
 385             break;
 386
 387         case VLC_VAR_GETLIST:
 388             p_val->p_list = malloc( sizeof(vlc_list_t) );
 389             if( p_var->choices.i_count )
 390                 p_val->p_list->p_values = malloc( p_var->choices.i_count
 391                                                   * sizeof(vlc_value_t) );
 392             p_val->p_list->i_count = p_var->choices.i_count;
 393             for( i = 0 ; i < p_var->choices.i_count ; i++ )
 394             {
 395                 p_val->p_list->p_values[i] = p_var->choices.p_values[i];
 396                 p_var->pf_dup( &p_val->p_list->p_values[i] );
 397             }
 398             break;
 399         case VLC_VAR_FREELIST:
 400             for( i = p_val->p_list->i_count ; i-- ; )
 401             {
 402                 p_var->pf_free( &p_val->p_list->p_values[i] );
 403             }
 404             if( p_val->p_list->i_count )
 405                 free( p_val->p_list->p_values );
 406             free( p_val->p_list );
 407             break;
 408
 409         default:
 410             break;
 411     }
 412
 413     vlc_mutex_unlock( &p_this->var_lock );
 414
 415     return VLC_SUCCESS;
 416 }
 417
 418 /*****************************************************************************
 419  * var_Type: request a variable's type
 420  *****************************************************************************
 421  * This function returns the variable type if it exists, or 0 if the
 422  * variable could not be found.
 423  *****************************************************************************/
 424 int __var_Type( vlc_object_t *p_this, const char *psz_name )
 425 {
 426     int i_var, i_type;
 427
 428     vlc_mutex_lock( &p_this->var_lock );
 429
 430     i_var = Lookup( p_this->p_vars, p_this->i_vars, psz_name );
 431
 432     if( i_var < 0 )
 433     {
 434         vlc_mutex_unlock( &p_this->var_lock );
 435         return 0;
 436     }
 437
 438     i_type = p_this->p_vars[i_var].i_type;
 439
 440     vlc_mutex_unlock( &p_this->var_lock );
 441
 442     return i_type;
 443 }
 444
 445 /*****************************************************************************
 446  * var_Set: set a variable's value
 447  *****************************************************************************
 448  *
 449  *****************************************************************************/
 450 int __var_Set( vlc_object_t *p_this, const char *psz_name, vlc_value_t val )
 451 {
 452     int i_var;
 453     variable_t *p_var;
 454     vlc_value_t oldval;
 455
 456     vlc_mutex_lock( &p_this->var_lock );
 457
 458     i_var = GetUnused( p_this, psz_name );
 459     if( i_var < 0 )
 460     {
 461         vlc_mutex_unlock( &p_this->var_lock );
 462         return i_var;
 463     }
 464
 465     p_var = &p_this->p_vars[i_var];
 466
 467     /* Duplicate data if needed */
 468     p_var->pf_dup( &val );
 469
 470     /* Backup needed stuff */
 471     oldval = p_var->val;
 472
 473     /* Check boundaries and list */
 474     CheckValue( p_var, &val );
 475
 476     /* Set the variable */
 477     p_var->val = val;
 478
 479     /* Deal with callbacks. Tell we're in a callback, release the lock,
 480      * call stored functions, retake the lock. */
 481     if( p_var->i_entries )
 482     {
 483         int i_var;
 484         int i_entries = p_var->i_entries;
 485         callback_entry_t *p_entries = p_var->p_entries;
 486
 487         p_var->b_incallback = VLC_TRUE;
 488         vlc_mutex_unlock( &p_this->var_lock );
 489
 490         /* The real calls */
 491         for( ; i_entries-- ; )
 492         {
 493             p_entries[i_entries].pf_callback( p_this, psz_name, oldval, val,
 494                                               p_entries[i_entries].p_data );
 495         }
 496
 497         vlc_mutex_lock( &p_this->var_lock );
 498
 499         i_var = Lookup( p_this->p_vars, p_this->i_vars, psz_name );
 500         if( i_var < 0 )
 501         {
 502             msg_Err( p_this, "variable %s has disappeared", psz_name );
 503             vlc_mutex_unlock( &p_this->var_lock );
 504             return VLC_ENOVAR;
 505         }
 506
 507         p_var = &p_this->p_vars[i_var];
 508         p_var->b_incallback = VLC_FALSE;
 509     }
 510
 511     /* Free data if needed */
 512     p_var->pf_free( &oldval );
 513
 514     vlc_mutex_unlock( &p_this->var_lock );
 515
 516     return VLC_SUCCESS;
 517 }
 518
 519 /*****************************************************************************
 520  * var_Get: get a variable's value
 521  *****************************************************************************
 522  *
 523  *****************************************************************************/
 524 int __var_Get( vlc_object_t *p_this, const char *psz_name, vlc_value_t *p_val )
 525 {
 526     int i_var;
 527     variable_t *p_var;
 528
 529     vlc_mutex_lock( &p_this->var_lock );
 530
 531     i_var = Lookup( p_this->p_vars, p_this->i_vars, psz_name );
 532
 533     if( i_var < 0 )
 534     {
 535         vlc_mutex_unlock( &p_this->var_lock );
 536         return VLC_ENOVAR;
 537     }
 538
 539     p_var = &p_this->p_vars[i_var];
 540
 541     /* Really get the variable */
 542     *p_val = p_var->val;
 543
 544     /* Duplicate value if needed */
 545     p_var->pf_dup( p_val );
 546
 547     vlc_mutex_unlock( &p_this->var_lock );
 548
 549     return VLC_SUCCESS;
 550 }
 551
 552 /*****************************************************************************
 553  * var_AddCallback: register a callback in a variable
 554  *****************************************************************************
 555  * We store a function pointer pf_callback that will be called upon variable
 556  * modification. p_data is a generic pointer that will be passed as additional
 557  * argument to the callback function.
 558  *****************************************************************************/
 559 int __var_AddCallback( vlc_object_t *p_this, const char *psz_name,
 560                        vlc_callback_t pf_callback, void *p_data )
 561 {
 562     int i_var;
 563     variable_t *p_var;
 564     callback_entry_t entry;
 565
 566     entry.pf_callback = pf_callback;
 567     entry.p_data = p_data;
 568
 569     vlc_mutex_lock( &p_this->var_lock );
 570
 571     i_var = GetUnused( p_this, psz_name );
 572     if( i_var < 0 )
 573     {
 574         vlc_mutex_unlock( &p_this->var_lock );
 575         return i_var;
 576     }
 577
 578     p_var = &p_this->p_vars[i_var];
 579
 580     INSERT_ELEM( p_var->p_entries,
 581                  p_var->i_entries,
 582                  p_var->i_entries,
 583                  entry );
 584
 585     vlc_mutex_unlock( &p_this->var_lock );
 586
 587     return VLC_SUCCESS;
 588 }
 589
 590 /*****************************************************************************
 591  * var_DelCallback: remove a callback from a variable
 592  *****************************************************************************
 593  * pf_callback and p_data have to be given again, because different objects
 594  * might have registered the same callback function.
 595  *****************************************************************************/
 596 int __var_DelCallback( vlc_object_t *p_this, const char *psz_name,
 597                        vlc_callback_t pf_callback, void *p_data )
 598 {
 599     int i_entry, i_var;
 600     variable_t *p_var;
 601
 602     vlc_mutex_lock( &p_this->var_lock );
 603
 604     i_var = GetUnused( p_this, psz_name );
 605     if( i_var < 0 )
 606     {
 607         vlc_mutex_unlock( &p_this->var_lock );
 608         return i_var;
 609     }
 610
 611     p_var = &p_this->p_vars[i_var];
 612
 613     for( i_entry = p_var->i_entries ; i_entry-- ; )
 614     {
 615         if( p_var->p_entries[i_entry].pf_callback == pf_callback
 616             && p_var->p_entries[i_entry].p_data == p_data )
 617         {
 618             break;
 619         }
 620     }
 621
 622     if( i_entry < 0 )
 623     {
 624         vlc_mutex_unlock( &p_this->var_lock );
 625         return VLC_EGENERIC;
 626     }
 627
 628     REMOVE_ELEM( p_var->p_entries, p_var->i_entries, i_entry );
 629
 630     vlc_mutex_unlock( &p_this->var_lock );
 631
 632     return VLC_SUCCESS;
 633 }
 634
 635 /* Following functions are local */
 636
 637 /*****************************************************************************
 638  * GetUnused: find an unused variable from its name
 639  *****************************************************************************
 640  * We do i_tries tries before giving up, just in case the variable is being
 641  * modified and called from a callback.
 642  *****************************************************************************/
 643 static int GetUnused( vlc_object_t *p_this, const char *psz_name )
 644 {
 645     int i_var, i_tries = 0;
 646
 647     while( VLC_TRUE )
 648     {
 649         i_var = Lookup( p_this->p_vars, p_this->i_vars, psz_name );
 650         if( i_var < 0 )
 651         {
 652             return VLC_ENOVAR;
 653         }
 654
 655         if( ! p_this->p_vars[i_var].b_incallback )
 656         {
 657             return i_var;
 658         }
 659
 660         if( i_tries++ > 100 )
 661         {
 662             msg_Err( p_this, "caught in a callback deadlock?" );
 663             return VLC_ETIMEOUT;
 664         }
 665
 666         vlc_mutex_unlock( &p_this->var_lock );
 667         msleep( THREAD_SLEEP );
 668         vlc_mutex_lock( &p_this->var_lock );
 669     }
 670 }
 671
 672 /*****************************************************************************
 673  * HashString: our cool hash function
 674  *****************************************************************************
 675  * This function is not intended to be crypto-secure, we only want it to be
 676  * fast and not suck too much. This one is pretty fast and did 0 collisions
 677  * in wenglish's dictionary.
 678  *****************************************************************************/
 679 static uint32_t HashString( const char *psz_string )
 680 {
 681     uint32_t i_hash = 0;
 682
 683     while( *psz_string )
 684     {
 685         i_hash += *psz_string++;
 686         i_hash += i_hash << 10;
 687         i_hash ^= i_hash >> 8;
 688     }
 689
 690     return i_hash;
 691 }
 692
 693 /*****************************************************************************
 694  * Insert: find an empty slot to insert a new variable
 695  *****************************************************************************
 696  * We use a recursive inner function indexed on the hash. This function does
 697  * nothing in the rare cases where a collision may occur, see Lookup()
 698  * to see how we handle them.
 699  * XXX: does this really need to be written recursively?
 700  *****************************************************************************/
 701 static int Insert( variable_t *p_vars, int i_count, const char *psz_name )
 702 {
 703     if( i_count == 0 )
 704     {
 705         return 0;
 706     }
 707
 708     return InsertInner( p_vars, i_count, HashString( psz_name ) );
 709 }
 710
 711 static int InsertInner( variable_t *p_vars, int i_count, uint32_t i_hash )
 712 {
 713     int i_middle;
 714
 715     if( i_hash <= p_vars[0].i_hash )
 716     {
 717         return 0;
 718     }
 719
 720     if( i_hash >= p_vars[i_count - 1].i_hash )
 721     {
 722         return i_count;
 723     }
 724
 725     i_middle = i_count / 2;
 726
 727     /* We know that 0 < i_middle */
 728     if( i_hash < p_vars[i_middle].i_hash )
 729     {
 730         return InsertInner( p_vars, i_middle, i_hash );
 731     }
 732
 733     /* We know that i_middle + 1 < i_count */
 734     if( i_hash > p_vars[i_middle + 1].i_hash )
 735     {
 736         return i_middle + 1 + InsertInner( p_vars + i_middle + 1,
 737                                            i_count - i_middle - 1,
 738                                            i_hash );
 739     }
 740
 741     return i_middle + 1;
 742 }
 743
 744 /*****************************************************************************
 745  * Lookup: find an existing variable given its name
 746  *****************************************************************************
 747  * We use a recursive inner function indexed on the hash. Care is taken of
 748  * possible hash collisions.
 749  * XXX: does this really need to be written recursively?
 750  *****************************************************************************/
 751 static int Lookup( variable_t *p_vars, int i_count, const char *psz_name )
 752 {
 753     uint32_t i_hash;
 754     int i, i_pos;
 755
 756     if( i_count == 0 )
 757     {
 758         return -1;
 759     }
 760
 761     i_hash = HashString( psz_name );
 762
 763     i_pos = LookupInner( p_vars, i_count, i_hash );
 764
 765     /* Hash not found */
 766     if( i_hash != p_vars[i_pos].i_hash )
 767     {
 768         return -1;
 769     }
 770
 771     /* Hash found, entry found */
 772     if( !strcmp( psz_name, p_vars[i_pos].psz_name ) )
 773     {
 774         return i_pos;
 775     }
 776
 777     /* Hash collision! This should be very rare, but we cannot guarantee
 778      * it will never happen. Just do an exhaustive search amongst all
 779      * entries with the same hash. */
 780     for( i = i_pos - 1 ; i > 0 && i_hash == p_vars[i].i_hash ; i-- )
 781     {
 782         if( !strcmp( psz_name, p_vars[i].psz_name ) )
 783         {
 784             return i;
 785         }
 786     }
 787
 788     for( i = i_pos + 1 ; i < i_count && i_hash == p_vars[i].i_hash ; i++ )
 789     {
 790         if( !strcmp( psz_name, p_vars[i].psz_name ) )
 791         {
 792             return i;
 793         }
 794     }
 795
 796     /* Hash found, but entry not found */
 797     return -1;
 798 }
 799
 800 static int LookupInner( variable_t *p_vars, int i_count, uint32_t i_hash )
 801 {
 802     int i_middle;
 803
 804     if( i_hash <= p_vars[0].i_hash )
 805     {
 806         return 0;
 807     }
 808
 809     if( i_hash >= p_vars[i_count-1].i_hash )
 810     {
 811         return i_count - 1;
 812     }
 813
 814     i_middle = i_count / 2;
 815
 816     /* We know that 0 < i_middle */
 817     if( i_hash < p_vars[i_middle].i_hash )
 818     {
 819         return LookupInner( p_vars, i_middle, i_hash );
 820     }
 821
 822     /* We know that i_middle + 1 < i_count */
 823     if( i_hash > p_vars[i_middle].i_hash )
 824     {
 825         return i_middle + LookupInner( p_vars + i_middle,
 826                                        i_count - i_middle,
 827                                        i_hash );
 828     }
 829
 830     return i_middle;
 831 }
 832
 833 /*****************************************************************************
 834  * CheckValue: check that a value is valid wrt. a variable
 835  *****************************************************************************
 836  * This function checks p_val's value against p_var's limitations such as
 837  * minimal and maximal value, step, in-list position, and modifies p_val if
 838  * necessary.
 839  *****************************************************************************/
 840 static void CheckValue ( variable_t *p_var, vlc_value_t *p_val )
 841 {
 842     /* Check that our variable is in the list */
 843     if( p_var->i_type & VLC_VAR_HASCHOICE && p_var->choices.i_count )
 844     {
 845         int i;
 846
 847         /* FIXME: the list is sorted, dude. Use something cleverer. */
 848         for( i = p_var->choices.i_count ; i-- ; )
 849         {
 850             if( p_var->pf_cmp( *p_val, p_var->choices.p_values[i] ) == 0 )
 851             {
 852                 break;
 853             }
 854         }
 855
 856         /* If not found, change it to anything vaguely valid */
 857         if( i < 0 )
 858         {
 859             /* Free the old variable, get the new one, dup it */
 860             p_var->pf_free( p_val );
 861             *p_val = p_var->choices.p_values[p_var->i_default >= 0
 862                                           ? p_var->i_default : 0 ];
 863             p_var->pf_dup( p_val );
 864         }
 865     }
 866
 867     /* Check that our variable is within the bounds */
 868     switch( p_var->i_type & VLC_VAR_TYPE )
 869     {
 870         case VLC_VAR_INTEGER:
 871             if( p_var->i_type & VLC_VAR_HASSTEP && p_var->step.i_int
 872                  && (p_val->i_int % p_var->step.i_int) )
 873             {
 874                 p_val->i_int = (p_val->i_int + (p_var->step.i_int / 2))
 875                                / p_var->step.i_int * p_var->step.i_int;
 876             }
 877             if( p_var->i_type & VLC_VAR_HASMIN
 878                  && p_val->i_int < p_var->min.i_int )
 879             {
 880                 p_val->i_int = p_var->min.i_int;
 881             }
 882             if( p_var->i_type & VLC_VAR_HASMAX
 883                  && p_val->i_int > p_var->max.i_int )
 884             {
 885                 p_val->i_int = p_var->max.i_int;
 886             }
 887             break;
 888         case VLC_VAR_FLOAT:
 889             if( p_var->i_type & VLC_VAR_HASSTEP && p_var->step.f_float )
 890             {
 891                 float f_round = p_var->step.f_float * (float)(int)( 0.5 +
 892                                         p_val->f_float / p_var->step.f_float );
 893                 if( p_val->f_float != f_round )
 894                 {
 895                     p_val->f_float = f_round;
 896                 }
 897             }
 898             if( p_var->i_type & VLC_VAR_HASMIN
 899                  && p_val->f_float < p_var->min.f_float )
 900             {
 901                 p_val->f_float = p_var->min.f_float;
 902             }
 903             if( p_var->i_type & VLC_VAR_HASMAX
 904                  && p_val->f_float > p_var->max.f_float )
 905             {
 906                 p_val->f_float = p_var->max.f_float;
 907             }
 908             break;
 909         case VLC_VAR_TIME:
 910             /* FIXME: TODO */
 911             break;
 912     }
 913 }