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