src/basic/hash-funcs.c

   1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
   2
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include <sys/sysmacros.h>
   6
   7 #include "hash-funcs.h"
   8 #include "path-util.h"
   9 #include "siphash24.h"
  10 #include "strv.h"
  11
  12 void string_hash_func(const char *p, struct siphash *state) {
  13         siphash24_compress(p, strlen(p) + 1, state);
  14 }
  15
  16 DEFINE_HASH_OPS(string_hash_ops,
  17                 char, string_hash_func, string_compare_func);
  18 DEFINE_HASH_OPS_WITH_KEY_DESTRUCTOR(
  19                 string_hash_ops_free,
  20                 char, string_hash_func, string_compare_func, free);
  21 DEFINE_HASH_OPS_WITH_VALUE_DESTRUCTOR(
  22                 string_hash_ops_value_free,
  23                 char, string_hash_func, string_compare_func,
  24                 void, free);
  25 DEFINE_HASH_OPS_FULL(
  26                 string_hash_ops_free_free,
  27                 char, string_hash_func, string_compare_func, free,
  28                 void, free);
  29 DEFINE_HASH_OPS_FULL(
  30                 string_hash_ops_free_strv_free,
  31                 char, string_hash_func, string_compare_func, free,
  32                 char*, strv_free);
  33
  34 void path_hash_func(const char *q, struct siphash *state) {
  35         bool add_slash = false;
  36
  37         assert(q);
  38         assert(state);
  39
  40         /* Calculates a hash for a path in a way this duplicate inner slashes don't make a differences, and also
  41          * whether there's a trailing slash or not. This fits well with the semantics of path_compare(), which does
  42          * similar checks and also doesn't care for trailing slashes. Note that relative and absolute paths (i.e. those
  43          * which begin in a slash or not) will hash differently though. */
  44
  45         /* if path is absolute, add one "/" to the hash. */
  46         if (path_is_absolute(q))
  47                 siphash24_compress_byte('/', state);
  48
  49         for (;;) {
  50                 const char *e;
  51                 int r;
  52
  53                 r = path_find_first_component(&q, true, &e);
  54                 if (r == 0)
  55                         return;
  56
  57                 if (add_slash)
  58                         siphash24_compress_byte('/', state);
  59
  60                 if (r < 0) {
  61                         /* if a component is invalid, then add remaining part as a string. */
  62                         string_hash_func(q, state);
  63                         return;
  64                 }
  65
  66                 /* Add this component to the hash. */
  67                 siphash24_compress(e, r, state);
  68
  69                 add_slash = true;
  70         }
  71 }
  72
  73 DEFINE_HASH_OPS(path_hash_ops,
  74                 char, path_hash_func, path_compare);
  75 DEFINE_HASH_OPS_WITH_KEY_DESTRUCTOR(
  76                 path_hash_ops_free,
  77                 char, path_hash_func, path_compare, free);
  78 DEFINE_HASH_OPS_FULL(
  79                 path_hash_ops_free_free,
  80                 char, path_hash_func, path_compare, free,
  81                 void, free);
  82
  83 void trivial_hash_func(const void *p, struct siphash *state) {
  84         siphash24_compress_typesafe(p, state);
  85 }
  86
  87 int trivial_compare_func(const void *a, const void *b) {
  88         return CMP(a, b);
  89 }
  90
  91 DEFINE_HASH_OPS(trivial_hash_ops,
  92                 void, trivial_hash_func, trivial_compare_func);
  93 DEFINE_HASH_OPS_WITH_KEY_DESTRUCTOR(
  94                 trivial_hash_ops_free,
  95                 void, trivial_hash_func, trivial_compare_func, free);
  96 DEFINE_HASH_OPS_WITH_VALUE_DESTRUCTOR(
  97                 trivial_hash_ops_value_free,
  98                 void, trivial_hash_func, trivial_compare_func,
  99                 void, free);
 100 DEFINE_HASH_OPS_FULL(
 101                 trivial_hash_ops_free_free,
 102                 void, trivial_hash_func, trivial_compare_func, free,
 103                 void, free);
 104
 105 void uint64_hash_func(const uint64_t *p, struct siphash *state) {
 106         siphash24_compress_typesafe(*p, state);
 107 }
 108
 109 int uint64_compare_func(const uint64_t *a, const uint64_t *b) {
 110         return CMP(*a, *b);
 111 }
 112
 113 DEFINE_HASH_OPS(uint64_hash_ops,
 114                 uint64_t, uint64_hash_func, uint64_compare_func);
 115 DEFINE_HASH_OPS_WITH_VALUE_DESTRUCTOR(
 116                 uint64_hash_ops_value_free,
 117                 uint64_t, uint64_hash_func, uint64_compare_func,
 118                 void, free);
 119
 120 #if SIZEOF_DEV_T != 8
 121 void devt_hash_func(const dev_t *p, struct siphash *state) {
 122         siphash24_compress_typesafe(*p, state);
 123 }
 124 #endif
 125
 126 int devt_compare_func(const dev_t *a, const dev_t *b) {
 127         int r;
 128
 129         r = CMP(major(*a), major(*b));
 130         if (r != 0)
 131                 return r;
 132
 133         return CMP(minor(*a), minor(*b));
 134 }
 135
 136 DEFINE_HASH_OPS(devt_hash_ops, dev_t, devt_hash_func, devt_compare_func);