2 * Copyright (C) 2018 "IoT.bzh"
3 * Author: José Bollo <jose.bollo@iot.bzh>
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at
9 * http://www.apache.org/licenses/LICENSE-2.0
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
28 /*************************************************************************
30 ************************************************************************/
33 * internal structure for handling patterns
37 /* link to the next handler of the list */
40 /* the hash value for the pattern */
44 struct globset_handler handler;
48 * Structure that handles a set of global pattern handlers
52 /** linked list of global patterns */
53 struct pathndl *globs;
55 /** hash dictionary of exact matches */
56 struct pathndl **exacts;
58 /** mask used for accessing dictionary of exact matches */
61 /** count of handlers stored in the dictionary of exact matches */
66 * Matches whether the string 'str' matches the pattern 'pat'
67 * and returns its matching score.
69 * @param pat the glob pattern
70 * @param str the string to match
71 * @return 0 if no match or number representing the matching score
73 static unsigned match(const char *pat, const char *str)
78 /* scan the prefix without glob */
80 while ((c = *pat++) != GLOB) {
82 return 0; /* no match */
84 return r; /* match up to end */
91 return r; /* not followed by pattern */
93 /* evaluate the best score for following pattern */
97 /* first char matches, check remaining string */
104 /* best score or not match if rs == 0 */
105 return rs ? rs + r : 0;
109 * Normalize the string 'from' to the string 'to' and computes the hash code.
110 * The normalization translates upper characters to lower characters.
111 * The returned hash code is greater than zero for exact patterns or zero
112 * for global patterns.
114 * @param from string to normalize
115 * @param to where to store the normalization
116 * @return 0 if 'from' is a glob pattern or the hash code for exacts patterns
118 static unsigned normhash(const char *from, char *to)
124 isglob = 0; /* is glob? */
125 i = hash = 0; /* index and hash code */
127 /* copy the normalized string and compute isglob and hash */
128 while ((c = from[i])) {
130 /* it is a glob pattern */
134 /* normalize to lower */
135 if (c >= 'A' && c <= 'Z')
136 c = (char)(c + 'a' - 'A');
137 /* compute hash if not glob */
139 hash += (unsigned)(unsigned char)c;
148 /* finalize hash if not glob */
160 * Ensure that there is enough place to store one more exact pattern
163 * @param set the set that has to grow if needed
164 * @return 0 in case of success or -1 on case of error
166 static int grow(struct globset *set)
168 unsigned old_gmask, new_gmask, i;
169 struct pathndl **new_exacts, **old_exacts, *ph, *next_ph;
171 /* test if grow is needed */
172 old_gmask = set->gmask;
173 if (old_gmask - (old_gmask >> 2) > set->count + 1)
176 /* compute the new mask */
177 new_gmask = (old_gmask << 1) | 15;
178 if (new_gmask + 1 <= new_gmask) {
183 /* allocates the new array */
184 new_exacts = calloc(1 + (size_t)new_gmask, sizeof *new_exacts);
189 old_exacts = set->exacts;
190 set->exacts = new_exacts;
191 set->gmask = new_gmask;
193 for(i = 0 ; i <= old_gmask ; i++) {
197 ph->next = new_exacts[ph->hash & new_gmask];
198 new_exacts[ph->hash & new_gmask] = ph;
205 /* release the previous values */
210 * Search in set the handler for the normalized pattern 'normal' of 'has' code.
212 * @param set the set to search
213 * @param normal the normalized pattern
214 * @param hash hash code of the normalized pattern
215 * @param pprev pointer where to store the pointer pointing to the returned result
216 * @return the handler found, can be NULL
218 static struct pathndl *search(
222 struct pathndl ***pprev)
224 struct pathndl *ph, **pph;
228 else if (set->exacts)
229 pph = &set->exacts[hash & set->gmask];
232 while ((ph = *pph) && strcmp(normal, ph->handler.pattern))
246 * Allocates a new set of handlers
248 * @return the new allocated global pattern set of handlers or NULL on failure
250 struct globset *globset_create()
252 return calloc(1, sizeof(struct globset));
257 * @param set the set to destroy
259 void globset_destroy(struct globset *set)
262 struct pathndl *ph, *next_ph;
264 /* free exact pattern handlers */
266 for(i = 0 ; i <= set->gmask ; i++) {
277 /* free global pattern handlers */
290 * Add a handler for the given pattern
292 * @param pattern the pattern of the handler
293 * @param callback the handler's callback
294 * @param closure the handler's closure
295 * @return 0 in case of success or -1 in case of error (ENOMEM, EEXIST)
303 struct pathndl *ph, **pph;
309 len = strlen(pattern);
310 pat = alloca(1 + len);
311 hash = normhash(pattern, pat);
313 /* grows if needed */
314 if (hash && grow(set))
318 ph = search(set, pat, hash, &pph);
325 /* not found, create it */
326 ph = malloc(len + sizeof *ph);
333 ph->handler.callback = callback;
334 ph->handler.closure = closure;
335 strcpy(ph->handler.pattern, pat);
343 * Delete the handler for the pattern
345 * @param pattern the pattern to delete
346 * @param closure where to put the closure if not NULL
347 * @return 0 in case of success or -1 in case of error (ENOENT)
354 struct pathndl *ph, **pph;
359 pat = alloca(1 + strlen(pattern));
360 hash = normhash(pattern, pat);
363 ph = search(set, pat, hash, &pph);
370 /* found, remove it */
375 /* store the closure back */
377 *closure = ph->handler.closure;
379 /* free the memory */
385 * Search the handler of 'pattern'
387 * @param pattern the pattern to search
388 * @return the handler found or NULL
390 struct globset_handler *globset_search(
394 struct pathndl *ph, **pph;
398 /* local normalization */
399 pat = alloca(1 + strlen(pattern));
400 hash = normhash(pattern, pat);
403 ph = search(set, pat, hash, &pph);
404 return ph ? &ph->handler : NULL;
408 * Search a handler for the string 'text'
410 * @param text the text to match
411 * @return the handler found or NULL
413 const struct globset_handler *globset_match(
417 struct pathndl *ph, *iph;
421 /* local normalization */
422 txt = alloca(1 + strlen(text));
423 hash = normhash(text, txt);
425 /* first, look in dictionary of exact matches */
427 if (hash && set->exacts) {
428 ph = set->exacts[hash & set->gmask];
429 while(ph && (ph->hash != hash || strcmp(txt, ph->handler.pattern)))
433 /* then if not found */
435 /* look in glob patterns for the best match */
439 g = match(iph->handler.pattern, txt);
447 return ph ? &ph->handler : NULL;