src/globset.c

   1 /*
   2  * Copyright (C) 2015-2020 "IoT.bzh"
   3  * Author: José Bollo <jose.bollo@iot.bzh>
   4  *
   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
   8  *
   9  *   http://www.apache.org/licenses/LICENSE-2.0
  10  *
  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.
  16  */
  17
  18 #define _GNU_SOURCE
  19
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include <errno.h>
  23
  24 #include "globset.h"
  25
  26 #define GLOB '*'
  27
  28 /*************************************************************************
  29  * internal types
  30  ************************************************************************/
  31
  32 /**
  33  * internal structure for handling patterns
  34  */
  35 struct pathndl
  36 {
  37         /* link to the next handler of the list */
  38         struct pathndl *next;
  39
  40         /* the hash value for the pattern */
  41         size_t hash;
  42
  43         /* the handler */
  44         struct globset_handler handler;
  45 };
  46
  47 /**
  48  * Structure that handles a set of global pattern handlers
  49  */
  50 struct globset
  51 {
  52         /** linked list of global patterns */
  53         struct pathndl *globs;
  54
  55         /** hash dictionary of exact matches */
  56         struct pathndl **exacts;
  57
  58         /** mask used for accessing dictionary of exact matches */
  59         unsigned gmask;
  60
  61         /** count of handlers stored in the dictionary of exact matches */
  62         unsigned count;
  63 };
  64
  65 /**
  66  * Matches whether the string 'str' matches the pattern 'pat'
  67  * and returns its matching score.
  68  *
  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
  72  */
  73 static unsigned match(const char *pat, const char *str)
  74 {
  75         unsigned r, rs, rr;
  76         char c;
  77
  78         /* scan the prefix without glob */
  79         r = 1;
  80         while ((c = *pat++) != GLOB) {
  81                 if (c != *str++)
  82                         return 0; /* no match */
  83                 if (!c)
  84                         return r; /* match up to end */
  85                 r++;
  86         }
  87
  88         /* glob found */
  89         c = *pat++;
  90         if (!c)
  91                 return r; /* not followed by pattern */
  92
  93         /* evaluate the best score for following pattern */
  94         rs = 0;
  95         while (*str) {
  96                 if (*str++ == c) {
  97                         /* first char matches, check remaining string */
  98                         rr = match(pat, str);
  99                         if (rr > rs)
 100                                 rs = rr;
 101                 }
 102         }
 103
 104         /* best score or not match if rs == 0 */
 105         return rs ? rs + r : 0;
 106 }
 107
 108 /**
 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.
 113  *
 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
 117  */
 118 static unsigned normhash(const char *from, char *to)
 119 {
 120         unsigned i, hash;
 121         int isglob;
 122         char c;
 123
 124         isglob = 0; /* is glob? */
 125         i = hash = 0; /* index and hash code */
 126
 127         /* copy the normalized string and compute isglob and hash */
 128         while ((c = from[i])) {
 129                 if (c == GLOB) {
 130                         /* it is a glob pattern */
 131                         isglob = 1;
 132                         hash = 0;
 133                 } else {
 134                         /* normalize to lower */
 135                         if (c >= 'A' && c <= 'Z')
 136                                 c = (char)(c + 'a' - 'A');
 137                         /* compute hash if not glob */
 138                         if (!isglob) {
 139                                 hash += (unsigned)(unsigned char)c;
 140                                 hash += hash << 10;
 141                                 hash ^= hash >> 6;
 142                         }
 143                 }
 144                 to[i++] = c;
 145         }
 146         to[i] = c;
 147         if (!isglob) {
 148                 /* finalize hash if not glob */
 149                 hash += i;
 150                 hash += hash << 3;
 151                 hash ^= hash >> 11;
 152                 hash += hash << 15;
 153                 if (hash == 0)
 154                         hash = 1 + i;
 155         }
 156         return hash;
 157 }
 158
 159 /**
 160  * Ensure that there is enough place to store one more exact pattern
 161  * in the dictionary.
 162  *
 163  * @param set the set that has to grow if needed
 164  * @return 0 in case of success or -1 on case of error
 165  */
 166 static int grow(struct globset *set)
 167 {
 168         unsigned old_gmask, new_gmask, i;
 169         struct pathndl **new_exacts, **old_exacts, *ph, *next_ph;
 170
 171         /* test if grow is needed */
 172         old_gmask = set->gmask;
 173         if (old_gmask - (old_gmask >> 2) > set->count + 1)
 174                 return 0;
 175
 176         /* compute the new mask */
 177         new_gmask = (old_gmask << 1) | 15;
 178         if (new_gmask + 1 <= new_gmask) {
 179                 errno = EOVERFLOW;
 180                 return -1;
 181         }
 182
 183         /* allocates the new array */
 184         new_exacts = calloc(1 + (size_t)new_gmask, sizeof *new_exacts);
 185         if (!new_exacts)
 186                 return -1;
 187
 188         /* copy values */
 189         old_exacts = set->exacts;
 190         set->exacts = new_exacts;
 191         set->gmask = new_gmask;
 192         if (old_gmask) {
 193                 for(i = 0 ; i <= old_gmask ; i++) {
 194                         ph = old_exacts[i];
 195                         while (ph) {
 196                                 next_ph = ph->next;
 197                                 ph->next = new_exacts[ph->hash & new_gmask];
 198                                 new_exacts[ph->hash & new_gmask] = ph;
 199                                 ph = next_ph;
 200                         }
 201                 }
 202                 free(old_exacts);
 203         }
 204
 205         /* release the previous values */
 206         return 0;
 207 }
 208
 209 /**
 210  * Search in set the handler for the normalized pattern 'normal' of 'has' code.
 211  *
 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
 217  */
 218 static struct pathndl *search(
 219                 struct globset *set,
 220                 const char *normal,
 221                 unsigned hash,
 222                 struct pathndl ***pprev)
 223 {
 224         struct pathndl *ph, **pph;
 225
 226         if (!hash)
 227                 pph = &set->globs;
 228         else if (set->exacts)
 229                 pph = &set->exacts[hash & set->gmask];
 230         else {
 231                 *pprev = NULL;
 232                 return NULL;
 233         }
 234         while ((ph = *pph) && strcmp(normal, ph->handler.pattern))
 235                 pph = &ph->next;
 236         *pprev = pph;
 237         return ph;
 238 }
 239
 240 /**
 241  * Allocates a new set of handlers
 242  *
 243  * @return the new allocated global pattern set of handlers or NULL on failure
 244  */
 245 struct globset *globset_create()
 246 {
 247         return calloc(1, sizeof(struct globset));
 248 }
 249
 250 /**
 251  * Destroy the set
 252  * @param set the set to destroy
 253  */
 254 void globset_destroy(struct globset *set)
 255 {
 256         unsigned i;
 257         struct pathndl *ph, *next_ph;
 258
 259         /* free exact pattern handlers */
 260         if (set->gmask) {
 261                 for(i = 0 ; i <= set->gmask ; i++) {
 262                         ph = set->exacts[i];
 263                         while (ph) {
 264                                 next_ph = ph->next;
 265                                 free(ph);
 266                                 ph = next_ph;
 267                         }
 268                 }
 269                 free(set->exacts);
 270         }
 271
 272         /* free global pattern handlers */
 273         ph = set->globs;
 274         while (ph) {
 275                 next_ph = ph->next;
 276                 free(ph);
 277                 ph = next_ph;
 278         }
 279
 280         /* free the set */
 281         free(set);
 282 }
 283
 284 /**
 285  * Add a handler for the given pattern
 286  * @param set the set
 287  * @param pattern the pattern of the handler
 288  * @param callback the handler's callback
 289  * @param closure the handler's closure
 290  * @return 0 in case of success or -1 in case of error (ENOMEM, EEXIST)
 291  */
 292 int globset_add(
 293                 struct globset *set,
 294                 const char *pattern,
 295                 void *callback,
 296                 void *closure)
 297 {
 298         struct pathndl *ph, **pph;
 299         unsigned hash;
 300         size_t len;
 301         char *pat;
 302
 303         /* normalize */
 304         len = strlen(pattern);
 305         pat = alloca(1 + len);
 306         hash = normhash(pattern, pat);
 307
 308         /* grows if needed */
 309         if (hash && grow(set))
 310                 return -1;
 311
 312         /* search */
 313         ph = search(set, pat, hash, &pph);
 314         if (ph) {
 315                 /* found */
 316                 errno = EEXIST;
 317                 return -1;
 318         }
 319
 320         /* not found, create it */
 321         ph = malloc(1 + len + sizeof *ph);
 322         if (!ph)
 323                 return -1;
 324
 325         /* initialize it */
 326         ph->next = NULL;
 327         ph->hash = hash;
 328         ph->handler.callback = callback;
 329         ph->handler.closure = closure;
 330         strcpy(ph->handler.pattern, pat);
 331         *pph = ph;
 332         if (hash)
 333                 set->count++;
 334         return 0;
 335 }
 336
 337 /**
 338  * Delete the handler for the pattern
 339  * @param set the set
 340  * @param pattern the pattern to delete
 341  * @param closure where to put the closure if not NULL
 342  * @return 0 in case of success or -1 in case of error (ENOENT)
 343  */
 344 int globset_del(
 345                         struct globset *set,
 346                         const char *pattern,
 347                         void **closure)
 348 {
 349         struct pathndl *ph, **pph;
 350         unsigned hash;
 351         char *pat;
 352
 353         /* normalize */
 354         pat = alloca(1 + strlen(pattern));
 355         hash = normhash(pattern, pat);
 356
 357         /* search */
 358         ph = search(set, pat, hash, &pph);
 359         if (!ph) {
 360                 /* not found */
 361                 errno = ENOENT;
 362                 return -1;
 363         }
 364
 365         /* found, remove it */
 366         if (hash)
 367                 set->count--;
 368         *pph = ph->next;
 369
 370         /* store the closure back */
 371         if (closure)
 372                 *closure = ph->handler.closure;
 373
 374         /* free the memory */
 375         free(ph);
 376         return 0;
 377 }
 378
 379 /**
 380  * Search the handler of 'pattern'
 381  * @param set the set
 382  * @param pattern the pattern to search
 383  * @return the handler found or NULL
 384  */
 385 struct globset_handler *globset_search(
 386                         struct globset *set,
 387                         const char *pattern)
 388 {
 389         struct pathndl *ph, **pph;
 390         unsigned hash;
 391         char *pat;
 392
 393         /* local normalization */
 394         pat = alloca(1 + strlen(pattern));
 395         hash = normhash(pattern, pat);
 396
 397         /* search */
 398         ph = search(set, pat, hash, &pph);
 399         return ph ? &ph->handler : NULL;
 400 }
 401
 402 /**
 403  * Search a handler for the string 'text'
 404  * @param set the set
 405  * @param text the text to match
 406  * @return the handler found or NULL
 407  */
 408 const struct globset_handler *globset_match(
 409                         struct globset *set,
 410                         const char *text)
 411 {
 412         struct pathndl *ph, *iph;
 413         unsigned hash, g, s;
 414         char *txt;
 415
 416         /* local normalization */
 417         txt = alloca(1 + strlen(text));
 418         hash = normhash(text, txt);
 419
 420         /* first, look in dictionary of exact matches */
 421         ph = NULL;
 422         if (hash && set->exacts) {
 423                 ph = set->exacts[hash & set->gmask];
 424                 while(ph && (ph->hash != hash || strcmp(txt, ph->handler.pattern)))
 425                         ph = ph->next;
 426         }
 427
 428         /* then if not found */
 429         if (ph == NULL) {
 430                 /* look in glob patterns for the best match */
 431                 s = 0;
 432                 iph = set->globs;
 433                 while(iph) {
 434                         g = match(iph->handler.pattern, txt);
 435                         if (g > s) {
 436                                 s = g;
 437                                 ph = iph;
 438                         }
 439                         iph = iph->next;
 440                 }
 441         }
 442         return ph ? &ph->handler : NULL;
 443 }
 444