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