src/basic/hash-funcs.c

   1 /* SPDX-License-Identifier: LGPL-2.1+ */
   2 /***
   3   This file is part of systemd.
   4
   5   Copyright 2010 Lennart Poettering
   6   Copyright 2014 Michal Schmidt
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU Lesser General Public License as published by
  10   the Free Software Foundation; either version 2.1 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 //#include <string.h>
  23
  24 #include "hash-funcs.h"
  25 //#include "path-util.h"
  26
  27 void string_hash_func(const void *p, struct siphash *state) {
  28         siphash24_compress(p, strlen(p) + 1, state);
  29 }
  30
  31 int string_compare_func(const void *a, const void *b) {
  32         return strcmp(a, b);
  33 }
  34
  35 const struct hash_ops string_hash_ops = {
  36         .hash = string_hash_func,
  37         .compare = string_compare_func
  38 };
  39
  40
  41 void path_hash_func(const void *p, struct siphash *state) {
  42         const char *q = p;
  43         size_t n;
  44
  45         assert(q);
  46         assert(state);
  47
  48         /* Calculates a hash for a path in a way this duplicate inner slashes don't make a differences, and also
  49          * whether there's a trailing slash or not. This fits well with the semantics of path_compare(), which does
  50          * similar checks and also doesn't care for trailing slashes. Note that relative and absolute paths (i.e. those
  51          * which begin in a slash or not) will hash differently though. */
  52
  53         n = strspn(q, "/");
  54         if (n > 0) { /* Eat up initial slashes, and add one "/" to the hash for all of them */
  55                 siphash24_compress(q, 1, state);
  56                 q += n;
  57         }
  58
  59         for (;;) {
  60                 /* Determine length of next component */
  61                 n = strcspn(q, "/");
  62                 if (n == 0) /* Reached the end? */
  63                         break;
  64
  65                 /* Add this component to the hash and skip over it */
  66                 siphash24_compress(q, n, state);
  67                 q += n;
  68
  69                 /* How many slashes follow this component? */
  70                 n = strspn(q, "/");
  71                 if (q[n] == 0) /* Is this a trailing slash? If so, we are at the end, and don't care about the slashes anymore */
  72                         break;
  73
  74                 /* We are not add the end yet. Hash exactly one slash for all of the ones we just encountered. */
  75                 siphash24_compress(q, 1, state);
  76                 q += n;
  77         }
  78 }
  79
  80 int path_compare_func(const void *a, const void *b) {
  81         return path_compare(a, b);
  82 }
  83
  84 const struct hash_ops path_hash_ops = {
  85         .hash = path_hash_func,
  86         .compare = path_compare_func
  87 };
  88
  89 void trivial_hash_func(const void *p, struct siphash *state) {
  90         siphash24_compress(&p, sizeof(p), state);
  91 }
  92
  93 int trivial_compare_func(const void *a, const void *b) {
  94         return a < b ? -1 : (a > b ? 1 : 0);
  95 }
  96
  97 const struct hash_ops trivial_hash_ops = {
  98         .hash = trivial_hash_func,
  99         .compare = trivial_compare_func
 100 };
 101
 102 void uint64_hash_func(const void *p, struct siphash *state) {
 103         siphash24_compress(p, sizeof(uint64_t), state);
 104 }
 105
 106 int uint64_compare_func(const void *_a, const void *_b) {
 107         uint64_t a, b;
 108         a = *(const uint64_t*) _a;
 109         b = *(const uint64_t*) _b;
 110         return a < b ? -1 : (a > b ? 1 : 0);
 111 }
 112
 113 const struct hash_ops uint64_hash_ops = {
 114         .hash = uint64_hash_func,
 115         .compare = uint64_compare_func
 116 };
 117
 118 #if SIZEOF_DEV_T != 8
 119 void devt_hash_func(const void *p, struct siphash *state) {
 120         siphash24_compress(p, sizeof(dev_t), state);
 121 }
 122
 123 int devt_compare_func(const void *_a, const void *_b) {
 124         dev_t a, b;
 125         a = *(const dev_t*) _a;
 126         b = *(const dev_t*) _b;
 127         return a < b ? -1 : (a > b ? 1 : 0);
 128 }
 129
 130 const struct hash_ops devt_hash_ops = {
 131         .hash = devt_hash_func,
 132         .compare = devt_compare_func
 133 };
 134 #endif