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