silo/masstree/kpermuter.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 KPERMUTER_HH
  17 #define KPERMUTER_HH
  18 #include "string.hh"
  19
  20 class identity_kpermuter {
  21     int size_;
  22   public:
  23     identity_kpermuter(int size)
  24         : size_(size) {
  25     }
  26
  27     int size() const {
  28         return size_;
  29     }
  30     int operator[](int i) const {
  31         return i;
  32     }
  33     bool operator==(const identity_kpermuter&) const {
  34         return true;
  35     }
  36     bool operator!=(const identity_kpermuter&) const {
  37         return false;
  38     }
  39 };
  40
  41 template <int C> struct sized_kpermuter_info {};
  42 template <> struct sized_kpermuter_info<0> {
  43     typedef uint16_t storage_type;
  44     typedef unsigned value_type;
  45     enum { initial_value = 0x0120U, full_value = 0x2100U };
  46 };
  47 template <> struct sized_kpermuter_info<1> {
  48     typedef uint32_t storage_type;
  49     typedef unsigned value_type;
  50     enum { initial_value = 0x01234560U, full_value = 0x65432100U };
  51 };
  52 template <> struct sized_kpermuter_info<2> {
  53     typedef uint64_t storage_type;
  54     typedef uint64_t value_type;
  55     enum { initial_value = (uint64_t) 0x0123456789ABCDE0ULL,
  56            full_value = (uint64_t) 0xEDCBA98765432100ULL };
  57 };
  58
  59 template <int width> class kpermuter {
  60   public:
  61     typedef sized_kpermuter_info<(width > 3) + (width > 7) + (width > 15)> info;
  62     typedef typename info::storage_type storage_type;
  63     typedef typename info::value_type value_type;
  64     enum { max_width = (int) (sizeof(storage_type) * 2 - 1) };
  65     enum { size_bits = 4 };
  66
  67     /** @brief Construct an uninitialized permuter. */
  68     kpermuter() {
  69     }
  70     /** @brief Construct a permuter with value @a x. */
  71     kpermuter(value_type x)
  72         : x_(x) {
  73     }
  74
  75     /** @brief Return an empty permuter with size 0.
  76
  77         Elements will be allocated in order 0, 1, ..., @a width - 1. */
  78     static inline value_type make_empty() {
  79         value_type p = (value_type) info::initial_value >> ((max_width - width) << 2);
  80         return p & ~(value_type) 15;
  81     }
  82     /** @brief Return a permuter with size @a n.
  83
  84         The returned permutation has size() @a n. For 0 <= i < @a n,
  85         (*this)[i] == i. Elements n through @a width - 1 are free, and will be
  86         allocated in that order. */
  87     static inline value_type make_sorted(int n) {
  88         value_type mask = (n == width ? (value_type) 0 : (value_type) 16 << (n << 2)) - 1;
  89         return (make_empty() << (n << 2))
  90             | ((value_type) info::full_value & mask)
  91             | n;
  92     }
  93
  94     /** @brief Return the permuter's size. */
  95     int size() const {
  96         return x_ & 15;
  97     }
  98     /** @brief Return the permuter's element @a i.
  99         @pre 0 <= i < width */
 100     int operator[](int i) const {
 101         return (x_ >> ((i << 2) + 4)) & 15;
 102     }
 103     int back() const {
 104         return (*this)[width - 1];
 105     }
 106     value_type value() const {
 107         return x_;
 108     }
 109     value_type value_from(int i) const {
 110         return x_ >> ((i + 1) << 2);
 111     }
 112
 113     void set_size(int n) {
 114         x_ = (x_ & ~(value_type) 15) | n;
 115     }
 116     /** @brief Allocate a new element and insert it at position @a i.
 117         @pre 0 <= @a i < @a width
 118         @pre size() < @a width
 119         @return The newly allocated element.
 120
 121         Consider the following code:
 122         <code>
 123         kpermuter<...> p = ..., q = p;
 124         int x = q.insert_from_back(i);
 125         </code>
 126
 127         The modified permuter, q, has the following properties.
 128         <ul>
 129         <li>q.size() == p.size() + 1</li>
 130         <li>Given j with 0 <= j < i, q[j] == p[j] && q[j] != x</li>
 131         <li>Given j with j == i, q[j] == x</li>
 132         <li>Given j with i < j < q.size(), q[j] == p[j-1] && q[j] != x</li>
 133         </ul> */
 134     int insert_from_back(int i) {
 135         int value = back();
 136         // increment size, leave lower slots unchanged
 137         x_ = ((x_ + 1) & (((value_type) 16 << (i << 2)) - 1))
 138             // insert slot
 139             | ((value_type) value << ((i << 2) + 4))
 140             // shift up unchanged higher entries & empty slots
 141             | ((x_ << 4) & ~(((value_type) 256 << (i << 2)) - 1));
 142         return value;
 143     }
 144     /** @brief Insert an unallocated element from position @a si at position @a di.
 145         @pre 0 <= @a di < @a width
 146         @pre size() < @a width
 147         @pre size() <= @a si
 148         @return The newly allocated element. */
 149     void insert_selected(int di, int si) {
 150         (void) width;
 151         int value = (*this)[si];
 152         value_type mask = ((value_type) 256 << (si << 2)) - 1;
 153         // increment size, leave lower slots unchanged
 154         x_ = ((x_ + 1) & (((value_type) 16 << (di << 2)) - 1))
 155             // insert slot
 156             | ((value_type) value << ((di << 2) + 4))
 157             // shift up unchanged higher entries & empty slots
 158             | ((x_ << 4) & mask & ~(((value_type) 256 << (di << 2)) - 1))
 159             // leave uppermost slots alone
 160             | (x_ & ~mask);
 161     }
 162     /** @brief Remove the element at position @a i.
 163         @pre 0 <= @a i < @a size()
 164         @pre size() < @a width
 165
 166         Consider the following code:
 167         <code>
 168         kpermuter<...> p = ..., q = p;
 169         q.remove(i);
 170         </code>
 171
 172         The modified permuter, q, has the following properties.
 173         <ul>
 174         <li>q.size() == p.size() - 1</li>
 175         <li>Given j with 0 <= j < i, q[j] == p[j]</li>
 176         <li>Given j with i <= j < q.size(), q[j] == p[j+1]</li>
 177         <li>q[q.size()] == p[i]</li>
 178         </ul> */
 179     void remove(int i) {
 180         (void) width;
 181         if (int(x_ & 15) == i + 1)
 182             --x_;
 183         else {
 184             int rot_amount = ((x_ & 15) - i - 1) << 2;
 185             value_type rot_mask =
 186                 (((value_type) 16 << rot_amount) - 1) << ((i + 1) << 2);
 187             // decrement size, leave lower slots unchanged
 188             x_ = ((x_ - 1) & ~rot_mask)
 189                 // shift higher entries down
 190                 | (((x_ & rot_mask) >> 4) & rot_mask)
 191                 // shift value up
 192                 | (((x_ & rot_mask) << rot_amount) & rot_mask);
 193         }
 194     }
 195     /** @brief Remove the element at position @a i to the back.
 196         @pre 0 <= @a i < @a size()
 197         @pre size() < @a width
 198
 199         Consider the following code:
 200         <code>
 201         kpermuter<...> p = ..., q = p;
 202         q.remove_to_back(i);
 203         </code>
 204
 205         The modified permuter, q, has the following properties.
 206         <ul>
 207         <li>q.size() == p.size() - 1</li>
 208         <li>Given j with 0 <= j < i, q[j] == p[j]</li>
 209         <li>Given j with i <= j < @a width - 1, q[j] == p[j+1]</li>
 210         <li>q.back() == p[i]</li>
 211         </ul> */
 212     void remove_to_back(int i) {
 213         value_type mask = ~(((value_type) 16 << (i << 2)) - 1);
 214         // clear unused slots
 215         value_type x = x_ & (((value_type) 16 << (width << 2)) - 1);
 216         // decrement size, leave lower slots unchanged
 217         x_ = ((x - 1) & ~mask)
 218             // shift higher entries down
 219             | ((x >> 4) & mask)
 220             // shift removed element up
 221             | ((x & mask) << ((width - i - 1) << 2));
 222     }
 223     /** @brief Rotate the permuter's elements between @a i and size().
 224         @pre 0 <= @a i <= @a j <= size()
 225
 226         Consider the following code:
 227         <code>
 228         kpermuter<...> p = ..., q = p;
 229         q.rotate(i, j);
 230         </code>
 231
 232         The modified permuter, q, has the following properties.
 233         <ul>
 234         <li>q.size() == p.size()</li>
 235         <li>Given k with 0 <= k < i, q[k] == p[k]</li>
 236         <li>Given k with i <= k < q.size(), q[k] == p[i + (k - i + j - i) mod (size() - i)]</li>
 237         </ul> */
 238     void rotate(int i, int j) {
 239         value_type mask = (i == width ? (value_type) 0 : (value_type) 16 << (i << 2)) - 1;
 240         // clear unused slots
 241         value_type x = x_ & (((value_type) 16 << (width << 2)) - 1);
 242         x_ = (x & mask)
 243             | ((x >> ((j - i) << 2)) & ~mask)
 244             | ((x & ~mask) << ((width - j) << 2));
 245     }
 246     /** @brief Exchange the elements at positions @a i and @a j. */
 247     void exchange(int i, int j) {
 248         value_type diff = ((x_ >> (i << 2)) ^ (x_ >> (j << 2))) & 240;
 249         x_ ^= (diff << (i << 2)) | (diff << (j << 2));
 250     }
 251     /** @brief Exchange positions of values @a x and @a y. */
 252     void exchange_values(int x, int y) {
 253         value_type diff = 0, p = x_;
 254         for (int i = 0; i < width; ++i, diff <<= 4, p <<= 4) {
 255             int v = (p >> (width << 2)) & 15;
 256             diff ^= -((v == x) | (v == y)) & (x ^ y);
 257         }
 258         x_ ^= diff;
 259     }
 260
 261     lcdf::String unparse() const;
 262
 263     bool operator==(const kpermuter<width>& x) const {
 264         return x_ == x.x_;
 265     }
 266     bool operator!=(const kpermuter<width>& x) const {
 267         return !(*this == x);
 268     }
 269
 270     static inline int size(value_type p) {
 271         return p & 15;
 272     }
 273   private:
 274     value_type x_;
 275 };
 276
 277 template <int width>
 278 lcdf::String kpermuter<width>::unparse() const
 279 {
 280     char buf[max_width + 3], *s = buf;
 281     value_type p(x_);
 282     value_type seen(0);
 283     int n = p & 15;
 284     p >>= 4;
 285     for (int i = 0; true; ++i) {
 286         if (i == n)
 287             *s++ = ':';
 288         if (i == width)
 289             break;
 290         if ((p & 15) < 10)
 291             *s++ = '0' + (p & 15);
 292         else
 293             *s++ = 'a' + (p & 15) - 10;
 294         seen |= 1 << (p & 15);
 295         p >>= 4;
 296     }
 297     if (seen != (1 << width) - 1) {
 298         *s++ = '?';
 299         *s++ = '!';
 300     }
 301     return lcdf::String(buf, s);
 302 }
 303
 304
 305 template <typename T> struct has_permuter_type {
 306     template <typename C> static char test(typename C::permuter_type *);
 307     template <typename> static int test(...);
 308     static constexpr bool value = sizeof(test<T>(0)) == 1;
 309 };
 310
 311 template <typename T, bool HP = has_permuter_type<T>::value> struct key_permuter {};
 312 template <typename T> struct key_permuter<T, true> {
 313     typedef typename T::permuter_type type;
 314     static type permutation(const T& n) {
 315         return n.permutation();
 316     }
 317 };
 318 template <typename T> struct key_permuter<T, false> {
 319     typedef identity_kpermuter type;
 320     static type permutation(const T& n) {
 321         return identity_kpermuter(n.size());
 322     }
 323 };
 324
 325 #endif