string_slice.hh

/* Masstree
 * Eddie Kohler, Yandong Mao, Robert Morris
 * Copyright (c) 2012-2013 President and Fellows of Harvard College
 * Copyright (c) 2012-2013 Massachusetts Institute of Technology
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, subject to the conditions
 * listed in the Masstree LICENSE file. These conditions include: you must
 * preserve this copyright notice, and you cannot mention the copyright
 * holders in advertising related to the Software without their permission.
 * The Software is provided WITHOUT ANY WARRANTY, EXPRESS OR IMPLIED. This
 * notice is a summary of the Masstree LICENSE file; the license in that file
 * is legally binding.
 */
#ifndef STRING_SLICE_HH
#define STRING_SLICE_HH 1
#include "str.hh"
#include <algorithm>
#include <assert.h>
#include <string.h>
class threadinfo;

/** @brief Provide access to T-typed slices of a string. */
template <typename T> struct string_slice {
  private:
    union union_type {
	T x;
	char s[sizeof(T)];
	union_type(T x)
	    : x(x) {
	}
    };

  public:
    typedef T type;

    /** @brief Size of T in bytes. */
    static constexpr int size = (int) sizeof(T);

    /** @brief Return a T containing data from a string's prefix. */
    static T make(const char *s, int len) {
	if (len <= 0)
	    return 0;
#if HAVE_UNALIGNED_ACCESS
	if (len >= size)
	    return *reinterpret_cast<const T *>(s);
#endif
	union_type u(0);
	memcpy(u.s, s, std::min(len, size));
	return u.x;
    }

    /** @brief Return a T that compares similarly to a string's prefix.

	If a = make_comparable(s1, l1) and b = make_comparable(s2, l2),
	then a < b iff the string (s1, l1) is lexicographically less than
	the string (s2, l2), and similarly for other comparators. */
    static T make_comparable(const char *s, int len) {
	return net_to_host_order(make(s, len));
    }

    /** @brief Return a T containing data from a string's prefix.
	@pre It is safe to access characters in the range
	  [@a s - size - 1, @a s + size).

	This function acts like make(), but can use single memory accesses for
	short strings. These accesses may observe data outside the range [@a
	s, @a s + len). */
    static T make_sloppy(const char *s, int len) {
	if (len <= 0)
	    return 0;
#if HAVE_UNALIGNED_ACCESS
	if (len >= size)
	    return *reinterpret_cast<const T *>(s);
# if ENDIAN_BIG
	return *reinterpret_cast<const T *>(s) & (~T(0) << (8 * (size - len)));
# else
	return *reinterpret_cast<const T *>(s - (size - len)) >> (8 * (size - len));
# endif
#else
	union_type u(0);
	memcpy(u.s, s, std::min(len, size));
	return u.x;
#endif
    }

    /** @brief Return a T that compares similarly to a string's prefix.
	@pre It is safe to access characters in the range
	  [@a s - size - 1, @a s + size).

	This function acts like make_comparable(), but can use single memory
	accesses for short strings. These accesses may observe data outside
	the range [@a s, @a s + len). */
    static T make_comparable_sloppy(const char *s, int len) {
	return net_to_host_order(make_sloppy(s, len));
    }


    /** @brief Unparse a comparable @a value into a buffer.
	@return Number of characters unparsed (<= buflen).

	If @a value was created by string_slice::make_comparable(s, x), then
	after this function returns, @a buf contains a string equal to the
	original @a s, except that trailing null characters have been
	removed. */
    static int unparse_comparable(char *buf, int buflen, T value) {
	union_type u(host_to_net_order(value));
	int l = size;
	while (l > 0 && u.s[l - 1] == 0)
	    --l;
	l = std::min(l, buflen);
	memcpy(buf, u.s, l);
	return l;
    }

    /** @brief Unparse a comparable @a value into a buffer.
	@return Number of characters unparsed (<= buflen).

	If @a value was created by string_slice::make_comparable(s, @a len),
	then after this function returns, @a buf contains a string equal to
	the first @a len bytes of s. */
    static int unparse_comparable(char *buf, int buflen, T value, int len) {
	union_type u(host_to_net_order(value));
	int l = std::min(std::min(len, size), buflen);
	memcpy(buf, u.s, l);
	return l;
    }


    /** @brief Test two strings for equality.
	@param a first string
	@param b second string
	@param len number of characters in @a a and @a b
	@return true iff the two strings' first @a len characters are equal
	@pre It is safe to access characters in the ranges
	  [@a a - size + 1, @a a + size) and [@a b - size + 1, @a b + size).

	Always returns the same result as "memcmp(@a a, @a b, @a len) == 0",
	but can be faster on some machines. */
    static bool equals_sloppy(const char *a, const char *b, int len) {
#if HAVE_UNALIGNED_ACCESS
	if (len <= size) {
	    typename mass::make_unsigned<T>::type delta
		= *reinterpret_cast<const T *>(a)
		^ *reinterpret_cast<const T *>(b);
	    if (unlikely(len <= 0))
		return true;
# if ENDIAN_BIG
	    return (delta >> (8 * (size - len))) == 0;
# else
	    return (delta << (8 * (size - len))) == 0;
# endif
	}
#endif
	return memcmp(a, b, len) == 0;
    }
};

template <typename T> constexpr int string_slice<T>::size;

#endif