1 /* -*- mode: C; c-file-style: "gnu" -*- */
2 /* xdgmimeglob.c: Private file. Datastructure for storing the globs.
3 *
4 * More info can be found at http://www.freedesktop.org/standards/
5 *
6 * Copyright (C) 2003 Red Hat, Inc.
7 * Copyright (C) 2003 Jonathan Blandford <jrb@alum.mit.edu>
8 *
9 * Licensed under the Academic Free License version 2.0
10 * Or under the following terms:
11 *
12 * This library is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU Lesser General Public
14 * License as published by the Free Software Foundation; either
15 * version 2 of the License, or (at your option) any later version.
16 *
17 * This library is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 * Lesser General Public License for more details.
21 *
22 * You should have received a copy of the GNU Lesser General Public
23 * License along with this library; if not, write to the
24 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
25 * Boston, MA 02111-1307, USA.
26 */
27
28 #ifdef HAVE_CONFIG_H
29 #include "config.h"
30 #endif
31
32 #include "xdgmimeglob.h"
33 #include "xdgmimeint.h"
34 #include <stdlib.h>
35 #include <stdio.h>
36 #include <assert.h>
37 #include <string.h>
38 #include <fnmatch.h>
39 #include <ctype.h>
40
41 #ifndef FALSE
42 #define FALSE (0)
43 #endif
44
45 #ifndef TRUE
46 #define TRUE (!FALSE)
47 #endif
48
49 typedef struct XdgGlobHashNode XdgGlobHashNode;
50 typedef struct XdgGlobList XdgGlobList;
51
52 struct XdgGlobHashNode
53 {
54 xdg_unichar_t character;
55 const char *mime_type;
56 int weight;
57 XdgGlobHashNode *next;
58 XdgGlobHashNode *child;
59 };
60 struct XdgGlobList
61 {
62 const char *data;
63 const char *mime_type;
64 int weight;
65 XdgGlobList *next;
66 };
67
68 struct XdgGlobHash
69 {
70 XdgGlobList *literal_list;
71 XdgGlobHashNode *simple_node;
72 XdgGlobList *full_list;
73 };
74
75
76 /* XdgGlobList
77 */
78 static XdgGlobList *
_xdg_glob_list_new(void)79 _xdg_glob_list_new (void)
80 {
81 XdgGlobList *new_element;
82
83 new_element = calloc (1, sizeof (XdgGlobList));
84
85 return new_element;
86 }
87
88 /* Frees glob_list and all of it's children */
89 static void
_xdg_glob_list_free(XdgGlobList * glob_list)90 _xdg_glob_list_free (XdgGlobList *glob_list)
91 {
92 XdgGlobList *ptr, *next;
93
94 ptr = glob_list;
95
96 while (ptr != NULL)
97 {
98 next = ptr->next;
99
100 if (ptr->data)
101 free ((void *) ptr->data);
102 if (ptr->mime_type)
103 free ((void *) ptr->mime_type);
104 free (ptr);
105
106 ptr = next;
107 }
108 }
109
110 static XdgGlobList *
_xdg_glob_list_append(XdgGlobList * glob_list,void * data,const char * mime_type,int weight)111 _xdg_glob_list_append (XdgGlobList *glob_list,
112 void *data,
113 const char *mime_type,
114 int weight)
115 {
116 XdgGlobList *new_element;
117 XdgGlobList *tmp_element;
118
119 new_element = _xdg_glob_list_new ();
120 new_element->data = data;
121 new_element->mime_type = mime_type;
122 new_element->weight = weight;
123 if (glob_list == NULL)
124 return new_element;
125
126 tmp_element = glob_list;
127 while (tmp_element->next != NULL)
128 tmp_element = tmp_element->next;
129
130 tmp_element->next = new_element;
131
132 return glob_list;
133 }
134
135 /* XdgGlobHashNode
136 */
137
138 static XdgGlobHashNode *
_xdg_glob_hash_node_new(void)139 _xdg_glob_hash_node_new (void)
140 {
141 XdgGlobHashNode *glob_hash_node;
142
143 glob_hash_node = calloc (1, sizeof (XdgGlobHashNode));
144
145 return glob_hash_node;
146 }
147
148 static void
_xdg_glob_hash_node_dump(XdgGlobHashNode * glob_hash_node,int depth)149 _xdg_glob_hash_node_dump (XdgGlobHashNode *glob_hash_node,
150 int depth)
151 {
152 int i;
153 for (i = 0; i < depth; i++)
154 printf (" ");
155
156 printf ("%c", (char)glob_hash_node->character);
157 if (glob_hash_node->mime_type)
158 printf (" - %s %d\n", glob_hash_node->mime_type, glob_hash_node->weight);
159 else
160 printf ("\n");
161 if (glob_hash_node->child)
162 _xdg_glob_hash_node_dump (glob_hash_node->child, depth + 1);
163 if (glob_hash_node->next)
164 _xdg_glob_hash_node_dump (glob_hash_node->next, depth);
165 }
166
167 static XdgGlobHashNode *
_xdg_glob_hash_insert_ucs4(XdgGlobHashNode * glob_hash_node,xdg_unichar_t * text,const char * mime_type,int weight)168 _xdg_glob_hash_insert_ucs4 (XdgGlobHashNode *glob_hash_node,
169 xdg_unichar_t *text,
170 const char *mime_type,
171 int weight)
172 {
173 XdgGlobHashNode *node;
174 xdg_unichar_t character;
175
176 character = text[0];
177
178 if ((glob_hash_node == NULL) ||
179 (character < glob_hash_node->character))
180 {
181 node = _xdg_glob_hash_node_new ();
182 node->character = character;
183 node->next = glob_hash_node;
184 glob_hash_node = node;
185 }
186 else if (character == glob_hash_node->character)
187 {
188 node = glob_hash_node;
189 }
190 else
191 {
192 XdgGlobHashNode *prev_node;
193 int found_node = FALSE;
194
195 /* Look for the first character of text in glob_hash_node, and insert it if we
196 * have to.*/
197 prev_node = glob_hash_node;
198 node = prev_node->next;
199
200 while (node != NULL)
201 {
202 if (character < node->character)
203 {
204 node = _xdg_glob_hash_node_new ();
205 node->character = character;
206 node->next = prev_node->next;
207 prev_node->next = node;
208
209 found_node = TRUE;
210 break;
211 }
212 else if (character == node->character)
213 {
214 found_node = TRUE;
215 break;
216 }
217 prev_node = node;
218 node = node->next;
219 }
220
221 if (! found_node)
222 {
223 node = _xdg_glob_hash_node_new ();
224 node->character = character;
225 node->next = prev_node->next;
226 prev_node->next = node;
227 }
228 }
229
230 text++;
231 if (*text == 0)
232 {
233 if (node->mime_type)
234 {
235 if (strcmp (node->mime_type, mime_type))
236 {
237 XdgGlobHashNode *child;
238 int found_node = FALSE;
239
240 child = node->child;
241 while (child && child->character == 0)
242 {
243 if (strcmp (child->mime_type, mime_type) == 0)
244 {
245 found_node = TRUE;
246 break;
247 }
248 child = child->next;
249 }
250
251 if (!found_node)
252 {
253 child = _xdg_glob_hash_node_new ();
254 child->character = 0;
255 child->mime_type = strdup (mime_type);
256 child->weight = weight;
257 child->child = NULL;
258 child->next = node->child;
259 node->child = child;
260 }
261 }
262 }
263 else
264 {
265 node->mime_type = strdup (mime_type);
266 node->weight = weight;
267 }
268 }
269 else
270 {
271 node->child = _xdg_glob_hash_insert_ucs4 (node->child, text, mime_type, weight);
272 }
273 return glob_hash_node;
274 }
275
276 /* glob must be valid UTF-8 */
277 static XdgGlobHashNode *
_xdg_glob_hash_insert_text(XdgGlobHashNode * glob_hash_node,const char * text,const char * mime_type,int weight)278 _xdg_glob_hash_insert_text (XdgGlobHashNode *glob_hash_node,
279 const char *text,
280 const char *mime_type,
281 int weight)
282 {
283 XdgGlobHashNode *node;
284 xdg_unichar_t *unitext;
285 int len;
286
287 unitext = _xdg_convert_to_ucs4 (text, &len);
288 _xdg_reverse_ucs4 (unitext, len);
289 node = _xdg_glob_hash_insert_ucs4 (glob_hash_node, unitext, mime_type, weight);
290 free (unitext);
291 return node;
292 }
293
294 typedef struct {
295 const char *mime;
296 int weight;
297 } MimeWeight;
298
299 static int
_xdg_glob_hash_node_lookup_file_name(XdgGlobHashNode * glob_hash_node,const char * file_name,int len,int ignore_case,MimeWeight mime_types[],int n_mime_types)300 _xdg_glob_hash_node_lookup_file_name (XdgGlobHashNode *glob_hash_node,
301 const char *file_name,
302 int len,
303 int ignore_case,
304 MimeWeight mime_types[],
305 int n_mime_types)
306 {
307 int n;
308 XdgGlobHashNode *node;
309 xdg_unichar_t character;
310
311 if (glob_hash_node == NULL)
312 return 0;
313
314 character = file_name[len - 1];
315 if (ignore_case)
316 character = tolower(character);
317
318 for (node = glob_hash_node; node && character >= node->character; node = node->next)
319 {
320 if (character == node->character)
321 {
322 len--;
323 n = 0;
324 if (len > 0)
325 {
326 n = _xdg_glob_hash_node_lookup_file_name (node->child,
327 file_name,
328 len,
329 ignore_case,
330 mime_types,
331 n_mime_types);
332 }
333 if (n == 0)
334 {
335 if (node->mime_type)
336 {
337 mime_types[n].mime = node->mime_type;
338 mime_types[n].weight = node->weight;
339 n++;
340 }
341 node = node->child;
342 while (n < n_mime_types && node && node->character == 0)
343 {
344 if (node->mime_type)
345 {
346 mime_types[n].mime = node->mime_type;
347 mime_types[n].weight = node->weight;
348 n++;
349 }
350 node = node->next;
351 }
352 }
353 return n;
354 }
355 }
356
357 return 0;
358 }
359
compare_mime_weight(const void * a,const void * b)360 static int compare_mime_weight (const void *a, const void *b)
361 {
362 const MimeWeight *aa = (const MimeWeight *)a;
363 const MimeWeight *bb = (const MimeWeight *)b;
364
365 return aa->weight - bb->weight;
366 }
367
368 int
_xdg_glob_hash_lookup_file_name(XdgGlobHash * glob_hash,const char * file_name,const char * mime_types[],int n_mime_types)369 _xdg_glob_hash_lookup_file_name (XdgGlobHash *glob_hash,
370 const char *file_name,
371 const char *mime_types[],
372 int n_mime_types)
373 {
374 XdgGlobList *list;
375 int i, n;
376 MimeWeight mimes[10];
377 int n_mimes = 10;
378 xdg_unichar_t *ucs4;
379 int len;
380
381 /* First, check the literals */
382
383 assert (file_name != NULL && n_mime_types > 0);
384
385 n = 0;
386
387 for (list = glob_hash->literal_list; list; list = list->next)
388 {
389 if (strcmp ((const char *)list->data, file_name) == 0)
390 {
391 mime_types[0] = list->mime_type;
392 return 1;
393 }
394 }
395
396 len = strlen (file_name);
397 n = _xdg_glob_hash_node_lookup_file_name (glob_hash->simple_node, file_name, len, FALSE,
398 mimes, n_mimes);
399 if (n == 0)
400 n = _xdg_glob_hash_node_lookup_file_name (glob_hash->simple_node, file_name, len, TRUE,
401 mimes, n_mimes);
402
403 if (n == 0)
404 {
405 for (list = glob_hash->full_list; list && n < n_mime_types; list = list->next)
406 {
407 if (fnmatch ((const char *)list->data, file_name, 0) == 0)
408 {
409 mimes[n].mime = list->mime_type;
410 mimes[n].weight = list->weight;
411 n++;
412 }
413 }
414 }
415
416 qsort (mimes, n, sizeof (MimeWeight), compare_mime_weight);
417
418 if (n_mime_types < n)
419 n = n_mime_types;
420
421 for (i = 0; i < n; i++)
422 mime_types[i] = mimes[i].mime;
423
424 return n;
425 }
426
427
428
429 /* XdgGlobHash
430 */
431
432 XdgGlobHash *
_xdg_glob_hash_new(void)433 _xdg_glob_hash_new (void)
434 {
435 XdgGlobHash *glob_hash;
436
437 glob_hash = calloc (1, sizeof (XdgGlobHash));
438
439 return glob_hash;
440 }
441
442
443 static void
_xdg_glob_hash_free_nodes(XdgGlobHashNode * node)444 _xdg_glob_hash_free_nodes (XdgGlobHashNode *node)
445 {
446 if (node)
447 {
448 if (node->child)
449 _xdg_glob_hash_free_nodes (node->child);
450 if (node->next)
451 _xdg_glob_hash_free_nodes (node->next);
452 if (node->mime_type)
453 free ((void *) node->mime_type);
454 free (node);
455 }
456 }
457
458 void
_xdg_glob_hash_free(XdgGlobHash * glob_hash)459 _xdg_glob_hash_free (XdgGlobHash *glob_hash)
460 {
461 _xdg_glob_list_free (glob_hash->literal_list);
462 _xdg_glob_list_free (glob_hash->full_list);
463 _xdg_glob_hash_free_nodes (glob_hash->simple_node);
464 free (glob_hash);
465 }
466
467 XdgGlobType
_xdg_glob_determine_type(const char * glob)468 _xdg_glob_determine_type (const char *glob)
469 {
470 const char *ptr;
471 int maybe_in_simple_glob = FALSE;
472 int first_char = TRUE;
473
474 ptr = glob;
475
476 while (*ptr != '\0')
477 {
478 if (*ptr == '*' && first_char)
479 maybe_in_simple_glob = TRUE;
480 else if (*ptr == '\\' || *ptr == '[' || *ptr == '?' || *ptr == '*')
481 return XDG_GLOB_FULL;
482
483 first_char = FALSE;
484 ptr = _xdg_utf8_next_char (ptr);
485 }
486 if (maybe_in_simple_glob)
487 return XDG_GLOB_SIMPLE;
488 else
489 return XDG_GLOB_LITERAL;
490 }
491
492 /* glob must be valid UTF-8 */
493 void
_xdg_glob_hash_append_glob(XdgGlobHash * glob_hash,const char * glob,const char * mime_type,int weight)494 _xdg_glob_hash_append_glob (XdgGlobHash *glob_hash,
495 const char *glob,
496 const char *mime_type,
497 int weight)
498 {
499 XdgGlobType type;
500
501 assert (glob_hash != NULL);
502 assert (glob != NULL);
503
504 type = _xdg_glob_determine_type (glob);
505
506 switch (type)
507 {
508 case XDG_GLOB_LITERAL:
509 glob_hash->literal_list = _xdg_glob_list_append (glob_hash->literal_list, strdup (glob), strdup (mime_type), weight);
510 break;
511 case XDG_GLOB_SIMPLE:
512 glob_hash->simple_node = _xdg_glob_hash_insert_text (glob_hash->simple_node, glob + 1, mime_type, weight);
513 break;
514 case XDG_GLOB_FULL:
515 glob_hash->full_list = _xdg_glob_list_append (glob_hash->full_list, strdup (glob), strdup (mime_type), weight);
516 break;
517 }
518 }
519
520 void
_xdg_glob_hash_dump(XdgGlobHash * glob_hash)521 _xdg_glob_hash_dump (XdgGlobHash *glob_hash)
522 {
523 XdgGlobList *list;
524 printf ("LITERAL STRINGS\n");
525 if (!glob_hash || glob_hash->literal_list == NULL)
526 {
527 printf (" None\n");
528 }
529 else
530 {
531 for (list = glob_hash->literal_list; list; list = list->next)
532 printf (" %s - %s %d\n", (char *)list->data, list->mime_type, list->weight);
533 }
534 printf ("\nSIMPLE GLOBS\n");
535 if (!glob_hash || glob_hash->simple_node == NULL)
536 {
537 printf (" None\n");
538 }
539 else
540 {
541 _xdg_glob_hash_node_dump (glob_hash->simple_node, 4);
542 }
543
544 printf ("\nFULL GLOBS\n");
545 if (!glob_hash || glob_hash->full_list == NULL)
546 {
547 printf (" None\n");
548 }
549 else
550 {
551 for (list = glob_hash->full_list; list; list = list->next)
552 printf (" %s - %s %d\n", (char *)list->data, list->mime_type, list->weight);
553 }
554 }
555
556
557 void
_xdg_mime_glob_read_from_file(XdgGlobHash * glob_hash,const char * file_name)558 _xdg_mime_glob_read_from_file (XdgGlobHash *glob_hash,
559 const char *file_name)
560 {
561 FILE *glob_file;
562 char line[255];
563
564 glob_file = fopen (file_name, "r");
565
566 if (glob_file == NULL)
567 return;
568
569 /* FIXME: Not UTF-8 safe. Doesn't work if lines are greater than 255 chars.
570 * Blah */
571 while (fgets (line, 255, glob_file) != NULL)
572 {
573 char *colon, *colon2;
574 char *mimetype, *glob;
575 int weight;
576
577 if (line[0] == '#')
578 continue;
579
580 colon = strchr (line, ':');
581 if (colon == NULL)
582 continue;
583 *(colon++) = '\0';
584 colon[strlen (colon) -1] = '\0';
585 colon2 = strchr (colon, ':');
586 if (colon2)
587 {
588 *(colon2++) = '\000';
589 weight = atoi (line);
590 mimetype = colon;
591 glob = colon2;
592 }
593 else
594 {
595 weight = 50;
596 mimetype = line;
597 glob = colon;
598 }
599 _xdg_glob_hash_append_glob (glob_hash, glob, mimetype, weight);
600 }
601
602 fclose (glob_file);
603 }
604