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