src/basic/hash-funcs.c

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