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