silo/masstree/stringbag.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 STRINGBAG_HH
  17 #define STRINGBAG_HH 1
  18 #include "compiler.hh"
  19 #include "string_slice.hh"
  20
  21 /** @brief String collection used for Masstree key suffixes.
  22
  23     A stringbag is a compact collection of up to W strings, where W is a
  24     parameter called the <em>bag width</em>. These strings are stored
  25     in contiguously allocated memory.
  26
  27     Stringbag component strings support
  28     string_slice<uintptr_t>::equals_sloppy() without memory errors.
  29
  30     The template parameter T is the offset type. This type determines the
  31     maximum supported capacity of a stringbag. Smaller types have lower
  32     overhead, but support smaller bags.
  33
  34     Stringbags favor compactness over usability. The bag width W is an
  35     important parameter, but you can't recover W from the stringbag itself;
  36     you'll need to store that externally. Stringbags cannot be allocated
  37     conventionally. You must manage stringbag memory yourself:
  38     allocate an array of characters for the stringbag, then use placement
  39     new to construct the stringbag on that memory. Stringbag has a
  40     trivial destructor. */
  41 template <typename T>
  42 class stringbag {
  43  public:
  44     /** @brief Type of offsets. */
  45     typedef T offset_type;
  46     typedef string_slice<uintptr_t> slice_type;
  47
  48  private:
  49     struct info_type {
  50         offset_type pos;
  51         offset_type len;
  52         info_type(unsigned p, unsigned l)
  53             : pos(p), len(l) {
  54         }
  55     };
  56
  57  public:
  58     /** @brief Return the maximum allowed capacity of a stringbag. */
  59     static constexpr unsigned max_size() {
  60         return ((unsigned) (offset_type) -1) + 1;
  61     }
  62     /** @brief Return the overhead for a stringbag of width @a width.
  63
  64         This is the number of bytes allocated for overhead. */
  65     static constexpr size_t overhead(int width) {
  66         return sizeof(stringbag<T>) + width * sizeof(info_type);
  67     }
  68     /** @brief Return a capacity that can definitely contain a stringbag.
  69         @param width number of strings in bag
  70         @param len total number of bytes in bag's strings */
  71     static constexpr size_t safe_size(int width, unsigned len) {
  72         return overhead(width) + len + slice_type::size - 1;
  73     }
  74
  75     /** @brief Construct an empty stringbag.
  76         @param width Number of strings in the bag
  77         @param capacity Number of bytes allocated for the bag
  78         @pre @a capacity > overhead(width)
  79         @pre @a capacity <= max_offset
  80
  81         Stringbags should not be constructed on the stack or by a direct call
  82         to new. Allocate space for a stringbag, then call the constructor on
  83         that space using placement new. @a capacity must be no bigger than
  84         the allocated space. */
  85     stringbag(int width, size_t capacity) {
  86         size_t firstpos = overhead(width);
  87         assert(capacity >= firstpos && capacity <= max_size());
  88         size_ = firstpos;
  89         capacity_ = capacity - 1;
  90         memset(info_, 0, sizeof(info_type) * width);
  91     }
  92
  93     /** @brief Return the capacity used to construct this bag. */
  94     size_t capacity() const {
  95         return capacity_ + 1;
  96     }
  97     /** @brief Return the number of bytes used so far (including overhead). */
  98     size_t used_capacity() const {
  99         return size_;
 100     }
 101
 102     /** @brief Return the string at position @a p.
 103         @pre @a p >= 0 && @a p < bag width */
 104     lcdf::Str operator[](int p) const {
 105         info_type info = info_[p];
 106         return lcdf::Str(s_ + info.pos, info.len);
 107     }
 108     /** @brief Return the string at position @a p.
 109         @pre @a p >= 0 && @a p < bag width */
 110     lcdf::Str get(int p) const {
 111         info_type info = info_[p];
 112         return lcdf::Str(s_ + info.pos, info.len);
 113     }
 114
 115     /** @brief Assign the string at position @a p to @a s.
 116         @param p position
 117         @param s string
 118         @param len length of string
 119         @return true if the assignment succeeded, false if it failed
 120            (because the stringbag is out of capacity)
 121         @pre @a p >= 0 && @a p < bag width */
 122     bool assign(int p, const char *s, int len) {
 123         unsigned pos, mylen = info_[p].len;
 124         if (mylen >= (unsigned) len)
 125             pos = info_[p].pos;
 126         else if (size_ + (unsigned) std::max(len, slice_type::size)
 127                    <= capacity()) {
 128             pos = size_;
 129             size_ += len;
 130         } else
 131             return false;
 132         memcpy(s_ + pos, s, len);
 133         info_[p] = info_type(pos, len);
 134         return true;
 135     }
 136     /** @override */
 137     bool assign(int p, lcdf::Str s) {
 138         return assign(p, s.s, s.len);
 139     }
 140
 141     /** @brief Print a representation of the stringbag to @a f. */
 142     void print(int width, FILE *f, const char *prefix, int indent) {
 143         fprintf(f, "%s%*s%p (%d:)%d:%d...\n", prefix, indent, "",
 144                 this, (int) overhead(width), size_, capacity());
 145         for (int i = 0; i < width; ++i)
 146             if (info_[i].len)
 147                 fprintf(f, "%s%*s  #%x %u:%u %.*s\n", prefix, indent, "",
 148                         i, info_[i].pos, info_[i].len, std::min(info_[i].len, 40U), s_ + info_[i].pos);
 149     }
 150
 151   private:
 152     union {
 153         struct {
 154             offset_type size_;
 155             offset_type capacity_;
 156             info_type info_[0];
 157         };
 158         char s_[0];
 159     };
 160 };
 161
 162 #endif