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