src/basic/hash-funcs.c

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