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 #if HAVE_NBTOOL_CONFIG_H
  35 #include "nbtool_config.h"
  36 #endif
  37
  38 #include <sys/param.h>
  39
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include <stdbool.h>
  44 #include <time.h>
  45 #include <err.h>
  46 #include <util.h>
  47
  48 #include "extern.h"
  49
  50 struct hentry {
  51         char *str;
  52         uint32_t hash;
  53         struct hentry *next;
  54 };
  55
  56 static struct hentry *table[1024];
  57 static bool loaded;
  58
  59 static uint32_t
  60 hash_str(const char *str)
  61 {
  62         const uint8_t *s = (const uint8_t *)str;
  63         uint8_t c;
  64         uint32_t hash = 0;
  65         while ((c = *s++) != '\0')
  66                 hash = hash * 33 + c;           /* "perl": k=33, r=r+r/32 */
  67         return hash + (hash >> 5);
  68 }
  69
  70 static bool
  71 hash_find(const char *str, uint32_t *h)
  72 {
  73         struct hentry *e;
  74         *h = hash_str(str) % NELEM(table);
  75
  76         for (e = table[*h]; e; e = e->next)
  77                 if (e->hash == *h && strcmp(e->str, str) == 0)
  78                         return true;
  79         return false;
  80 }
  81
  82 static void
  83 hash_insert(char *str, uint32_t h)
  84 {
  85         struct hentry *e;
  86         char *x;
  87
  88         if ((e = malloc(sizeof(*e))) == NULL)
  89                 mtree_err("memory allocation error");
  90         if ((x = strdup(str)) == NULL)
  91                 mtree_err("memory allocation error");
  92
  93         e->str = x;
  94         e->hash = h;
  95         e->next = table[h];
  96         table[h] = e;
  97 }
  98
  99 static void
 100 fill(char *str)
 101 {
 102         uint32_t h;
 103         char *ptr = strrchr(str, '/');
 104
 105         if (ptr == NULL)
 106                 return;
 107
 108         *ptr = '\0';
 109         if (!hash_find(str, &h)) {
 110                 hash_insert(str, h);
 111                 fill(str);
 112         }
 113         *ptr = '/';
 114 }
 115
 116 void
 117 load_only(const char *fname)
 118 {
 119         FILE *fp;
 120         char *line;
 121         size_t len, lineno;
 122
 123         if ((fp = fopen(fname, "r")) == NULL)
 124                 err(1, "Cannot open `%s'", fname);
 125
 126         while ((line = fparseln(fp, &len, &lineno, NULL, FPARSELN_UNESCALL))) {
 127                 uint32_t h;
 128                 if (hash_find(line, &h))
 129                         err(1, "Duplicate entry %s", line);
 130                 hash_insert(line, h);
 131                 fill(line);
 132                 free(line);
 133         }
 134
 135         fclose(fp);
 136         loaded = true;
 137 }
 138
 139 bool
 140 find_only(const char *path)
 141 {
 142         uint32_t h;
 143
 144         if (!loaded)
 145                 return true;
 146         return hash_find(path, &h);
 147 }