Release version 0.0.16
[platform/core/appfw/xdgmime.git] / xdgmime / src / 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_MIN 1
76 #define MINOR_VERSION_MAX 2
77
78 struct _XdgMimeCache
79 {
80   int ref_count;
81   int minor;
82
83   size_t  size;
84   char   *buffer;
85 };
86
87 #define GET_UINT16(cache,offset) (ntohs(*(xdg_uint16_t*)((cache) + (offset))))
88 #define GET_UINT32(cache,offset) (ntohl(*(xdg_uint32_t*)((cache) + (offset))))
89
90 XdgMimeCache *
91 _xdg_mime_cache_ref (XdgMimeCache *cache)
92 {
93   cache->ref_count++;
94   return cache;
95 }
96
97 void
98 _xdg_mime_cache_unref (XdgMimeCache *cache)
99 {
100   cache->ref_count--;
101
102   if (cache->ref_count == 0)
103     {
104 #ifdef HAVE_MMAP
105       munmap (cache->buffer, cache->size);
106 #endif
107       free (cache);
108     }
109 }
110
111 XdgMimeCache *
112 _xdg_mime_cache_new_from_file (const char *file_name)
113 {
114   XdgMimeCache *cache = NULL;
115
116 #ifdef HAVE_MMAP
117   int fd = -1;
118   struct stat st;
119   char *buffer = NULL;
120   int minor;
121
122   /* Open the file and map it into memory */
123   fd = open (file_name, O_RDONLY|_O_BINARY, 0);
124
125   if (fd < 0)
126     return NULL;
127
128   if (fstat (fd, &st) < 0 || st.st_size < 4)
129     goto done;
130
131   buffer = (char *) mmap (NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
132
133   if (buffer == MAP_FAILED)
134     goto done;
135
136   minor = GET_UINT16 (buffer, 2);
137   /* Verify version */
138   if (GET_UINT16 (buffer, 0) != MAJOR_VERSION ||
139       (minor < MINOR_VERSION_MIN ||
140        minor > MINOR_VERSION_MAX))
141     {
142       munmap (buffer, st.st_size);
143
144       goto done;
145     }
146
147   cache = (XdgMimeCache *) malloc (sizeof (XdgMimeCache));
148   if (cache == NULL)
149     {
150       munmap (buffer, st.st_size);
151
152       goto done;
153     }
154
155   cache->minor = minor;
156   cache->ref_count = 1;
157   cache->buffer = buffer;
158   cache->size = st.st_size;
159
160  done:
161   if (fd != -1)
162     close (fd);
163
164 #endif  /* HAVE_MMAP */
165
166   return cache;
167 }
168
169 static int
170 cache_magic_matchlet_compare_to_data (XdgMimeCache *cache, 
171                                       xdg_uint32_t  offset,
172                                       const void   *data,
173                                       size_t        len)
174 {
175   xdg_uint32_t range_start = GET_UINT32 (cache->buffer, offset);
176   xdg_uint32_t range_length = GET_UINT32 (cache->buffer, offset + 4);
177   xdg_uint32_t data_length = GET_UINT32 (cache->buffer, offset + 12);
178   xdg_uint32_t data_offset = GET_UINT32 (cache->buffer, offset + 16);
179   xdg_uint32_t mask_offset = GET_UINT32 (cache->buffer, offset + 20);
180   
181   int i, j;
182
183   for (i = range_start; i < range_start + range_length; i++)
184     {
185       int valid_matchlet = TRUE;
186       
187       if (i + data_length > len)
188         return FALSE;
189
190       if (mask_offset)
191         {
192           for (j = 0; j < data_length; j++)
193             {
194               if ((((unsigned char *)cache->buffer)[data_offset + j] & ((unsigned char *)cache->buffer)[mask_offset + j]) !=
195                   ((((unsigned char *) data)[j + i]) & ((unsigned char *)cache->buffer)[mask_offset + j]))
196                 {
197                   valid_matchlet = FALSE;
198                   break;
199                 }
200             }
201         }
202       else
203         {
204           for (j = 0; j < data_length; j++)
205             {
206               if (((unsigned char *)cache->buffer)[data_offset + j] != ((unsigned char *) data)[j + i])
207                 {
208                   valid_matchlet = FALSE;
209                   break;
210                 }
211             }
212         }
213       
214       if (valid_matchlet)
215         return TRUE;
216     }
217   
218   return FALSE;  
219 }
220
221 static int
222 cache_magic_matchlet_compare (XdgMimeCache *cache, 
223                               xdg_uint32_t  offset,
224                               const void   *data,
225                               size_t        len)
226 {
227   xdg_uint32_t n_children = GET_UINT32 (cache->buffer, offset + 24);
228   xdg_uint32_t child_offset = GET_UINT32 (cache->buffer, offset + 28);
229
230   int i;
231   
232   if (cache_magic_matchlet_compare_to_data (cache, offset, data, len))
233     {
234       if (n_children == 0)
235         return TRUE;
236       
237       for (i = 0; i < n_children; i++)
238         {
239           if (cache_magic_matchlet_compare (cache, child_offset + 32 * i,
240                                             data, len))
241             return TRUE;
242         }
243     }
244   
245   return FALSE;  
246 }
247
248 static const char *
249 cache_magic_compare_to_data (XdgMimeCache *cache, 
250                              xdg_uint32_t  offset,
251                              const void   *data, 
252                              size_t        len, 
253                              int          *prio)
254 {
255   xdg_uint32_t priority = GET_UINT32 (cache->buffer, offset);
256   xdg_uint32_t mimetype_offset = GET_UINT32 (cache->buffer, offset + 4);
257   xdg_uint32_t n_matchlets = GET_UINT32 (cache->buffer, offset + 8);
258   xdg_uint32_t matchlet_offset = GET_UINT32 (cache->buffer, offset + 12);
259
260   int i;
261
262   for (i = 0; i < n_matchlets; i++)
263     {
264       if (cache_magic_matchlet_compare (cache, matchlet_offset + i * 32, 
265                                         data, len))
266         {
267           *prio = priority;
268           
269           return cache->buffer + mimetype_offset;
270         }
271     }
272
273   return NULL;
274 }
275
276 static const char *
277 cache_magic_lookup_data (XdgMimeCache *cache, 
278                          const void   *data, 
279                          size_t        len, 
280                          int          *prio,
281                          const char   *mime_types[],
282                          int           n_mime_types)
283 {
284   xdg_uint32_t list_offset;
285   xdg_uint32_t n_entries;
286   xdg_uint32_t offset;
287
288   int j, n;
289
290   *prio = 0;
291
292   list_offset = GET_UINT32 (cache->buffer, 24);
293   n_entries = GET_UINT32 (cache->buffer, list_offset);
294   offset = GET_UINT32 (cache->buffer, list_offset + 8);
295   
296   for (j = 0; j < n_entries; j++)
297     {
298       const char *match;
299
300       match = cache_magic_compare_to_data (cache, offset + 16 * j, 
301                                            data, len, prio);
302       if (match)
303         return match;
304       else
305         {
306           xdg_uint32_t mimetype_offset;
307           const char *non_match;
308           
309           mimetype_offset = GET_UINT32 (cache->buffer, offset + 16 * j + 4);
310           non_match = cache->buffer + mimetype_offset;
311
312           for (n = 0; n < n_mime_types; n++)
313             {
314               if (mime_types[n] && 
315                   _xdg_mime_mime_type_equal (mime_types[n], non_match))
316                 mime_types[n] = NULL;
317             }
318         }
319     }
320
321   return NULL;
322 }
323
324 static const char *
325 cache_alias_lookup (const char *alias)
326 {
327   const char *ptr;
328   int i, min, max, mid, cmp;
329
330   for (i = 0; _caches[i]; i++)
331     {
332       XdgMimeCache *cache = _caches[i];
333       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 4);
334       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
335       xdg_uint32_t offset;
336
337       min = 0; 
338       max = n_entries - 1;
339       while (max >= min) 
340         {
341           mid = (min + max) / 2;
342
343           offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * mid);
344           ptr = cache->buffer + offset;
345           cmp = strcmp (ptr, alias);
346           
347           if (cmp < 0)
348             min = mid + 1;
349           else if (cmp > 0)
350             max = mid - 1;
351           else
352             {
353               offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * mid + 4);
354               return cache->buffer + offset;
355             }
356         }
357     }
358
359   return NULL;
360 }
361
362 typedef struct {
363   const char *mime;
364   int weight;
365 } MimeWeight;
366
367 static int
368 cache_glob_lookup_literal (const char *file_name,
369                            const char *mime_types[],
370                            int         n_mime_types,
371                            int         case_sensitive_check)
372 {
373   const char *ptr;
374   int i, min, max, mid, cmp;
375
376   for (i = 0; _caches[i]; i++)
377     {
378       XdgMimeCache *cache = _caches[i];
379       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 12);
380       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
381       xdg_uint32_t offset;
382
383       min = 0; 
384       max = n_entries - 1;
385       while (max >= min) 
386         {
387           mid = (min + max) / 2;
388
389           offset = GET_UINT32 (cache->buffer, list_offset + 4 + 12 * mid);
390           ptr = cache->buffer + offset;
391           cmp = strcmp (ptr, file_name);
392
393           if (cmp < 0)
394             min = mid + 1;
395           else if (cmp > 0)
396             max = mid - 1;
397           else
398             {
399               int weight = GET_UINT32 (cache->buffer, list_offset + 4 + 12 * mid + 8);
400               int case_sensitive = weight & 0x100;
401               weight = weight & 0xff;
402
403               if (case_sensitive_check || !case_sensitive)
404                 {
405                   offset = GET_UINT32 (cache->buffer, list_offset + 4 + 12 * mid + 4);
406                   mime_types[0] = (const char *)(cache->buffer + offset);
407
408                   return 1;
409                 }
410               return 0;
411             }
412         }
413     }
414
415   return 0;
416 }
417
418 static int
419 cache_glob_lookup_fnmatch (const char *file_name,
420                            MimeWeight  mime_types[],
421                            int         n_mime_types)
422 {
423   const char *mime_type;
424   const char *ptr;
425
426   int i, j, n;
427
428   n = 0;
429   for (i = 0; _caches[i]; i++)
430     {
431       XdgMimeCache *cache = _caches[i];
432
433       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 20);
434       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
435
436       for (j = 0; j < n_entries && n < n_mime_types; j++)
437         {
438           xdg_uint32_t offset = GET_UINT32 (cache->buffer, list_offset + 4 + 12 * j);
439           xdg_uint32_t mimetype_offset = GET_UINT32 (cache->buffer, list_offset + 4 + 12 * j + 4);
440           int weight = GET_UINT32 (cache->buffer, list_offset + 4 + 12 * j + 8);
441           weight = weight & 0xff;
442           ptr = cache->buffer + offset;
443           mime_type = cache->buffer + mimetype_offset;
444
445           /* FIXME: Not UTF-8 safe */
446           if (fnmatch (ptr, file_name, 0) == 0)
447             {
448               mime_types[n].mime = mime_type;
449               mime_types[n].weight = weight;
450               n++;
451             }
452         }
453
454       if (n > 0)
455         return n;
456     }
457   
458   return 0;
459 }
460
461 static int
462 cache_glob_node_lookup_suffix (XdgMimeCache  *cache,
463                                xdg_uint32_t   n_entries,
464                                xdg_uint32_t   offset,
465                                const char    *file_name,
466                                int            len,
467                                int            case_sensitive_check,
468                                MimeWeight     mime_types[],
469                                int            n_mime_types)
470 {
471   xdg_unichar_t character;
472   xdg_unichar_t match_char;
473   xdg_uint32_t mimetype_offset;
474   xdg_uint32_t n_children;
475   xdg_uint32_t child_offset; 
476   int weight;
477   int case_sensitive;
478
479   int min, max, mid, n, i;
480
481   character = file_name[len - 1];
482
483   assert (character != 0);
484
485   min = 0;
486   max = n_entries - 1;
487   while (max >= min)
488     {
489       mid = (min + max) /  2;
490       match_char = GET_UINT32 (cache->buffer, offset + 12 * mid);
491       if (match_char < character)
492         min = mid + 1;
493       else if (match_char > character)
494         max = mid - 1;
495       else 
496         {
497           len--;
498           n = 0;
499           n_children = GET_UINT32 (cache->buffer, offset + 12 * mid + 4);
500           child_offset = GET_UINT32 (cache->buffer, offset + 12 * mid + 8);
501       
502           if (len > 0)
503             {
504               n = cache_glob_node_lookup_suffix (cache, 
505                                                  n_children, child_offset,
506                                                  file_name, len, 
507                                                  case_sensitive_check,
508                                                  mime_types,
509                                                  n_mime_types);
510             }
511           if (n == 0)
512             {
513               i = 0;
514               while (n < n_mime_types && i < n_children)
515                 {
516                   match_char = GET_UINT32 (cache->buffer, child_offset + 12 * i);
517                   if (match_char != 0)
518                     break;
519
520                   mimetype_offset = GET_UINT32 (cache->buffer, child_offset + 12 * i + 4);
521                   weight = GET_UINT32 (cache->buffer, child_offset + 12 * i + 8);
522                   case_sensitive = weight & 0x100;
523                   weight = weight & 0xff;
524
525                   if (case_sensitive_check || !case_sensitive)
526                     {
527                       mime_types[n].mime = cache->buffer + mimetype_offset;
528                       mime_types[n].weight = weight;
529                       n++;
530                     }
531                   i++;
532                 }
533             }
534           return n;
535         }
536     }
537   return 0;
538 }
539
540 static int
541 cache_glob_lookup_suffix (const char *file_name,
542                           int         len,
543                           int         ignore_case,
544                           MimeWeight  mime_types[],
545                           int         n_mime_types)
546 {
547   int i, n;
548
549   for (i = 0; _caches[i]; i++)
550     {
551       XdgMimeCache *cache = _caches[i];
552
553       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 16);
554       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
555       xdg_uint32_t offset = GET_UINT32 (cache->buffer, list_offset + 4);
556
557       n = cache_glob_node_lookup_suffix (cache, 
558                                          n_entries, offset, 
559                                          file_name, len,
560                                          ignore_case,
561                                          mime_types,
562                                          n_mime_types);
563       if (n > 0)
564         return n;
565     }
566
567   return 0;
568 }
569
570 static int compare_mime_weight (const void *a, const void *b)
571 {
572   const MimeWeight *aa = (const MimeWeight *)a;
573   const MimeWeight *bb = (const MimeWeight *)b;
574
575   return bb->weight - aa->weight;
576 }
577
578 #define ISUPPER(c)              ((c) >= 'A' && (c) <= 'Z')
579 static char *
580 ascii_tolower (const char *str)
581 {
582   char *p, *lower;
583
584   lower = strdup (str);
585   p = lower;
586   while (*p != 0)
587     {
588       char c = *p;
589       *p++ = ISUPPER (c) ? c - 'A' + 'a' : c;
590     }
591   return lower;
592 }
593
594 static int
595 cache_glob_lookup_file_name (const char *file_name, 
596                              const char *mime_types[],
597                              int         n_mime_types)
598 {
599   int n;
600   MimeWeight mimes[10];
601   int n_mimes = 10;
602   int i;
603   int len;
604   char *lower_case;
605
606   assert (file_name != NULL && n_mime_types > 0);
607
608   /* First, check the literals */
609
610   lower_case = ascii_tolower (file_name);
611
612   n = cache_glob_lookup_literal (lower_case, mime_types, n_mime_types, FALSE);
613   if (n > 0)
614     {
615       free (lower_case);
616       return n;
617     }
618
619   n = cache_glob_lookup_literal (file_name, mime_types, n_mime_types, TRUE);
620   if (n > 0)
621     {
622       free (lower_case);
623       return n;
624     }
625
626   len = strlen (file_name);
627   n = cache_glob_lookup_suffix (lower_case, len, FALSE, mimes, n_mimes);
628   if (n == 0)
629     n = cache_glob_lookup_suffix (file_name, len, TRUE, mimes, n_mimes);
630
631   free (lower_case);
632
633   /* Last, try fnmatch */
634   if (n == 0)
635     n = cache_glob_lookup_fnmatch (file_name, mimes, n_mimes);
636
637   qsort (mimes, n, sizeof (MimeWeight), compare_mime_weight);
638
639   if (n_mime_types < n)
640     n = n_mime_types;
641
642   for (i = 0; i < n; i++)
643     mime_types[i] = mimes[i].mime;
644
645   return n;
646 }
647
648 int
649 _xdg_mime_cache_get_max_buffer_extents (void)
650 {
651   xdg_uint32_t offset;
652   xdg_uint32_t max_extent;
653   int i;
654
655   max_extent = 0;
656   for (i = 0; _caches[i]; i++)
657     {
658       XdgMimeCache *cache = _caches[i];
659
660       offset = GET_UINT32 (cache->buffer, 24);
661       max_extent = MAX (max_extent, GET_UINT32 (cache->buffer, offset + 4));
662     }
663
664   return max_extent;
665 }
666
667 static const char *
668 cache_get_mime_type_for_data (const void *data,
669                               size_t      len,
670                               int        *result_prio,
671                               const char *mime_types[],
672                               int         n_mime_types)
673 {
674   const char *mime_type;
675   int i, n, priority;
676
677   priority = 0;
678   mime_type = NULL;
679   for (i = 0; _caches[i]; i++)
680     {
681       XdgMimeCache *cache = _caches[i];
682
683       int prio;
684       const char *match;
685
686       match = cache_magic_lookup_data (cache, data, len, &prio, 
687                                        mime_types, n_mime_types);
688       if (prio > priority)
689         {
690           priority = prio;
691           mime_type = match;
692         }
693     }
694
695   if (result_prio)
696     *result_prio = priority;
697   
698   if (priority > 0)
699     return mime_type;
700
701   for (n = 0; n < n_mime_types; n++)
702     {
703       
704       if (mime_types[n])
705         return mime_types[n];
706     }
707
708   return XDG_MIME_TYPE_UNKNOWN;
709 }
710
711 const char *
712 _xdg_mime_cache_get_mime_type_for_data (const void *data,
713                                         size_t      len,
714                                         int        *result_prio)
715 {
716   return cache_get_mime_type_for_data (data, len, result_prio, NULL, 0);
717 }
718
719 const char *
720 _xdg_mime_cache_get_mime_type_for_file (const char  *file_name,
721                                         struct stat *statbuf)
722 {
723   const char *mime_type;
724   const char *mime_types[10];
725   FILE *file;
726   unsigned char *data;
727   int max_extent;
728   int bytes_read;
729   struct stat buf;
730   const char *base_name;
731   int n;
732   int fd;
733
734   if (file_name == NULL)
735     return NULL;
736
737   if (! _xdg_utf8_validate (file_name))
738     return NULL;
739
740   base_name = _xdg_get_base_name (file_name);
741   n = cache_glob_lookup_file_name (base_name, mime_types, 10);
742
743   if (n == 1)
744     return mime_types[0];
745
746   file = fopen (file_name, "r");
747   if (file == NULL)
748     return XDG_MIME_TYPE_UNKNOWN;
749
750   if (!statbuf)
751     {
752       fd = fileno(file);
753       if (fstat (fd, &buf) != 0)
754         {
755           fclose(file);
756           return XDG_MIME_TYPE_UNKNOWN;
757         }
758
759       statbuf = &buf;
760     }
761
762   if (!S_ISREG (statbuf->st_mode))
763     {
764       fclose(file);
765       return XDG_MIME_TYPE_UNKNOWN;
766     }
767
768   /* FIXME: Need to make sure that max_extent isn't totally broken.  This could
769    * be large and need getting from a stream instead of just reading it all
770    * in. */
771   max_extent = _xdg_mime_cache_get_max_buffer_extents ();
772   data = malloc (max_extent);
773   if (data == NULL)
774     {
775       fclose(file);
776       return XDG_MIME_TYPE_UNKNOWN;
777     }
778
779   bytes_read = fread (data, 1, max_extent, file);
780   if (ferror (file))
781     {
782       free (data);
783       fclose (file);
784       return XDG_MIME_TYPE_UNKNOWN;
785     }
786
787   mime_type = cache_get_mime_type_for_data (data, bytes_read, NULL,
788                                             mime_types, n);
789
790   free (data);
791   fclose (file);
792
793   return mime_type;
794 }
795
796 const char *
797 _xdg_mime_cache_get_mime_type_from_file_name (const char *file_name)
798 {
799   const char *mime_type;
800
801   if (cache_glob_lookup_file_name (file_name, &mime_type, 1))
802     return mime_type;
803   else
804     return XDG_MIME_TYPE_UNKNOWN;
805 }
806
807 int
808 _xdg_mime_cache_get_mime_types_from_file_name (const char *file_name,
809                                                const char  *mime_types[],
810                                                int          n_mime_types)
811 {
812   return cache_glob_lookup_file_name (file_name, mime_types, n_mime_types);
813 }
814
815 #if 1
816 static int
817 is_super_type (const char *mime)
818 {
819   int length;
820   const char *type;
821
822   length = strlen (mime);
823   type = &(mime[length - 2]);
824
825   if (strcmp (type, "/*") == 0)
826     return 1;
827
828   return 0;
829 }
830 #endif
831
832 int
833 _xdg_mime_cache_mime_type_subclass (const char *mime,
834                                     const char *base)
835 {
836   const char *umime, *ubase;
837
838   int i, j, min, max, med, cmp;
839   
840   umime = _xdg_mime_cache_unalias_mime_type (mime);
841   ubase = _xdg_mime_cache_unalias_mime_type (base);
842
843   if (strcmp (umime, ubase) == 0)
844     return 1;
845
846   /* We really want to handle text/ * in GtkFileFilter, so we just
847    * turn on the supertype matching
848    */
849 #if 1
850   /* Handle supertypes */
851   if (is_super_type (ubase) &&
852       xdg_mime_media_type_equal (umime, ubase))
853     return 1;
854 #endif
855
856   /*  Handle special cases text/plain and application/octet-stream */
857   if (strcmp (ubase, "text/plain") == 0 && 
858       strncmp (umime, "text/", 5) == 0)
859     return 1;
860
861   if (strcmp (ubase, "application/octet-stream") == 0)
862     return 1;
863  
864   for (i = 0; _caches[i]; i++)
865     {
866       XdgMimeCache *cache = _caches[i];
867       
868       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 8);
869       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
870       xdg_uint32_t offset, n_parents, parent_offset;
871
872       min = 0; 
873       max = n_entries - 1;
874       while (max >= min)
875         {
876           med = (min + max)/2;
877           
878           offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * med);
879           cmp = strcmp (cache->buffer + offset, umime);
880           if (cmp < 0)
881             min = med + 1;
882           else if (cmp > 0)
883             max = med - 1;
884           else
885             {
886               offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * med + 4);
887               n_parents = GET_UINT32 (cache->buffer, offset);
888               
889               for (j = 0; j < n_parents; j++)
890                 {
891                   parent_offset = GET_UINT32 (cache->buffer, offset + 4 + 4 * j);
892                   if (_xdg_mime_cache_mime_type_subclass (cache->buffer + parent_offset, ubase))
893                     return 1;
894                 }
895
896               break;
897             }
898         }
899     }
900
901   return 0;
902 }
903
904 const char *
905 _xdg_mime_cache_unalias_mime_type (const char *mime)
906 {
907   const char *lookup;
908   
909   lookup = cache_alias_lookup (mime);
910   
911   if (lookup)
912     return lookup;
913   
914   return mime;  
915 }
916
917 char **
918 _xdg_mime_cache_list_mime_parents (const char *mime)
919 {
920   int i, j, k, l, p;
921   char *all_parents[128]; /* we'll stop at 128 */ 
922   char **result;
923
924   mime = xdg_mime_unalias_mime_type (mime);
925
926   p = 0;
927   for (i = 0; _caches[i]; i++)
928     {
929       XdgMimeCache *cache = _caches[i];
930   
931       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, 8);
932       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
933
934       for (j = 0; j < n_entries; j++)
935         {
936           xdg_uint32_t mimetype_offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * j);
937           xdg_uint32_t parents_offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * j + 4);
938
939           if (strcmp (cache->buffer + mimetype_offset, mime) == 0)
940             {
941               xdg_uint32_t parent_mime_offset;
942               xdg_uint32_t n_parents = GET_UINT32 (cache->buffer, parents_offset);
943
944               for (k = 0; k < n_parents && p < 127; k++)
945                 {
946                   parent_mime_offset = GET_UINT32 (cache->buffer, parents_offset + 4 + 4 * k);
947
948                   /* Don't add same parent multiple times.
949                    * This can happen for instance if the same type is listed in multiple directories
950                    */
951                   for (l = 0; l < p; l++)
952                     {
953                       if (strcmp (all_parents[l], cache->buffer + parent_mime_offset) == 0)
954                         break;
955                     }
956
957                   if (l == p)
958                     all_parents[p++] = cache->buffer + parent_mime_offset;
959                 }
960
961               break;
962             }
963         }
964     }
965   all_parents[p++] = NULL;
966   
967   result = (char **) malloc (p * sizeof (char *));
968   memcpy (result, all_parents, p * sizeof (char *));
969
970   return result;
971 }
972
973 static const char *
974 cache_lookup_icon (const char *mime, int header)
975 {
976   const char *ptr;
977   int i, min, max, mid, cmp;
978
979   for (i = 0; _caches[i]; i++)
980     {
981       XdgMimeCache *cache = _caches[i];
982       xdg_uint32_t list_offset = GET_UINT32 (cache->buffer, header);
983       xdg_uint32_t n_entries = GET_UINT32 (cache->buffer, list_offset);
984       xdg_uint32_t offset;
985
986       min = 0; 
987       max = n_entries - 1;
988       while (max >= min) 
989         {
990           mid = (min + max) / 2;
991
992           offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * mid);
993           ptr = cache->buffer + offset;
994           cmp = strcmp (ptr, mime);
995          
996           if (cmp < 0)
997             min = mid + 1;
998           else if (cmp > 0)
999             max = mid - 1;
1000           else
1001             {
1002               offset = GET_UINT32 (cache->buffer, list_offset + 4 + 8 * mid + 4);
1003               return cache->buffer + offset;
1004             }
1005         }
1006     }
1007
1008   return NULL;
1009 }
1010
1011 const char *
1012 _xdg_mime_cache_get_generic_icon (const char *mime)
1013 {
1014   return cache_lookup_icon (mime, 36);
1015 }
1016
1017 const char *
1018 _xdg_mime_cache_get_icon (const char *mime)
1019 {
1020   return cache_lookup_icon (mime, 32);
1021 }
1022
1023 static void
1024 dump_glob_node (XdgMimeCache *cache,
1025                 xdg_uint32_t  offset,
1026                 int           depth)
1027 {
1028   xdg_unichar_t character;
1029   xdg_uint32_t mime_offset;
1030   xdg_uint32_t n_children;
1031   xdg_uint32_t child_offset;
1032   int i;
1033
1034   character = GET_UINT32 (cache->buffer, offset);
1035   mime_offset = GET_UINT32 (cache->buffer, offset + 4);
1036   n_children = GET_UINT32 (cache->buffer, offset + 8);
1037   child_offset = GET_UINT32 (cache->buffer, offset + 12);
1038   for (i = 0; i < depth; i++)
1039     printf (" ");
1040   printf ("%c", character);
1041   if (mime_offset)
1042     printf (" - %s", cache->buffer + mime_offset);
1043   printf ("\n");
1044   if (child_offset)
1045   {
1046     for (i = 0; i < n_children; i++)
1047       dump_glob_node (cache, child_offset + 20 * i, depth + 1);
1048   }
1049 }
1050
1051 void
1052 _xdg_mime_cache_glob_dump (void)
1053 {
1054   int i, j;
1055   for (i = 0; _caches[i]; i++)
1056   {
1057     XdgMimeCache *cache = _caches[i];
1058     xdg_uint32_t list_offset;
1059     xdg_uint32_t n_entries;
1060     xdg_uint32_t offset;
1061     list_offset = GET_UINT32 (cache->buffer, 16);
1062     n_entries = GET_UINT32 (cache->buffer, list_offset);
1063     offset = GET_UINT32 (cache->buffer, list_offset + 4);
1064     for (j = 0; j < n_entries; j++)
1065             dump_glob_node (cache, offset + 20 * j, 0);
1066   }
1067 }
1068
1069