usr.sbin/mtree/only.c

   1 /*      $NetBSD: only.c,v 1.3 2017/09/07 04:04:13 nakayama Exp $        */
   2
   3 /*-
   4  * Copyright (c) 2013 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Christos Zoulas.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of The NetBSD Foundation nor the names of its
  19  *    contributors may be used to endorse or promote products derived
  20  *    from this software without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  23  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  24  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  25  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  26  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  27  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  28  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  29  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  30  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  31  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  32  * POSSIBILITY OF SUCH DAMAGE.
  33  */
  34
  35 #include <sys/param.h>
  36
  37 #include <stdio.h>
  38 #include <stdint.h>
  39 #include <stdlib.h>
  40 #include <string.h>
  41 #include <stdbool.h>
  42 #include <time.h>
  43 #include <err.h>
  44 #include <util.h>
  45
  46 #include "extern.h"
  47
  48 struct hentry {
  49         char *str;
  50         uint32_t hash;
  51         struct hentry *next;
  52 };
  53
  54 static struct hentry *table[1024];
  55 static bool loaded;
  56
  57 static uint32_t
  58 hash_str(const char *str)
  59 {
  60         const uint8_t *s = (const uint8_t *)str;
  61         uint8_t c;
  62         uint32_t hash = 0;
  63         while ((c = *s++) != '\0')
  64                 hash = hash * 33 + c;           /* "perl": k=33, r=r+r/32 */
  65         return hash + (hash >> 5);
  66 }
  67
  68 static bool
  69 hash_find(const char *str, uint32_t *h)
  70 {
  71         struct hentry *e;
  72         *h = hash_str(str) % NELEM(table);
  73
  74         for (e = table[*h]; e; e = e->next)
  75                 if (e->hash == *h && strcmp(e->str, str) == 0)
  76                         return true;
  77         return false;
  78 }
  79
  80 static void
  81 hash_insert(char *str, uint32_t h)
  82 {
  83         struct hentry *e;
  84         char *x;
  85
  86         if ((e = malloc(sizeof(*e))) == NULL)
  87                 mtree_err("memory allocation error");
  88         if ((x = strdup(str)) == NULL)
  89                 mtree_err("memory allocation error");
  90
  91         e->str = x;
  92         e->hash = h;
  93         e->next = table[h];
  94         table[h] = e;
  95 }
  96
  97 static void
  98 fill(char *str)
  99 {
 100         uint32_t h;
 101         char *ptr = strrchr(str, '/');
 102
 103         if (ptr == NULL)
 104                 return;
 105
 106         *ptr = '\0';
 107         if (!hash_find(str, &h)) {
 108                 hash_insert(str, h);
 109                 fill(str);
 110         }
 111         *ptr = '/';
 112 }
 113
 114 void
 115 load_only(const char *fname)
 116 {
 117         FILE *fp;
 118         char *line;
 119         size_t len, lineno;
 120
 121         if ((fp = fopen(fname, "r")) == NULL)
 122                 err(1, "Cannot open `%s'", fname);
 123
 124         while ((line = fparseln(fp, &len, &lineno, NULL, FPARSELN_UNESCALL))) {
 125                 uint32_t h;
 126                 if (hash_find(line, &h))
 127                         err(1, "Duplicate entry %s", line);
 128                 hash_insert(line, h);
 129                 fill(line);
 130                 free(line);
 131         }
 132
 133         fclose(fp);
 134         loaded = true;
 135 }
 136
 137 bool
 138 find_only(const char *path)
 139 {
 140         uint32_t h;
 141
 142         if (!loaded)
 143                 return true;
 144         return hash_find(path, &h);
 145 }