src/basic/hash-funcs.c

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