src/basic/hash-funcs.c

   1 /* SPDX-License-Identifier: LGPL-2.1+ */
   2
   3 #include <string.h>
   4
   5 #include "hash-funcs.h"
   6 #include "path-util.h"
   7
   8 void string_hash_func(const char *p, struct siphash *state) {
   9         siphash24_compress(p, strlen(p) + 1, state);
  10 }
  11
  12 DEFINE_HASH_OPS(string_hash_ops, char, string_hash_func, string_compare_func);
  13
  14 void path_hash_func(const char *q, struct siphash *state) {
  15         size_t n;
  16
  17         assert(q);
  18         assert(state);
  19
  20         /* Calculates a hash for a path in a way this duplicate inner slashes don't make a differences, and also
  21          * whether there's a trailing slash or not. This fits well with the semantics of path_compare(), which does
  22          * similar checks and also doesn't care for trailing slashes. Note that relative and absolute paths (i.e. those
  23          * which begin in a slash or not) will hash differently though. */
  24
  25         n = strspn(q, "/");
  26         if (n > 0) { /* Eat up initial slashes, and add one "/" to the hash for all of them */
  27                 siphash24_compress(q, 1, state);
  28                 q += n;
  29         }
  30
  31         for (;;) {
  32                 /* Determine length of next component */
  33                 n = strcspn(q, "/");
  34                 if (n == 0) /* Reached the end? */
  35                         break;
  36
  37                 /* Add this component to the hash and skip over it */
  38                 siphash24_compress(q, n, state);
  39                 q += n;
  40
  41                 /* How many slashes follow this component? */
  42                 n = strspn(q, "/");
  43                 if (q[n] == 0) /* Is this a trailing slash? If so, we are at the end, and don't care about the slashes anymore */
  44                         break;
  45
  46                 /* We are not add the end yet. Hash exactly one slash for all of the ones we just encountered. */
  47                 siphash24_compress(q, 1, state);
  48                 q += n;
  49         }
  50 }
  51
  52 int path_compare_func(const char *a, const char *b) {
  53         return path_compare(a, b);
  54 }
  55
  56 DEFINE_HASH_OPS(path_hash_ops, char, path_hash_func, path_compare_func);
  57
  58 void trivial_hash_func(const void *p, struct siphash *state) {
  59         siphash24_compress(&p, sizeof(p), state);
  60 }
  61
  62 int trivial_compare_func(const void *a, const void *b) {
  63         return CMP(a, b);
  64 }
  65
  66 const struct hash_ops trivial_hash_ops = {
  67         .hash = trivial_hash_func,
  68         .compare = trivial_compare_func,
  69 };
  70
  71 void uint64_hash_func(const uint64_t *p, struct siphash *state) {
  72         siphash24_compress(p, sizeof(uint64_t), state);
  73 }
  74
  75 int uint64_compare_func(const uint64_t *a, const uint64_t *b) {
  76         return CMP(*a, *b);
  77 }
  78
  79 DEFINE_HASH_OPS(uint64_hash_ops, uint64_t, uint64_hash_func, uint64_compare_func);
  80
  81 #if SIZEOF_DEV_T != 8
  82 void devt_hash_func(const dev_t *p, struct siphash *state) {
  83         siphash24_compress(p, sizeof(dev_t), state);
  84 }
  85
  86 int devt_compare_func(const dev_t *a, const dev_t *b) {
  87         return CMP(*a, *b);
  88 }
  89
  90 DEFINE_HASH_OPS(devt_hash_ops, dev_t, devt_hash_func, devt_compare_func);
  91 #endif