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