don't rely on malloc to handle (0) parameter; abort before.
[citadel] / libcitadel / lib / xdgmime / xdgmimecache.c
1 /* -*- mode: C; c-file-style: "gnu" -*- */
2 /* xdgmimealias.c: Private file.  mmappable caches for mime data
3  *
4  * More info can be found at http://www.freedesktop.org/standards/
5  *
6  * Copyright (C) 2005  Matthias Clasen <mclasen@redhat.com>
7  *
8  * Licensed under the Academic Free License version 2.0
9  * Or under the following terms:
10  *
11  * This library is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU Lesser General Public
13  * License as published by the Free Software Foundation; either
14  * version 2 of the License, or (at your option) any later version.
15  *
16  * This library is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
19  * Lesser General Public License for more details.
20  *
21  * You should have received a copy of the GNU Lesser General Public
22  * License along with this library; if not, write to the
23  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
24  * Boston, MA 02111-1307, USA.
25  */
26
27 #ifdef HAVE_CONFIG_H
28 #include <config.h>
29 #endif
30
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34
35 #include <fcntl.h>
36 #include <unistd.h>
37 #include <fnmatch.h>
38 #include <assert.h>
39
40 #include <netinet/in.h> /* for ntohl/ntohs */
41
42 #ifdef HAVE_MMAP
43 #include <sys/mman.h>
44 #else
45 #warning Building xdgmime without MMAP support. Binary "mime.info" cache files will not be used.
46 #endif
47
48 #include <sys/stat.h>
49 #include <sys/types.h>
50
51 #include "xdgmimecache.h"
52 #include "xdgmimeint.h"
53
54 #ifndef MAX
55 #define MAX(a,b) ((a) > (b) ? (a) : (b))
56 #endif
57
58 #ifndef FALSE
59 #define FALSE   (0)
60 #endif
61
62 #ifndef TRUE
63 #define TRUE    (!FALSE)
64 #endif
65
66 #ifndef _O_BINARY
67 #define _O_BINARY 0
68 #endif
69
70 #ifndef MAP_FAILED
71 #define MAP_FAILED ((void *) -1)
72 #endif
73
74 #define MAJOR_VERSION 1
75 #define MINOR_VERSION 0
76
77 struct _XdgMimeCache
78 {
79   int ref_count;
80
81   size_t  size;
82   char   *buffer;
83 };
84
85 #define GET_UINT16(cache,offset) (ntohs(*(xdg_uint16_t*)((cache) + (offset))))
86 #define GET_UINT32(cache,offset) (ntohl(*(xdg_uint32_t*)((cache) + (offset))))
87
88 XdgMimeCache *
89 _xdg_mime_cache_ref (XdgMimeCache *cache)
90 {
91   cache->ref_count++;
92   return cache;
93 }
94
95 void
96 _xdg_mime_cache_unref (XdgMimeCache *cache)
97 {
98   cache->ref_count--;
99
100   if (cache->ref_count == 0)
101     {
102 #ifdef HAVE_MMAP
103       munmap (cache->buffer, cache->size);
104 #endif
105       free (cache);
106     }
107 }
108
109 XdgMimeCache *
110 _xdg_mime_cache_new_from_file (const char *file_name)
111 {
112   XdgMimeCache *cache = NULL;
113
114 #ifdef HAVE_MMAP
115   int fd = -1;
116   struct stat st;
117   char *buffer = NULL;
118
119   /* Open the file and map it into memory */
120   fd = open (file_name, O_RDONLY|_O_BINARY, 0);
121
122   if (fd < 0)
123     return NULL;
124   
125   if (fstat (fd, &st) < 0 || st.st_size < 4)
126     goto done;
127
128   buffer = (char *) mmap (NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
129
130   if (buffer == MAP_FAILED)
131     goto done;
132
133   /* Verify version */
134   if (GET_UINT16 (buffer, 0) != MAJOR_VERSION ||
135       GET_UINT16 (buffer, 2) != MINOR_VERSION)
136     {
137       munmap (buffer, st.st_size);
138
139       goto done;
140     }
141   
142   cache = (XdgMimeCache *) malloc (sizeof (XdgMimeCache));
143   cache->ref_count = 1;
144   cache->buffer = buffer;
145   cache->size = st.st_size;
146
147  done:
148   if (fd != -1)
149     close (fd);
150
151 #endif  /* HAVE_MMAP */
152
153   return cache;
154 }
155
156 static int
157 cache_magic_matchlet_compare_to_data (XdgMimeCache *cache, 
158                                       xdg_uint32_t  offset,
159                                       const void   *data,
160                                       size_t        len)
161 {
162   xdg_uint32_t range_start = GET_UINT32 (cache->buffer, offset);
163   xdg_uint32_t range_length = GET_UINT32 (cache->buffer, offset + 4);
164   xdg_uint32_t data_length = GET_UINT32 (cache->buffer, offset + 12);
165   xdg_uint32_t data_offset = GET_UINT32 (cache->buffer, offset + 16);
166   xdg_uint32_t mask_offset = GET_UINT32 (cache->buffer, offset + 20);
167   
168   int i, j;
169
170   for (i = range_start; i <= range_start + range_length; i++)
171     {
172       int valid_matchlet = TRUE;
173       
174       if (i + data_length > len)
175         return FALSE;
176
177       if (mask_offset)
178         {
179           for (j = 0; j < data_length; j++)
180             {
181               if ((((unsigned char *)cache->buffer)[data_offset + j] & ((unsigned char *)cache->buffer)[mask_offset + j]) !=
182                   ((((unsigned char *) data)[j + i]) & ((unsigned char *)cache->buffer)[mask_offset + j]))
183                 {
184                   valid_matchlet = FALSE;
185                   break;
186                 }
187             }
188         }
189       else
190         {
191           for (j = 0; j < data_length; j++)
192             {
193               if (((unsigned char *)cache->buffer)[data_offset + j] != ((unsigned char *) data)[j + i])
194                 {
195                   valid_matchlet = FALSE;
196                   break;
197                 }
198             }
199         }
200       
201       if (valid_matchlet)
202         return TRUE;
203     }
204   
205   return FALSE;  
206 }
207
208 static int
209 cache_magic_matchlet_compare (XdgMimeCache *cache, 
210                               xdg_uint32_t  offset,
211                               const void   *data,
212                               size_t        len)
213 {
214   xdg_uint32_t n_children = GET_UINT32 (cache->buffer, offset + 24);
215   xdg_uint32_t child_offset = GET_UINT32 (cache->buffer, offset + 28);
216
217   int i;
218   
219   if (cache_magic_matchlet_compare_to_data (cache, offset, data, len))
220     {
221       if (n_children == 0)
222         return TRUE;
223       
224       for (i = 0; i < n_children; i++)
225         {
226           if (cache_magic_matchlet_compare (cache, child_offset + 32 * i,
227                                             data, len))
228             return TRUE;
229         }
230     }
231   
232   return FALSE;  
233 }
234
235 static const char *
236 cache_magic_compare_to_data (XdgMimeCache *cache, 
237                              xdg_uint32_t  offset,
238                              const void   *data, 
239                              size_t        len, 
240                              int          *prio)
241 {
242   xdg_uint32_t priority = GET_UINT32 (cache->buffer, offset);
243   xdg_uint32_t mimetype_offset = GET_UINT32 (cache->buffer, offset + 4);
244   xdg_uint32_t n_matchlets = GET_UINT32 (cache->buffer, offset + 8);
245   xdg_uint32_t matchlet_offset = GET_UINT32 (cache->buffer, offset + 12);
246
247   int i;
248
249   for (i = 0; i < n_matchlets; i++)
250     {
251       if (cache_magic_matchlet_compare (cache, matchlet_offset + i * 32, 
252                                         data, len))
253         {
254           *prio = priority;
255           
256           return cache->buffer + mimetype_offset;
257         }
258     }
259
260   return NULL;
261 }
262
263 static const char *
264 cache_magic_lookup_data (XdgMimeCache *cache, 
265                          const void   *data, 
266                          size_t        len, 
267                          int          *prio,
268                          const char   *mime_types[],
269                          int           n_mime_types)
270 {
271   xdg_uint32_t list_offset;
272   xdg_uint32_t n_entries;
273   xdg_uint32_t offset;
274
275   int j, n;
276
277   *prio = 0;
278
279   list_offset = GET_UINT32 (cache->buffer, 24);
280   n_entries = GET_UINT32 (cache->buffer, list_offset);
281   offset = GET_UINT32 (cache->buffer, list_offset + 8);
282   
283   for (j = 0; j < n_entries; j++)
284     {
285       const char *match;
286
287       match = cache_magic_compare_to_data (cache, offset + 16 * j, 
288                                            data, len, prio);
289       if (match)
290         return match;
291       else
292         {
293           xdg_uint32_t mimetype_offset;
294           const char *non_match;
295           
296           mimetype_offset = GET_UINT32 (cache->buffer, offset + 16 * j + 4);
297           non_match = cache->buffer + mimetype_offset;
298
299           for (n = 0; n < n_mime_types; n++)
300             {
301               if (mime_types[n] && 
302                   xdg_mime_mime_type_equal (mime_types[n], non_match))
303                 mime_types[n] = NULL;
304             }
305         }
306     }
307
308   return NULL;
309 }
310
311 static const char *
312 cache_alias_lookup (const char *alias)
313 {
314   const char *ptr;
315   int i, min, max, mid, cmp;
316
317   for (i = 0; _xdg_mime_caches[i]; i++)
318     {
319       XdgMimeCache *cache = _xdg_mime_caches[i];
320       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 4);
321       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
322       xdg_uint32_t offset;
323
324       min = 0; 
325       max = n_entries - 1;
326       while (max >= min) 
327         {
328           mid = (min + max) / 2;
329
330           offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * mid);
331           ptr = cache->buffer + offset;
332           cmp = strcmp (ptr, alias);
333           
334           if (cmp < 0)
335             min = mid + 1;
336           else if (cmp > 0)
337             max = mid - 1;
338           else
339             {
340               offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * mid + 4);
341               return cache->buffer + offset;
342             }
343         }
344     }
345
346   return NULL;
347 }
348
349 static int
350 cache_glob_lookup_literal (const char *file_name,
351                            const char *mime_types[],
352                            int         n_mime_types)
353 {
354   const char *ptr;
355   int i, min, max, mid, cmp;
356
357   for (i = 0; _xdg_mime_caches[i]; i++)
358     {
359       XdgMimeCache *cache = _xdg_mime_caches[i];
360       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 12);
361       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
362       xdg_uint32_t offset;
363
364       min = 0; 
365       max = n_entries - 1;
366       while (max >= min) 
367         {
368           mid = (min + max) / 2;
369
370           offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * mid);
371           ptr = cache->buffer + offset;
372           cmp = strcmp (ptr, file_name);
373           
374           if (cmp < 0)
375             min = mid + 1;
376           else if (cmp > 0)
377             max = mid - 1;
378           else
379             {
380               offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * mid + 4);
381               mime_types[0] = (const char *)(cache->buffer + offset);
382               
383               return 1;
384             }
385         }
386     }
387
388   return 0;
389 }
390
391 static int
392 cache_glob_lookup_fnmatch (const char *file_name,
393                            const char *mime_types[],
394                            int         n_mime_types)
395 {
396   const char *mime_type;
397   const char *ptr;
398
399   int i, j, n;
400
401   n = 0;
402   for (i = 0; _xdg_mime_caches[i]; i++)
403     {
404       XdgMimeCache *cache = _xdg_mime_caches[i];
405
406       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 20);
407       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
408
409       for (j = 0; j < n_entries && n < n_mime_types; j++)
410         {
411           xdg_uint32_t offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * j);
412           xdg_uint32_t mimetype_offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * j + 4);
413           ptr = cache->buffer + offset;
414           mime_type = cache->buffer + mimetype_offset;
415
416           /* FIXME: Not UTF-8 safe */
417           if (fnmatch (ptr, file_name, 0) == 0)
418             mime_types[n++] = mime_type;
419         }
420
421       if (n > 0)
422         return n;
423     }
424   
425   return 0;
426 }
427
428 static int
429 cache_glob_node_lookup_suffix (XdgMimeCache *cache,
430                                xdg_uint32_t  n_entries,
431                                xdg_uint32_t  offset,
432                                const char   *suffix, 
433                                int           ignore_case,
434                                const char   *mime_types[],
435                                int           n_mime_types)
436 {
437   xdg_unichar_t character;
438   xdg_unichar_t match_char;
439   xdg_uint32_t mimetype_offset;
440   xdg_uint32_t n_children;
441   xdg_uint32_t child_offset; 
442
443   int min, max, mid, n, i;
444
445   character = _xdg_utf8_to_ucs4 (suffix);
446   if (ignore_case)
447     character = _xdg_ucs4_to_lower (character);
448
449   min = 0;
450   max = n_entries - 1;
451   while (max >= min)
452     {
453       mid = (min + max) /  2;
454
455       match_char = GET_UINT32 (cache->buffer, offset + 16 * mid);
456
457       if (match_char < character)
458         min = mid + 1;
459       else if (match_char > character)
460         max = mid - 1;
461       else 
462         {
463           suffix = _xdg_utf8_next_char (suffix);
464           if (*suffix == '\0')
465             {
466               mimetype_offset = GET_UINT32 (cache->buffer, offset + 16 * mid + 4);
467               n = 0;
468               if (cache->buffer[mimetype_offset])
469                 mime_types[n++] = cache->buffer + mimetype_offset;
470
471               n_children = GET_UINT32 (cache->buffer, offset + 16 * mid + 8);
472               child_offset = GET_UINT32 (cache->buffer, offset + 16 * mid + 12);
473               i = 0;
474               while (n < n_mime_types && i < n_children)
475                 {
476                   match_char = GET_UINT32 (cache->buffer, child_offset + 16 * i);
477                   mimetype_offset = GET_UINT32 (cache->buffer, offset + 16 * i + 4);
478                   if (match_char != 0)
479                     break;
480
481                   mime_types[n++] = cache->buffer + mimetype_offset;
482                   i++;
483                 }
484
485               return n;
486             }
487           else
488             {
489               n_children = GET_UINT32 (cache->buffer, offset + 16 * mid + 8);
490               child_offset = GET_UINT32 (cache->buffer, offset + 16 * mid + 12);
491       
492               return cache_glob_node_lookup_suffix (cache, 
493                                                     n_children, child_offset,
494                                                     suffix, ignore_case,
495                                                     mime_types,
496                                                     n_mime_types);
497             }
498         }
499     }
500
501   return 0;
502 }
503
504 static int
505 cache_glob_lookup_suffix (const char *suffix, 
506                           int         ignore_case,
507                           const char *mime_types[],
508                           int         n_mime_types)
509 {
510   int i, n;
511
512   for (i = 0; _xdg_mime_caches[i]; i++)
513     {
514       XdgMimeCache *cache = _xdg_mime_caches[i];
515
516       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 16);
517       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
518       xdg_uint32_t offset = GET_UINT32 (cache->buffer, list_offset + 4);
519
520       n = cache_glob_node_lookup_suffix (cache, 
521                                          n_entries, offset, 
522                                          suffix, ignore_case,
523                                          mime_types,
524                                          n_mime_types);
525       if (n > 0)
526         return n;
527     }
528
529   return 0;
530 }
531
532 static void
533 find_stopchars (char *stopchars)
534 {
535   int i, j, k, l;
536  
537   k = 0;
538   for (i = 0; _xdg_mime_caches[i]; i++)
539     {
540       XdgMimeCache *cache = _xdg_mime_caches[i];
541
542       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 16);
543       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
544       xdg_uint32_t offset = GET_UINT32 (cache->buffer, list_offset + 4);
545
546       for (j = 0; j < n_entries; j++)
547         {
548           xdg_uint32_t match_char = GET_UINT32 (cache->buffer, offset);
549           
550           if (match_char < 128)
551             {
552               for (l = 0; l < k; l++)
553                 if (stopchars[l] == match_char)
554                   break;
555               if (l == k)
556                 {
557                   stopchars[k] = (char) match_char;
558                   k++;
559                 }
560             }
561
562           offset += 16;
563         }
564     }
565
566   stopchars[k] = '\0';
567 }
568
569 static int
570 cache_glob_lookup_file_name (const char *file_name, 
571                              const char *mime_types[],
572                              int         n_mime_types)
573 {
574   const char *ptr;
575   char stopchars[128];
576   int n;
577   
578   assert (file_name != NULL);
579
580   /* First, check the literals */
581   n = cache_glob_lookup_literal (file_name, mime_types, n_mime_types);
582   if (n > 0)
583     return n;
584
585   find_stopchars (stopchars);
586
587   /* Next, check suffixes */
588   ptr = strpbrk (file_name, stopchars);
589   while (ptr)
590     {
591       n = cache_glob_lookup_suffix (ptr, FALSE, mime_types, n_mime_types);
592       if (n > 0)
593         return n;
594       
595       n = cache_glob_lookup_suffix (ptr, TRUE, mime_types, n_mime_types);
596       if (n > 0)
597         return n;
598
599       ptr = strpbrk (ptr + 1, stopchars);
600     }
601   
602   /* Last, try fnmatch */
603   return cache_glob_lookup_fnmatch (file_name, mime_types, n_mime_types);
604 }
605
606 int
607 _xdg_mime_cache_get_max_buffer_extents (void)
608 {
609   xdg_uint32_t offset;
610   xdg_uint32_t max_extent;
611   int i;
612
613   max_extent = 0;
614   for (i = 0; _xdg_mime_caches[i]; i++)
615     {
616       XdgMimeCache *cache = _xdg_mime_caches[i];
617
618       offset = GET_UINT32 (cache->buffer, 24);
619       max_extent = MAX (max_extent, GET_UINT32 (cache->buffer, offset + 4));
620     }
621
622   return max_extent;
623 }
624
625 static const char *
626 cache_get_mime_type_for_data (const void *data,
627                               size_t      len,
628                               const char *mime_types[],
629                               int         n_mime_types)
630 {
631   const char *mime_type;
632   int i, n, priority;
633
634   priority = 0;
635   mime_type = NULL;
636   for (i = 0; _xdg_mime_caches[i]; i++)
637     {
638       XdgMimeCache *cache = _xdg_mime_caches[i];
639
640       int prio;
641       const char *match;
642
643       match = cache_magic_lookup_data (cache, data, len, &prio, 
644                                        mime_types, n_mime_types);
645       if (prio > priority)
646         {
647           priority = prio;
648           mime_type = match;
649         }
650     }
651
652   if (priority > 0)
653     return mime_type;
654
655   for (n = 0; n < n_mime_types; n++)
656     {
657       if (mime_types[n])
658         return mime_types[n];
659     }
660
661   return XDG_MIME_TYPE_UNKNOWN;
662 }
663
664 const char *
665 _xdg_mime_cache_get_mime_type_for_data (const void *data,
666                                         size_t      len)
667 {
668   return cache_get_mime_type_for_data (data, len, NULL, 0);
669 }
670
671 const char *
672 _xdg_mime_cache_get_mime_type_for_file (const char  *file_name,
673                                         struct stat *statbuf)
674 {
675   const char *mime_type;
676   const char *mime_types[2];
677   FILE *file;
678   unsigned char *data;
679   int max_extent;
680   int bytes_read;
681   struct stat buf;
682   const char *base_name;
683   int n;
684
685   if (file_name == NULL)
686     return NULL;
687
688   if (! _xdg_utf8_validate (file_name))
689     return NULL;
690
691   base_name = _xdg_get_base_name (file_name);
692   n = cache_glob_lookup_file_name (base_name, mime_types, 2);
693
694   if (n == 1)
695     return mime_types[0];
696
697   if (!statbuf)
698     {
699       if (stat (file_name, &buf) != 0)
700         return XDG_MIME_TYPE_UNKNOWN;
701
702       statbuf = &buf;
703     }
704
705   if (!S_ISREG (statbuf->st_mode))
706     return XDG_MIME_TYPE_UNKNOWN;
707
708   /* FIXME: Need to make sure that max_extent isn't totally broken.  This could
709    * be large and need getting from a stream instead of just reading it all
710    * in. */
711   max_extent = _xdg_mime_cache_get_max_buffer_extents ();
712   if (max_extent == 0)
713     return XDG_MIME_TYPE_UNKNOWN;
714   data = malloc (max_extent);
715   if (data == NULL)
716     return XDG_MIME_TYPE_UNKNOWN;
717         
718   file = fopen (file_name, "r");
719   if (file == NULL)
720     {
721       free (data);
722       return XDG_MIME_TYPE_UNKNOWN;
723     }
724
725   bytes_read = fread (data, 1, max_extent, file);
726   if (ferror (file))
727     {
728       free (data);
729       fclose (file);
730       return XDG_MIME_TYPE_UNKNOWN;
731     }
732
733   mime_type = cache_get_mime_type_for_data (data, bytes_read,
734                                             mime_types, n);
735
736   free (data);
737   fclose (file);
738
739   return mime_type;
740 }
741
742 const char *
743 _xdg_mime_cache_get_mime_type_from_file_name (const char *file_name)
744 {
745   const char *mime_types[2];
746
747   if (cache_glob_lookup_file_name (file_name, mime_types, 2) == 1)
748     return mime_types[0];
749   else
750     return XDG_MIME_TYPE_UNKNOWN;
751 }
752
753 #if 1
754 static int
755 is_super_type (const char *mime)
756 {
757   int length;
758   const char *type;
759
760   length = strlen (mime);
761   type = &(mime[length - 2]);
762
763   if (strcmp (type, "/*") == 0)
764     return 1;
765
766   return 0;
767 }
768 #endif
769
770 int
771 _xdg_mime_cache_mime_type_subclass (const char *mime,
772                                     const char *base)
773 {
774   const char *umime, *ubase;
775
776   int i, j, min, max, med, cmp;
777   
778   umime = _xdg_mime_cache_unalias_mime_type (mime);
779   ubase = _xdg_mime_cache_unalias_mime_type (base);
780
781   if (strcmp (umime, ubase) == 0)
782     return 1;
783
784   /* We really want to handle text/ * in GtkFileFilter, so we just
785    * turn on the supertype matching
786    */
787 #if 1
788   /* Handle supertypes */
789   if (is_super_type (ubase) &&
790       xdg_mime_media_type_equal (umime, ubase))
791     return 1;
792 #endif
793
794   /*  Handle special cases text/plain and application/octet-stream */
795   if (strcmp (ubase, "text/plain") == 0 && 
796       strncmp (umime, "text/", 5) == 0)
797     return 1;
798
799   if (strcmp (ubase, "application/octet-stream") == 0)
800     return 1;
801  
802   for (i = 0; _xdg_mime_caches[i]; i++)
803     {
804       XdgMimeCache *cache = _xdg_mime_caches[i];
805       
806       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 8);
807       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
808       xdg_uint32_t offset, n_parents, parent_offset;
809
810       min = 0; 
811       max = n_entries - 1;
812       while (max >= min)
813         {
814           med = (min + max)/2;
815           
816           offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * med);
817           cmp = strcmp (cache->buffer + offset, umime);
818           if (cmp < 0)
819             min = med + 1;
820           else if (cmp > 0)
821             max = med - 1;
822           else
823             {
824               offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * med + 4);
825               n_parents = GET_UINT32 (cache->buffer, offset);
826               
827               for (j = 0; j < n_parents; j++)
828                 {
829                   parent_offset = GET_UINT32 (cache->buffer, offset + 4 + 4 * j);
830                   if (_xdg_mime_cache_mime_type_subclass (cache->buffer + parent_offset, ubase))
831                     return 1;
832                 }
833
834               break;
835             }
836         }
837     }
838
839   return 0;
840 }
841
842 const char *
843 _xdg_mime_cache_unalias_mime_type (const char *mime)
844 {
845   const char *lookup;
846   
847   lookup = cache_alias_lookup (mime);
848   
849   if (lookup)
850     return lookup;
851   
852   return mime;  
853 }
854
855 char **
856 _xdg_mime_cache_list_mime_parents (const char *mime)
857 {
858   int i, j, p;
859   char *all_parents[128]; /* we'll stop at 128 */ 
860   char **result;
861
862   mime = xdg_mime_unalias_mime_type (mime);
863
864   p = 0;
865   for (i = 0; _xdg_mime_caches[i]; i++)
866     {
867       XdgMimeCache *cache = _xdg_mime_caches[i];
868
869       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 8);
870       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
871
872       for (j = 0; j < n_entries; j++)
873         {
874           xdg_uint32_t mimetype_offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * j);
875           xdg_uint32_t parents_offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * j + 4);
876
877           if (strcmp (cache->buffer + mimetype_offset, mime) == 0)
878             {
879               int k;
880               xdg_uint32_t parent_mime_offset;
881               xdg_uint32_t n_parents = GET_UINT32 (cache->buffer, parents_offset);
882
883               for (k = 0; k < n_parents && p < 127; k++)
884                 {
885                   parent_mime_offset = GET_UINT32 (cache->buffer, parents_offset + 4 + 4 * k);
886                   all_parents[p++] = cache->buffer + parent_mime_offset;
887                 }
888
889               break;
890             }
891         }
892     }
893   all_parents[p++] = 0;
894   
895   result = (char **) malloc (p * sizeof (char *));
896   memcpy (result, all_parents, p * sizeof (char *));
897
898   return result;
899 }
900