contrib/mtree/only.c

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