Implement the same PLT reduction technique used in GTK+:
[platform/upstream/glib.git] / glib / gcompletion.c
1 /* GLIB - Library of useful routines for C programming
2  * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 /*
21  * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
22  * file for a list of people on the GLib Team.  See the ChangeLog
23  * files for a list of changes.  These files are distributed with
24  * GLib at ftp://ftp.gtk.org/pub/gtk/. 
25  */
26
27 /* 
28  * MT safe
29  */
30
31 #include "config.h"
32
33 #include <string.h>
34
35 #include "galias.h"
36 #include "glib.h"
37
38
39 static void completion_check_cache (GCompletion* cmp,
40                                     gchar**      new_prefix);
41
42 GCompletion* 
43 g_completion_new (GCompletionFunc func)
44 {
45   GCompletion* gcomp;
46   
47   gcomp = g_new (GCompletion, 1);
48   gcomp->items = NULL;
49   gcomp->cache = NULL;
50   gcomp->prefix = NULL;
51   gcomp->func = func;
52   gcomp->strncmp_func = strncmp;
53
54   return gcomp;
55 }
56
57 void 
58 g_completion_add_items (GCompletion* cmp,
59                         GList*       items)
60 {
61   GList* it;
62   
63   g_return_if_fail (cmp != NULL);
64   
65   /* optimize adding to cache? */
66   if (cmp->cache)
67     {
68       g_list_free (cmp->cache);
69       cmp->cache = NULL;
70     }
71
72   if (cmp->prefix)
73     {
74       g_free (cmp->prefix);
75       cmp->prefix = NULL;
76     }
77   
78   it = items;
79   while (it)
80     {
81       cmp->items = g_list_prepend (cmp->items, it->data);
82       it = it->next;
83     }
84 }
85
86 void 
87 g_completion_remove_items (GCompletion* cmp,
88                            GList*       items)
89 {
90   GList* it;
91   
92   g_return_if_fail (cmp != NULL);
93   
94   it = items;
95   while (cmp->items && it)
96     {
97       cmp->items = g_list_remove (cmp->items, it->data);
98       it = it->next;
99     }
100
101   it = items;
102   while (cmp->cache && it)
103     {
104       cmp->cache = g_list_remove(cmp->cache, it->data);
105       it = it->next;
106     }
107 }
108
109 void 
110 g_completion_clear_items (GCompletion* cmp)
111 {
112   g_return_if_fail (cmp != NULL);
113   
114   g_list_free (cmp->items);
115   cmp->items = NULL;
116   g_list_free (cmp->cache);
117   cmp->cache = NULL;
118   g_free (cmp->prefix);
119   cmp->prefix = NULL;
120 }
121
122 static void   
123 completion_check_cache (GCompletion* cmp,
124                         gchar**      new_prefix)
125 {
126   register GList* list;
127   register gsize len;  
128   register gsize i;
129   register gsize plen;
130   gchar* postfix;
131   gchar* s;
132   
133   if (!new_prefix)
134     return;
135   if (!cmp->cache)
136     {
137       *new_prefix = NULL;
138       return;
139     }
140   
141   len = strlen(cmp->prefix);
142   list = cmp->cache;
143   s = cmp->func ? cmp->func (list->data) : (gchar*) list->data;
144   postfix = s + len;
145   plen = strlen (postfix);
146   list = list->next;
147   
148   while (list && plen)
149     {
150       s = cmp->func ? cmp->func (list->data) : (gchar*) list->data;
151       s += len;
152       for (i = 0; i < plen; ++i)
153         {
154           if (postfix[i] != s[i])
155             break;
156         }
157       plen = i;
158       list = list->next;
159     }
160   
161   *new_prefix = g_new0 (gchar, len + plen + 1);
162   strncpy (*new_prefix, cmp->prefix, len);
163   strncpy (*new_prefix + len, postfix, plen);
164 }
165
166 /**
167  * g_completion_complete_utf8:
168  * @cmp: the #GCompletion
169  * @prefix: the prefix string, typically used by the user, which is compared
170  *    with each of the items
171  * @new_prefix: if non-%NULL, returns the longest prefix which is common to all
172  *    items that matched @prefix, or %NULL if no items matched @prefix.
173  *    This string should be freed when no longer needed.
174  *
175  * Attempts to complete the string @prefix using the #GCompletion target items.
176  * In contrast to g_completion_complete(), this function returns the largest common
177  * prefix that is a valid UTF-8 string, omitting a possible common partial 
178  * character.
179  *
180  * You should use this function instead of g_completion_complete() if your 
181  * items are UTF-8 strings.
182  *
183  * Return value: the list of items whose strings begin with @prefix. This should
184  * not be changed.
185  *
186  * Since: 2.4
187  **/
188 GList*
189 g_completion_complete_utf8 (GCompletion  *cmp,
190                             const gchar  *prefix,
191                             gchar       **new_prefix)
192 {
193   GList *list;
194   gchar *p, *q;
195
196   list = g_completion_complete (cmp, prefix, new_prefix);
197
198   if (*new_prefix)
199     {
200       p = *new_prefix + strlen (*new_prefix);
201       q = g_utf8_find_prev_char (*new_prefix, p);
202       
203       switch (g_utf8_get_char_validated (q, p - q))
204         {
205         case (gunichar)-2:
206         case (gunichar)-1:
207           *q = 0;
208           break;
209         default: ;
210         }
211
212     }
213
214   return list;
215 }
216
217 GList* 
218 g_completion_complete (GCompletion* cmp,
219                        const gchar* prefix,
220                        gchar**      new_prefix)
221 {
222   gsize plen, len;
223   gboolean done = FALSE;
224   GList* list;
225   
226   g_return_val_if_fail (cmp != NULL, NULL);
227   g_return_val_if_fail (prefix != NULL, NULL);
228   
229   len = strlen (prefix);
230   if (cmp->prefix && cmp->cache)
231     {
232       plen = strlen (cmp->prefix);
233       if (plen <= len && ! cmp->strncmp_func (prefix, cmp->prefix, plen))
234         { 
235           /* use the cache */
236           list = cmp->cache;
237           while (list)
238             {
239               GList *next = list->next;
240               
241               if (cmp->strncmp_func (prefix,
242                                      cmp->func ? cmp->func (list->data) : (gchar*) list->data,
243                                      len))
244                 cmp->cache = g_list_delete_link (cmp->cache, list);
245
246               list = next;
247             }
248           done = TRUE;
249         }
250     }
251   
252   if (!done)
253     {
254       /* normal code */
255       g_list_free (cmp->cache);
256       cmp->cache = NULL;
257       list = cmp->items;
258       while (*prefix && list)
259         {
260           if (!cmp->strncmp_func (prefix,
261                         cmp->func ? cmp->func (list->data) : (gchar*) list->data,
262                         len))
263             cmp->cache = g_list_prepend (cmp->cache, list->data);
264           list = list->next;
265         }
266     }
267   if (cmp->prefix)
268     {
269       g_free (cmp->prefix);
270       cmp->prefix = NULL;
271     }
272   if (cmp->cache)
273     cmp->prefix = g_strdup (prefix);
274   completion_check_cache (cmp, new_prefix);
275   
276   return *prefix ? cmp->cache : cmp->items;
277 }
278
279 void 
280 g_completion_free (GCompletion* cmp)
281 {
282   g_return_if_fail (cmp != NULL);
283   
284   g_completion_clear_items (cmp);
285   g_free (cmp);
286 }
287
288 void
289 g_completion_set_compare(GCompletion *cmp,
290                          GCompletionStrncmpFunc strncmp_func)
291 {
292   cmp->strncmp_func = strncmp_func;
293 }
294
295 #ifdef TEST_COMPLETION
296 #include <stdio.h>
297 int
298 main (int   argc,
299       char* argv[])
300 {
301   FILE *file;
302   gchar buf[1024];
303   GList *list;
304   GList *result;
305   GList *tmp;
306   GCompletion *cmp;
307   gint i;
308   gchar *longp = NULL;
309   
310   if (argc < 3)
311     {
312       g_warning ("Usage: %s filename prefix1 [prefix2 ...]\n", argv[0]);
313       return 1;
314     }
315   
316   file = fopen (argv[1], "r");
317   if (!file)
318     {
319       g_warning ("Cannot open %s\n", argv[1]);
320       return 1;
321     }
322   
323   cmp = g_completion_new (NULL);
324   list = g_list_alloc ();
325   while (fgets (buf, 1024, file))
326     {
327       list->data = g_strdup (buf);
328       g_completion_add_items (cmp, list);
329     }
330   fclose (file);
331   
332   for (i = 2; i < argc; ++i)
333     {
334       printf ("COMPLETING: %s\n", argv[i]);
335       result = g_completion_complete (cmp, argv[i], &longp);
336       g_list_foreach (result, (GFunc) printf, NULL);
337       printf ("LONG MATCH: %s\n", longp);
338       g_free (longp);
339       longp = NULL;
340     }
341   
342   g_list_foreach (cmp->items, (GFunc) g_free, NULL);
343   g_completion_free (cmp);
344   g_list_free (list);
345   
346   return 0;
347 }
348 #endif