silo/masstree/string_slice.hh

   1 /* Masstree
   2  * Eddie Kohler, Yandong Mao, Robert Morris
   3  * Copyright (c) 2012-2014 President and Fellows of Harvard College
   4  * Copyright (c) 2012-2014 Massachusetts Institute of Technology
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the "Software"),
   8  * to deal in the Software without restriction, subject to the conditions
   9  * listed in the Masstree LICENSE file. These conditions include: you must
  10  * preserve this copyright notice, and you cannot mention the copyright
  11  * holders in advertising related to the Software without their permission.
  12  * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
  13  * notice is a summary of the Masstree LICENSE file; the license in that file
  14  * is legally binding.
  15  */
  16 #ifndef STRING_SLICE_HH
  17 #define STRING_SLICE_HH 1
  18 #include "str.hh"
  19 #include <algorithm>
  20 #include <assert.h>
  21 #include <string.h>
  22 class threadinfo;
  23
  24 /** @brief Provide access to T-typed slices of a string. */
  25 template <typename T> struct string_slice {
  26   private:
  27     union union_type {
  28         T x;
  29         char s[sizeof(T)];
  30         union_type(T x)
  31             : x(x) {
  32         }
  33     };
  34
  35   public:
  36     typedef T type;
  37
  38     /** @brief Size of T in bytes. */
  39     static constexpr int size = (int) sizeof(T);
  40
  41     /** @brief Return a T containing data from a string's prefix. */
  42     static T make(const char *s, int len) {
  43         if (len <= 0)
  44             return 0;
  45 #if HAVE_UNALIGNED_ACCESS
  46         if (len >= size)
  47             return *reinterpret_cast<const T *>(s);
  48 #endif
  49         union_type u(0);
  50         memcpy(u.s, s, std::min(len, size));
  51         return u.x;
  52     }
  53
  54     /** @brief Return a T that compares similarly to a string's prefix.
  55
  56         If a = make_comparable(s1, l1), b = make_comparable(s2, l2), and
  57         a < b, then the string (s1, l1) is lexicographically less than
  58         the string (s2, l2). Similarly, if a > b, then (s1, l1) is
  59         lexicographically greater than (s2, l2). If a == b, then the
  60         prefixes of (s1, l1) and (s2, l2) are lexicographically equal. */
  61     static T make_comparable(const char *s, int len) {
  62         return net_to_host_order(make(s, len));
  63     }
  64
  65     /** @brief Return a T containing data from a string's prefix.
  66         @pre It is safe to access characters in the range
  67           [@a s - size - 1, @a s + size).
  68
  69         This function acts like make(), but can use single memory accesses for
  70         short strings. These accesses may observe data outside the range [@a
  71         s, @a s + len). */
  72     static T make_sloppy(const char *s, int len) {
  73         if (len <= 0)
  74             return 0;
  75 #if HAVE_UNALIGNED_ACCESS
  76         if (len >= size)
  77             return *reinterpret_cast<const T *>(s);
  78 # if WORDS_BIGENDIAN
  79         return *reinterpret_cast<const T *>(s) & (~T(0) << (8 * (size - len)));
  80 # elif WORDS_BIGENDIAN_SET
  81         return *reinterpret_cast<const T *>(s - (size - len)) >> (8 * (size - len));
  82 # else
  83 #  error "WORDS_BIGENDIAN has not been set!"
  84 # endif
  85 #else
  86         union_type u(0);
  87         memcpy(u.s, s, std::min(len, size));
  88         return u.x;
  89 #endif
  90     }
  91
  92     /** @brief Return a T that compares similarly to a string's prefix.
  93         @pre It is safe to access characters in the range
  94           [@a s - size - 1, @a s + size).
  95
  96         This function acts like make_comparable(), but can use single memory
  97         accesses for short strings. These accesses may observe data outside
  98         the range [@a s, @a s + len). */
  99     static T make_comparable_sloppy(const char *s, int len) {
 100         return net_to_host_order(make_sloppy(s, len));
 101     }
 102
 103
 104     /** @brief Unparse a comparable @a value into a buffer.
 105         @return Number of characters unparsed (<= buflen).
 106
 107         If @a value was created by string_slice::make_comparable(s, x), then
 108         after this function returns, @a buf contains a string equal to the
 109         original @a s, except that trailing null characters have been
 110         removed. */
 111     static int unparse_comparable(char *buf, int buflen, T value) {
 112         union_type u(host_to_net_order(value));
 113         int l = size;
 114         while (l > 0 && u.s[l - 1] == 0)
 115             --l;
 116         l = std::min(l, buflen);
 117         memcpy(buf, u.s, l);
 118         return l;
 119     }
 120
 121     /** @brief Unparse a comparable @a value into a buffer.
 122         @return Number of characters unparsed (<= buflen).
 123
 124         If @a value was created by string_slice::make_comparable(s, @a len),
 125         then after this function returns, @a buf contains a string equal to
 126         the first @a len bytes of s. */
 127     static int unparse_comparable(char *buf, int buflen, T value, int len) {
 128         union_type u(host_to_net_order(value));
 129         int l = std::min(std::min(len, size), buflen);
 130         memcpy(buf, u.s, l);
 131         return l;
 132     }
 133
 134
 135     /** @brief Test two strings for equality.
 136         @param a first string
 137         @param b second string
 138         @param len number of characters in @a a and @a b
 139         @return true iff the two strings' first @a len characters are equal
 140         @pre It is safe to access characters in the ranges
 141           [@a a - size + 1, @a a + size) and [@a b - size + 1, @a b + size).
 142
 143         Always returns the same result as "memcmp(@a a, @a b, @a len) == 0",
 144         but can be faster on some machines. */
 145     static bool equals_sloppy(const char *a, const char *b, int len) {
 146 #if HAVE_UNALIGNED_ACCESS
 147         if (len <= size) {
 148             typename mass::make_unsigned<T>::type delta
 149                 = *reinterpret_cast<const T *>(a)
 150                 ^ *reinterpret_cast<const T *>(b);
 151             if (unlikely(len <= 0))
 152                 return true;
 153 # if WORDS_BIGENDIAN
 154             return (delta >> (8 * (size - len))) == 0;
 155 # else
 156             return (delta << (8 * (size - len))) == 0;
 157 # endif
 158         }
 159 #endif
 160         return memcmp(a, b, len) == 0;
 161     }
 162 };
 163
 164 template <typename T> constexpr int string_slice<T>::size;
 165
 166 #endif