src/globset.c

   1 /*
   2  * Copyright (C) 2018, 2019 "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                 return NULL;
 232         while ((ph = *pph) && strcmp(normal, ph->handler.pattern))
 233                 pph = &ph->next;
 234         *pprev = pph;
 235         return ph;
 236 }
 237
 238
 239
 240
 241
 242
 243
 244
 245 /**
 246  * Allocates a new set of handlers
 247  *
 248  * @return the new allocated global pattern set of handlers or NULL on failure
 249  */
 250 struct globset *globset_create()
 251 {
 252         return calloc(1, sizeof(struct globset));
 253 }
 254
 255 /**
 256  * Destroy the set
 257  * @param set the set to destroy
 258  */
 259 void globset_destroy(struct globset *set)
 260 {
 261         unsigned i;
 262         struct pathndl *ph, *next_ph;
 263
 264         /* free exact pattern handlers */
 265         if (set->gmask) {
 266                 for(i = 0 ; i <= set->gmask ; i++) {
 267                         ph = set->exacts[i];
 268                         while (ph) {
 269                                 next_ph = ph->next;
 270                                 free(ph);
 271                                 ph = next_ph;
 272                         }
 273                 }
 274                 free(set->exacts);
 275         }
 276
 277         /* free global pattern handlers */
 278         ph = set->globs;
 279         while (ph) {
 280                 next_ph = ph->next;
 281                 free(ph);
 282                 ph = next_ph;
 283         }
 284
 285         /* free the set */
 286         free(set);
 287 }
 288
 289 /**
 290  * Add a handler for the given pattern
 291  * @param set the set
 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)
 296  */
 297 int globset_add(
 298                 struct globset *set,
 299                 const char *pattern,
 300                 void *callback,
 301                 void *closure)
 302 {
 303         struct pathndl *ph, **pph;
 304         unsigned hash;
 305         size_t len;
 306         char *pat;
 307
 308         /* normalize */
 309         len = strlen(pattern);
 310         pat = alloca(1 + len);
 311         hash = normhash(pattern, pat);
 312
 313         /* grows if needed */
 314         if (hash && grow(set))
 315                 return -1;
 316
 317         /* search */
 318         ph = search(set, pat, hash, &pph);
 319         if (ph) {
 320                 /* found */
 321                 errno = EEXIST;
 322                 return -1;
 323         }
 324
 325         /* not found, create it */
 326         ph = malloc(1 + len + sizeof *ph);
 327         if (!ph)
 328                 return -1;
 329
 330         /* initialize it */
 331         ph->next = NULL;
 332         ph->hash = hash;
 333         ph->handler.callback = callback;
 334         ph->handler.closure = closure;
 335         strcpy(ph->handler.pattern, pat);
 336         *pph = ph;
 337         if (hash)
 338                 set->count++;
 339         return 0;
 340 }
 341
 342 /**
 343  * Delete the handler for the pattern
 344  * @param set the set
 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)
 348  */
 349 int globset_del(
 350                         struct globset *set,
 351                         const char *pattern,
 352                         void **closure)
 353 {
 354         struct pathndl *ph, **pph;
 355         unsigned hash;
 356         char *pat;
 357
 358         /* normalize */
 359         pat = alloca(1 + strlen(pattern));
 360         hash = normhash(pattern, pat);
 361
 362         /* search */
 363         ph = search(set, pat, hash, &pph);
 364         if (!ph) {
 365                 /* not found */
 366                 errno = ENOENT;
 367                 return -1;
 368         }
 369
 370         /* found, remove it */
 371         if (hash)
 372                 set->count--;
 373         *pph = ph->next;
 374
 375         /* store the closure back */
 376         if (closure)
 377                 *closure = ph->handler.closure;
 378
 379         /* free the memory */
 380         free(ph);
 381         return 0;
 382 }
 383
 384 /**
 385  * Search the handler of 'pattern'
 386  * @param set the set
 387  * @param pattern the pattern to search
 388  * @return the handler found or NULL
 389  */
 390 struct globset_handler *globset_search(
 391                         struct globset *set,
 392                         const char *pattern)
 393 {
 394         struct pathndl *ph, **pph;
 395         unsigned hash;
 396         char *pat;
 397
 398         /* local normalization */
 399         pat = alloca(1 + strlen(pattern));
 400         hash = normhash(pattern, pat);
 401
 402         /* search */
 403         ph = search(set, pat, hash, &pph);
 404         return ph ? &ph->handler : NULL;
 405 }
 406
 407 /**
 408  * Search a handler for the string 'text'
 409  * @param set the set
 410  * @param text the text to match
 411  * @return the handler found or NULL
 412  */
 413 const struct globset_handler *globset_match(
 414                         struct globset *set,
 415                         const char *text)
 416 {
 417         struct pathndl *ph, *iph;
 418         unsigned hash, g, s;
 419         char *txt;
 420
 421         /* local normalization */
 422         txt = alloca(1 + strlen(text));
 423         hash = normhash(text, txt);
 424
 425         /* first, look in dictionary of exact matches */
 426         ph = NULL;
 427         if (hash && set->exacts) {
 428                 ph = set->exacts[hash & set->gmask];
 429                 while(ph && (ph->hash != hash || strcmp(txt, ph->handler.pattern)))
 430                         ph = ph->next;
 431         }
 432
 433         /* then if not found */
 434         if (ph == NULL) {
 435                 /* look in glob patterns for the best match */
 436                 s = 0;
 437                 iph = set->globs;
 438                 while(iph) {
 439                         g = match(iph->handler.pattern, txt);
 440                         if (g > s) {
 441                                 s = g;
 442                                 ph = iph;
 443                         }
 444                         iph = iph->next;
 445                 }
 446         }
 447         return ph ? &ph->handler : NULL;
 448 }
 449