From a247c8d3ff52e65c097170614ecb0639edebc569 Mon Sep 17 00:00:00 2001 From: Jordan DeLong Date: Thu, 16 Jan 2014 15:28:45 -0800 Subject: [PATCH] Remove some files that should have been deleted in earlier commits Summary: Our script wasn't picking up removed files. --- folly/Histogram-inl.h | 269 ---- folly/Histogram.h | 408 ------ folly/LICENSE | 177 --- folly/README | 55 - folly/SpookyHash.cpp | 374 ------ folly/SpookyHash.h | 304 ----- folly/StlAllocator.h | 267 ---- folly/eventfd.h | 79 -- folly/experimental/File-inl.h | 56 - folly/experimental/File.cpp | 46 - folly/experimental/File.h | 90 -- .../exception_tracer/StackTrace.c | 146 --- folly/experimental/io/Cursor.h | 480 ------- folly/experimental/io/IOBuf.cpp | 638 ---------- folly/experimental/io/IOBuf.h | 1119 ----------------- folly/experimental/io/IOBufQueue.cpp | 268 ---- folly/experimental/io/IOBufQueue.h | 234 ---- folly/experimental/io/Stream-inl.h | 98 -- folly/experimental/io/Stream.cpp | 98 -- folly/experimental/io/Stream.h | 226 ---- folly/experimental/io/TypedIOBuf.h | 206 --- .../experimental/io/test/IOBufCursorTest.cpp | 415 ------ folly/experimental/io/test/IOBufQueueTest.cpp | 274 ---- folly/experimental/io/test/IOBufTest.cpp | 759 ----------- .../experimental/io/test/NetworkBenchmark.cpp | 172 --- folly/experimental/io/test/StreamTest.cpp | 117 -- .../symbolizer/SymbolizerTest.cpp | 36 - folly/experimental/test/FileTest.cpp | 86 -- folly/test/EventFDTest.cpp | 73 -- folly/test/FBStringLibstdcxxStdexceptTest.cpp | 24 - folly/test/SpookyHashTest.cpp | 530 -------- 31 files changed, 8124 deletions(-) delete mode 100644 folly/Histogram-inl.h delete mode 100644 folly/Histogram.h delete mode 100644 folly/LICENSE delete mode 100644 folly/README delete mode 100644 folly/SpookyHash.cpp delete mode 100644 folly/SpookyHash.h delete mode 100644 folly/StlAllocator.h delete mode 100644 folly/eventfd.h delete mode 100644 folly/experimental/File-inl.h delete mode 100644 folly/experimental/File.cpp delete mode 100644 folly/experimental/File.h delete mode 100644 folly/experimental/exception_tracer/StackTrace.c delete mode 100644 folly/experimental/io/Cursor.h delete mode 100644 folly/experimental/io/IOBuf.cpp delete mode 100644 folly/experimental/io/IOBuf.h delete mode 100644 folly/experimental/io/IOBufQueue.cpp delete mode 100644 folly/experimental/io/IOBufQueue.h delete mode 100644 folly/experimental/io/Stream-inl.h delete mode 100644 folly/experimental/io/Stream.cpp delete mode 100644 folly/experimental/io/Stream.h delete mode 100644 folly/experimental/io/TypedIOBuf.h delete mode 100644 folly/experimental/io/test/IOBufCursorTest.cpp delete mode 100644 folly/experimental/io/test/IOBufQueueTest.cpp delete mode 100644 folly/experimental/io/test/IOBufTest.cpp delete mode 100644 folly/experimental/io/test/NetworkBenchmark.cpp delete mode 100644 folly/experimental/io/test/StreamTest.cpp delete mode 100644 folly/experimental/symbolizer/SymbolizerTest.cpp delete mode 100644 folly/experimental/test/FileTest.cpp delete mode 100644 folly/test/EventFDTest.cpp delete mode 100644 folly/test/FBStringLibstdcxxStdexceptTest.cpp delete mode 100644 folly/test/SpookyHashTest.cpp diff --git a/folly/Histogram-inl.h b/folly/Histogram-inl.h deleted file mode 100644 index 42ff2989..00000000 --- a/folly/Histogram-inl.h +++ /dev/null @@ -1,269 +0,0 @@ -/* - * Copyright 2013 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef FOLLY_HISTOGRAM_INL_H_ -#define FOLLY_HISTOGRAM_INL_H_ - -#include "folly/Conv.h" - -#include - -namespace folly { - -namespace detail { - -template -HistogramBuckets::HistogramBuckets(ValueType bucketSize, - ValueType min, - ValueType max, - const BucketType& defaultBucket) - : bucketSize_(bucketSize), - min_(min), - max_(max) { - CHECK_GT(bucketSize_, ValueType(0)); - CHECK_LT(min_, max_); - - unsigned int numBuckets = (max - min) / bucketSize; - // Round up if the bucket size does not fit evenly - if (numBuckets * bucketSize < max - min) { - ++numBuckets; - } - // Add 2 for the extra 'below min' and 'above max' buckets - numBuckets += 2; - buckets_.assign(numBuckets, defaultBucket); -} - -template -unsigned int HistogramBuckets::getBucketIdx( - ValueType value) const { - if (value < min_) { - return 0; - } else if (value >= max_) { - return buckets_.size() - 1; - } else { - // the 1 is the below_min bucket - return ((value - min_) / bucketSize_) + 1; - } -} - -template -template -unsigned int HistogramBuckets::getPercentileBucketIdx( - double pct, - CountFn countFromBucket, - double* lowPct, double* highPct) const { - CHECK_GE(pct, 0.0); - CHECK_LE(pct, 1.0); - - unsigned int numBuckets = buckets_.size(); - - // Compute the counts in each bucket - std::vector counts(numBuckets); - uint64_t totalCount = 0; - for (unsigned int n = 0; n < numBuckets; ++n) { - uint64_t bucketCount = - countFromBucket(const_cast(buckets_[n])); - counts[n] = bucketCount; - totalCount += bucketCount; - } - - // If there are no elements, just return the lowest bucket. - // Note that we return bucket 1, which is the first bucket in the - // histogram range; bucket 0 is for all values below min_. - if (totalCount == 0) { - // Set lowPct and highPct both to 0. - // getPercentileEstimate() will recognize this to mean that the histogram - // is empty. - if (lowPct) { - *lowPct = 0.0; - } - if (highPct) { - *highPct = 0.0; - } - return 1; - } - - // Loop through all the buckets, keeping track of each bucket's - // percentile range: [0,10], [10,17], [17,45], etc. When we find a range - // that includes our desired percentile, we return that bucket index. - double prevPct = 0.0; - double curPct = 0.0; - uint64_t curCount = 0; - unsigned int idx; - for (idx = 0; idx < numBuckets; ++idx) { - if (counts[idx] == 0) { - // skip empty buckets - continue; - } - - prevPct = curPct; - curCount += counts[idx]; - curPct = static_cast(curCount) / totalCount; - if (pct <= curPct) { - // This is the desired bucket - break; - } - } - - if (lowPct) { - *lowPct = prevPct; - } - if (highPct) { - *highPct = curPct; - } - return idx; -} - -template -template -T HistogramBuckets::getPercentileEstimate( - double pct, - CountFn countFromBucket, - AvgFn avgFromBucket) const { - - // Find the bucket where this percentile falls - double lowPct; - double highPct; - unsigned int bucketIdx = getPercentileBucketIdx(pct, countFromBucket, - &lowPct, &highPct); - if (lowPct == 0.0 && highPct == 0.0) { - // Invalid range -- the buckets must all be empty - // Return the default value for ValueType. - return ValueType(); - } - if (lowPct == highPct) { - // Unlikely to have exact equality, - // but just return the bucket average in this case. - // We handle this here to avoid division by 0 below. - return avgFromBucket(buckets_[bucketIdx]); - } - - CHECK_GE(pct, lowPct); - CHECK_LE(pct, highPct); - CHECK_LT(lowPct, highPct); - - // Compute information about this bucket - ValueType avg = avgFromBucket(buckets_[bucketIdx]); - ValueType low; - ValueType high; - if (bucketIdx == 0) { - if (avg > min_) { - // This normally shouldn't happen. This bucket is only supposed to track - // values less than min_. Most likely this means that integer overflow - // occurred, and the code in avgFromBucket() returned a huge value - // instead of a small one. Just return the minimum possible value for - // now. - // - // (Note that if the counter keeps being decremented, eventually it will - // wrap and become small enough that we won't detect this any more, and - // we will return bogus information.) - LOG(ERROR) << "invalid average value in histogram minimum bucket: " << - avg << " > " << min_ << ": possible integer overflow?"; - return getBucketMin(bucketIdx); - } - // For the below-min bucket, just assume the lowest value ever seen is - // twice as far away from min_ as avg. - high = min_; - low = high - (2 * (high - avg)); - // Adjust low in case it wrapped - if (low > avg) { - low = std::numeric_limits::min(); - } - } else if (bucketIdx == buckets_.size() - 1) { - if (avg < max_) { - // Most likely this means integer overflow occurred. See the comments - // above in the minimum case. - LOG(ERROR) << "invalid average value in histogram maximum bucket: " << - avg << " < " << max_ << ": possible integer overflow?"; - return getBucketMax(bucketIdx); - } - // Similarly for the above-max bucket, assume the highest value ever seen - // is twice as far away from max_ as avg. - low = max_; - high = low + (2 * (avg - low)); - // Adjust high in case it wrapped - if (high < avg) { - high = std::numeric_limits::max(); - } - } else { - low = getBucketMin(bucketIdx); - high = getBucketMax(bucketIdx); - if (avg < low || avg > high) { - // Most likely this means an integer overflow occurred. - // See the comments above. Return the midpoint between low and high - // as a best guess, since avg is meaningless. - LOG(ERROR) << "invalid average value in histogram bucket: " << - avg << " not in range [" << low << ", " << high << - "]: possible integer overflow?"; - return (low + high) / 2; - } - } - - // Since we know the average value in this bucket, we can do slightly better - // than just assuming the data points in this bucket are uniformly - // distributed between low and high. - // - // Assume that the median value in this bucket is the same as the average - // value. - double medianPct = (lowPct + highPct) / 2.0; - if (pct < medianPct) { - // Assume that the data points lower than the median of this bucket - // are uniformly distributed between low and avg - double pctThroughSection = (pct - lowPct) / (medianPct - lowPct); - return low + ((avg - low) * pctThroughSection); - } else { - // Assume that the data points greater than the median of this bucket - // are uniformly distributed between avg and high - double pctThroughSection = (pct - medianPct) / (highPct - medianPct); - return avg + ((high - avg) * pctThroughSection); - } -} - -} // detail - - -template -std::string Histogram::debugString() const { - std::string ret = folly::to( - "num buckets: ", buckets_.getNumBuckets(), - ", bucketSize: ", buckets_.getBucketSize(), - ", min: ", buckets_.getMin(), ", max: ", buckets_.getMax(), "\n"); - - for (unsigned int i = 0; i < buckets_.getNumBuckets(); ++i) { - folly::toAppend(" ", buckets_.getBucketMin(i), ": ", - buckets_.getByIndex(i).count, "\n", - &ret); - } - - return ret; -} - -template -void Histogram::toTSV(std::ostream& out, bool skipEmptyBuckets) const { - for (unsigned int i = 0; i < buckets_.getNumBuckets(); ++i) { - // Do not output empty buckets in order to reduce data file size. - if (skipEmptyBuckets && getBucketByIndex(i).count == 0) { - continue; - } - const auto& bucket = getBucketByIndex(i); - out << getBucketMin(i) << '\t' << getBucketMax(i) << '\t' - << bucket.count << '\t' << bucket.sum << '\n'; - } -} - -} // folly - -#endif // FOLLY_HISTOGRAM_INL_H_ diff --git a/folly/Histogram.h b/folly/Histogram.h deleted file mode 100644 index 3eb34f77..00000000 --- a/folly/Histogram.h +++ /dev/null @@ -1,408 +0,0 @@ -/* - * Copyright 2013 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef FOLLY_HISTOGRAM_H_ -#define FOLLY_HISTOGRAM_H_ - -#include -#include -#include -#include -#include -#include - -#include "folly/detail/Stats.h" - -namespace folly { - -namespace detail { - -/* - * A helper class to manage a set of histogram buckets. - */ -template -class HistogramBuckets { - public: - typedef T ValueType; - typedef BucketT BucketType; - - /* - * Create a set of histogram buckets. - * - * One bucket will be created for each bucketSize interval of values within - * the specified range. Additionally, one bucket will be created to track - * all values that fall below the specified minimum, and one bucket will be - * created for all values above the specified maximum. - * - * If (max - min) is not a multiple of bucketSize, the last bucket will cover - * a smaller range of values than the other buckets. - * - * (max - min) must be larger than or equal to bucketSize. - */ - HistogramBuckets(ValueType bucketSize, ValueType min, ValueType max, - const BucketType& defaultBucket); - - /* Returns the bucket size of each bucket in the histogram. */ - ValueType getBucketSize() const { - return bucketSize_; - } - - /* Returns the min value at which bucketing begins. */ - ValueType getMin() const { - return min_; - } - - /* Returns the max value at which bucketing ends. */ - ValueType getMax() const { - return max_; - } - - /* - * Returns the number of buckets. - * - * This includes the total number of buckets for the [min, max) range, - * plus 2 extra buckets, one for handling values less than min, and one for - * values greater than max. - */ - unsigned int getNumBuckets() const { - return buckets_.size(); - } - - /* Returns the bucket index into which the given value would fall. */ - unsigned int getBucketIdx(ValueType value) const; - - /* Returns the bucket for the specified value */ - BucketType& getByValue(ValueType value) { - return buckets_[getBucketIdx(value)]; - } - - /* Returns the bucket for the specified value */ - const BucketType& getByValue(ValueType value) const { - return buckets_[getBucketIdx(value)]; - } - - /* - * Returns the bucket at the specified index. - * - * Note that index 0 is the bucket for all values less than the specified - * minimum. Index 1 is the first bucket in the specified bucket range. - */ - BucketType& getByIndex(unsigned int idx) { - return buckets_[idx]; - } - - /* Returns the bucket at the specified index. */ - const BucketType& getByIndex(unsigned int idx) const { - return buckets_[idx]; - } - - /* - * Returns the minimum threshold for the bucket at the given index. - * - * The bucket at the specified index will store values in the range - * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall - * max is smaller than bucketMin + bucketSize. - */ - ValueType getBucketMin(unsigned int idx) const { - if (idx == 0) { - return std::numeric_limits::min(); - } - if (idx == buckets_.size() - 1) { - return max_; - } - - return min_ + ((idx - 1) * bucketSize_); - } - - /* - * Returns the maximum threshold for the bucket at the given index. - * - * The bucket at the specified index will store values in the range - * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall - * max is smaller than bucketMin + bucketSize. - */ - ValueType getBucketMax(unsigned int idx) const { - if (idx == buckets_.size() - 1) { - return std::numeric_limits::max(); - } - - return min_ + (idx * bucketSize_); - } - - /** - * Determine which bucket the specified percentile falls into. - * - * Looks for the bucket that contains the Nth percentile data point. - * - * @param pct The desired percentile to find, as a value from 0.0 to 1.0. - * @param countFn A function that takes a const BucketType&, and returns the - * number of values in that bucket. - * @param lowPct The lowest percentile stored in the selected bucket will be - * returned via this parameter. - * @param highPct The highest percentile stored in the selected bucket will - * be returned via this parameter. - * - * @return Returns the index of the bucket that contains the Nth percentile - * data point. - */ - template - unsigned int getPercentileBucketIdx(double pct, - CountFn countFromBucket, - double* lowPct = NULL, - double* highPct = NULL) const; - - /** - * Estimate the value at the specified percentile. - * - * @param pct The desired percentile to find, as a value from 0.0 to 1.0. - * @param countFn A function that takes a const BucketType&, and returns the - * number of values in that bucket. - * @param avgFn A function that takes a const BucketType&, and returns the - * average of all the values in that bucket. - * - * @return Returns an estimate for N, where N is the number where exactly pct - * percentage of the data points in the histogram are less than N. - */ - template - ValueType getPercentileEstimate(double pct, - CountFn countFromBucket, - AvgFn avgFromBucket) const; - - /* - * Iterator access to the buckets. - * - * Note that the first bucket is for all values less than min, and the last - * bucket is for all values greater than max. The buckets tracking values in - * the [min, max) actually start at the second bucket. - */ - typename std::vector::const_iterator begin() const { - return buckets_.begin(); - } - typename std::vector::iterator begin() { - return buckets_.begin(); - } - typename std::vector::const_iterator end() const { - return buckets_.end(); - } - typename std::vector::iterator end() { - return buckets_.end(); - } - - private: - const ValueType bucketSize_; - const ValueType min_; - const ValueType max_; - std::vector buckets_; -}; - -} // detail - - -/* - * A basic histogram class. - * - * Groups data points into equally-sized buckets, and stores the overall sum of - * the data points in each bucket, as well as the number of data points in the - * bucket. - * - * The caller must specify the minimum and maximum data points to expect ahead - * of time, as well as the bucket width. - */ -template -class Histogram { - public: - typedef T ValueType; - typedef detail::Bucket Bucket; - - Histogram(ValueType bucketSize, ValueType min, ValueType max) - : buckets_(bucketSize, min, max, Bucket()) {} - - /* Add a data point to the histogram */ - void addValue(ValueType value) { - Bucket& bucket = buckets_.getByValue(value); - // TODO: It would be nice to handle overflow here. - bucket.sum += value; - bucket.count += 1; - } - - /* - * Remove a data point to the histogram - * - * Note that this method does not actually verify that this exact data point - * had previously been added to the histogram; it merely subtracts the - * requested value from the appropriate bucket's sum. - */ - void removeValue(ValueType value) { - Bucket& bucket = buckets_.getByValue(value); - // TODO: It would be nice to handle overflow here. - bucket.sum -= value; - bucket.count -= 1; - } - - /* Remove all data points from the histogram */ - void clear() { - for (int i = 0; i < buckets_.getNumBuckets(); i++) { - buckets_.getByIndex(i).clear(); - } - } - - /* Merge two histogram data together */ - void merge(Histogram &hist) { - // the two histogram bucket definitions must match to support - // a merge. - if (getBucketSize() != hist.getBucketSize() || - getMin() != hist.getMin() || - getMax() != hist.getMax() || - getNumBuckets() != hist.getNumBuckets() ) { - throw std::invalid_argument("Cannot merge from input histogram."); - } - - for (int i = 0; i < buckets_.getNumBuckets(); i++) { - buckets_.getByIndex(i) += hist.buckets_.getByIndex(i); - } - } - - /* Copy bucket values from another histogram */ - void copy(Histogram &hist) { - // the two histogram bucket definition must match - if (getBucketSize() != hist.getBucketSize() || - getMin() != hist.getMin() || - getMax() != hist.getMax() || - getNumBuckets() != hist.getNumBuckets() ) { - throw std::invalid_argument("Cannot copy from input histogram."); - } - - for (int i = 0; i < buckets_.getNumBuckets(); i++) { - buckets_.getByIndex(i) = hist.buckets_.getByIndex(i); - } - } - - /* Returns the bucket size of each bucket in the histogram. */ - ValueType getBucketSize() const { - return buckets_.getBucketSize(); - } - /* Returns the min value at which bucketing begins. */ - ValueType getMin() const { - return buckets_.getMin(); - } - /* Returns the max value at which bucketing ends. */ - ValueType getMax() const { - return buckets_.getMax(); - } - /* Returns the number of buckets */ - unsigned int getNumBuckets() const { - return buckets_.getNumBuckets(); - } - - /* Returns the specified bucket (for reading only!) */ - const Bucket& getBucketByIndex(int idx) const { - return buckets_.getByIndex(idx); - } - - /* - * Returns the minimum threshold for the bucket at the given index. - * - * The bucket at the specified index will store values in the range - * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall - * max is smaller than bucketMin + bucketSize. - */ - ValueType getBucketMin(unsigned int idx) const { - return buckets_.getBucketMin(idx); - } - - /* - * Returns the maximum threshold for the bucket at the given index. - * - * The bucket at the specified index will store values in the range - * [bucketMin, bucketMin + bucketSize), or [bucketMin, max), if the overall - * max is smaller than bucketMin + bucketSize. - */ - ValueType getBucketMax(unsigned int idx) const { - return buckets_.getBucketMax(idx); - } - - /* - * Get the bucket that the specified percentile falls into - * - * The lowest and highest percentile data points in returned bucket will be - * returned in the lowPct and highPct arguments, if they are non-NULL. - */ - unsigned int getPercentileBucketIdx(double pct, - double* lowPct = NULL, - double* highPct = NULL) const { - // We unfortunately can't use lambdas here yet; - // Some users of this code are still built with gcc-4.4. - CountFromBucket countFn; - return buckets_.getPercentileBucketIdx(pct, countFn, lowPct, highPct); - } - - /** - * Estimate the value at the specified percentile. - * - * @param pct The desired percentile to find, as a value from 0.0 to 1.0. - * - * @return Returns an estimate for N, where N is the number where exactly pct - * percentage of the data points in the histogram are less than N. - */ - ValueType getPercentileEstimate(double pct) const { - CountFromBucket countFn; - AvgFromBucket avgFn; - return buckets_.getPercentileEstimate(pct, countFn, avgFn); - } - - /* - * Get a human-readable string describing the histogram contents - */ - std::string debugString() const; - - /* - * Write the histogram contents in tab-separated values (TSV) format. - * Format is "min max count sum". - */ - void toTSV(std::ostream& out, bool skipEmptyBuckets = true) const; - - private: - struct CountFromBucket { - uint64_t operator()(const Bucket& bucket) const { - return bucket.count; - } - }; - struct AvgFromBucket { - ValueType operator()(const Bucket& bucket) const { - if (bucket.count == 0) { - return ValueType(0); - } - // Cast bucket.count to a signed integer type. This ensures that we - // perform division properly here: If bucket.sum is a signed integer - // type but we divide by an unsigned number, unsigned division will be - // performed and bucket.sum will be converted to unsigned first. - // If bucket.sum is unsigned, the code will still do unsigned division - // correctly. - // - // The only downside is if bucket.count is large enough to be negative - // when treated as signed. That should be extremely unlikely, though. - return bucket.sum / static_cast(bucket.count); - } - }; - - detail::HistogramBuckets buckets_; -}; - -} // folly - -#include "folly/Histogram-inl.h" - -#endif // FOLLY_HISTOGRAM_H_ diff --git a/folly/LICENSE b/folly/LICENSE deleted file mode 100644 index f433b1a5..00000000 --- a/folly/LICENSE +++ /dev/null @@ -1,177 +0,0 @@ - - Apache License - Version 2.0, January 2004 - http://www.apache.org/licenses/ - - TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION - - 1. Definitions. - - "License" shall mean the terms and conditions for use, reproduction, - and distribution as defined by Sections 1 through 9 of this document. - - "Licensor" shall mean the copyright owner or entity authorized by - the copyright owner that is granting the License. - - "Legal Entity" shall mean the union of the acting entity and all - other entities that control, are controlled by, or are under common - control with that entity. For the purposes of this definition, - "control" means (i) the power, direct or indirect, to cause the - direction or management of such entity, whether by contract or - otherwise, or (ii) ownership of fifty percent (50%) or more of the - outstanding shares, or (iii) beneficial ownership of such entity. - - "You" (or "Your") shall mean an individual or Legal Entity - exercising permissions granted by this License. - - "Source" form shall mean the preferred form for making modifications, - including but not limited to software source code, documentation - source, and configuration files. - - "Object" form shall mean any form resulting from mechanical - transformation or translation of a Source form, including but - not limited to compiled object code, generated documentation, - and conversions to other media types. - - "Work" shall mean the work of authorship, whether in Source or - Object form, made available under the License, as indicated by a - copyright notice that is included in or attached to the work - (an example is provided in the Appendix below). - - "Derivative Works" shall mean any work, whether in Source or Object - form, that is based on (or derived from) the Work and for which the - editorial revisions, annotations, elaborations, or other modifications - represent, as a whole, an original work of authorship. For the purposes - of this License, Derivative Works shall not include works that remain - separable from, or merely link (or bind by name) to the interfaces of, - the Work and Derivative Works thereof. - - "Contribution" shall mean any work of authorship, including - the original version of the Work and any modifications or additions - to that Work or Derivative Works thereof, that is intentionally - submitted to Licensor for inclusion in the Work by the copyright owner - or by an individual or Legal Entity authorized to submit on behalf of - the copyright owner. For the purposes of this definition, "submitted" - means any form of electronic, verbal, or written communication sent - to the Licensor or its representatives, including but not limited to - communication on electronic mailing lists, source code control systems, - and issue tracking systems that are managed by, or on behalf of, the - Licensor for the purpose of discussing and improving the Work, but - excluding communication that is conspicuously marked or otherwise - designated in writing by the copyright owner as "Not a Contribution." - - "Contributor" shall mean Licensor and any individual or Legal Entity - on behalf of whom a Contribution has been received by Licensor and - subsequently incorporated within the Work. - - 2. Grant of Copyright License. Subject to the terms and conditions of - this License, each Contributor hereby grants to You a perpetual, - worldwide, non-exclusive, no-charge, royalty-free, irrevocable - copyright license to reproduce, prepare Derivative Works of, - publicly display, publicly perform, sublicense, and distribute the - Work and such Derivative Works in Source or Object form. - - 3. Grant of Patent License. Subject to the terms and conditions of - this License, each Contributor hereby grants to You a perpetual, - worldwide, non-exclusive, no-charge, royalty-free, irrevocable - (except as stated in this section) patent license to make, have made, - use, offer to sell, sell, import, and otherwise transfer the Work, - where such license applies only to those patent claims licensable - by such Contributor that are necessarily infringed by their - Contribution(s) alone or by combination of their Contribution(s) - with the Work to which such Contribution(s) was submitted. If You - institute patent litigation against any entity (including a - cross-claim or counterclaim in a lawsuit) alleging that the Work - or a Contribution incorporated within the Work constitutes direct - or contributory patent infringement, then any patent licenses - granted to You under this License for that Work shall terminate - as of the date such litigation is filed. - - 4. Redistribution. You may reproduce and distribute copies of the - Work or Derivative Works thereof in any medium, with or without - modifications, and in Source or Object form, provided that You - meet the following conditions: - - (a) You must give any other recipients of the Work or - Derivative Works a copy of this License; and - - (b) You must cause any modified files to carry prominent notices - stating that You changed the files; and - - (c) You must retain, in the Source form of any Derivative Works - that You distribute, all copyright, patent, trademark, and - attribution notices from the Source form of the Work, - excluding those notices that do not pertain to any part of - the Derivative Works; and - - (d) If the Work includes a "NOTICE" text file as part of its - distribution, then any Derivative Works that You distribute must - include a readable copy of the attribution notices contained - within such NOTICE file, excluding those notices that do not - pertain to any part of the Derivative Works, in at least one - of the following places: within a NOTICE text file distributed - as part of the Derivative Works; within the Source form or - documentation, if provided along with the Derivative Works; or, - within a display generated by the Derivative Works, if and - wherever such third-party notices normally appear. The contents - of the NOTICE file are for informational purposes only and - do not modify the License. You may add Your own attribution - notices within Derivative Works that You distribute, alongside - or as an addendum to the NOTICE text from the Work, provided - that such additional attribution notices cannot be construed - as modifying the License. - - You may add Your own copyright statement to Your modifications and - may provide additional or different license terms and conditions - for use, reproduction, or distribution of Your modifications, or - for any such Derivative Works as a whole, provided Your use, - reproduction, and distribution of the Work otherwise complies with - the conditions stated in this License. - - 5. Submission of Contributions. Unless You explicitly state otherwise, - any Contribution intentionally submitted for inclusion in the Work - by You to the Licensor shall be under the terms and conditions of - this License, without any additional terms or conditions. - Notwithstanding the above, nothing herein shall supersede or modify - the terms of any separate license agreement you may have executed - with Licensor regarding such Contributions. - - 6. Trademarks. This License does not grant permission to use the trade - names, trademarks, service marks, or product names of the Licensor, - except as required for reasonable and customary use in describing the - origin of the Work and reproducing the content of the NOTICE file. - - 7. Disclaimer of Warranty. Unless required by applicable law or - agreed to in writing, Licensor provides the Work (and each - Contributor provides its Contributions) on an "AS IS" BASIS, - WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or - implied, including, without limitation, any warranties or conditions - of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A - PARTICULAR PURPOSE. You are solely responsible for determining the - appropriateness of using or redistributing the Work and assume any - risks associated with Your exercise of permissions under this License. - - 8. Limitation of Liability. In no event and under no legal theory, - whether in tort (including negligence), contract, or otherwise, - unless required by applicable law (such as deliberate and grossly - negligent acts) or agreed to in writing, shall any Contributor be - liable to You for damages, including any direct, indirect, special, - incidental, or consequential damages of any character arising as a - result of this License or out of the use or inability to use the - Work (including but not limited to damages for loss of goodwill, - work stoppage, computer failure or malfunction, or any and all - other commercial damages or losses), even if such Contributor - has been advised of the possibility of such damages. - - 9. Accepting Warranty or Additional Liability. While redistributing - the Work or Derivative Works thereof, You may choose to offer, - and charge a fee for, acceptance of support, warranty, indemnity, - or other liability obligations and/or rights consistent with this - License. However, in accepting such obligations, You may act only - on Your own behalf and on Your sole responsibility, not on behalf - of any other Contributor, and only if You agree to indemnify, - defend, and hold each Contributor harmless for any liability - incurred by, or claims asserted against, such Contributor by reason - of your accepting any such warranty or additional liability. - - END OF TERMS AND CONDITIONS diff --git a/folly/README b/folly/README deleted file mode 100644 index 766078b3..00000000 --- a/folly/README +++ /dev/null @@ -1,55 +0,0 @@ -Folly: Facebook Open-source LibrarY ------------------------------------ - -Folly is an open-source C++ library developed and used at Facebook. - -Dependencies ------------- - -- double-conversion (http://code.google.com/p/double-conversion/) - - By default, the build tooling for double-conversion does not build - any libraries, which folly requires. To build the necessary libraries - copy folly/SConstruct.double-conversion to your double-conversion - source directory before building: - - [double-conversion/] scons -f SConstruct.double-conversion - - Then set CPPFLAGS/LDFLAGS so that folly can find your double-conversion - build: - - [folly/] LDFLAGS=-L/ CPPFLAGS=-I/src/ - configure ... - -- googletest (Google C++ Testing Framework) - - Grab gtest 1.6.0 from: - http://googletest.googlecode.com/files/gtest-1.6.0.zip - - Unzip it inside of the test/ subdirectory. - -- additional platform specific dependencies: - - Ubuntu 12.04 64-bit - - g++ - - automake - - autoconf - - libtool - - libboost1.46-all-dev - - libgoogle-glog-dev - This package has been removed from 12.04 -- use the one from 11.10 - - gflags (packages need to be downloaded from below) - http://gflags.googlecode.com/files/libgflags-dev_2.0-1_amd64.deb - http://gflags.googlecode.com/files/libgflags0_2.0-1_amd64.deb - - scons (for double-conversion) - - Fedora 17 64-bit - - gcc - - gcc-c++ - - autoconf - - automake - - boost-devel - - libtool - - glog-devel - - gflags-devel - - scons (for double-conversion) diff --git a/folly/SpookyHash.cpp b/folly/SpookyHash.cpp deleted file mode 100644 index a439b9d2..00000000 --- a/folly/SpookyHash.cpp +++ /dev/null @@ -1,374 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -// Spooky Hash -// A 128-bit noncryptographic hash, for checksums and table lookup -// By Bob Jenkins. Public domain. -// Oct 31 2010: published framework, disclaimer ShortHash isn't right -// Nov 7 2010: disabled ShortHash -// Oct 31 2011: replace End, ShortMix, ShortEnd, enable ShortHash again -// April 10 2012: buffer overflow on platforms without unaligned reads -// July 12 2012: was passing out variables in final to in/out in short -// July 30 2012: I reintroduced the buffer overflow - -#include "folly/SpookyHash.h" - -#include - -#define ALLOW_UNALIGNED_READS 1 - -namespace folly { -namespace hash { - -// -// short hash ... it could be used on any message, -// but it's used by Spooky just for short messages. -// -void SpookyHash::Short( - const void *message, - size_t length, - uint64_t *hash1, - uint64_t *hash2) -{ - uint64_t buf[2*sc_numVars]; - union - { - const uint8_t *p8; - uint32_t *p32; - uint64_t *p64; - size_t i; - } u; - - u.p8 = (const uint8_t *)message; - - if (!ALLOW_UNALIGNED_READS && (u.i & 0x7)) - { - memcpy(buf, message, length); - u.p64 = buf; - } - - size_t remainder = length%32; - uint64_t a=*hash1; - uint64_t b=*hash2; - uint64_t c=sc_const; - uint64_t d=sc_const; - - if (length > 15) - { - const uint64_t *end = u.p64 + (length/32)*4; - - // handle all complete sets of 32 bytes - for (; u.p64 < end; u.p64 += 4) - { - c += u.p64[0]; - d += u.p64[1]; - ShortMix(a,b,c,d); - a += u.p64[2]; - b += u.p64[3]; - } - - //Handle the case of 16+ remaining bytes. - if (remainder >= 16) - { - c += u.p64[0]; - d += u.p64[1]; - ShortMix(a,b,c,d); - u.p64 += 2; - remainder -= 16; - } - } - - // Handle the last 0..15 bytes, and its length - d = ((uint64_t)length) << 56; - switch (remainder) - { - case 15: - d += ((uint64_t)u.p8[14]) << 48; - case 14: - d += ((uint64_t)u.p8[13]) << 40; - case 13: - d += ((uint64_t)u.p8[12]) << 32; - case 12: - d += u.p32[2]; - c += u.p64[0]; - break; - case 11: - d += ((uint64_t)u.p8[10]) << 16; - case 10: - d += ((uint64_t)u.p8[9]) << 8; - case 9: - d += (uint64_t)u.p8[8]; - case 8: - c += u.p64[0]; - break; - case 7: - c += ((uint64_t)u.p8[6]) << 48; - case 6: - c += ((uint64_t)u.p8[5]) << 40; - case 5: - c += ((uint64_t)u.p8[4]) << 32; - case 4: - c += u.p32[0]; - break; - case 3: - c += ((uint64_t)u.p8[2]) << 16; - case 2: - c += ((uint64_t)u.p8[1]) << 8; - case 1: - c += (uint64_t)u.p8[0]; - break; - case 0: - c += sc_const; - d += sc_const; - } - ShortEnd(a,b,c,d); - *hash1 = a; - *hash2 = b; -} - - - - -// do the whole hash in one call -void SpookyHash::Hash128( - const void *message, - size_t length, - uint64_t *hash1, - uint64_t *hash2) -{ - if (length < sc_bufSize) - { - Short(message, length, hash1, hash2); - return; - } - - uint64_t h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11; - uint64_t buf[sc_numVars]; - uint64_t *end; - union - { - const uint8_t *p8; - uint64_t *p64; - size_t i; - } u; - size_t remainder; - - h0=h3=h6=h9 = *hash1; - h1=h4=h7=h10 = *hash2; - h2=h5=h8=h11 = sc_const; - - u.p8 = (const uint8_t *)message; - end = u.p64 + (length/sc_blockSize)*sc_numVars; - - // handle all whole sc_blockSize blocks of bytes - if (ALLOW_UNALIGNED_READS || ((u.i & 0x7) == 0)) - { - while (u.p64 < end) - { - Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - u.p64 += sc_numVars; - } - } - else - { - while (u.p64 < end) - { - memcpy(buf, u.p64, sc_blockSize); - Mix(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - u.p64 += sc_numVars; - } - } - - // handle the last partial block of sc_blockSize bytes - remainder = (length - ((const uint8_t *)end-(const uint8_t *)message)); - memcpy(buf, end, remainder); - memset(((uint8_t *)buf)+remainder, 0, sc_blockSize-remainder); - ((uint8_t *)buf)[sc_blockSize-1] = remainder; - Mix(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - - // do some final mixing - End(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - *hash1 = h0; - *hash2 = h1; -} - - - -// init spooky state -void SpookyHash::Init(uint64_t seed1, uint64_t seed2) -{ - m_length = 0; - m_remainder = 0; - m_state[0] = seed1; - m_state[1] = seed2; -} - - -// add a message fragment to the state -void SpookyHash::Update(const void *message, size_t length) -{ - uint64_t h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11; - size_t newLength = length + m_remainder; - uint8_t remainder; - union - { - const uint8_t *p8; - uint64_t *p64; - size_t i; - } u; - const uint64_t *end; - - // Is this message fragment too short? If it is, stuff it away. - if (newLength < sc_bufSize) - { - memcpy(&((uint8_t *)m_data)[m_remainder], message, length); - m_length = length + m_length; - m_remainder = (uint8_t)newLength; - return; - } - - // init the variables - if (m_length < sc_bufSize) - { - h0=h3=h6=h9 = m_state[0]; - h1=h4=h7=h10 = m_state[1]; - h2=h5=h8=h11 = sc_const; - } - else - { - h0 = m_state[0]; - h1 = m_state[1]; - h2 = m_state[2]; - h3 = m_state[3]; - h4 = m_state[4]; - h5 = m_state[5]; - h6 = m_state[6]; - h7 = m_state[7]; - h8 = m_state[8]; - h9 = m_state[9]; - h10 = m_state[10]; - h11 = m_state[11]; - } - m_length = length + m_length; - - // if we've got anything stuffed away, use it now - if (m_remainder) - { - uint8_t prefix = sc_bufSize-m_remainder; - memcpy(&(((uint8_t *)m_data)[m_remainder]), message, prefix); - u.p64 = m_data; - Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - Mix(&u.p64[sc_numVars], h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - u.p8 = ((const uint8_t *)message) + prefix; - length -= prefix; - } - else - { - u.p8 = (const uint8_t *)message; - } - - // handle all whole blocks of sc_blockSize bytes - end = u.p64 + (length/sc_blockSize)*sc_numVars; - remainder = (uint8_t)(length-((const uint8_t *)end-u.p8)); - if (ALLOW_UNALIGNED_READS || (u.i & 0x7) == 0) - { - while (u.p64 < end) - { - Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - u.p64 += sc_numVars; - } - } - else - { - while (u.p64 < end) - { - memcpy(m_data, u.p8, sc_blockSize); - Mix(m_data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - u.p64 += sc_numVars; - } - } - - // stuff away the last few bytes - m_remainder = remainder; - memcpy(m_data, end, remainder); - - // stuff away the variables - m_state[0] = h0; - m_state[1] = h1; - m_state[2] = h2; - m_state[3] = h3; - m_state[4] = h4; - m_state[5] = h5; - m_state[6] = h6; - m_state[7] = h7; - m_state[8] = h8; - m_state[9] = h9; - m_state[10] = h10; - m_state[11] = h11; -} - - -// report the hash for the concatenation of all message fragments so far -void SpookyHash::Final(uint64_t *hash1, uint64_t *hash2) -{ - // init the variables - if (m_length < sc_bufSize) - { - *hash1 = m_state[0]; - *hash2 = m_state[1]; - Short( m_data, m_length, hash1, hash2); - return; - } - - const uint64_t *data = (const uint64_t *)m_data; - uint8_t remainder = m_remainder; - - uint64_t h0 = m_state[0]; - uint64_t h1 = m_state[1]; - uint64_t h2 = m_state[2]; - uint64_t h3 = m_state[3]; - uint64_t h4 = m_state[4]; - uint64_t h5 = m_state[5]; - uint64_t h6 = m_state[6]; - uint64_t h7 = m_state[7]; - uint64_t h8 = m_state[8]; - uint64_t h9 = m_state[9]; - uint64_t h10 = m_state[10]; - uint64_t h11 = m_state[11]; - - if (remainder >= sc_blockSize) - { - // m_data can contain two blocks; handle any whole first block - Mix(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - data += sc_numVars; - remainder -= sc_blockSize; - } - - // mix in the last partial block, and the length mod sc_blockSize - memset(&((uint8_t *)data)[remainder], 0, (sc_blockSize-remainder)); - - ((uint8_t *)data)[sc_blockSize-1] = remainder; - Mix(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - - // do some final mixing - End(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - - *hash1 = h0; - *hash2 = h1; -} - -} // namespace hash -} // namespace folly diff --git a/folly/SpookyHash.h b/folly/SpookyHash.h deleted file mode 100644 index 3f26e5f3..00000000 --- a/folly/SpookyHash.h +++ /dev/null @@ -1,304 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -// -// SpookyHash: a 128-bit noncryptographic hash function -// By Bob Jenkins, public domain -// Oct 31 2010: alpha, framework + SpookyHash::Mix appears right -// Oct 31 2011: alpha again, Mix only good to 2^^69 but rest appears right -// Dec 31 2011: beta, improved Mix, tested it for 2-bit deltas -// Feb 2 2012: production, same bits as beta -// Feb 5 2012: adjusted definitions of uint* to be more portable -// Mar 30 2012: 3 bytes/cycle, not 4. Alpha was 4 but wasn't thorough enough. -// -// Up to 3 bytes/cycle for long messages. Reasonably fast for short messages. -// All 1 or 2 bit deltas achieve avalanche within 1% bias per output bit. -// -// This was developed for and tested on 64-bit x86-compatible processors. -// It assumes the processor is little-endian. There is a macro -// controlling whether unaligned reads are allowed (by default they are). -// This should be an equally good hash on big-endian machines, but it will -// compute different results on them than on little-endian machines. -// -// Google's CityHash has similar specs to SpookyHash, and CityHash is faster -// on some platforms. MD4 and MD5 also have similar specs, but they are orders -// of magnitude slower. CRCs are two or more times slower, but unlike -// SpookyHash, they have nice math for combining the CRCs of pieces to form -// the CRCs of wholes. There are also cryptographic hashes, but those are even -// slower than MD5. -// - -#ifndef FOLLY_SPOOKYHASH_H_ -#define FOLLY_SPOOKYHASH_H_ - -#include -#include - -namespace folly { -namespace hash { - -class SpookyHash -{ -public: - // - // SpookyHash: hash a single message in one call, produce 128-bit output - // - static void Hash128( - const void *message, // message to hash - size_t length, // length of message in bytes - uint64_t *hash1, // in/out: in seed 1, out hash value 1 - uint64_t *hash2); // in/out: in seed 2, out hash value 2 - - // - // Hash64: hash a single message in one call, return 64-bit output - // - static uint64_t Hash64( - const void *message, // message to hash - size_t length, // length of message in bytes - uint64_t seed) // seed - { - uint64_t hash1 = seed; - Hash128(message, length, &hash1, &seed); - return hash1; - } - - // - // Hash32: hash a single message in one call, produce 32-bit output - // - static uint32_t Hash32( - const void *message, // message to hash - size_t length, // length of message in bytes - uint32_t seed) // seed - { - uint64_t hash1 = seed, hash2 = seed; - Hash128(message, length, &hash1, &hash2); - return (uint32_t)hash1; - } - - // - // Init: initialize the context of a SpookyHash - // - void Init( - uint64_t seed1, // any 64-bit value will do, including 0 - uint64_t seed2); // different seeds produce independent hashes - - // - // Update: add a piece of a message to a SpookyHash state - // - void Update( - const void *message, // message fragment - size_t length); // length of message fragment in bytes - - - // - // Final: compute the hash for the current SpookyHash state - // - // This does not modify the state; you can keep updating it afterward - // - // The result is the same as if SpookyHash() had been called with - // all the pieces concatenated into one message. - // - void Final( - uint64_t *hash1, // out only: first 64 bits of hash value. - uint64_t *hash2); // out only: second 64 bits of hash value. - - // - // left rotate a 64-bit value by k bytes - // - static inline uint64_t Rot64(uint64_t x, int k) - { - return (x << k) | (x >> (64 - k)); - } - - // - // This is used if the input is 96 bytes long or longer. - // - // The internal state is fully overwritten every 96 bytes. - // Every input bit appears to cause at least 128 bits of entropy - // before 96 other bytes are combined, when run forward or backward - // For every input bit, - // Two inputs differing in just that input bit - // Where "differ" means xor or subtraction - // And the base value is random - // When run forward or backwards one Mix - // I tried 3 pairs of each; they all differed by at least 212 bits. - // - static inline void Mix( - const uint64_t *data, - uint64_t &s0, uint64_t &s1, uint64_t &s2, uint64_t &s3, - uint64_t &s4, uint64_t &s5, uint64_t &s6, uint64_t &s7, - uint64_t &s8, uint64_t &s9, uint64_t &s10,uint64_t &s11) - { - s0 += data[0]; s2 ^= s10; s11 ^= s0; s0 = Rot64(s0,11); s11 += s1; - s1 += data[1]; s3 ^= s11; s0 ^= s1; s1 = Rot64(s1,32); s0 += s2; - s2 += data[2]; s4 ^= s0; s1 ^= s2; s2 = Rot64(s2,43); s1 += s3; - s3 += data[3]; s5 ^= s1; s2 ^= s3; s3 = Rot64(s3,31); s2 += s4; - s4 += data[4]; s6 ^= s2; s3 ^= s4; s4 = Rot64(s4,17); s3 += s5; - s5 += data[5]; s7 ^= s3; s4 ^= s5; s5 = Rot64(s5,28); s4 += s6; - s6 += data[6]; s8 ^= s4; s5 ^= s6; s6 = Rot64(s6,39); s5 += s7; - s7 += data[7]; s9 ^= s5; s6 ^= s7; s7 = Rot64(s7,57); s6 += s8; - s8 += data[8]; s10 ^= s6; s7 ^= s8; s8 = Rot64(s8,55); s7 += s9; - s9 += data[9]; s11 ^= s7; s8 ^= s9; s9 = Rot64(s9,54); s8 += s10; - s10 += data[10]; s0 ^= s8; s9 ^= s10; s10 = Rot64(s10,22); s9 += s11; - s11 += data[11]; s1 ^= s9; s10 ^= s11; s11 = Rot64(s11,46); s10 += s0; - } - - // - // Mix all 12 inputs together so that h0, h1 are a hash of them all. - // - // For two inputs differing in just the input bits - // Where "differ" means xor or subtraction - // And the base value is random, or a counting value starting at that bit - // The final result will have each bit of h0, h1 flip - // For every input bit, - // with probability 50 +- .3% - // For every pair of input bits, - // with probability 50 +- 3% - // - // This does not rely on the last Mix() call having already mixed some. - // Two iterations was almost good enough for a 64-bit result, but a - // 128-bit result is reported, so End() does three iterations. - // - static inline void EndPartial( - uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3, - uint64_t &h4, uint64_t &h5, uint64_t &h6, uint64_t &h7, - uint64_t &h8, uint64_t &h9, uint64_t &h10,uint64_t &h11) - { - h11+= h1; h2 ^= h11; h1 = Rot64(h1,44); - h0 += h2; h3 ^= h0; h2 = Rot64(h2,15); - h1 += h3; h4 ^= h1; h3 = Rot64(h3,34); - h2 += h4; h5 ^= h2; h4 = Rot64(h4,21); - h3 += h5; h6 ^= h3; h5 = Rot64(h5,38); - h4 += h6; h7 ^= h4; h6 = Rot64(h6,33); - h5 += h7; h8 ^= h5; h7 = Rot64(h7,10); - h6 += h8; h9 ^= h6; h8 = Rot64(h8,13); - h7 += h9; h10^= h7; h9 = Rot64(h9,38); - h8 += h10; h11^= h8; h10= Rot64(h10,53); - h9 += h11; h0 ^= h9; h11= Rot64(h11,42); - h10+= h0; h1 ^= h10; h0 = Rot64(h0,54); - } - - static inline void End( - uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3, - uint64_t &h4, uint64_t &h5, uint64_t &h6, uint64_t &h7, - uint64_t &h8, uint64_t &h9, uint64_t &h10,uint64_t &h11) - { - EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11); - } - - // - // The goal is for each bit of the input to expand into 128 bits of - // apparent entropy before it is fully overwritten. - // n trials both set and cleared at least m bits of h0 h1 h2 h3 - // n: 2 m: 29 - // n: 3 m: 46 - // n: 4 m: 57 - // n: 5 m: 107 - // n: 6 m: 146 - // n: 7 m: 152 - // when run forwards or backwards - // for all 1-bit and 2-bit diffs - // with diffs defined by either xor or subtraction - // with a base of all zeros plus a counter, or plus another bit, or random - // - static inline void ShortMix(uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3) - { - h2 = Rot64(h2,50); h2 += h3; h0 ^= h2; - h3 = Rot64(h3,52); h3 += h0; h1 ^= h3; - h0 = Rot64(h0,30); h0 += h1; h2 ^= h0; - h1 = Rot64(h1,41); h1 += h2; h3 ^= h1; - h2 = Rot64(h2,54); h2 += h3; h0 ^= h2; - h3 = Rot64(h3,48); h3 += h0; h1 ^= h3; - h0 = Rot64(h0,38); h0 += h1; h2 ^= h0; - h1 = Rot64(h1,37); h1 += h2; h3 ^= h1; - h2 = Rot64(h2,62); h2 += h3; h0 ^= h2; - h3 = Rot64(h3,34); h3 += h0; h1 ^= h3; - h0 = Rot64(h0,5); h0 += h1; h2 ^= h0; - h1 = Rot64(h1,36); h1 += h2; h3 ^= h1; - } - - // - // Mix all 4 inputs together so that h0, h1 are a hash of them all. - // - // For two inputs differing in just the input bits - // Where "differ" means xor or subtraction - // And the base value is random, or a counting value starting at that bit - // The final result will have each bit of h0, h1 flip - // For every input bit, - // with probability 50 +- .3% (it is probably better than that) - // For every pair of input bits, - // with probability 50 +- .75% (the worst case is approximately that) - // - static inline void ShortEnd(uint64_t &h0, uint64_t &h1, uint64_t &h2, uint64_t &h3) - { - h3 ^= h2; h2 = Rot64(h2,15); h3 += h2; - h0 ^= h3; h3 = Rot64(h3,52); h0 += h3; - h1 ^= h0; h0 = Rot64(h0,26); h1 += h0; - h2 ^= h1; h1 = Rot64(h1,51); h2 += h1; - h3 ^= h2; h2 = Rot64(h2,28); h3 += h2; - h0 ^= h3; h3 = Rot64(h3,9); h0 += h3; - h1 ^= h0; h0 = Rot64(h0,47); h1 += h0; - h2 ^= h1; h1 = Rot64(h1,54); h2 += h1; - h3 ^= h2; h2 = Rot64(h2,32); h3 += h2; - h0 ^= h3; h3 = Rot64(h3,25); h0 += h3; - h1 ^= h0; h0 = Rot64(h0,63); h1 += h0; - } - -private: - - // - // Short is used for messages under 192 bytes in length - // Short has a low startup cost, the normal mode is good for long - // keys, the cost crossover is at about 192 bytes. The two modes were - // held to the same quality bar. - // - static void Short( - const void *message, // message (array of bytes, not necessarily aligned) - size_t length, // length of message (in bytes) - uint64_t *hash1, // in/out: in the seed, out the hash value - uint64_t *hash2); // in/out: in the seed, out the hash value - - // number of uint64_t's in internal state - static const size_t sc_numVars = 12; - - // size of the internal state - static const size_t sc_blockSize = sc_numVars*8; - - // size of buffer of unhashed data, in bytes - static const size_t sc_bufSize = 2*sc_blockSize; - - // - // sc_const: a constant which: - // * is not zero - // * is odd - // * is a not-very-regular mix of 1's and 0's - // * does not need any other special mathematical properties - // - static const uint64_t sc_const = 0xdeadbeefdeadbeefLL; - - uint64_t m_data[2*sc_numVars]; // unhashed data, for partial messages - uint64_t m_state[sc_numVars]; // internal state of the hash - size_t m_length; // total length of the input so far - uint8_t m_remainder; // length of unhashed data stashed in m_data -}; - -} // namespace hash -} // namespace folly - -#endif - diff --git a/folly/StlAllocator.h b/folly/StlAllocator.h deleted file mode 100644 index 4cbe8f8b..00000000 --- a/folly/StlAllocator.h +++ /dev/null @@ -1,267 +0,0 @@ -/* - * Copyright 2013 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef FOLLY_STLALLOCATOR_H_ -#define FOLLY_STLALLOCATOR_H_ - -#include "folly/Traits.h" - -#include -#include -#include -#include -#include - -#include - -namespace folly { - -/** - * Wrap a SimpleAllocator into a STL-compliant allocator. - * - * The SimpleAllocator must provide two methods: - * void* allocate(size_t size); - * void deallocate(void* ptr); - * which, respectively, allocate a block of size bytes (aligned to the maximum - * alignment required on your system), throwing std::bad_alloc if the - * allocation can't be satisfied, and free a previously allocated block. - * - * Note that the following allocator resembles the standard allocator - * quite well: - * - * class MallocAllocator { - * public: - * void* allocate(size_t size) { - * void* p = malloc(size); - * if (!p) throw std::bad_alloc(); - * return p; - * } - * void deallocate(void* p) { - * free(p); - * } - * }; - * - * author: Tudor Bosman - */ - -// This would be so much simpler with std::allocator_traits, but gcc 4.6.2 -// doesn't support it -template class StlAllocator; - -template class StlAllocator { - public: - typedef void value_type; - typedef void* pointer; - typedef const void* const_pointer; - template struct rebind { - typedef StlAllocator other; - }; -}; - -template -class StlAllocator { - public: - typedef T value_type; - typedef T* pointer; - typedef const T* const_pointer; - typedef T& reference; - typedef const T& const_reference; - - typedef ptrdiff_t difference_type; - typedef size_t size_type; - - StlAllocator() : alloc_(nullptr) { } - explicit StlAllocator(Alloc* alloc) : alloc_(alloc) { } - - template StlAllocator(const StlAllocator& other) - : alloc_(other.alloc()) { } - - T* allocate(size_t n, const void* hint = nullptr) { - return static_cast(alloc_->allocate(n * sizeof(T))); - } - - void deallocate(T* p, size_t n) { - alloc_->deallocate(p); - } - - size_t max_size() const { - return std::numeric_limits::max(); - } - - T* address(T& x) const { - return std::addressof(x); - } - - const T* address(const T& x) const { - return std::addressof(x); - } - - template - void construct(T* p, Args&&... args) { - new (p) T(std::forward(args)...); - } - - void destroy(T* p) { - p->~T(); - } - - Alloc* alloc() const { - return alloc_; - } - - template struct rebind { - typedef StlAllocator other; - }; - - bool operator!=(const StlAllocator& other) const { - return alloc_ != other.alloc_; - } - - bool operator==(const StlAllocator& other) const { - return alloc_ == other.alloc_; - } - - private: - Alloc* alloc_; -}; - -/* - * Helper classes/functions for creating a unique_ptr using a custom allocator - * - * @author: Marcelo Juchem - */ - -// A deleter implementation based on std::default_delete, -// which uses a custom allocator to free memory -template -class allocator_delete { - typedef typename std::remove_reference::type allocator_type; - -public: - allocator_delete() = default; - - explicit allocator_delete(const allocator_type& allocator): - allocator_(allocator) - {} - - explicit allocator_delete(allocator_type&& allocator): - allocator_(std::move(allocator)) - {} - - template - allocator_delete(const allocator_delete& other): - allocator_(other.get_allocator()) - {} - - allocator_type& get_allocator() const { - return allocator_; - } - - void operator()(typename allocator_type::pointer p) const { - if (!p) { - return; - } - - allocator_.destroy(p); - allocator_.deallocate(p, 1); - } - -private: - mutable allocator_type allocator_; -}; - -template -class is_simple_allocator { - FOLLY_CREATE_HAS_MEMBER_FN_TRAITS(has_destroy, destroy); - - typedef typename std::remove_const< - typename std::remove_reference::type - >::type allocator; - typedef typename std::remove_reference::type value_type; - typedef value_type* pointer; - -public: - constexpr static bool value = !has_destroy::value - && !has_destroy::value; -}; - -template -typename std::enable_if< - is_simple_allocator::value, - folly::StlAllocator< - typename std::remove_reference::type, - typename std::remove_reference::type - > ->::type make_stl_allocator(Allocator&& allocator) { - return folly::StlAllocator< - typename std::remove_reference::type, - typename std::remove_reference::type - >(&allocator); -} - -template -typename std::enable_if< - !is_simple_allocator::value, - typename std::remove_reference::type ->::type make_stl_allocator(Allocator&& allocator) { - return std::move(allocator); -} - -template -struct AllocatorUniquePtr { - typedef std::unique_ptr::value, - folly::StlAllocator::type, T>, - typename std::remove_reference::type - >::type - > - > type; -}; - -template -typename AllocatorUniquePtr::type allocate_unique( - Allocator&& allocator, Args&&... args -) { - auto stlAllocator = folly::make_stl_allocator( - std::forward(allocator) - ); - auto p = stlAllocator.allocate(1); - - try { - stlAllocator.construct(p, std::forward(args)...); - - return {p, - folly::allocator_delete(std::move(stlAllocator)) - }; - } catch (...) { - stlAllocator.deallocate(p, 1); - throw; - } -} - -template -std::shared_ptr allocate_shared(Allocator&& allocator, Args&&... args) { - return std::allocate_shared( - folly::make_stl_allocator(std::forward(allocator)), - std::forward(args)... - ); -} - -} // namespace folly - -#endif /* FOLLY_STLALLOCATOR_H_ */ diff --git a/folly/eventfd.h b/folly/eventfd.h deleted file mode 100644 index 36b66a21..00000000 --- a/folly/eventfd.h +++ /dev/null @@ -1,79 +0,0 @@ -/* - * Copyright 2013 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -/** - * Wrapper around the eventfd system call, as defined in - * in glibc 2.9+. - * - * @author Tudor Bosman (tudorb@fb.com) - */ - -#ifndef FOLLY_BASE_EVENTFD_H_ -#define FOLLY_BASE_EVENTFD_H_ - -#ifndef __linux__ -#error This file may be compiled on Linux only. -#endif - -#include -#include -#include - -// Use existing __NR_eventfd2 if already defined -// Values from the Linux kernel source: -// arch/x86/include/asm/unistd_{32,64}.h -#ifndef __NR_eventfd2 -#if defined(__x86_64__) -#define __NR_eventfd2 290 -#elif defined(__i386__) -#define __NR_eventfd2 328 -#else -#error "Can't define __NR_eventfd2 for your architecture." -#endif -#endif - -#ifndef EFD_SEMAPHORE -#define EFD_SEMAPHORE 1 -#endif - -/* from linux/fcntl.h - this conflicts with fcntl.h so include just the #define - * we need - */ -#ifndef O_CLOEXEC -#define O_CLOEXEC 02000000 /* set close_on_exec */ -#endif - -#ifndef EFD_CLOEXEC -#define EFD_CLOEXEC O_CLOEXEC -#endif - -#ifndef EFD_NONBLOCK -#define EFD_NONBLOCK O_NONBLOCK -#endif - -namespace folly { - -// http://www.kernel.org/doc/man-pages/online/pages/man2/eventfd.2.html -inline int eventfd(unsigned int initval, int flags) { - // Use the eventfd2 system call, as in glibc 2.9+ - // (requires kernel 2.6.30+) - return syscall(__NR_eventfd2, initval, flags); -} - -} // namespace folly - -#endif /* FOLLY_BASE_EVENTFD_H_ */ - diff --git a/folly/experimental/File-inl.h b/folly/experimental/File-inl.h deleted file mode 100644 index 02240d6a..00000000 --- a/folly/experimental/File-inl.h +++ /dev/null @@ -1,56 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef FOLLY_FILE_H_ -#error This file may only be included from folly/experimental/File.h -#endif - -#include - -namespace folly { - -inline File::File(int fd, bool ownsFd) : fd_(fd), ownsFd_(ownsFd) { } - -inline File::~File() { - closeNoThrow(); // ignore error -} - -inline void File::release() { - fd_ = -1; - ownsFd_ = false; -} - -inline void File::swap(File& other) { - using std::swap; - swap(fd_, other.fd_); - swap(ownsFd_, other.ownsFd_); -} - -inline File::File(File&& other) : fd_(other.fd_), ownsFd_(other.ownsFd_) { - other.release(); -} - -inline File& File::operator=(File&& other) { - File(std::move(other)).swap(*this); - return *this; -} - -inline void swap(File& a, File& b) { - a.swap(b); -} - -} // namespace folly - diff --git a/folly/experimental/File.cpp b/folly/experimental/File.cpp deleted file mode 100644 index a0f05f6b..00000000 --- a/folly/experimental/File.cpp +++ /dev/null @@ -1,46 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "folly/experimental/File.h" - -#include - -#include - -namespace folly { - -File::File(const char* name, int flags, mode_t mode) - : fd_(::open(name, flags, mode)), ownsFd_(false) { - if (fd_ == -1) { - throw std::system_error(errno, std::system_category(), "open() failed"); - } - ownsFd_ = true; -} - -void File::close() { - if (!closeNoThrow()) { - throw std::system_error(errno, std::system_category(), "close() failed"); - } -} - -bool File::closeNoThrow() { - int r = ownsFd_ ? ::close(fd_) : 0; - release(); - return r == 0; -} - -} // namespace folly - diff --git a/folly/experimental/File.h b/folly/experimental/File.h deleted file mode 100644 index 4fd69d6c..00000000 --- a/folly/experimental/File.h +++ /dev/null @@ -1,90 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef FOLLY_FILE_H_ -#define FOLLY_FILE_H_ - -#include -#include -#include - -namespace folly { - -/** - * A File represents an open file. - */ -class File { - public: - /** - * Create a File object from an existing file descriptor. - * Takes ownership of the file descriptor if ownsFd is true. - */ - /* implicit */ File(int fd, bool ownsFd=false); - - /** - * Open and create a file object. Throws on error. - */ - /* implicit */ File(const char* name, int flags=O_RDONLY, mode_t mode=0644); - - ~File(); - - /** - * Return the file descriptor, or -1 if the file was closed. - */ - int fd() const { return fd_; } - - /** - * If we own the file descriptor, close the file and throw on error. - * Otherwise, do nothing. - */ - void close(); - - /** - * Closes the file (if owned). Returns true on success, false (and sets - * errno) on error. - */ - bool closeNoThrow(); - - /** - * Releases the file descriptor; no longer owned by this File. - */ - void release(); - - /** - * Swap this File with another. - */ - void swap(File& other); - - // movable - File(File&&); - File& operator=(File&&); - private: - // not copyable - File(const File&) = delete; - File& operator=(const File&) = delete; - - int fd_; - bool ownsFd_; -}; - -void swap(File& a, File& b); - -} // namespace folly - -#include "folly/experimental/File-inl.h" - -#endif /* FOLLY_FILE_H_ */ - diff --git a/folly/experimental/exception_tracer/StackTrace.c b/folly/experimental/exception_tracer/StackTrace.c deleted file mode 100644 index 7a3d5cef..00000000 --- a/folly/experimental/exception_tracer/StackTrace.c +++ /dev/null @@ -1,146 +0,0 @@ -/* - * Copyright 2013 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - - -#include "folly/experimental/exception_tracer/StackTrace.h" - -#include -#include -#include - -#define UNW_LOCAL_ONLY 1 - -#include - -struct Context { - StackTrace* trace; - size_t skip; - size_t capacity; -}; - -static int checkError(const char* name, int err) { - if (err < 0) { - fprintf(stderr, "libunwind error: %s %d\n", name, err); - return -EINVAL; - } - return 0; -} - -static int addIP(struct Context* ctx, unw_cursor_t* cursor) { - if (ctx->skip) { - --ctx->skip; - return 0; - } - - unw_word_t ip; - int r = unw_get_reg(cursor, UNW_REG_IP, &ip); - int err = checkError("unw_get_reg", r); - if (err) return err; - - if (ctx->trace->frameCount == ctx->capacity) { - size_t newCapacity = (ctx->capacity < 8 ? 8 : ctx->capacity * 1.5); - uintptr_t* newBlock = - realloc(ctx->trace->frameIPs, newCapacity * sizeof(uintptr_t)); - if (!newBlock) { - return -ENOMEM; - } - ctx->trace->frameIPs = newBlock; - ctx->capacity = newCapacity; - } - - ctx->trace->frameIPs[ctx->trace->frameCount++] = ip; - return 0; /* success */ -} - -int getCurrentStackTrace(size_t skip, StackTrace* trace) { - trace->frameIPs = NULL; - trace->frameCount = 0; - - struct Context ctx; - ctx.trace = trace; - ctx.skip = skip; - ctx.capacity = 0; - - unw_context_t uctx; - int r = unw_getcontext(&uctx); - int err = checkError("unw_get_context", r); - if (err) return err; - - unw_cursor_t cursor; - r = unw_init_local(&cursor, &uctx); - err = checkError("unw_init_local", r); - if (err) return err; - - while ((r = unw_step(&cursor)) > 0) { - if ((err = addIP(&ctx, &cursor)) != 0) { - destroyStackTrace(trace); - return err; - } - } - err = checkError("unw_step", r); - if (err) return err; - - return 0; -} - -void destroyStackTrace(StackTrace* trace) { - free(trace->frameIPs); - trace->frameIPs = NULL; - trace->frameCount = 0; -} - -int pushCurrentStackTrace(size_t skip, StackTraceStack** head) { - StackTraceStack* newHead = malloc(sizeof(StackTraceStack)); - if (!newHead) { - return -ENOMEM; - } - - int err; - if ((err = getCurrentStackTrace(skip, &newHead->trace)) != 0) { - free(newHead); - return -ENOMEM; - } - - newHead->next = *head; - *head = newHead; - return 0; -} - -void popStackTrace(StackTraceStack** head) { - StackTraceStack* oldHead = *head; - *head = oldHead->next; - destroyStackTrace(&oldHead->trace); - free(oldHead); -} - -void clearStack(StackTraceStack** head) { - while (*head) { - popStackTrace(head); - } -} - -int moveTop(StackTraceStack** from, StackTraceStack** to) { - StackTraceStack* top = *from; - if (!top) { - return -EINVAL; - } - - *from = top->next; - top->next = *to; - *to = top; - return 0; -} - diff --git a/folly/experimental/io/Cursor.h b/folly/experimental/io/Cursor.h deleted file mode 100644 index 5b6e8b26..00000000 --- a/folly/experimental/io/Cursor.h +++ /dev/null @@ -1,480 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef FOLLY_CURSOR_H -#define FOLLY_CURSOR_H - -#include -#include -#include -#include -#include - -#include "folly/Bits.h" -#include "folly/experimental/io/IOBuf.h" -#include "folly/Likely.h" - -/** - * Cursor class for fast iteration over IOBuf chains. - * - * Cursor - Read-only access - * - * RWPrivateCursor - Read-write access, assumes private access to IOBuf chain - * RWUnshareCursor - Read-write access, calls unshare on write (COW) - * Appender - Write access, assumes private access to IOBuf chian - * - * Note that RW cursors write in the preallocated part of buffers (that is, - * between the buffer's data() and tail()), while Appenders append to the end - * of the buffer (between the buffer's tail() and bufferEnd()). Appenders - * automatically adjust the buffer pointers, so you may only use one - * Appender with a buffer chain; for this reason, Appenders assume private - * access to the buffer (you need to call unshare() yourself if necessary). - **/ -namespace folly { namespace io { -namespace detail { - -template -class CursorBase { - public: - const uint8_t* data() const { - return crtBuf_->data() + offset_; - } - - // Space available in the current IOBuf. May be 0; use peek() instead which - // will always point to a non-empty chunk of data or at the end of the - // chain. - size_t length() const { - return crtBuf_->length() - offset_; - } - - Derived& operator+=(size_t offset) { - Derived* p = static_cast(this); - p->skip(offset); - return *p; - } - - template - typename std::enable_if::value, T>::type - read() { - T val; - pull(&val, sizeof(T)); - return val; - } - - template - T readBE() { - return Endian::big(read()); - } - - template - T readLE() { - return Endian::little(read()); - } - - explicit CursorBase(BufType* buf) - : crtBuf_(buf) - , offset_(0) - , buffer_(buf) {} - - // Make all the templated classes friends for copy constructor. - template friend class CursorBase; - - template - explicit CursorBase(const T& cursor) { - crtBuf_ = cursor.crtBuf_; - offset_ = cursor.offset_; - buffer_ = cursor.buffer_; - } - - // reset cursor to point to a new buffer. - void reset(BufType* buf) { - crtBuf_ = buf; - buffer_ = buf; - offset_ = 0; - } - - /** - * Return the available data in the current buffer. - * If you want to gather more data from the chain into a contiguous region - * (for hopefully zero-copy access), use gather() before peek(). - */ - std::pair peek() { - // Ensure that we're pointing to valid data - size_t available = length(); - while (UNLIKELY(available == 0 && tryAdvanceBuffer())) { - available = length(); - } - - return std::make_pair(data(), available); - } - - void pull(void* buf, size_t length) { - if (UNLIKELY(pullAtMost(buf, length) != length)) { - throw std::out_of_range("underflow"); - } - } - - void clone(std::unique_ptr& buf, size_t length) { - if (UNLIKELY(cloneAtMost(buf, length) != length)) { - throw std::out_of_range("underflow"); - } - } - - void skip(size_t length) { - if (UNLIKELY(skipAtMost(length) != length)) { - throw std::out_of_range("underflow"); - } - } - - size_t pullAtMost(void* buf, size_t len) { - uint8_t* p = reinterpret_cast(buf); - size_t copied = 0; - for (;;) { - // Fast path: it all fits in one buffer. - size_t available = length(); - if (LIKELY(available >= len)) { - memcpy(p, data(), len); - offset_ += len; - return copied + len; - } - - memcpy(p, data(), available); - copied += available; - if (UNLIKELY(!tryAdvanceBuffer())) { - return copied; - } - p += available; - len -= available; - } - } - - size_t cloneAtMost(std::unique_ptr& buf, size_t len) { - buf.reset(nullptr); - - std::unique_ptr tmp; - size_t copied = 0; - for (;;) { - // Fast path: it all fits in one buffer. - size_t available = length(); - if (LIKELY(available >= len)) { - tmp = crtBuf_->cloneOne(); - tmp->trimStart(offset_); - tmp->trimEnd(tmp->length() - len); - offset_ += len; - if (!buf) { - buf = std::move(tmp); - } else { - buf->prependChain(std::move(tmp)); - } - return copied + len; - } - - tmp = crtBuf_->cloneOne(); - tmp->trimStart(offset_); - if (!buf) { - buf = std::move(tmp); - } else { - buf->prependChain(std::move(tmp)); - } - - copied += available; - if (UNLIKELY(!tryAdvanceBuffer())) { - return copied; - } - len -= available; - } - } - - size_t skipAtMost(size_t len) { - size_t skipped = 0; - for (;;) { - // Fast path: it all fits in one buffer. - size_t available = length(); - if (LIKELY(available >= len)) { - offset_ += len; - return skipped + len; - } - - skipped += available; - if (UNLIKELY(!tryAdvanceBuffer())) { - return skipped; - } - len -= available; - } - } - - protected: - BufType* crtBuf_; - size_t offset_; - - ~CursorBase(){} - - bool tryAdvanceBuffer() { - BufType* nextBuf = crtBuf_->next(); - if (UNLIKELY(nextBuf == buffer_)) { - offset_ = crtBuf_->length(); - return false; - } - - offset_ = 0; - crtBuf_ = nextBuf; - static_cast(this)->advanceDone(); - return true; - } - - private: - void advanceDone() { - } - - BufType* buffer_; -}; - -template -class Writable { - public: - template - typename std::enable_if::value>::type - write(T value) { - const uint8_t* u8 = reinterpret_cast(&value); - push(u8, sizeof(T)); - } - - template - void writeBE(T value) { - write(Endian::big(value)); - } - - template - void writeLE(T value) { - write(Endian::little(value)); - } - - void push(const uint8_t* buf, size_t len) { - Derived* d = static_cast(this); - if (d->pushAtMost(buf, len) != len) { - throw std::out_of_range("overflow"); - } - } -}; - -} // namespace detail - -class Cursor : public detail::CursorBase { - public: - explicit Cursor(const IOBuf* buf) - : detail::CursorBase(buf) {} - - template - explicit Cursor(CursorType& cursor) - : detail::CursorBase(cursor) {} -}; - -enum class CursorAccess { - PRIVATE, - UNSHARE -}; - -template -class RWCursor - : public detail::CursorBase, IOBuf>, - public detail::Writable> { - friend class detail::CursorBase, IOBuf>; - public: - explicit RWCursor(IOBuf* buf) - : detail::CursorBase, IOBuf>(buf), - maybeShared_(true) {} - - template - explicit RWCursor(CursorType& cursor) - : detail::CursorBase, IOBuf>(cursor), - maybeShared_(true) {} - /** - * Gather at least n bytes contiguously into the current buffer, - * by coalescing subsequent buffers from the chain as necessary. - */ - void gather(size_t n) { - this->crtBuf_->gather(this->offset_ + n); - } - - size_t pushAtMost(const uint8_t* buf, size_t len) { - size_t copied = 0; - for (;;) { - // Fast path: the current buffer is big enough. - size_t available = this->length(); - if (LIKELY(available >= len)) { - if (access == CursorAccess::UNSHARE) { - maybeUnshare(); - } - memcpy(writableData(), buf, len); - this->offset_ += len; - return copied + len; - } - - if (access == CursorAccess::UNSHARE) { - maybeUnshare(); - } - memcpy(writableData(), buf, available); - copied += available; - if (UNLIKELY(!this->tryAdvanceBuffer())) { - return copied; - } - buf += available; - len -= available; - } - } - - void insert(std::unique_ptr buf) { - folly::IOBuf* nextBuf; - if (this->offset_ == 0) { - // Can just prepend - nextBuf = buf.get(); - this->crtBuf_->prependChain(std::move(buf)); - } else { - std::unique_ptr remaining; - if (this->crtBuf_->length() - this->offset_ > 0) { - // Need to split current IOBuf in two. - remaining = this->crtBuf_->cloneOne(); - remaining->trimStart(this->offset_); - nextBuf = remaining.get(); - buf->prependChain(std::move(remaining)); - } else { - // Can just append - nextBuf = this->crtBuf_->next(); - } - this->crtBuf_->trimEnd(this->length()); - this->crtBuf_->appendChain(std::move(buf)); - } - // Jump past the new links - this->offset_ = 0; - this->crtBuf_ = nextBuf; - } - - uint8_t* writableData() { - return this->crtBuf_->writableData() + this->offset_; - } - - private: - void maybeUnshare() { - if (UNLIKELY(maybeShared_)) { - this->crtBuf_->unshareOne(); - maybeShared_ = false; - } - } - - void advanceDone() { - maybeShared_ = true; - } - - bool maybeShared_; -}; - -typedef RWCursor RWPrivateCursor; -typedef RWCursor RWUnshareCursor; - -/** - * Append to the end of a buffer chain, growing the chain (by allocating new - * buffers) in increments of at least growth bytes every time. Won't grow - * (and push() and ensure() will throw) if growth == 0. - * - * TODO(tudorb): add a flavor of Appender that reallocates one IOBuf instead - * of chaining. - */ -class Appender : public detail::Writable { - public: - Appender(IOBuf* buf, uint32_t growth) - : buffer_(buf), - crtBuf_(buf->prev()), - growth_(growth) { - } - - uint8_t* writableData() { - return crtBuf_->writableTail(); - } - - size_t length() const { - return crtBuf_->tailroom(); - } - - /** - * Mark n bytes (must be <= length()) as appended, as per the - * IOBuf::append() method. - */ - void append(size_t n) { - crtBuf_->append(n); - } - - /** - * Ensure at least n contiguous bytes available to write. - * Postcondition: length() >= n. - */ - void ensure(uint32_t n) { - if (LIKELY(length() >= n)) { - return; - } - - // Waste the rest of the current buffer and allocate a new one. - // Don't make it too small, either. - if (growth_ == 0) { - throw std::out_of_range("can't grow buffer chain"); - } - - n = std::max(n, growth_); - buffer_->prependChain(IOBuf::create(n)); - crtBuf_ = buffer_->prev(); - } - - size_t pushAtMost(const uint8_t* buf, size_t len) { - size_t copied = 0; - for (;;) { - // Fast path: it all fits in one buffer. - size_t available = length(); - if (LIKELY(available >= len)) { - memcpy(writableData(), buf, len); - append(len); - return copied + len; - } - - memcpy(writableData(), buf, available); - append(available); - copied += available; - if (UNLIKELY(!tryGrowChain())) { - return copied; - } - buf += available; - len -= available; - } - } - - private: - bool tryGrowChain() { - assert(crtBuf_->next() == buffer_); - if (growth_ == 0) { - return false; - } - - buffer_->prependChain(IOBuf::create(growth_)); - crtBuf_ = buffer_->prev(); - return true; - } - - IOBuf* buffer_; - IOBuf* crtBuf_; - uint32_t growth_; -}; - -}} // folly::io - -#endif // FOLLY_CURSOR_H diff --git a/folly/experimental/io/IOBuf.cpp b/folly/experimental/io/IOBuf.cpp deleted file mode 100644 index 931af87f..00000000 --- a/folly/experimental/io/IOBuf.cpp +++ /dev/null @@ -1,638 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#define __STDC_LIMIT_MACROS - -#include "folly/experimental/io/IOBuf.h" - -#include "folly/Malloc.h" -#include "folly/Likely.h" - -#include -#include -#include -#include - -using std::unique_ptr; - -namespace folly { - -const uint32_t IOBuf::kMaxIOBufSize; -// Note: Applying offsetof() to an IOBuf is legal according to C++11, since -// IOBuf is a standard-layout class. However, this isn't legal with earlier -// C++ standards, which require that offsetof() only be used with POD types. -// -// This code compiles with g++ 4.6, but not with g++ 4.4 or earlier versions. -const uint32_t IOBuf::kMaxInternalDataSize = - kMaxIOBufSize - offsetof(folly::IOBuf, int_.buf); - -IOBuf::SharedInfo::SharedInfo() - : freeFn(NULL), - userData(NULL) { - // Use relaxed memory ordering here. Since we are creating a new SharedInfo, - // no other threads should be referring to it yet. - refcount.store(1, std::memory_order_relaxed); -} - -IOBuf::SharedInfo::SharedInfo(FreeFunction fn, void* arg) - : freeFn(fn), - userData(arg) { - // Use relaxed memory ordering here. Since we are creating a new SharedInfo, - // no other threads should be referring to it yet. - refcount.store(1, std::memory_order_relaxed); -} - -void* IOBuf::operator new(size_t size) { - // Since IOBuf::create() manually allocates space for some IOBuf objects - // using malloc(), override operator new so that all IOBuf objects are - // always allocated using malloc(). This way operator delete can always know - // that free() is the correct way to deallocate the memory. - void* ptr = malloc(size); - - // operator new is not allowed to return NULL - if (UNLIKELY(ptr == NULL)) { - throw std::bad_alloc(); - } - - return ptr; -} - -void* IOBuf::operator new(size_t size, void* ptr) { - assert(size <= kMaxIOBufSize); - return ptr; -} - -void IOBuf::operator delete(void* ptr) { - // For small buffers, IOBuf::create() manually allocates the space for the - // IOBuf object using malloc(). Therefore we override delete to ensure that - // the IOBuf space is freed using free() rather than a normal delete. - free(ptr); -} - -unique_ptr IOBuf::create(uint32_t capacity) { - // If the desired capacity is less than kMaxInternalDataSize, - // just allocate a single region large enough for both the IOBuf header and - // the data. - if (capacity <= kMaxInternalDataSize) { - void* buf = malloc(kMaxIOBufSize); - if (UNLIKELY(buf == NULL)) { - throw std::bad_alloc(); - } - - uint8_t* bufEnd = static_cast(buf) + kMaxIOBufSize; - unique_ptr iobuf(new(buf) IOBuf(bufEnd)); - assert(iobuf->capacity() >= capacity); - return iobuf; - } - - // Allocate an external buffer - uint8_t* buf; - SharedInfo* sharedInfo; - uint32_t actualCapacity; - allocExtBuffer(capacity, &buf, &sharedInfo, &actualCapacity); - - // Allocate the IOBuf header - try { - return unique_ptr(new IOBuf(kExtAllocated, 0, - buf, actualCapacity, - buf, 0, - sharedInfo)); - } catch (...) { - free(buf); - throw; - } -} - -unique_ptr IOBuf::takeOwnership(void* buf, uint32_t capacity, - uint32_t length, - FreeFunction freeFn, - void* userData, - bool freeOnError) { - SharedInfo* sharedInfo = NULL; - try { - sharedInfo = new SharedInfo(freeFn, userData); - - uint8_t* bufPtr = static_cast(buf); - return unique_ptr(new IOBuf(kExtUserSupplied, kFlagFreeSharedInfo, - bufPtr, capacity, - bufPtr, length, - sharedInfo)); - } catch (...) { - delete sharedInfo; - if (freeOnError) { - if (freeFn) { - try { - freeFn(buf, userData); - } catch (...) { - // The user's free function is not allowed to throw. - abort(); - } - } else { - free(buf); - } - } - throw; - } -} - -unique_ptr IOBuf::wrapBuffer(const void* buf, uint32_t capacity) { - // We cast away the const-ness of the buffer here. - // This is okay since IOBuf users must use unshare() to create a copy of - // this buffer before writing to the buffer. - uint8_t* bufPtr = static_cast(const_cast(buf)); - return unique_ptr(new IOBuf(kExtUserSupplied, kFlagUserOwned, - bufPtr, capacity, - bufPtr, capacity, - NULL)); -} - -IOBuf::IOBuf(uint8_t* end) - : next_(this), - prev_(this), - data_(int_.buf), - length_(0), - flags_(0) { - assert(end - int_.buf == kMaxInternalDataSize); - assert(end - reinterpret_cast(this) == kMaxIOBufSize); -} - -IOBuf::IOBuf(ExtBufTypeEnum type, - uint32_t flags, - uint8_t* buf, - uint32_t capacity, - uint8_t* data, - uint32_t length, - SharedInfo* sharedInfo) - : next_(this), - prev_(this), - data_(data), - length_(length), - flags_(kFlagExt | flags) { - ext_.capacity = capacity; - ext_.type = type; - ext_.buf = buf; - ext_.sharedInfo = sharedInfo; - - assert(data >= buf); - assert(data + length <= buf + capacity); - assert(static_cast(flags & kFlagUserOwned) == - (sharedInfo == NULL)); -} - -IOBuf::~IOBuf() { - // Destroying an IOBuf destroys the entire chain. - // Users of IOBuf should only explicitly delete the head of any chain. - // The other elements in the chain will be automatically destroyed. - while (next_ != this) { - // Since unlink() returns unique_ptr() and we don't store it, - // it will automatically delete the unlinked element. - (void)next_->unlink(); - } - - if (flags_ & kFlagExt) { - decrementRefcount(); - } -} - -bool IOBuf::empty() const { - const IOBuf* current = this; - do { - if (current->length() != 0) { - return false; - } - current = current->next_; - } while (current != this); - return true; -} - -uint32_t IOBuf::countChainElements() const { - uint32_t numElements = 1; - for (IOBuf* current = next_; current != this; current = current->next_) { - ++numElements; - } - return numElements; -} - -uint64_t IOBuf::computeChainDataLength() const { - uint64_t fullLength = length_; - for (IOBuf* current = next_; current != this; current = current->next_) { - fullLength += current->length_; - } - return fullLength; -} - -void IOBuf::prependChain(unique_ptr&& iobuf) { - // Take ownership of the specified IOBuf - IOBuf* other = iobuf.release(); - - // Remember the pointer to the tail of the other chain - IOBuf* otherTail = other->prev_; - - // Hook up prev_->next_ to point at the start of the other chain, - // and other->prev_ to point at prev_ - prev_->next_ = other; - other->prev_ = prev_; - - // Hook up otherTail->next_ to point at us, - // and prev_ to point back at otherTail, - otherTail->next_ = this; - prev_ = otherTail; -} - -unique_ptr IOBuf::clone() const { - unique_ptr newHead(cloneOne()); - - for (IOBuf* current = next_; current != this; current = current->next_) { - newHead->prependChain(current->cloneOne()); - } - - return newHead; -} - -unique_ptr IOBuf::cloneOne() const { - if (flags_ & kFlagExt) { - unique_ptr iobuf(new IOBuf(static_cast(ext_.type), - flags_, ext_.buf, ext_.capacity, - data_, length_, - ext_.sharedInfo)); - if (ext_.sharedInfo) { - ext_.sharedInfo->refcount.fetch_add(1, std::memory_order_acq_rel); - } - return iobuf; - } else { - // We have an internal data buffer that cannot be shared - // Allocate a new IOBuf and copy the data into it. - unique_ptr iobuf(IOBuf::create(kMaxInternalDataSize)); - assert((iobuf->flags_ & kFlagExt) == 0); - iobuf->data_ += headroom(); - memcpy(iobuf->data_, data_, length_); - iobuf->length_ = length_; - return iobuf; - } -} - -void IOBuf::unshareOneSlow() { - // Internal buffers are always unshared, so unshareOneSlow() can only be - // called for external buffers - assert(flags_ & kFlagExt); - - // Allocate a new buffer for the data - uint8_t* buf; - SharedInfo* sharedInfo; - uint32_t actualCapacity; - allocExtBuffer(ext_.capacity, &buf, &sharedInfo, &actualCapacity); - - // Copy the data - // Maintain the same amount of headroom. Since we maintained the same - // minimum capacity we also maintain at least the same amount of tailroom. - uint32_t headlen = headroom(); - memcpy(buf + headlen, data_, length_); - - // Release our reference on the old buffer - decrementRefcount(); - // Make sure kFlagExt is set, and kFlagUserOwned and kFlagFreeSharedInfo - // are not set. - flags_ = kFlagExt; - - // Update the buffer pointers to point to the new buffer - data_ = buf + headlen; - ext_.buf = buf; - ext_.sharedInfo = sharedInfo; -} - -void IOBuf::unshareChained() { - // unshareChained() should only be called if we are part of a chain of - // multiple IOBufs. The caller should have already verified this. - assert(isChained()); - - IOBuf* current = this; - while (true) { - if (current->isSharedOne()) { - // we have to unshare - break; - } - - current = current->next_; - if (current == this) { - // None of the IOBufs in the chain are shared, - // so return without doing anything - return; - } - } - - // We have to unshare. Let coalesceSlow() do the work. - coalesceSlow(); -} - -void IOBuf::coalesceSlow(size_t maxLength) { - // coalesceSlow() should only be called if we are part of a chain of multiple - // IOBufs. The caller should have already verified this. - assert(isChained()); - assert(length_ < maxLength); - - // Compute the length of the entire chain - uint64_t newLength = 0; - IOBuf* end = this; - do { - newLength += end->length_; - end = end->next_; - } while (newLength < maxLength && end != this); - - uint64_t newHeadroom = headroom(); - uint64_t newTailroom = end->prev_->tailroom(); - coalesceAndReallocate(newHeadroom, newLength, end, newTailroom); - // We should be only element left in the chain now - assert(length_ >= maxLength || !isChained()); -} - -void IOBuf::coalesceAndReallocate(size_t newHeadroom, - size_t newLength, - IOBuf* end, - size_t newTailroom) { - uint64_t newCapacity = newLength + newHeadroom + newTailroom; - if (newCapacity > UINT32_MAX) { - throw std::overflow_error("IOBuf chain too large to coalesce"); - } - - // Allocate space for the coalesced buffer. - // We always convert to an external buffer, even if we happened to be an - // internal buffer before. - uint8_t* newBuf; - SharedInfo* newInfo; - uint32_t actualCapacity; - allocExtBuffer(newCapacity, &newBuf, &newInfo, &actualCapacity); - - // Copy the data into the new buffer - uint8_t* newData = newBuf + newHeadroom; - uint8_t* p = newData; - IOBuf* current = this; - size_t remaining = newLength; - do { - assert(current->length_ <= remaining); - remaining -= current->length_; - memcpy(p, current->data_, current->length_); - p += current->length_; - current = current->next_; - } while (current != end); - assert(remaining == 0); - - // Point at the new buffer - if (flags_ & kFlagExt) { - decrementRefcount(); - } - - // Make sure kFlagExt is set, and kFlagUserOwned and kFlagFreeSharedInfo - // are not set. - flags_ = kFlagExt; - - ext_.capacity = actualCapacity; - ext_.type = kExtAllocated; - ext_.buf = newBuf; - ext_.sharedInfo = newInfo; - data_ = newData; - length_ = newLength; - - // Separate from the rest of our chain. - // Since we don't store the unique_ptr returned by separateChain(), - // this will immediately delete the returned subchain. - if (isChained()) { - (void)separateChain(next_, current->prev_); - } -} - -void IOBuf::decrementRefcount() { - assert(flags_ & kFlagExt); - - // Externally owned buffers don't have a SharedInfo object and aren't managed - // by the reference count - if (flags_ & kFlagUserOwned) { - assert(ext_.sharedInfo == NULL); - return; - } - - // Decrement the refcount - uint32_t newcnt = ext_.sharedInfo->refcount.fetch_sub( - 1, std::memory_order_acq_rel); - // Note that fetch_sub() returns the value before we decremented. - // If it is 1, we were the only remaining user; if it is greater there are - // still other users. - if (newcnt > 1) { - return; - } - - // We were the last user. Free the buffer - if (ext_.sharedInfo->freeFn != NULL) { - try { - ext_.sharedInfo->freeFn(ext_.buf, ext_.sharedInfo->userData); - } catch (...) { - // The user's free function should never throw. Otherwise we might - // throw from the IOBuf destructor. Other code paths like coalesce() - // also assume that decrementRefcount() cannot throw. - abort(); - } - } else { - free(ext_.buf); - } - - // Free the SharedInfo if it was allocated separately. - // - // This is only used by takeOwnership(). - // - // To avoid this special case handling in decrementRefcount(), we could have - // takeOwnership() set a custom freeFn() that calls the user's free function - // then frees the SharedInfo object. (This would require that - // takeOwnership() store the user's free function with its allocated - // SharedInfo object.) However, handling this specially with a flag seems - // like it shouldn't be problematic. - if (flags_ & kFlagFreeSharedInfo) { - delete ext_.sharedInfo; - } -} - -void IOBuf::reserveSlow(uint32_t minHeadroom, uint32_t minTailroom) { - size_t newCapacity = (size_t)length_ + minHeadroom + minTailroom; - CHECK_LT(newCapacity, UINT32_MAX); - - // We'll need to reallocate the buffer. - // There are a few options. - // - If we have enough total room, move the data around in the buffer - // and adjust the data_ pointer. - // - If we're using an internal buffer, we'll switch to an external - // buffer with enough headroom and tailroom. - // - If we have enough headroom (headroom() >= minHeadroom) but not too much - // (so we don't waste memory), we can try one of two things, depending on - // whether we use jemalloc or not: - // - If using jemalloc, we can try to expand in place, avoiding a memcpy() - // - If not using jemalloc and we don't have too much to copy, - // we'll use realloc() (note that realloc might have to copy - // headroom + data + tailroom, see smartRealloc in folly/Malloc.h) - // - Otherwise, bite the bullet and reallocate. - if (headroom() + tailroom() >= minHeadroom + minTailroom) { - uint8_t* newData = writableBuffer() + minHeadroom; - memmove(newData, data_, length_); - data_ = newData; - return; - } - - size_t newAllocatedCapacity = goodExtBufferSize(newCapacity); - uint8_t* newBuffer = nullptr; - uint32_t newHeadroom = 0; - uint32_t oldHeadroom = headroom(); - - if ((flags_ & kFlagExt) && length_ != 0 && oldHeadroom >= minHeadroom) { - if (usingJEMalloc()) { - size_t headSlack = oldHeadroom - minHeadroom; - // We assume that tailroom is more useful and more important than - // tailroom (not least because realloc / rallocm allow us to grow the - // buffer at the tail, but not at the head) So, if we have more headroom - // than we need, we consider that "wasted". We arbitrarily define "too - // much" headroom to be 25% of the capacity. - if (headSlack * 4 <= newCapacity) { - size_t allocatedCapacity = capacity() + sizeof(SharedInfo); - void* p = ext_.buf; - if (allocatedCapacity >= jemallocMinInPlaceExpandable) { - int r = rallocm(&p, &newAllocatedCapacity, newAllocatedCapacity, - 0, ALLOCM_NO_MOVE); - if (r == ALLOCM_SUCCESS) { - newBuffer = static_cast(p); - newHeadroom = oldHeadroom; - } else if (r == ALLOCM_ERR_OOM) { - // shouldn't happen as we don't actually allocate new memory - // (due to ALLOCM_NO_MOVE) - throw std::bad_alloc(); - } - // if ALLOCM_ERR_NOT_MOVED, do nothing, fall back to - // malloc/memcpy/free - } - } - } else { // Not using jemalloc - size_t copySlack = capacity() - length_; - if (copySlack * 2 <= length_) { - void* p = realloc(ext_.buf, newAllocatedCapacity); - if (UNLIKELY(p == nullptr)) { - throw std::bad_alloc(); - } - newBuffer = static_cast(p); - newHeadroom = oldHeadroom; - } - } - } - - // None of the previous reallocation strategies worked (or we're using - // an internal buffer). malloc/copy/free. - if (newBuffer == nullptr) { - void* p = malloc(newAllocatedCapacity); - if (UNLIKELY(p == nullptr)) { - throw std::bad_alloc(); - } - newBuffer = static_cast(p); - memcpy(newBuffer + minHeadroom, data_, length_); - if (flags_ & kFlagExt) { - free(ext_.buf); - } - newHeadroom = minHeadroom; - } - - SharedInfo* info; - uint32_t cap; - initExtBuffer(newBuffer, newAllocatedCapacity, &info, &cap); - - flags_ = kFlagExt; - - ext_.capacity = cap; - ext_.type = kExtAllocated; - ext_.buf = newBuffer; - ext_.sharedInfo = info; - data_ = newBuffer + newHeadroom; - // length_ is unchanged -} - -void IOBuf::allocExtBuffer(uint32_t minCapacity, - uint8_t** bufReturn, - SharedInfo** infoReturn, - uint32_t* capacityReturn) { - size_t mallocSize = goodExtBufferSize(minCapacity); - uint8_t* buf = static_cast(malloc(mallocSize)); - if (UNLIKELY(buf == NULL)) { - throw std::bad_alloc(); - } - initExtBuffer(buf, mallocSize, infoReturn, capacityReturn); - *bufReturn = buf; -} - -size_t IOBuf::goodExtBufferSize(uint32_t minCapacity) { - // Determine how much space we should allocate. We'll store the SharedInfo - // for the external buffer just after the buffer itself. (We store it just - // after the buffer rather than just before so that the code can still just - // use free(ext_.buf) to free the buffer.) - size_t minSize = static_cast(minCapacity) + sizeof(SharedInfo); - // Add room for padding so that the SharedInfo will be aligned on an 8-byte - // boundary. - minSize = (minSize + 7) & ~7; - - // Use goodMallocSize() to bump up the capacity to a decent size to request - // from malloc, so we can use all of the space that malloc will probably give - // us anyway. - return goodMallocSize(minSize); -} - -void IOBuf::initExtBuffer(uint8_t* buf, size_t mallocSize, - SharedInfo** infoReturn, - uint32_t* capacityReturn) { - // Find the SharedInfo storage at the end of the buffer - // and construct the SharedInfo. - uint8_t* infoStart = (buf + mallocSize) - sizeof(SharedInfo); - SharedInfo* sharedInfo = new(infoStart) SharedInfo; - - size_t actualCapacity = infoStart - buf; - // On the unlikely possibility that the actual capacity is larger than can - // fit in a uint32_t after adding room for the refcount and calling - // goodMallocSize(), truncate downwards if necessary. - if (actualCapacity >= UINT32_MAX) { - *capacityReturn = UINT32_MAX; - } else { - *capacityReturn = actualCapacity; - } - - *infoReturn = sharedInfo; -} - -fbstring IOBuf::moveToFbString() { - // Externally allocated buffers (malloc) are just fine, everything else needs - // to be turned into one. - if (flags_ != kFlagExt || // not malloc()-ed - headroom() != 0 || // malloc()-ed block doesn't start at beginning - tailroom() == 0 || // no room for NUL terminator - isShared() || // shared - isChained()) { // chained - // We might as well get rid of all head and tailroom if we're going - // to reallocate; we need 1 byte for NUL terminator. - coalesceAndReallocate(0, computeChainDataLength(), this, 1); - } - - // Ensure NUL terminated - *writableTail() = 0; - fbstring str(reinterpret_cast(writableData()), - length(), capacity(), - AcquireMallocatedString()); - - // Reset to internal buffer. - flags_ = 0; - clear(); - return str; -} - -} // folly diff --git a/folly/experimental/io/IOBuf.h b/folly/experimental/io/IOBuf.h deleted file mode 100644 index 3a0abb8a..00000000 --- a/folly/experimental/io/IOBuf.h +++ /dev/null @@ -1,1119 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef FOLLY_IO_IOBUF_H_ -#define FOLLY_IO_IOBUF_H_ - -#include -#include -#include -#include -#include -#include -#include -#include -#include - -#include "folly/FBString.h" - -namespace folly { - -/** - * An IOBuf is a pointer to a buffer of data. - * - * IOBuf objects are intended to be used primarily for networking code, and are - * modelled somewhat after FreeBSD's mbuf data structure, and Linux's sk_buff - * structure. - * - * IOBuf objects facilitate zero-copy network programming, by allowing multiple - * IOBuf objects to point to the same underlying buffer of data, using a - * reference count to track when the buffer is no longer needed and can be - * freed. - * - * - * Data Layout - * ----------- - * - * The IOBuf itself is a small object containing a pointer to the buffer and - * information about which segment of the buffer contains valid data. - * - * The data layout looks like this: - * - * +-------+ - * | IOBuf | - * +-------+ - * / - * | - * v - * +------------+--------------------+-----------+ - * | headroom | data | tailroom | - * +------------+--------------------+-----------+ - * ^ ^ ^ ^ - * buffer() data() tail() bufferEnd() - * - * The length() method returns the length of the valid data; capacity() - * returns the entire capacity of the buffer (from buffer() to bufferEnd()). - * The headroom() and tailroom() methods return the amount of unused capacity - * available before and after the data. - * - * - * Buffer Sharing - * -------------- - * - * The buffer itself is reference counted, and multiple IOBuf objects may point - * to the same buffer. Each IOBuf may point to a different section of valid - * data within the underlying buffer. For example, if multiple protocol - * requests are read from the network into a single buffer, a separate IOBuf - * may be created for each request, all sharing the same underlying buffer. - * - * In other words, when multiple IOBufs share the same underlying buffer, the - * data() and tail() methods on each IOBuf may point to a different segment of - * the data. However, the buffer() and bufferEnd() methods will point to the - * same location for all IOBufs sharing the same underlying buffer. - * - * +-----------+ +---------+ - * | IOBuf 1 | | IOBuf 2 | - * +-----------+ +---------+ - * | | _____/ | - * data | tail |/ data | tail - * v v v - * +-------------------------------------+ - * | | | | | - * +-------------------------------------+ - * - * If you only read data from an IOBuf, you don't need to worry about other - * IOBuf objects possibly sharing the same underlying buffer. However, if you - * ever write to the buffer you need to first ensure that no other IOBufs point - * to the same buffer. The unshare() method may be used to ensure that you - * have an unshared buffer. - * - * - * IOBuf Chains - * ------------ - * - * IOBuf objects also contain pointers to next and previous IOBuf objects. - * This can be used to represent a single logical piece of data that its stored - * in non-contiguous chunks in separate buffers. - * - * A single IOBuf object can only belong to one chain at a time. - * - * IOBuf chains are always circular. The "prev" pointer in the head of the - * chain points to the tail of the chain. However, it is up to the user to - * decide which IOBuf is the head. Internally the IOBuf code does not care - * which element is the head. - * - * The lifetime of all IOBufs in the chain are linked: when one element in the - * chain is deleted, all other chained elements are also deleted. Conceptually - * it is simplest to treat this as if the head of the chain owns all other - * IOBufs in the chain. When you delete the head of the chain, it will delete - * the other elements as well. For this reason, prependChain() and - * appendChain() take ownership of of the new elements being added to this - * chain. - * - * When the coalesce() method is used to coalesce an entire IOBuf chain into a - * single IOBuf, all other IOBufs in the chain are eliminated and automatically - * deleted. The unshare() method may coalesce the chain; if it does it will - * similarly delete all IOBufs eliminated from the chain. - * - * As discussed in the following section, it is up to the user to maintain a - * lock around the entire IOBuf chain if multiple threads need to access the - * chain. IOBuf does not provide any internal locking. - * - * - * Synchronization - * --------------- - * - * When used in multithread programs, a single IOBuf object should only be used - * in a single thread at a time. If a caller uses a single IOBuf across - * multiple threads the caller is responsible for using an external lock to - * synchronize access to the IOBuf. - * - * Two separate IOBuf objects may be accessed concurrently in separate threads - * without locking, even if they point to the same underlying buffer. The - * buffer reference count is always accessed atomically, and no other - * operations should affect other IOBufs that point to the same data segment. - * The caller is responsible for using unshare() to ensure that the data buffer - * is not shared by other IOBufs before writing to it, and this ensures that - * the data itself is not modified in one thread while also being accessed from - * another thread. - * - * For IOBuf chains, no two IOBufs in the same chain should be accessed - * simultaneously in separate threads. The caller must maintain a lock around - * the entire chain if the chain, or individual IOBufs in the chain, may be - * accessed by multiple threads. - * - * - * IOBuf Object Allocation/Sharing - * ------------------------------- - * - * IOBuf objects themselves are always allocated on the heap. The IOBuf - * constructors are private, so IOBuf objects may not be created on the stack. - * In part this is done since some IOBuf objects use small-buffer optimization - * and contain the buffer data immediately after the IOBuf object itself. The - * coalesce() and unshare() methods also expect to be able to delete subsequent - * IOBuf objects in the chain if they are no longer needed due to coalescing. - * - * The IOBuf structure also does not provide room for an intrusive refcount on - * the IOBuf object itself, only the underlying data buffer is reference - * counted. If users want to share the same IOBuf object between multiple - * parts of the code, they are responsible for managing this sharing on their - * own. (For example, by using a shared_ptr. Alternatively, users always have - * the option of using clone() to create a second IOBuf that points to the same - * underlying buffer.) - * - * With jemalloc, allocating small objects like IOBuf objects should be - * relatively fast, and the cost of allocating IOBuf objects on the heap and - * cloning new IOBufs should be relatively cheap. - */ -namespace detail { -// Is T a unique_ptr<> to a standard-layout type? -template struct IsUniquePtrToSL - : public std::false_type { }; -template -struct IsUniquePtrToSL< - std::unique_ptr, - typename std::enable_if::value>::type> - : public std::true_type { }; -} // namespace detail - -class IOBuf { - public: - typedef void (*FreeFunction)(void* buf, void* userData); - - /** - * Allocate a new IOBuf object with the requested capacity. - * - * Returns a new IOBuf object that must be (eventually) deleted by the - * caller. The returned IOBuf may actually have slightly more capacity than - * requested. - * - * The data pointer will initially point to the start of the newly allocated - * buffer, and will have a data length of 0. - * - * Throws std::bad_alloc on error. - */ - static std::unique_ptr create(uint32_t capacity); - - /** - * Create a new IOBuf pointing to an existing data buffer. - * - * The new IOBuffer will assume ownership of the buffer, and free it by - * calling the specified FreeFunction when the last IOBuf pointing to this - * buffer is destroyed. The function will be called with a pointer to the - * buffer as the first argument, and the supplied userData value as the - * second argument. The free function must never throw exceptions. - * - * If no FreeFunction is specified, the buffer will be freed using free(). - * - * The IOBuf data pointer will initially point to the start of the buffer, - * - * In the first version of this function, the length of data is unspecified - * and is initialized to the capacity of the buffer - * - * In the second version, the user specifies the valid length of data - * in the buffer - * - * On error, std::bad_alloc will be thrown. If freeOnError is true (the - * default) the buffer will be freed before throwing the error. - */ - static std::unique_ptr takeOwnership(void* buf, uint32_t capacity, - FreeFunction freeFn = NULL, - void* userData = NULL, - bool freeOnError = true) { - return takeOwnership(buf, capacity, capacity, freeFn, - userData, freeOnError); - } - - static std::unique_ptr takeOwnership(void* buf, uint32_t capacity, - uint32_t length, - FreeFunction freeFn = NULL, - void* userData = NULL, - bool freeOnError = true); - - /** - * Create a new IOBuf pointing to an existing data buffer made up of - * count objects of a given standard-layout type. - * - * This is dangerous -- it is essentially equivalent to doing - * reinterpret_cast on your data -- but it's often useful - * for serialization / deserialization. - * - * The new IOBuffer will assume ownership of the buffer, and free it - * appropriately (by calling the UniquePtr's custom deleter, or by calling - * delete or delete[] appropriately if there is no custom deleter) - * when the buffer is destroyed. The custom deleter, if any, must never - * throw exceptions. - * - * The IOBuf data pointer will initially point to the start of the buffer, - * and the length will be the full capacity of the buffer (count * - * sizeof(T)). - * - * On error, std::bad_alloc will be thrown, and the buffer will be freed - * before throwing the error. - */ - template - static typename std::enable_if::value, - std::unique_ptr>::type - takeOwnership(UniquePtr&& buf, size_t count=1); - - /** - * Create a new IOBuf object that points to an existing user-owned buffer. - * - * This should only be used when the caller knows the lifetime of the IOBuf - * object ahead of time and can ensure that all IOBuf objects that will point - * to this buffer will be destroyed before the buffer itself is destroyed. - * - * This buffer will not be freed automatically when the last IOBuf - * referencing it is destroyed. It is the caller's responsibility to free - * the buffer after the last IOBuf has been destroyed. - * - * The IOBuf data pointer will initially point to the start of the buffer, - * and the length will be the full capacity of the buffer. - * - * An IOBuf created using wrapBuffer() will always be reported as shared. - * unshare() may be used to create a writable copy of the buffer. - * - * On error, std::bad_alloc will be thrown. - */ - static std::unique_ptr wrapBuffer(const void* buf, uint32_t capacity); - - /** - * Convenience function to create a new IOBuf object that copies data from a - * user-supplied buffer, optionally allocating a given amount of - * headroom and tailroom. - */ - static std::unique_ptr copyBuffer(const void* buf, uint32_t size, - uint32_t headroom=0, - uint32_t minTailroom=0); - - /** - * Convenience function to create a new IOBuf object that copies data from a - * user-supplied string, optionally allocating a given amount of - * headroom and tailroom. - * - * Beware when attempting to invoke this function with a constant string - * literal and a headroom argument: you will likely end up invoking the - * version of copyBuffer() above. IOBuf::copyBuffer("hello", 3) will treat - * the first argument as a const void*, and will invoke the version of - * copyBuffer() above, with the size argument of 3. - */ - static std::unique_ptr copyBuffer(const std::string& buf, - uint32_t headroom=0, - uint32_t minTailroom=0); - - /** - * A version of copyBuffer() that returns a null pointer if the input string - * is empty. - */ - static std::unique_ptr maybeCopyBuffer(const std::string& buf, - uint32_t headroom=0, - uint32_t minTailroom=0); - - /** - * Convenience function to free a chain of IOBufs held by a unique_ptr. - */ - static void destroy(std::unique_ptr&& data) { - auto destroyer = std::move(data); - } - - /** - * Destroy this IOBuf. - * - * Deleting an IOBuf will automatically destroy all IOBufs in the chain. - * (See the comments above regarding the ownership model of IOBuf chains. - * All subsequent IOBufs in the chain are considered to be owned by the head - * of the chain. Users should only explicitly delete the head of a chain.) - * - * When each individual IOBuf is destroyed, it will release its reference - * count on the underlying buffer. If it was the last user of the buffer, - * the buffer will be freed. - */ - ~IOBuf(); - - /** - * Check whether the chain is empty (i.e., whether the IOBufs in the - * chain have a total data length of zero). - * - * This method is semantically equivalent to - * i->computeChainDataLength()==0 - * but may run faster because it can short-circuit as soon as it - * encounters a buffer with length()!=0 - */ - bool empty() const; - - /** - * Get the pointer to the start of the data. - */ - const uint8_t* data() const { - return data_; - } - - /** - * Get a writable pointer to the start of the data. - * - * The caller is responsible for calling unshare() first to ensure that it is - * actually safe to write to the buffer. - */ - uint8_t* writableData() { - return data_; - } - - /** - * Get the pointer to the end of the data. - */ - const uint8_t* tail() const { - return data_ + length_; - } - - /** - * Get a writable pointer to the end of the data. - * - * The caller is responsible for calling unshare() first to ensure that it is - * actually safe to write to the buffer. - */ - uint8_t* writableTail() { - return data_ + length_; - } - - /** - * Get the data length. - */ - uint32_t length() const { - return length_; - } - - /** - * Get the amount of head room. - * - * Returns the number of bytes in the buffer before the start of the data. - */ - uint32_t headroom() const { - return data_ - buffer(); - } - - /** - * Get the amount of tail room. - * - * Returns the number of bytes in the buffer after the end of the data. - */ - uint32_t tailroom() const { - return bufferEnd() - tail(); - } - - /** - * Get the pointer to the start of the buffer. - * - * Note that this is the pointer to the very beginning of the usable buffer, - * not the start of valid data within the buffer. Use the data() method to - * get a pointer to the start of the data within the buffer. - */ - const uint8_t* buffer() const { - return (flags_ & kFlagExt) ? ext_.buf : int_.buf; - } - - /** - * Get a writable pointer to the start of the buffer. - * - * The caller is responsible for calling unshare() first to ensure that it is - * actually safe to write to the buffer. - */ - uint8_t* writableBuffer() { - return (flags_ & kFlagExt) ? ext_.buf : int_.buf; - } - - /** - * Get the pointer to the end of the buffer. - * - * Note that this is the pointer to the very end of the usable buffer, - * not the end of valid data within the buffer. Use the tail() method to - * get a pointer to the end of the data within the buffer. - */ - const uint8_t* bufferEnd() const { - return (flags_ & kFlagExt) ? - ext_.buf + ext_.capacity : - int_.buf + kMaxInternalDataSize; - } - - /** - * Get the total size of the buffer. - * - * This returns the total usable length of the buffer. Use the length() - * method to get the length of the actual valid data in this IOBuf. - */ - uint32_t capacity() const { - return (flags_ & kFlagExt) ? ext_.capacity : kMaxInternalDataSize; - } - - /** - * Get a pointer to the next IOBuf in this chain. - */ - IOBuf* next() { - return next_; - } - const IOBuf* next() const { - return next_; - } - - /** - * Get a pointer to the previous IOBuf in this chain. - */ - IOBuf* prev() { - return prev_; - } - const IOBuf* prev() const { - return prev_; - } - - /** - * Shift the data forwards in the buffer. - * - * This shifts the data pointer forwards in the buffer to increase the - * headroom. This is commonly used to increase the headroom in a newly - * allocated buffer. - * - * The caller is responsible for ensuring that there is sufficient - * tailroom in the buffer before calling advance(). - * - * If there is a non-zero data length, advance() will use memmove() to shift - * the data forwards in the buffer. In this case, the caller is responsible - * for making sure the buffer is unshared, so it will not affect other IOBufs - * that may be sharing the same underlying buffer. - */ - void advance(uint32_t amount) { - // In debug builds, assert if there is a problem. - assert(amount <= tailroom()); - - if (length_ > 0) { - memmove(data_ + amount, data_, length_); - } - data_ += amount; - } - - /** - * Shift the data backwards in the buffer. - * - * The caller is responsible for ensuring that there is sufficient headroom - * in the buffer before calling retreat(). - * - * If there is a non-zero data length, retreat() will use memmove() to shift - * the data backwards in the buffer. In this case, the caller is responsible - * for making sure the buffer is unshared, so it will not affect other IOBufs - * that may be sharing the same underlying buffer. - */ - void retreat(uint32_t amount) { - // In debug builds, assert if there is a problem. - assert(amount <= headroom()); - - if (length_ > 0) { - memmove(data_ - amount, data_, length_); - } - data_ -= amount; - } - - /** - * Adjust the data pointer to include more valid data at the beginning. - * - * This moves the data pointer backwards to include more of the available - * buffer. The caller is responsible for ensuring that there is sufficient - * headroom for the new data. The caller is also responsible for populating - * this section with valid data. - * - * This does not modify any actual data in the buffer. - */ - void prepend(uint32_t amount) { - CHECK(amount <= headroom()); - data_ -= amount; - length_ += amount; - } - - /** - * Adjust the tail pointer to include more valid data at the end. - * - * This moves the tail pointer forwards to include more of the available - * buffer. The caller is responsible for ensuring that there is sufficient - * tailroom for the new data. The caller is also responsible for populating - * this section with valid data. - * - * This does not modify any actual data in the buffer. - */ - void append(uint32_t amount) { - CHECK(amount <= tailroom()); - length_ += amount; - } - - /** - * Adjust the data pointer forwards to include less valid data. - * - * This moves the data pointer forwards so that the first amount bytes are no - * longer considered valid data. The caller is responsible for ensuring that - * amount is less than or equal to the actual data length. - * - * This does not modify any actual data in the buffer. - */ - void trimStart(uint32_t amount) { - CHECK(amount <= length_); - data_ += amount; - length_ -= amount; - } - - /** - * Adjust the tail pointer backwards to include less valid data. - * - * This moves the tail pointer backwards so that the last amount bytes are no - * longer considered valid data. The caller is responsible for ensuring that - * amount is less than or equal to the actual data length. - * - * This does not modify any actual data in the buffer. - */ - void trimEnd(uint32_t amount) { - CHECK(amount <= length_); - length_ -= amount; - } - - /** - * Clear the buffer. - * - * Postcondition: headroom() == 0, length() == 0, tailroom() == capacity() - */ - void clear() { - data_ = writableBuffer(); - length_ = 0; - } - - /** - * Ensure that this buffer has at least minHeadroom headroom bytes and at - * least minTailroom tailroom bytes. The buffer must be writable - * (you must call unshare() before this, if necessary). - * - * Postcondition: headroom() >= minHeadroom, tailroom() >= minTailroom, - * the data (between data() and data() + length()) is preserved. - */ - void reserve(uint32_t minHeadroom, uint32_t minTailroom) { - // Maybe we don't need to do anything. - if (headroom() >= minHeadroom && tailroom() >= minTailroom) { - return; - } - // If the buffer is empty but we have enough total room (head + tail), - // move the data_ pointer around. - if (length() == 0 && - headroom() + tailroom() >= minHeadroom + minTailroom) { - data_ = writableBuffer() + minHeadroom; - return; - } - // Bah, we have to do actual work. - reserveSlow(minHeadroom, minTailroom); - } - - /** - * Return true if this IOBuf is part of a chain of multiple IOBufs, or false - * if this is the only IOBuf in its chain. - */ - bool isChained() const { - assert((next_ == this) == (prev_ == this)); - return next_ != this; - } - - /** - * Get the number of IOBufs in this chain. - * - * Beware that this method has to walk the entire chain. - * Use isChained() if you just want to check if this IOBuf is part of a chain - * or not. - */ - uint32_t countChainElements() const; - - /** - * Get the length of all the data in this IOBuf chain. - * - * Beware that this method has to walk the entire chain. - */ - uint64_t computeChainDataLength() const; - - /** - * Insert another IOBuf chain immediately before this IOBuf. - * - * For example, if there are two IOBuf chains (A, B, C) and (D, E, F), - * and B->prependChain(D) is called, the (D, E, F) chain will be subsumed - * and become part of the chain starting at A, which will now look like - * (A, D, E, F, B, C) - * - * Note that since IOBuf chains are circular, head->prependChain(other) can - * be used to append the other chain at the very end of the chain pointed to - * by head. For example, if there are two IOBuf chains (A, B, C) and - * (D, E, F), and A->prependChain(D) is called, the chain starting at A will - * now consist of (A, B, C, D, E, F) - * - * The elements in the specified IOBuf chain will become part of this chain, - * and will be owned by the head of this chain. When this chain is - * destroyed, all elements in the supplied chain will also be destroyed. - * - * For this reason, appendChain() only accepts an rvalue-reference to a - * unique_ptr(), to make it clear that it is taking ownership of the supplied - * chain. If you have a raw pointer, you can pass in a new temporary - * unique_ptr around the raw pointer. If you have an existing, - * non-temporary unique_ptr, you must call std::move(ptr) to make it clear - * that you are destroying the original pointer. - */ - void prependChain(std::unique_ptr&& iobuf); - - /** - * Append another IOBuf chain immediately after this IOBuf. - * - * For example, if there are two IOBuf chains (A, B, C) and (D, E, F), - * and B->appendChain(D) is called, the (D, E, F) chain will be subsumed - * and become part of the chain starting at A, which will now look like - * (A, B, D, E, F, C) - * - * The elements in the specified IOBuf chain will become part of this chain, - * and will be owned by the head of this chain. When this chain is - * destroyed, all elements in the supplied chain will also be destroyed. - * - * For this reason, appendChain() only accepts an rvalue-reference to a - * unique_ptr(), to make it clear that it is taking ownership of the supplied - * chain. If you have a raw pointer, you can pass in a new temporary - * unique_ptr around the raw pointer. If you have an existing, - * non-temporary unique_ptr, you must call std::move(ptr) to make it clear - * that you are destroying the original pointer. - */ - void appendChain(std::unique_ptr&& iobuf) { - // Just use prependChain() on the next element in our chain - next_->prependChain(std::move(iobuf)); - } - - /** - * Remove this IOBuf from its current chain. - * - * Since ownership of all elements an IOBuf chain is normally maintained by - * the head of the chain, unlink() transfers ownership of this IOBuf from the - * chain and gives it to the caller. A new unique_ptr to the IOBuf is - * returned to the caller. The caller must store the returned unique_ptr (or - * call release() on it) to take ownership, otherwise the IOBuf will be - * immediately destroyed. - * - * Since unlink transfers ownership of the IOBuf to the caller, be careful - * not to call unlink() on the head of a chain if you already maintain - * ownership on the head of the chain via other means. The pop() method - * is a better choice for that situation. - */ - std::unique_ptr unlink() { - next_->prev_ = prev_; - prev_->next_ = next_; - prev_ = this; - next_ = this; - return std::unique_ptr(this); - } - - /** - * Remove this IOBuf from its current chain and return a unique_ptr to - * the IOBuf that formerly followed it in the chain. - */ - std::unique_ptr pop() { - IOBuf *next = next_; - next_->prev_ = prev_; - prev_->next_ = next_; - prev_ = this; - next_ = this; - return std::unique_ptr((next == this) ? NULL : next); - } - - /** - * Remove a subchain from this chain. - * - * Remove the subchain starting at head and ending at tail from this chain. - * - * Returns a unique_ptr pointing to head. (In other words, ownership of the - * head of the subchain is transferred to the caller.) If the caller ignores - * the return value and lets the unique_ptr be destroyed, the subchain will - * be immediately destroyed. - * - * The subchain referenced by the specified head and tail must be part of the - * same chain as the current IOBuf, but must not contain the current IOBuf. - * However, the specified head and tail may be equal to each other (i.e., - * they may be a subchain of length 1). - */ - std::unique_ptr separateChain(IOBuf* head, IOBuf* tail) { - assert(head != this); - assert(tail != this); - - head->prev_->next_ = tail->next_; - tail->next_->prev_ = head->prev_; - - head->prev_ = tail; - tail->next_ = head; - - return std::unique_ptr(head); - } - - /** - * Return true if at least one of the IOBufs in this chain are shared, - * or false if all of the IOBufs point to unique buffers. - * - * Use isSharedOne() to only check this IOBuf rather than the entire chain. - */ - bool isShared() const { - const IOBuf* current = this; - while (true) { - if (current->isSharedOne()) { - return true; - } - current = current->next_; - if (current == this) { - return false; - } - } - } - - /** - * Return true if other IOBufs are also pointing to the buffer used by this - * IOBuf, and false otherwise. - * - * If this IOBuf points at a buffer owned by another (non-IOBuf) part of the - * code (i.e., if the IOBuf was created using wrapBuffer(), or was cloned - * from such an IOBuf), it is always considered shared. - * - * This only checks the current IOBuf, and not other IOBufs in the chain. - */ - bool isSharedOne() const { - // If this is a user-owned buffer, it is always considered shared - if (flags_ & kFlagUserOwned) { - return true; - } - - if (flags_ & kFlagExt) { - return ext_.sharedInfo->refcount.load(std::memory_order_acquire) > 1; - } else { - return false; - } - } - - /** - * Ensure that this IOBuf has a unique buffer that is not shared by other - * IOBufs. - * - * unshare() operates on an entire chain of IOBuf objects. If the chain is - * shared, it may also coalesce the chain when making it unique. If the - * chain is coalesced, subsequent IOBuf objects in the current chain will be - * automatically deleted. - * - * Note that buffers owned by other (non-IOBuf) users are automatically - * considered shared. - * - * Throws std::bad_alloc on error. On error the IOBuf chain will be - * unmodified. - * - * Currently unshare may also throw std::overflow_error if it tries to - * coalesce. (TODO: In the future it would be nice if unshare() were smart - * enough not to coalesce the entire buffer if the data is too large. - * However, in practice this seems unlikely to become an issue.) - */ - void unshare() { - if (isChained()) { - unshareChained(); - } else { - unshareOne(); - } - } - - /** - * Ensure that this IOBuf has a unique buffer that is not shared by other - * IOBufs. - * - * unshareOne() operates on a single IOBuf object. This IOBuf will have a - * unique buffer after unshareOne() returns, but other IOBufs in the chain - * may still be shared after unshareOne() returns. - * - * Throws std::bad_alloc on error. On error the IOBuf will be unmodified. - */ - void unshareOne() { - if (isSharedOne()) { - unshareOneSlow(); - } - } - - /** - * Coalesce this IOBuf chain into a single buffer. - * - * This method moves all of the data in this IOBuf chain into a single - * contiguous buffer, if it is not already in one buffer. After coalesce() - * returns, this IOBuf will be a chain of length one. Other IOBufs in the - * chain will be automatically deleted. - * - * After coalescing, the IOBuf will have at least as much headroom as the - * first IOBuf in the chain, and at least as much tailroom as the last IOBuf - * in the chain. - * - * Throws std::bad_alloc on error. On error the IOBuf chain will be - * unmodified. Throws std::overflow_error if the length of the entire chain - * larger than can be described by a uint32_t capacity. - */ - void coalesce() { - if (!isChained()) { - return; - } - coalesceSlow(); - } - - /** - * Ensure that this chain has at least maxLength bytes available as a - * contiguous memory range. - * - * This method coalesces whole buffers in the chain into this buffer as - * necessary until this buffer's length() is at least maxLength. - * - * After coalescing, the IOBuf will have at least as much headroom as the - * first IOBuf in the chain, and at least as much tailroom as the last IOBuf - * that was coalesced. - * - * Throws std::bad_alloc on error. On error the IOBuf chain will be - * unmodified. Throws std::overflow_error if the length of the coalesced - * portion of the chain is larger than can be described by a uint32_t - * capacity. (Although maxLength is uint32_t, gather() doesn't split - * buffers, so coalescing whole buffers may result in a capacity that can't - * be described in uint32_t. - * - * Upon return, either enough of the chain was coalesced into a contiguous - * region, or the entire chain was coalesced. That is, - * length() >= maxLength || !isChained() is true. - */ - void gather(uint32_t maxLength) { - if (!isChained() || length_ >= maxLength) { - return; - } - coalesceSlow(maxLength); - } - - /** - * Return a new IOBuf chain sharing the same data as this chain. - * - * The new IOBuf chain will normally point to the same underlying data - * buffers as the original chain. (The one exception to this is if some of - * the IOBufs in this chain contain small internal data buffers which cannot - * be shared.) - */ - std::unique_ptr clone() const; - - /** - * Return a new IOBuf with the same data as this IOBuf. - * - * The new IOBuf returned will not be part of a chain (even if this IOBuf is - * part of a larger chain). - */ - std::unique_ptr cloneOne() const; - - // Overridden operator new and delete. - // These directly use malloc() and free() to allocate the space for IOBuf - // objects. This is needed since IOBuf::create() manually uses malloc when - // allocating IOBuf objects with an internal buffer. - void* operator new(size_t size); - void* operator new(size_t size, void* ptr); - void operator delete(void* ptr); - - /** - * Destructively convert this IOBuf to a fbstring efficiently. - * We rely on fbstring's AcquireMallocatedString constructor to - * transfer memory. - */ - fbstring moveToFbString(); - - private: - enum FlagsEnum { - kFlagExt = 0x1, - kFlagUserOwned = 0x2, - kFlagFreeSharedInfo = 0x4, - }; - - // Values for the ExternalBuf type field. - // We currently don't really use this for anything, other than to have it - // around for debugging purposes. We store it at the moment just because we - // have the 4 extra bytes in the ExternalBuf struct that would just be - // padding otherwise. - enum ExtBufTypeEnum { - kExtAllocated = 0, - kExtUserSupplied = 1, - kExtUserOwned = 2, - }; - - struct SharedInfo { - SharedInfo(); - SharedInfo(FreeFunction fn, void* arg); - - // A pointer to a function to call to free the buffer when the refcount - // hits 0. If this is NULL, free() will be used instead. - FreeFunction freeFn; - void* userData; - std::atomic refcount; - }; - struct ExternalBuf { - uint32_t capacity; - uint32_t type; - uint8_t* buf; - // SharedInfo may be NULL if kFlagUserOwned is set. It is non-NULL - // in all other cases. - SharedInfo* sharedInfo; - }; - struct InternalBuf { - uint8_t buf[] __attribute__((aligned)); - }; - - // The maximum size for an IOBuf object, including any internal data buffer - static const uint32_t kMaxIOBufSize = 256; - static const uint32_t kMaxInternalDataSize; - - // Forbidden copy constructor and assignment opererator - IOBuf(IOBuf const &); - IOBuf& operator=(IOBuf const &); - - /** - * Create a new IOBuf with internal data. - * - * end is a pointer to the end of the IOBuf's internal data buffer. - */ - explicit IOBuf(uint8_t* end); - - /** - * Create a new IOBuf pointing to an external buffer. - * - * The caller is responsible for holding a reference count for this new - * IOBuf. The IOBuf constructor does not automatically increment the - * reference count. - */ - IOBuf(ExtBufTypeEnum type, uint32_t flags, - uint8_t* buf, uint32_t capacity, - uint8_t* data, uint32_t length, - SharedInfo* sharedInfo); - - void unshareOneSlow(); - void unshareChained(); - void coalesceSlow(size_t maxLength=std::numeric_limits::max()); - // newLength must be the entire length of the buffers between this and - // end (no truncation) - void coalesceAndReallocate( - size_t newHeadroom, - size_t newLength, - IOBuf* end, - size_t newTailroom); - void decrementRefcount(); - void reserveSlow(uint32_t minHeadroom, uint32_t minTailroom); - - static size_t goodExtBufferSize(uint32_t minCapacity); - static void initExtBuffer(uint8_t* buf, size_t mallocSize, - SharedInfo** infoReturn, - uint32_t* capacityReturn); - static void allocExtBuffer(uint32_t minCapacity, - uint8_t** bufReturn, - SharedInfo** infoReturn, - uint32_t* capacityReturn); - - /* - * Member variables - */ - - /* - * Links to the next and the previous IOBuf in this chain. - * - * The chain is circularly linked (the last element in the chain points back - * at the head), and next_ and prev_ can never be NULL. If this IOBuf is the - * only element in the chain, next_ and prev_ will both point to this. - */ - IOBuf* next_; - IOBuf* prev_; - - /* - * A pointer to the start of the data referenced by this IOBuf, and the - * length of the data. - * - * This may refer to any subsection of the actual buffer capacity. - */ - uint8_t* data_; - uint32_t length_; - uint32_t flags_; - - union { - ExternalBuf ext_; - InternalBuf int_; - }; - - struct DeleterBase { - virtual ~DeleterBase() { } - virtual void dispose(void* p) = 0; - }; - - template - struct UniquePtrDeleter : public DeleterBase { - typedef typename UniquePtr::pointer Pointer; - typedef typename UniquePtr::deleter_type Deleter; - - explicit UniquePtrDeleter(Deleter deleter) : deleter_(std::move(deleter)){ } - void dispose(void* p) { - try { - deleter_(static_cast(p)); - delete this; - } catch (...) { - abort(); - } - } - - private: - Deleter deleter_; - }; - - static void freeUniquePtrBuffer(void* ptr, void* userData) { - static_cast(userData)->dispose(ptr); - } -}; - -template -typename std::enable_if::value, - std::unique_ptr>::type -IOBuf::takeOwnership(UniquePtr&& buf, size_t count) { - size_t size = count * sizeof(typename UniquePtr::element_type); - CHECK_LT(size, size_t(std::numeric_limits::max())); - auto deleter = new UniquePtrDeleter(buf.get_deleter()); - return takeOwnership(buf.release(), - size, - &IOBuf::freeUniquePtrBuffer, - deleter); -} - -inline std::unique_ptr IOBuf::copyBuffer( - const void* data, uint32_t size, uint32_t headroom, - uint32_t minTailroom) { - uint32_t capacity = headroom + size + minTailroom; - std::unique_ptr buf = create(capacity); - buf->advance(headroom); - memcpy(buf->writableData(), data, size); - buf->append(size); - return buf; -} - -inline std::unique_ptr IOBuf::copyBuffer(const std::string& buf, - uint32_t headroom, - uint32_t minTailroom) { - return copyBuffer(buf.data(), buf.size(), headroom, minTailroom); -} - -inline std::unique_ptr IOBuf::maybeCopyBuffer(const std::string& buf, - uint32_t headroom, - uint32_t minTailroom) { - if (buf.empty()) { - return nullptr; - } - return copyBuffer(buf.data(), buf.size(), headroom, minTailroom); -} - -} // folly - -#endif // FOLLY_IO_IOBUF_H_ diff --git a/folly/experimental/io/IOBufQueue.cpp b/folly/experimental/io/IOBufQueue.cpp deleted file mode 100644 index 6491d6d3..00000000 --- a/folly/experimental/io/IOBufQueue.cpp +++ /dev/null @@ -1,268 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "folly/experimental/io/IOBufQueue.h" - -#include - -#include - -using std::make_pair; -using std::pair; -using std::unique_ptr; - -namespace { - -using folly::IOBuf; - -const size_t MIN_ALLOC_SIZE = 2000; -const size_t MAX_ALLOC_SIZE = 8000; // Must fit within a uint32_t - -/** - * Convenience function to append chain src to chain dst. - */ -void -appendToChain(unique_ptr& dst, unique_ptr&& src) { - if (dst == NULL) { - dst = std::move(src); - } else { - dst->prev()->appendChain(std::move(src)); - } -} - -} // anonymous namespace - -namespace folly { - -IOBufQueue::IOBufQueue(const Options& options) - : options_(options), - chainLength_(0) { -} - -IOBufQueue::IOBufQueue(IOBufQueue&& other) - : options_(other.options_), - chainLength_(other.chainLength_), - head_(std::move(other.head_)) { - other.chainLength_ = 0; -} - -IOBufQueue& IOBufQueue::operator=(IOBufQueue&& other) { - if (&other != this) { - options_ = other.options_; - chainLength_ = other.chainLength_; - head_ = std::move(other.head_); - other.chainLength_ = 0; - } - return *this; -} - -std::pair -IOBufQueue::headroom() { - if (head_) { - return std::make_pair(head_->writableBuffer(), head_->headroom()); - } else { - return std::make_pair(nullptr, 0); - } -} - -void -IOBufQueue::markPrepended(uint32_t n) { - if (n == 0) { - return; - } - assert(head_); - head_->prepend(n); - if (options_.cacheChainLength) { - chainLength_ += n; - } -} - -void -IOBufQueue::prepend(const void* buf, uint32_t n) { - auto p = headroom(); - if (n > p.second) { - throw std::overflow_error("Not enough room to prepend"); - } - memcpy(static_cast(p.first) + p.second - n, buf, n); - markPrepended(n); -} - -void -IOBufQueue::append(unique_ptr&& buf) { - if (!buf) { - return; - } - if (options_.cacheChainLength) { - chainLength_ += buf->computeChainDataLength(); - } - appendToChain(head_, std::move(buf)); -} - -void -IOBufQueue::append(IOBufQueue& other) { - if (!other.head_) { - return; - } - if (options_.cacheChainLength) { - if (other.options_.cacheChainLength) { - chainLength_ += other.chainLength_; - } else { - chainLength_ += other.head_->computeChainDataLength(); - } - } - appendToChain(head_, std::move(other.head_)); - other.chainLength_ = 0; -} - -void -IOBufQueue::append(const void* buf, size_t len) { - auto src = static_cast(buf); - while (len != 0) { - if ((head_ == NULL) || head_->prev()->isSharedOne() || - (head_->prev()->tailroom() == 0)) { - appendToChain(head_, std::move( - IOBuf::create(std::max(MIN_ALLOC_SIZE, - std::min(len, MAX_ALLOC_SIZE))))); - } - IOBuf* last = head_->prev(); - uint32_t copyLen = std::min(len, (size_t)last->tailroom()); - memcpy(last->writableTail(), src, copyLen); - src += copyLen; - last->append(copyLen); - if (options_.cacheChainLength) { - chainLength_ += copyLen; - } - len -= copyLen; - } -} - -void -IOBufQueue::wrapBuffer(const void* buf, size_t len, uint32_t blockSize) { - auto src = static_cast(buf); - while (len != 0) { - size_t n = std::min(len, size_t(blockSize)); - append(IOBuf::wrapBuffer(src, n)); - src += n; - len -= n; - } -} - -pair -IOBufQueue::preallocate(uint32_t min, uint32_t newAllocationSize, - uint32_t max) { - if (head_ != NULL) { - // If there's enough space left over at the end of the queue, use that. - IOBuf* last = head_->prev(); - if (!last->isSharedOne()) { - uint32_t avail = last->tailroom(); - if (avail >= min) { - return make_pair(last->writableTail(), std::min(max, avail)); - } - } - } - // Allocate a new buffer of the requested max size. - unique_ptr newBuf(IOBuf::create(std::max(min, newAllocationSize))); - appendToChain(head_, std::move(newBuf)); - IOBuf* last = head_->prev(); - return make_pair(last->writableTail(), - std::min(max, last->tailroom())); -} - -void -IOBufQueue::postallocate(uint32_t n) { - head_->prev()->append(n); - if (options_.cacheChainLength) { - chainLength_ += n; - } -} - -unique_ptr -IOBufQueue::split(size_t n) { - unique_ptr result; - while (n != 0) { - if (head_ == NULL) { - throw std::underflow_error( - "Attempt to remove more bytes than are present in IOBufQueue"); - } else if (head_->length() <= n) { - n -= head_->length(); - if (options_.cacheChainLength) { - chainLength_ -= head_->length(); - } - unique_ptr remainder = head_->pop(); - appendToChain(result, std::move(head_)); - head_ = std::move(remainder); - } else { - unique_ptr clone = head_->cloneOne(); - clone->trimEnd(clone->length() - n); - appendToChain(result, std::move(clone)); - head_->trimStart(n); - if (options_.cacheChainLength) { - chainLength_ -= n; - } - break; - } - } - return std::move(result); -} - -void IOBufQueue::trimStart(size_t amount) { - while (amount > 0) { - if (!head_) { - throw std::underflow_error( - "Attempt to trim more bytes than are present in IOBufQueue"); - } - if (head_->length() > amount) { - head_->trimStart(amount); - if (options_.cacheChainLength) { - chainLength_ -= amount; - } - break; - } - amount -= head_->length(); - if (options_.cacheChainLength) { - chainLength_ -= head_->length(); - } - head_ = head_->pop(); - } -} - -void IOBufQueue::trimEnd(size_t amount) { - while (amount > 0) { - if (!head_) { - throw std::underflow_error( - "Attempt to trim more bytes than are present in IOBufQueue"); - } - if (head_->prev()->length() > amount) { - head_->prev()->trimEnd(amount); - if (options_.cacheChainLength) { - chainLength_ -= amount; - } - break; - } - amount -= head_->prev()->length(); - if (options_.cacheChainLength) { - chainLength_ -= head_->prev()->length(); - } - unique_ptr b = head_->prev()->unlink(); - - // Null queue if we unlinked the head. - if (b.get() == head_.get()) { - head_.reset(); - } - } -} - -} // folly diff --git a/folly/experimental/io/IOBufQueue.h b/folly/experimental/io/IOBufQueue.h deleted file mode 100644 index cca5f985..00000000 --- a/folly/experimental/io/IOBufQueue.h +++ /dev/null @@ -1,234 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef FOLLY_IO_IOBUF_QUEUE_H -#define FOLLY_IO_IOBUF_QUEUE_H - -#include "folly/experimental/io/IOBuf.h" - -#include -#include - -namespace folly { - -/** - * An IOBufQueue encapsulates a chain of IOBufs and provides - * convenience functions to append data to the back of the chain - * and remove data from the front. - * - * You may also prepend data into the headroom of the first buffer in the - * chain, if any. - */ -class IOBufQueue { - public: - struct Options { - Options() : cacheChainLength(false) { } - bool cacheChainLength; - }; - - /** - * Commonly used Options, currently the only possible value other than - * the default. - */ - static Options cacheChainLength() { - Options options; - options.cacheChainLength = true; - return options; - } - - explicit IOBufQueue(const Options& options = Options()); - - /** - * Return a space to prepend bytes and the amount of headroom available. - */ - std::pair headroom(); - - /** - * Indicate that n bytes from the headroom have been used. - */ - void markPrepended(uint32_t n); - - /** - * Prepend an existing range; throws std::overflow_error if not enough - * room. - */ - void prepend(const void* buf, uint32_t n); - - /** - * Add a buffer or buffer chain to the end of this queue. The - * queue takes ownership of buf. - */ - void append(std::unique_ptr&& buf); - - /** - * Add a queue to the end of this queue. The queue takes ownership of - * all buffers from the other queue. - */ - void append(IOBufQueue& other); - void append(IOBufQueue&& other) { - append(other); // call lvalue reference overload, above - } - - /** - * Copy len bytes, starting at buf, to the end of this queue. - * The caller retains ownership of the source data. - */ - void append(const void* buf, size_t len); - - /** - * Copy a string to the end of this queue. - * The caller retains ownership of the source data. - */ - void append(const std::string& buf) { - append(buf.data(), buf.length()); - } - - /** - * Append a chain of IOBuf objects that point to consecutive regions - * within buf. - * - * Just like IOBuf::wrapBuffer, this should only be used when the caller - * knows ahead of time and can ensure that all IOBuf objects that will point - * to this buffer will be destroyed before the buffer itself is destroyed; - * all other caveats from wrapBuffer also apply. - * - * Every buffer except for the last will wrap exactly blockSize bytes. - * Importantly, this method may be used to wrap buffers larger than 4GB. - */ - void wrapBuffer(const void* buf, size_t len, - uint32_t blockSize=(1U << 31)); // default block size: 2GB - - /** - * Obtain a writable block of contiguous bytes at the end of this - * queue, allocating more space if necessary. The amount of space - * reserved will be at least min. If min contiguous space is not - * available at the end of the queue, and IOBuf with size newAllocationSize - * is appended to the chain and returned. The actual available space - * may be larger than newAllocationSize, but will be truncated to max, - * if specified. - * - * If the caller subsequently writes anything into the returned space, - * it must call the postallocate() method. - * - * @return The starting address of the block and the length in bytes. - * - * @note The point of the preallocate()/postallocate() mechanism is - * to support I/O APIs such as Thrift's TAsyncSocket::ReadCallback - * that request a buffer from the application and then, in a later - * callback, tell the application how much of the buffer they've - * filled with data. - */ - std::pair preallocate( - uint32_t min, uint32_t newAllocationSize, - uint32_t max = std::numeric_limits::max()); - - /** - * Tell the queue that the caller has written data into the first n - * bytes provided by the previous preallocate() call. - * - * @note n should be less than or equal to the size returned by - * preallocate(). If n is zero, the caller may skip the call - * to postallocate(). If n is nonzero, the caller must not - * invoke any other non-const methods on this IOBufQueue between - * the call to preallocate and the call to postallocate(). - */ - void postallocate(uint32_t n); - - /** - * Obtain a writable block of n contiguous bytes, allocating more space - * if necessary, and mark it as used. The caller can fill it later. - */ - void* allocate(uint32_t n) { - void* p = preallocate(n, n).first; - postallocate(n); - return p; - } - - /** - * Split off the first n bytes of the queue into a separate IOBuf chain, - * and transfer ownership of the new chain to the caller. The IOBufQueue - * retains ownership of everything after the split point. - * - * @warning If the split point lies in the middle of some IOBuf within - * the chain, this function may, as an implementation detail, - * clone that IOBuf. - * - * @throws std::underflow_error if n exceeds the number of bytes - * in the queue. - */ - std::unique_ptr split(size_t n); - - /** - * Similar to IOBuf::trimStart, but works on the whole queue. Will - * pop off buffers that have been completely trimmed. - */ - void trimStart(size_t amount); - - /** - * Similar to IOBuf::trimEnd, but works on the whole queue. Will - * pop off buffers that have been completely trimmed. - */ - void trimEnd(size_t amount); - - /** - * Transfer ownership of the queue's entire IOBuf chain to the caller. - */ - std::unique_ptr move() { - chainLength_ = 0; - return std::move(head_); - } - - /** - * Access - */ - const folly::IOBuf* front() const { - return head_.get(); - } - - /** - * Total chain length, only valid if cacheLength was specified in the - * constructor. - */ - size_t chainLength() const { - if (!options_.cacheChainLength) { - throw std::invalid_argument("IOBufQueue: chain length not cached"); - } - return chainLength_; - } - - const Options& options() const { - return options_; - } - - /** Movable */ - IOBufQueue(IOBufQueue&&); - IOBufQueue& operator=(IOBufQueue&&); - - private: - static const size_t kChainLengthNotCached = (size_t)-1; - /** Not copyable */ - IOBufQueue(const IOBufQueue&) = delete; - IOBufQueue& operator=(const IOBufQueue&) = delete; - - Options options_; - size_t chainLength_; - /** Everything that has been appended but not yet discarded or moved out */ - std::unique_ptr head_; -}; - -} // folly - -#endif // FOLLY_IO_IOBUF_QUEUE_H diff --git a/folly/experimental/io/Stream-inl.h b/folly/experimental/io/Stream-inl.h deleted file mode 100644 index 925c1988..00000000 --- a/folly/experimental/io/Stream-inl.h +++ /dev/null @@ -1,98 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef FOLLY_IO_STREAM_H_ -#error This file may only be included from Stream.h -#endif - -#include - -#include - -namespace folly { - -template -InputByteStreamSplitter::InputByteStreamSplitter( - char delimiter, Stream stream) - : done_(false), - delimiter_(delimiter), - stream_(std::move(stream)) { -} - -template -bool InputByteStreamSplitter::operator()(ByteRange& chunk) { - DCHECK(!buffer_ || buffer_->length() == 0); - chunk.clear(); - if (rest_.empty()) { - if (done_) { - return false; - } else if (!stream_(rest_)) { - done_ = true; - return false; - } - } - - auto p = static_cast(memchr(rest_.data(), delimiter_, - rest_.size())); - if (p) { - chunk.assign(rest_.data(), p); - rest_.assign(p + 1, rest_.end()); - return true; - } - - // Incomplete line read, copy to buffer - if (!buffer_) { - static const size_t kDefaultLineSize = 256; - // Arbitrarily assume that we have half of a line in rest_, and - // get enough room for twice that. - buffer_ = IOBuf::create(std::max(kDefaultLineSize, 2 * rest_.size())); - } else { - buffer_->reserve(0, rest_.size()); - } - memcpy(buffer_->writableTail(), rest_.data(), rest_.size()); - buffer_->append(rest_.size()); - - while (stream_(rest_)) { - auto p = static_cast( - memchr(rest_.data(), delimiter_, rest_.size())); - if (p) { - // Copy everything up to the delimiter and return it - size_t n = p - rest_.data(); - buffer_->reserve(0, n); - memcpy(buffer_->writableTail(), rest_.data(), n); - buffer_->append(n); - chunk.reset(buffer_->data(), buffer_->length()); - buffer_->trimStart(buffer_->length()); - rest_.assign(p + 1, rest_.end()); - return true; - } - - // Nope, copy the entire chunk that we read - buffer_->reserve(0, rest_.size()); - memcpy(buffer_->writableTail(), rest_.data(), rest_.size()); - buffer_->append(rest_.size()); - } - - // Incomplete last line - done_ = true; - rest_.clear(); - chunk.reset(buffer_->data(), buffer_->length()); - buffer_->trimStart(buffer_->length()); - return true; -} - -} // namespace folly - diff --git a/folly/experimental/io/Stream.cpp b/folly/experimental/io/Stream.cpp deleted file mode 100644 index 2f519dcd..00000000 --- a/folly/experimental/io/Stream.cpp +++ /dev/null @@ -1,98 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "folly/experimental/io/Stream.h" - -#include -#include -#include - -#include -#include - -#include "folly/String.h" - -namespace folly { - -FileInputByteStream::FileInputByteStream(int fd, bool ownsFd, size_t bufferSize) - : fd_(fd), - ownsFd_(ownsFd), - buffer_(IOBuf::create(bufferSize)) { -} - -FileInputByteStream::FileInputByteStream(int fd, bool ownsFd, - std::unique_ptr&& buffer) - : fd_(fd), - ownsFd_(ownsFd), - buffer_(std::move(buffer)) { - buffer_->clear(); -} - -bool FileInputByteStream::operator()(ByteRange& chunk) { - ssize_t n = ::read(fd_, buffer_->writableTail(), buffer_->capacity()); - if (n == -1) { - throw std::system_error(errno, std::system_category(), "read failed"); - } - chunk.reset(buffer_->tail(), n); - return (n != 0); -} - -FileInputByteStream::FileInputByteStream(FileInputByteStream&& other) - : fd_(other.fd_), - ownsFd_(other.ownsFd_), - buffer_(std::move(other.buffer_)) { - other.fd_ = -1; - other.ownsFd_ = false; -} - -FileInputByteStream& FileInputByteStream::operator=( - FileInputByteStream&& other) { - if (&other != this) { - closeNoThrow(); - fd_ = other.fd_; - ownsFd_ = other.ownsFd_; - buffer_ = std::move(other.buffer_); - other.fd_ = -1; - other.ownsFd_ = false; - } - return *this; -} - -FileInputByteStream::~FileInputByteStream() { - closeNoThrow(); -} - -void FileInputByteStream::closeNoThrow() { - if (!ownsFd_) { - return; - } - ownsFd_ = false; - if (::close(fd_) == -1) { - PLOG(ERROR) << "close failed"; - } -} - -InputByteStreamSplitter byLine( - const char* fileName, char delim) { - int fd = ::open(fileName, O_RDONLY); - if (fd == -1) { - throw std::system_error(errno, std::system_category(), "open failed"); - } - return makeInputByteStreamSplitter(delim, FileInputByteStream(fd, true)); -} - -} // namespace folly - diff --git a/folly/experimental/io/Stream.h b/folly/experimental/io/Stream.h deleted file mode 100644 index 15b58aa7..00000000 --- a/folly/experimental/io/Stream.h +++ /dev/null @@ -1,226 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef FOLLY_IO_STREAM_H_ -#define FOLLY_IO_STREAM_H_ - -#include -#include - -#include "folly/Range.h" -#include "folly/FBString.h" -#include "folly/experimental/io/IOBuf.h" - -namespace folly { - -/** - * An InputByteStream is a functional object with the following signature: - * - * bool operator()(ByteRange& data); - * - * Input byte streams must be movable. - * - * The stream returns false at EOF; otherwise, it returns true and sets data to - * the next chunk of data from the stream. The memory that data points to must - * remain valid until the next call to the stream. In case of error, the - * stream throws an exception. - * - * The meaning of a "chunk" is left up to the stream implementation. Some - * streams return chunks limited to the size of an internal buffer. Other - * streams return the entire input as one (potentially huge) ByteRange. - * Others assign meaning to chunks: StreamSplitter returns "lines" -- sequences - * of bytes between delimiters. This ambiguity is intentional; resolving it - * would significantly increase the complexity of the code. - * - * An OutputByteStream is an object with the following signature: - * - * void operator()(ByteRange data); - * void close(); - * - * Output byte streams must be movable. - * - * The stream appends a chunk of data to the stream when calling operator(). - * close() closes the stream, allowing us to detect any errors before - * destroying the stream object (to avoid throwing exceptions from the - * destructor). The destructor must close the stream if close() was not - * explicitly called, and abort the program if closing the stream caused - * an error. - * - * Just like with input byte streams, the meaning of a "chunk" is left up - * to the stream implementation. Some streams will just append all chunks - * as given; others might assign meaning to chunks and (for example) append - * delimiters between chunks. - */ - -template class InputByteStreamIterator; - -/** - * Convenient base class template to derive all streams from; provides begin() - * and end() for iterator access. This class makes use of the curriously - * recurring template pattern; your stream class S may derive from - * InputByteStreamBase. - * - * Deriving from InputByteStreamBase is not required, but is convenient. - */ -template -class InputByteStreamBase { - public: - InputByteStreamIterator begin() { - return InputByteStreamIterator(static_cast(*this)); - } - - InputByteStreamIterator end() { - return InputByteStreamIterator(); - } - - InputByteStreamBase() { } - InputByteStreamBase(InputByteStreamBase&&) = default; - InputByteStreamBase& operator=(InputByteStreamBase&&) = default; - - private: - InputByteStreamBase(const InputByteStreamBase&) = delete; - InputByteStreamBase& operator=(const InputByteStreamBase&) = delete; -}; - -/** - * Stream iterator - */ -template -class InputByteStreamIterator - : public boost::iterator_facade< - InputByteStreamIterator, - const ByteRange, - boost::single_pass_traversal_tag> { - public: - InputByteStreamIterator() : stream_(nullptr) { } - - explicit InputByteStreamIterator(Stream& stream) : stream_(&stream) { - increment(); - } - - private: - friend class boost::iterator_core_access; - - void increment() { - DCHECK(stream_); - if (stream_ && !(*stream_)(chunk_)) { - stream_ = nullptr; - } - } - - // This is a single pass iterator, so all we care about is that - // equal forms an equivalence class on the subset of iterators that it's - // defined on. In our case, only identical (same object) iterators and - // past-the-end iterators compare equal. (so that it != end() works) - bool equal(const InputByteStreamIterator& other) const { - return (this == &other) || (!stream_ && !other.stream_); - } - - const ByteRange& dereference() const { - DCHECK(stream_); - return chunk_; - } - - Stream* stream_; - ByteRange chunk_; -}; - -/** - * Stream that read()s from a file. - */ -class FileInputByteStream : public InputByteStreamBase { - public: - static const size_t kDefaultBufferSize = 4096; - explicit FileInputByteStream(int fd, - bool ownsFd = false, - size_t bufferSize = kDefaultBufferSize); - FileInputByteStream(int fd, bool ownsFd, std::unique_ptr&& buffer); - FileInputByteStream(FileInputByteStream&& other); - FileInputByteStream& operator=(FileInputByteStream&& other); - ~FileInputByteStream(); - bool operator()(ByteRange& chunk); - - private: - void closeNoThrow(); - - int fd_; - bool ownsFd_; - std::unique_ptr buffer_; -}; - -/** - * Split a stream on a delimiter. Returns "lines" between delimiters; - * the delimiters are not included in the returned string. - * - * Note that the InputByteStreamSplitter acts as a stream itself, and you can - * iterate over it. - */ -template -class InputByteStreamSplitter - : public InputByteStreamBase> { - public: - InputByteStreamSplitter(char delimiter, Stream stream); - bool operator()(ByteRange& chunk); - - InputByteStreamSplitter(InputByteStreamSplitter&&) = default; - InputByteStreamSplitter& operator=(InputByteStreamSplitter&&) = default; - - private: - InputByteStreamSplitter(const InputByteStreamSplitter&) = delete; - InputByteStreamSplitter& operator=(const InputByteStreamSplitter&) = delete; - - bool done_; - char delimiter_; - Stream stream_; - std::unique_ptr buffer_; - ByteRange rest_; -}; - -/** - * Shortcut to create a stream splitter around a stream and deduce - * the type of the template argument. - */ -template -InputByteStreamSplitter makeInputByteStreamSplitter( - char delimiter, Stream stream) { - return InputByteStreamSplitter(delimiter, std::move(stream)); -} - -/** - * Create a stream that splits a file into chunks (default: lines, with - * '\n' as the delimiter) - */ -InputByteStreamSplitter byLine( - const char* fileName, char delim='\n'); - -// overload for std::string -inline InputByteStreamSplitter byLine( - const std::string& fileName, char delim='\n') { - return byLine(fileName.c_str(), delim); -} - -// overload for fbstring -inline InputByteStreamSplitter byLine( - const fbstring& fileName, char delim='\n') { - return byLine(fileName.c_str(), delim); -} - -} // namespace folly - -#include "folly/experimental/io/Stream-inl.h" - -#endif /* FOLLY_IO_STREAM_H_ */ - diff --git a/folly/experimental/io/TypedIOBuf.h b/folly/experimental/io/TypedIOBuf.h deleted file mode 100644 index f9901a80..00000000 --- a/folly/experimental/io/TypedIOBuf.h +++ /dev/null @@ -1,206 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#ifndef FOLLY_IO_TYPEDIOBUF_H_ -#define FOLLY_IO_TYPEDIOBUF_H_ - -#include -#include -#include -#include "folly/experimental/io/IOBuf.h" - -namespace folly { - -/** - * Wrapper class to handle a IOBuf as a typed buffer (to a standard layout - * class). - * - * This class punts on alignment, and assumes that you know what you're doing. - * - * All methods are wrappers around the corresponding IOBuf methods. The - * TypedIOBuf object is stateless, so it's perfectly okay to access the - * underlying IOBuf in between TypedIOBuf method calls. - */ -template -class TypedIOBuf { - static_assert(std::is_standard_layout::value, "must be standard layout"); - public: - typedef T value_type; - typedef value_type& reference; - typedef const value_type& const_reference; - typedef uint32_t size_type; - typedef value_type* iterator; - typedef const value_type* const_iterator; - - explicit TypedIOBuf(IOBuf* buf) : buf_(buf) { } - - IOBuf* ioBuf() { - return buf_; - } - const IOBuf* ioBuf() const { - return buf_; - } - - bool empty() const { - return buf_->empty(); - } - const T* data() const { - return cast(buf_->data()); - } - T* writableData() { - return cast(buf_->writableData()); - } - const T* tail() const { - return cast(buf_->tail()); - } - T* writableTail() { - return cast(buf_->writableTail()); - } - uint32_t length() const { - return sdiv(buf_->length()); - } - uint32_t size() const { return length(); } - - uint32_t headroom() const { - return sdiv(buf_->headroom()); - } - uint32_t tailroom() const { - return sdiv(buf_->tailroom()); - } - const T* buffer() const { - return cast(buf_->buffer()); - } - T* writableBuffer() { - return cast(buf_->writableBuffer()); - } - const T* bufferEnd() const { - return cast(buf_->bufferEnd()); - } - uint32_t capacity() const { - return sdiv(buf_->capacity()); - } - void advance(uint32_t n) { - buf_->advance(smul(n)); - } - void retreat(uint32_t n) { - buf_->retreat(smul(n)); - } - void prepend(uint32_t n) { - buf_->prepend(smul(n)); - } - void append(uint32_t n) { - buf_->append(smul(n)); - } - void trimStart(uint32_t n) { - buf_->trimStart(smul(n)); - } - void trimEnd(uint32_t n) { - buf_->trimEnd(smul(n)); - } - void clear() { - buf_->clear(); - } - void reserve(uint32_t minHeadroom, uint32_t minTailroom) { - buf_->reserve(smul(minHeadroom), smul(minTailroom)); - } - void reserve(uint32_t minTailroom) { reserve(0, minTailroom); } - - const T* cbegin() const { return data(); } - const T* cend() const { return tail(); } - const T* begin() const { return cbegin(); } - const T* end() const { return cend(); } - T* begin() { return writableData(); } - T* end() { return writableTail(); } - - const T& front() const { - assert(!empty()); - return *begin(); - } - T& front() { - assert(!empty()); - return *begin(); - } - const T& back() const { - assert(!empty()); - return end()[-1]; - } - T& back() { - assert(!empty()); - return end()[-1]; - } - - /** - * Simple wrapper to make it easier to treat this TypedIOBuf as an array of - * T. - */ - const T& operator[](ssize_t idx) const { - assert(idx >= 0 && idx < length()); - return data()[idx]; - } - - /** - * Append one element. - */ - void push(const T& data) { - push(&data, &data + 1); - } - void push_back(const T& data) { push(data); } - - /** - * Append multiple elements in a sequence; will call distance(). - */ - template - void push(IT begin, IT end) { - auto n = std::distance(begin, end); - reserve(headroom(), n); - std::copy(begin, end, writableTail()); - append(n); - } - - // Movable - TypedIOBuf(TypedIOBuf&&) = default; - TypedIOBuf& operator=(TypedIOBuf&&) = default; - - private: - // Non-copyable - TypedIOBuf(const TypedIOBuf&) = delete; - TypedIOBuf& operator=(const TypedIOBuf&) = delete; - - // cast to T* - static T* cast(uint8_t* p) { - return reinterpret_cast(p); - } - static const T* cast(const uint8_t* p) { - return reinterpret_cast(p); - } - // divide by size - static uint32_t sdiv(uint32_t n) { - return n / sizeof(T); - } - // multiply by size - static uint32_t smul(uint32_t n) { - // In debug mode, check for overflow - assert((uint64_t(n) * sizeof(T)) < (uint64_t(1) << 32)); - return n * sizeof(T); - } - - IOBuf* buf_; -}; - -} // namespace folly - -#endif /* FOLLY_IO_TYPEDIOBUF_H_ */ - diff --git a/folly/experimental/io/test/IOBufCursorTest.cpp b/folly/experimental/io/test/IOBufCursorTest.cpp deleted file mode 100644 index 6ef4d0a5..00000000 --- a/folly/experimental/io/test/IOBufCursorTest.cpp +++ /dev/null @@ -1,415 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "folly/experimental/io/IOBuf.h" - -#include -#include -#include -#include "folly/Benchmark.h" -#include "folly/Range.h" -#include "folly/experimental/io/Cursor.h" - -DECLARE_bool(benchmark); - -using folly::IOBuf; -using std::unique_ptr; -using namespace folly::io; - -TEST(IOBuf, RWCursor) { - unique_ptr iobuf1(IOBuf::create(20)); - iobuf1->append(20); - unique_ptr iobuf2(IOBuf::create(20)); - iobuf2->append(20); - - IOBuf* iob2ptr = iobuf2.get(); - iobuf1->prependChain(std::move(iobuf2)); - - EXPECT_TRUE(iobuf1->isChained()); - - RWPrivateCursor wcursor(iobuf1.get()); - Cursor rcursor(iobuf1.get()); - wcursor.writeLE((uint64_t)1); - wcursor.writeLE((uint64_t)1); - wcursor.writeLE((uint64_t)1); - wcursor.write((uint8_t)1); - - EXPECT_EQ(1, rcursor.readLE()); - rcursor.skip(8); - EXPECT_EQ(1, rcursor.readLE()); - rcursor.skip(0); - EXPECT_EQ(0, rcursor.read()); - EXPECT_EQ(0, rcursor.read()); - EXPECT_EQ(0, rcursor.read()); - EXPECT_EQ(0, rcursor.read()); - EXPECT_EQ(1, rcursor.read()); -} - -TEST(IOBuf, skip) { - unique_ptr iobuf1(IOBuf::create(20)); - iobuf1->append(20); - RWPrivateCursor wcursor(iobuf1.get()); - wcursor.write((uint8_t)1); - wcursor.write((uint8_t)2); - Cursor cursor(iobuf1.get()); - cursor.skip(1); - EXPECT_EQ(2, cursor.read()); -} - -TEST(IOBuf, reset) { - unique_ptr iobuf1(IOBuf::create(20)); - iobuf1->append(20); - RWPrivateCursor wcursor(iobuf1.get()); - wcursor.write((uint8_t)1); - wcursor.write((uint8_t)2); - wcursor.reset(iobuf1.get()); - EXPECT_EQ(1, wcursor.read()); -} - -TEST(IOBuf, copy_assign_convert) { - unique_ptr iobuf1(IOBuf::create(20)); - iobuf1->append(20); - RWPrivateCursor wcursor(iobuf1.get()); - RWPrivateCursor cursor2(wcursor); - RWPrivateCursor cursor3(iobuf1.get()); - - wcursor.write((uint8_t)1); - cursor3 = wcursor; - wcursor.write((uint8_t)2); - Cursor cursor4(wcursor); - RWPrivateCursor cursor5(wcursor); - wcursor.write((uint8_t)3); - - EXPECT_EQ(1, cursor2.read()); - EXPECT_EQ(2, cursor3.read()); - EXPECT_EQ(3, cursor4.read()); -} - -TEST(IOBuf, overloading) { - unique_ptr iobuf1(IOBuf::create(20)); - iobuf1->append(20); - RWPrivateCursor wcursor(iobuf1.get()); - wcursor += 1; - wcursor.write((uint8_t)1); - Cursor cursor(iobuf1.get()); - cursor += 1; - EXPECT_EQ(1, cursor.read()); -} - -TEST(IOBuf, endian) { - unique_ptr iobuf1(IOBuf::create(20)); - iobuf1->append(20); - RWPrivateCursor wcursor(iobuf1.get()); - Cursor rcursor(iobuf1.get()); - uint16_t v = 1; - int16_t vu = -1; - wcursor.writeBE(v); - wcursor.writeBE(vu); - // Try a couple combinations to ensure they were generated correctly - wcursor.writeBE(vu); - wcursor.writeLE(vu); - wcursor.writeLE(vu); - wcursor.writeLE(v); - EXPECT_EQ(v, rcursor.readBE()); -} - -TEST(IOBuf, Cursor) { - unique_ptr iobuf1(IOBuf::create(1)); - iobuf1->append(1); - RWPrivateCursor c(iobuf1.get()); - c.write((uint8_t)40); // OK - try { - c.write((uint8_t)10); // Bad write, checked should except. - EXPECT_EQ(true, false); - } catch (...) { - } -} - -TEST(IOBuf, UnshareCursor) { - uint8_t buf = 0; - unique_ptr iobuf1(IOBuf::wrapBuffer(&buf, 1)); - unique_ptr iobuf2(IOBuf::wrapBuffer(&buf, 1)); - RWUnshareCursor c1(iobuf1.get()); - RWUnshareCursor c2(iobuf2.get()); - - c1.write((uint8_t)10); // This should duplicate the two buffers. - uint8_t t = c2.read(); - EXPECT_EQ(0, t); - - iobuf1 = IOBuf::wrapBuffer(&buf, 1); - iobuf2 = IOBuf::wrapBuffer(&buf, 1); - RWPrivateCursor c3(iobuf1.get()); - RWPrivateCursor c4(iobuf2.get()); - - c3.write((uint8_t)10); // This should _not_ duplicate the two buffers. - t = c4.read(); - EXPECT_EQ(10, t); -} - -namespace { -void append(std::unique_ptr& buf, folly::StringPiece data) { - EXPECT_LE(data.size(), buf->tailroom()); - memcpy(buf->writableData(), data.data(), data.size()); - buf->append(data.size()); -} - -void append(Appender& appender, folly::StringPiece data) { - appender.push(reinterpret_cast(data.data()), data.size()); -} - -std::string toString(const IOBuf& buf) { - std::string str; - Cursor cursor(&buf); - std::pair p; - while ((p = cursor.peek()).second) { - str.append(reinterpret_cast(p.first), p.second); - cursor.skip(p.second); - } - return str; -} - -} // namespace - -TEST(IOBuf, PullAndPeek) { - std::unique_ptr iobuf1(IOBuf::create(10)); - append(iobuf1, "he"); - std::unique_ptr iobuf2(IOBuf::create(10)); - append(iobuf2, "llo "); - std::unique_ptr iobuf3(IOBuf::create(10)); - append(iobuf3, "world"); - iobuf1->prependChain(std::move(iobuf2)); - iobuf1->prependChain(std::move(iobuf3)); - EXPECT_EQ(3, iobuf1->countChainElements()); - EXPECT_EQ(11, iobuf1->computeChainDataLength()); - - char buf[12]; - memset(buf, 0, sizeof(buf)); - Cursor(iobuf1.get()).pull(buf, 11); - EXPECT_EQ("hello world", std::string(buf)); - - memset(buf, 0, sizeof(buf)); - EXPECT_EQ(11, Cursor(iobuf1.get()).pullAtMost(buf, 20)); - EXPECT_EQ("hello world", std::string(buf)); - - EXPECT_THROW({Cursor(iobuf1.get()).pull(buf, 20);}, - std::out_of_range); - - { - RWPrivateCursor cursor(iobuf1.get()); - auto p = cursor.peek(); - EXPECT_EQ("he", std::string(reinterpret_cast(p.first), - p.second)); - cursor.skip(p.second); - p = cursor.peek(); - EXPECT_EQ("llo ", std::string(reinterpret_cast(p.first), - p.second)); - cursor.skip(p.second); - p = cursor.peek(); - EXPECT_EQ("world", std::string(reinterpret_cast(p.first), - p.second)); - cursor.skip(p.second); - EXPECT_EQ(3, iobuf1->countChainElements()); - EXPECT_EQ(11, iobuf1->computeChainDataLength()); - } - - { - RWPrivateCursor cursor(iobuf1.get()); - cursor.gather(11); - auto p = cursor.peek(); - EXPECT_EQ("hello world", std::string(reinterpret_cast(p.first), p.second)); - EXPECT_EQ(1, iobuf1->countChainElements()); - EXPECT_EQ(11, iobuf1->computeChainDataLength()); - } -} - -TEST(IOBuf, cloneAndInsert) { - std::unique_ptr iobuf1(IOBuf::create(10)); - append(iobuf1, "he"); - std::unique_ptr iobuf2(IOBuf::create(10)); - append(iobuf2, "llo "); - std::unique_ptr iobuf3(IOBuf::create(10)); - append(iobuf3, "world"); - iobuf1->prependChain(std::move(iobuf2)); - iobuf1->prependChain(std::move(iobuf3)); - EXPECT_EQ(3, iobuf1->countChainElements()); - EXPECT_EQ(11, iobuf1->computeChainDataLength()); - - std::unique_ptr cloned; - - Cursor(iobuf1.get()).clone(cloned, 3); - EXPECT_EQ(2, cloned->countChainElements()); - EXPECT_EQ(3, cloned->computeChainDataLength()); - - - EXPECT_EQ(11, Cursor(iobuf1.get()).cloneAtMost(cloned, 20)); - EXPECT_EQ(3, cloned->countChainElements()); - EXPECT_EQ(11, cloned->computeChainDataLength()); - - - EXPECT_THROW({Cursor(iobuf1.get()).clone(cloned, 20);}, - std::out_of_range); - - { - // Check that inserting in the middle of an iobuf splits - RWPrivateCursor cursor(iobuf1.get()); - Cursor(iobuf1.get()).clone(cloned, 3); - EXPECT_EQ(2, cloned->countChainElements()); - EXPECT_EQ(3, cloned->computeChainDataLength()); - - cursor.skip(1); - - cursor.insert(std::move(cloned)); - EXPECT_EQ(6, iobuf1->countChainElements()); - EXPECT_EQ(14, iobuf1->computeChainDataLength()); - // Check that nextBuf got set correctly - cursor.read(); - } - - { - // Check that inserting at the end doesn't create empty buf - RWPrivateCursor cursor(iobuf1.get()); - Cursor(iobuf1.get()).clone(cloned, 1); - EXPECT_EQ(1, cloned->countChainElements()); - EXPECT_EQ(1, cloned->computeChainDataLength()); - - cursor.skip(1); - - cursor.insert(std::move(cloned)); - EXPECT_EQ(7, iobuf1->countChainElements()); - EXPECT_EQ(15, iobuf1->computeChainDataLength()); - // Check that nextBuf got set correctly - cursor.read(); - } - { - // Check that inserting at the beginning doesn't create empty buf - RWPrivateCursor cursor(iobuf1.get()); - Cursor(iobuf1.get()).clone(cloned, 1); - EXPECT_EQ(1, cloned->countChainElements()); - EXPECT_EQ(1, cloned->computeChainDataLength()); - - cursor.insert(std::move(cloned)); - EXPECT_EQ(8, iobuf1->countChainElements()); - EXPECT_EQ(16, iobuf1->computeChainDataLength()); - // Check that nextBuf got set correctly - cursor.read(); - } -} - -TEST(IOBuf, Appender) { - std::unique_ptr head(IOBuf::create(10)); - append(head, "hello"); - - Appender app(head.get(), 10); - uint32_t cap = head->capacity(); - uint32_t len1 = app.length(); - EXPECT_EQ(cap - 5, len1); - app.ensure(len1); // won't grow - EXPECT_EQ(len1, app.length()); - app.ensure(len1 + 1); // will grow - EXPECT_LE(len1 + 1, app.length()); - - append(app, " world"); - EXPECT_EQ("hello world", toString(*head)); -} - -int benchmark_size = 1000; -unique_ptr iobuf_benchmark; - -unique_ptr iobuf_read_benchmark; - -template -void runBenchmark() { - CursClass c(iobuf_benchmark.get()); - - for(int i = 0; i < benchmark_size; i++) { - c.write((uint8_t)0); - } -} - -BENCHMARK(rwPrivateCursorBenchmark, iters) { - while (--iters) { - runBenchmark(); - } -} - -BENCHMARK(rwUnshareCursorBenchmark, iters) { - while (--iters) { - runBenchmark(); - } -} - - -BENCHMARK(cursorBenchmark, iters) { - while (--iters) { - Cursor c(iobuf_read_benchmark.get()); - for(int i = 0; i < benchmark_size ; i++) { - c.read(); - } - } -} - -BENCHMARK(skipBenchmark, iters) { - uint8_t buf; - while (--iters) { - Cursor c(iobuf_read_benchmark.get()); - for(int i = 0; i < benchmark_size ; i++) { - c.peek(); - c.skip(1); - } - } -} - -// fbmake opt -// _bin/folly/experimental/io/test/iobuf_cursor_test -benchmark -// -// Benchmark Iters Total t t/iter iter/sec -// --------------------------------------------------------------------------- -// rwPrivateCursorBenchmark 100000 142.9 ms 1.429 us 683.5 k -// rwUnshareCursorBenchmark 100000 309.3 ms 3.093 us 315.7 k -// cursorBenchmark 100000 741.4 ms 7.414 us 131.7 k -// skipBenchmark 100000 738.9 ms 7.389 us 132.2 k -// -// uname -a: -// -// Linux dev2159.snc6.facebook.com 2.6.33-7_fbk15_104e4d0 #1 SMP -// Tue Oct 19 22:40:30 PDT 2010 x86_64 x86_64 x86_64 GNU/Linux -// -// 72GB RAM, 2 CPUs (Intel(R) Xeon(R) CPU L5630 @ 2.13GHz) -// hyperthreading disabled - -int main(int argc, char** argv) { - testing::InitGoogleTest(&argc, argv); - google::ParseCommandLineFlags(&argc, &argv, true); - - auto ret = RUN_ALL_TESTS(); - - if (ret == 0 && FLAGS_benchmark) { - iobuf_benchmark = IOBuf::create(benchmark_size); - iobuf_benchmark->append(benchmark_size); - - iobuf_read_benchmark = IOBuf::create(1); - for (int i = 0; i < benchmark_size; i++) { - unique_ptr iobuf2(IOBuf::create(1)); - iobuf2->append(1); - iobuf_read_benchmark->prependChain(std::move(iobuf2)); - } - - folly::runBenchmarks(); - } - - return ret; -} diff --git a/folly/experimental/io/test/IOBufQueueTest.cpp b/folly/experimental/io/test/IOBufQueueTest.cpp deleted file mode 100644 index 47555e05..00000000 --- a/folly/experimental/io/test/IOBufQueueTest.cpp +++ /dev/null @@ -1,274 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "folly/experimental/io/IOBufQueue.h" -#include "folly/Range.h" - -#include -#include - -#include -#include -#include - -using folly::IOBuf; -using folly::IOBufQueue; -using folly::StringPiece; -using std::pair; -using std::string; -using std::unique_ptr; - -// String Comma Length macro for string literals -#define SCL(x) (x), sizeof(x) - 1 - -namespace { - -IOBufQueue::Options clOptions; -struct Initializer { - Initializer() { - clOptions.cacheChainLength = true; - } -}; -Initializer initializer; - -unique_ptr -stringToIOBuf(const char* s, uint32_t len) { - unique_ptr buf = IOBuf::create(len); - memcpy(buf->writableTail(), s, len); - buf->append(len); - return std::move(buf); -} - -void checkConsistency(const IOBufQueue& queue) { - if (queue.options().cacheChainLength) { - size_t len = queue.front() ? queue.front()->computeChainDataLength() : 0; - EXPECT_EQ(len, queue.chainLength()); - } -} - -} - -TEST(IOBufQueue, Simple) { - IOBufQueue queue(clOptions); - EXPECT_EQ(NULL, queue.front()); - queue.append(SCL("")); - EXPECT_EQ(NULL, queue.front()); - queue.append(unique_ptr()); - EXPECT_EQ(NULL, queue.front()); - string emptyString; - queue.append(emptyString); - EXPECT_EQ(NULL, queue.front()); -} - -TEST(IOBufQueue, Append) { - IOBufQueue queue(clOptions); - queue.append(SCL("Hello")); - IOBufQueue queue2(clOptions); - queue2.append(SCL(", ")); - queue2.append(SCL("World")); - checkConsistency(queue); - checkConsistency(queue2); - queue.append(queue2.move()); - checkConsistency(queue); - checkConsistency(queue2); - const IOBuf* chain = queue.front(); - EXPECT_NE((IOBuf*)NULL, chain); - EXPECT_EQ(12, chain->computeChainDataLength()); - EXPECT_EQ(NULL, queue2.front()); -} - -TEST(IOBufQueue, Append2) { - IOBufQueue queue(clOptions); - queue.append(SCL("Hello")); - IOBufQueue queue2(clOptions); - queue2.append(SCL(", ")); - queue2.append(SCL("World")); - checkConsistency(queue); - checkConsistency(queue2); - queue.append(queue2); - checkConsistency(queue); - checkConsistency(queue2); - const IOBuf* chain = queue.front(); - EXPECT_NE((IOBuf*)NULL, chain); - EXPECT_EQ(12, chain->computeChainDataLength()); - EXPECT_EQ(NULL, queue2.front()); -} - -TEST(IOBufQueue, Split) { - IOBufQueue queue(clOptions); - queue.append(stringToIOBuf(SCL("Hello"))); - queue.append(stringToIOBuf(SCL(","))); - queue.append(stringToIOBuf(SCL(" "))); - queue.append(stringToIOBuf(SCL(""))); - queue.append(stringToIOBuf(SCL("World"))); - checkConsistency(queue); - EXPECT_EQ(12, queue.front()->computeChainDataLength()); - - unique_ptr prefix(queue.split(1)); - checkConsistency(queue); - EXPECT_EQ(1, prefix->computeChainDataLength()); - EXPECT_EQ(11, queue.front()->computeChainDataLength()); - prefix = queue.split(2); - checkConsistency(queue); - EXPECT_EQ(2, prefix->computeChainDataLength()); - EXPECT_EQ(9, queue.front()->computeChainDataLength()); - prefix = queue.split(3); - checkConsistency(queue); - EXPECT_EQ(3, prefix->computeChainDataLength()); - EXPECT_EQ(6, queue.front()->computeChainDataLength()); - prefix = queue.split(1); - checkConsistency(queue); - EXPECT_EQ(1, prefix->computeChainDataLength()); - EXPECT_EQ(5, queue.front()->computeChainDataLength()); - prefix = queue.split(5); - checkConsistency(queue); - EXPECT_EQ(5, prefix->computeChainDataLength()); - EXPECT_EQ((IOBuf*)NULL, queue.front()); - - queue.append(stringToIOBuf(SCL("Hello,"))); - queue.append(stringToIOBuf(SCL(" World"))); - checkConsistency(queue); - bool exceptionFired = false; - EXPECT_THROW({prefix = queue.split(13);}, std::underflow_error); - checkConsistency(queue); -} - -TEST(IOBufQueue, Preallocate) { - IOBufQueue queue(clOptions); - queue.append(string("Hello")); - pair writable = queue.preallocate(2, 64, 64); - checkConsistency(queue); - EXPECT_NE((void*)NULL, writable.first); - EXPECT_LE(2, writable.second); - EXPECT_GE(64, writable.second); - memcpy(writable.first, SCL(", ")); - queue.postallocate(2); - checkConsistency(queue); - EXPECT_EQ(7, queue.front()->computeChainDataLength()); - queue.append(SCL("World")); - checkConsistency(queue); - EXPECT_EQ(12, queue.front()->computeChainDataLength()); - // There are not 2048 bytes available, this will alloc a new buf - writable = queue.preallocate(2048, 4096); - checkConsistency(queue); - EXPECT_LE(2048, writable.second); - // IOBuf allocates more than newAllocationSize, and we didn't cap it - EXPECT_GE(writable.second, 4096); - queue.postallocate(writable.second); - // queue has no empty space, make sure we allocate at least min, even if - // newAllocationSize < min - writable = queue.preallocate(1024, 1, 1024); - checkConsistency(queue); - EXPECT_EQ(1024, writable.second); -} - -TEST(IOBufQueue, Wrap) { - IOBufQueue queue(clOptions); - const char* buf = "hello world goodbye"; - size_t len = strlen(buf); - queue.wrapBuffer(buf, len, 6); - auto iob = queue.move(); - EXPECT_EQ((len - 1) / 6 + 1, iob->countChainElements()); - iob->unshare(); - iob->coalesce(); - EXPECT_EQ(StringPiece(buf), - StringPiece(reinterpret_cast(iob->data()), - iob->length())); -} - -TEST(IOBufQueue, trim) { - IOBufQueue queue(clOptions); - unique_ptr a = IOBuf::create(4); - a->append(4); - queue.append(std::move(a)); - checkConsistency(queue); - a = IOBuf::create(6); - a->append(6); - queue.append(std::move(a)); - checkConsistency(queue); - a = IOBuf::create(8); - a->append(8); - queue.append(std::move(a)); - checkConsistency(queue); - a = IOBuf::create(10); - a->append(10); - queue.append(std::move(a)); - checkConsistency(queue); - - EXPECT_EQ(4, queue.front()->countChainElements()); - EXPECT_EQ(28, queue.front()->computeChainDataLength()); - EXPECT_EQ(4, queue.front()->length()); - - queue.trimStart(1); - checkConsistency(queue); - EXPECT_EQ(4, queue.front()->countChainElements()); - EXPECT_EQ(27, queue.front()->computeChainDataLength()); - EXPECT_EQ(3, queue.front()->length()); - - queue.trimStart(5); - checkConsistency(queue); - EXPECT_EQ(3, queue.front()->countChainElements()); - EXPECT_EQ(22, queue.front()->computeChainDataLength()); - EXPECT_EQ(4, queue.front()->length()); - - queue.trimEnd(1); - checkConsistency(queue); - EXPECT_EQ(3, queue.front()->countChainElements()); - EXPECT_EQ(21, queue.front()->computeChainDataLength()); - EXPECT_EQ(9, queue.front()->prev()->length()); - - queue.trimEnd(20); - checkConsistency(queue); - EXPECT_EQ(1, queue.front()->countChainElements()); - EXPECT_EQ(1, queue.front()->computeChainDataLength()); - EXPECT_EQ(1, queue.front()->prev()->length()); - - queue.trimEnd(1); - checkConsistency(queue); - EXPECT_EQ(NULL, queue.front()); - - EXPECT_THROW(queue.trimStart(2), std::underflow_error); - checkConsistency(queue); - - EXPECT_THROW(queue.trimEnd(30), std::underflow_error); - checkConsistency(queue); -} - -TEST(IOBufQueue, Prepend) { - folly::IOBufQueue queue; - - auto buf = folly::IOBuf::create(10); - buf->advance(5); - queue.append(std::move(buf)); - - queue.append(SCL(" World")); - queue.prepend(SCL("Hello")); - - EXPECT_THROW(queue.prepend(SCL("x")), std::overflow_error); - - auto out = queue.move(); - out->coalesce(); - EXPECT_EQ("Hello World", - StringPiece(reinterpret_cast(out->data()), - out->length())); -} - -int main(int argc, char** argv) { - testing::InitGoogleTest(&argc, argv); - google::ParseCommandLineFlags(&argc, &argv, true); - - return RUN_ALL_TESTS(); -} diff --git a/folly/experimental/io/test/IOBufTest.cpp b/folly/experimental/io/test/IOBufTest.cpp deleted file mode 100644 index f6f6fe28..00000000 --- a/folly/experimental/io/test/IOBufTest.cpp +++ /dev/null @@ -1,759 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "folly/experimental/io/IOBuf.h" -#include "folly/experimental/io/TypedIOBuf.h" - -// googletest requires std::tr1::tuple, not std::tuple -#include - -#include -#include -#include - -#include "folly/Malloc.h" -#include "folly/Range.h" - -using folly::fbstring; -using folly::IOBuf; -using folly::TypedIOBuf; -using folly::StringPiece; -using std::unique_ptr; - -void append(std::unique_ptr& buf, StringPiece str) { - EXPECT_LE(str.size(), buf->tailroom()); - memcpy(buf->writableData(), str.data(), str.size()); - buf->append(str.size()); -} - -void prepend(std::unique_ptr& buf, StringPiece str) { - EXPECT_LE(str.size(), buf->headroom()); - memcpy(buf->writableData() - str.size(), str.data(), str.size()); - buf->prepend(str.size()); -} - -TEST(IOBuf, Simple) { - unique_ptr buf(IOBuf::create(100)); - uint32_t cap = buf->capacity(); - EXPECT_LE(100, cap); - EXPECT_EQ(0, buf->headroom()); - EXPECT_EQ(0, buf->length()); - EXPECT_EQ(cap, buf->tailroom()); - - append(buf, "world"); - buf->advance(10); - EXPECT_EQ(10, buf->headroom()); - EXPECT_EQ(5, buf->length()); - EXPECT_EQ(cap - 15, buf->tailroom()); - - prepend(buf, "hello "); - EXPECT_EQ(4, buf->headroom()); - EXPECT_EQ(11, buf->length()); - EXPECT_EQ(cap - 15, buf->tailroom()); - - const char* p = reinterpret_cast(buf->data()); - EXPECT_EQ("hello world", std::string(p, buf->length())); - - buf->clear(); - EXPECT_EQ(0, buf->headroom()); - EXPECT_EQ(0, buf->length()); - EXPECT_EQ(cap, buf->tailroom()); -} - - -void testAllocSize(uint32_t requestedCapacity) { - unique_ptr iobuf(IOBuf::create(requestedCapacity)); - EXPECT_GE(iobuf->capacity(), requestedCapacity); -} - -TEST(IOBuf, AllocSizes) { - // Try with a small allocation size that should fit in the internal buffer - testAllocSize(28); - - // Try with a large allocation size that will require an external buffer. - testAllocSize(9000); - - // 220 bytes is currently the cutoff - // (It would be nice to use the IOBuf::kMaxInternalDataSize constant, - // but it's private and it doesn't seem worth making it public just for this - // test code.) - testAllocSize(220); - testAllocSize(219); - testAllocSize(221); -} - -void deleteArrayBuffer(void *buf, void* arg) { - uint32_t* deleteCount = static_cast(arg); - ++(*deleteCount); - uint8_t* bufPtr = static_cast(buf); - delete[] bufPtr; -} - -TEST(IOBuf, TakeOwnership) { - uint32_t size1 = 99; - uint8_t *buf1 = static_cast(malloc(size1)); - unique_ptr iobuf1(IOBuf::takeOwnership(buf1, size1)); - EXPECT_EQ(buf1, iobuf1->data()); - EXPECT_EQ(size1, iobuf1->length()); - EXPECT_EQ(buf1, iobuf1->buffer()); - EXPECT_EQ(size1, iobuf1->capacity()); - - uint32_t deleteCount = 0; - uint32_t size2 = 4321; - uint8_t *buf2 = new uint8_t[size2]; - unique_ptr iobuf2(IOBuf::takeOwnership(buf2, size2, - deleteArrayBuffer, - &deleteCount)); - EXPECT_EQ(buf2, iobuf2->data()); - EXPECT_EQ(size2, iobuf2->length()); - EXPECT_EQ(buf2, iobuf2->buffer()); - EXPECT_EQ(size2, iobuf2->capacity()); - EXPECT_EQ(0, deleteCount); - iobuf2.reset(); - EXPECT_EQ(1, deleteCount); - - deleteCount = 0; - uint32_t size3 = 3456; - uint8_t *buf3 = new uint8_t[size3]; - uint32_t length3 = 48; - unique_ptr iobuf3(IOBuf::takeOwnership(buf3, size3, length3, - deleteArrayBuffer, - &deleteCount)); - EXPECT_EQ(buf3, iobuf3->data()); - EXPECT_EQ(length3, iobuf3->length()); - EXPECT_EQ(buf3, iobuf3->buffer()); - EXPECT_EQ(size3, iobuf3->capacity()); - EXPECT_EQ(0, deleteCount); - iobuf3.reset(); - EXPECT_EQ(1, deleteCount); - - -} - -TEST(IOBuf, WrapBuffer) { - const uint32_t size1 = 1234; - uint8_t buf1[size1]; - unique_ptr iobuf1(IOBuf::wrapBuffer(buf1, size1)); - EXPECT_EQ(buf1, iobuf1->data()); - EXPECT_EQ(size1, iobuf1->length()); - EXPECT_EQ(buf1, iobuf1->buffer()); - EXPECT_EQ(size1, iobuf1->capacity()); - - uint32_t size2 = 0x1234; - unique_ptr buf2(new uint8_t[size2]); - unique_ptr iobuf2(IOBuf::wrapBuffer(buf2.get(), size2)); - EXPECT_EQ(buf2.get(), iobuf2->data()); - EXPECT_EQ(size2, iobuf2->length()); - EXPECT_EQ(buf2.get(), iobuf2->buffer()); - EXPECT_EQ(size2, iobuf2->capacity()); -} - -void fillBuf(uint8_t* buf, uint32_t length, boost::mt19937& gen) { - for (uint32_t n = 0; n < length; ++n) { - buf[n] = static_cast(gen() & 0xff); - } -} - -void fillBuf(IOBuf* buf, boost::mt19937& gen) { - buf->unshare(); - fillBuf(buf->writableData(), buf->length(), gen); -} - -void checkBuf(const uint8_t* buf, uint32_t length, boost::mt19937& gen) { - // Rather than using EXPECT_EQ() to check each character, - // count the number of differences and the first character that differs. - // This way on error we'll report just that information, rather than tons of - // failed checks for each byte in the buffer. - uint32_t numDifferences = 0; - uint32_t firstDiffIndex = 0; - uint8_t firstDiffExpected = 0; - for (uint32_t n = 0; n < length; ++n) { - uint8_t expected = static_cast(gen() & 0xff); - if (buf[n] == expected) { - continue; - } - - if (numDifferences == 0) { - firstDiffIndex = n; - firstDiffExpected = expected; - } - ++numDifferences; - } - - EXPECT_EQ(0, numDifferences); - if (numDifferences > 0) { - // Cast to int so it will be printed numerically - // rather than as a char if the check fails - EXPECT_EQ(static_cast(buf[firstDiffIndex]), - static_cast(firstDiffExpected)); - } -} - -void checkBuf(IOBuf* buf, boost::mt19937& gen) { - checkBuf(buf->data(), buf->length(), gen); -} - -void checkChain(IOBuf* buf, boost::mt19937& gen) { - IOBuf *current = buf; - do { - checkBuf(current->data(), current->length(), gen); - current = current->next(); - } while (current != buf); -} - -TEST(IOBuf, Chaining) { - uint32_t fillSeed = 0x12345678; - boost::mt19937 gen(fillSeed); - - // An IOBuf with external storage - uint32_t headroom = 123; - unique_ptr iob1(IOBuf::create(2048)); - iob1->advance(headroom); - iob1->append(1500); - fillBuf(iob1.get(), gen); - - // An IOBuf with internal storage - unique_ptr iob2(IOBuf::create(20)); - iob2->append(20); - fillBuf(iob2.get(), gen); - - // An IOBuf around a buffer it doesn't own - uint8_t localbuf[1234]; - fillBuf(localbuf, 1234, gen); - unique_ptr iob3(IOBuf::wrapBuffer(localbuf, sizeof(localbuf))); - - // An IOBuf taking ownership of a user-supplied buffer - uint32_t heapBufSize = 900; - uint8_t* heapBuf = static_cast(malloc(heapBufSize)); - fillBuf(heapBuf, heapBufSize, gen); - unique_ptr iob4(IOBuf::takeOwnership(heapBuf, heapBufSize)); - - // An IOBuf taking ownership of a user-supplied buffer with - // a custom free function - uint32_t arrayBufSize = 321; - uint8_t* arrayBuf = new uint8_t[arrayBufSize]; - fillBuf(arrayBuf, arrayBufSize, gen); - uint32_t arrayBufFreeCount = 0; - unique_ptr iob5(IOBuf::takeOwnership(arrayBuf, arrayBufSize, - deleteArrayBuffer, - &arrayBufFreeCount)); - - EXPECT_FALSE(iob1->isChained()); - EXPECT_FALSE(iob2->isChained()); - EXPECT_FALSE(iob3->isChained()); - EXPECT_FALSE(iob4->isChained()); - EXPECT_FALSE(iob5->isChained()); - - EXPECT_FALSE(iob1->isSharedOne()); - EXPECT_FALSE(iob2->isSharedOne()); - EXPECT_TRUE(iob3->isSharedOne()); // since we own the buffer - EXPECT_FALSE(iob4->isSharedOne()); - EXPECT_FALSE(iob5->isSharedOne()); - - // Chain the buffers all together - // Since we are going to relinquish ownership of iob2-5 to the chain, - // store raw pointers to them so we can reference them later. - IOBuf* iob2ptr = iob2.get(); - IOBuf* iob3ptr = iob3.get(); - IOBuf* iob4ptr = iob4.get(); - IOBuf* iob5ptr = iob5.get(); - - iob1->prependChain(std::move(iob2)); - iob1->prependChain(std::move(iob4)); - iob2ptr->appendChain(std::move(iob3)); - iob1->prependChain(std::move(iob5)); - - EXPECT_EQ(iob2ptr, iob1->next()); - EXPECT_EQ(iob3ptr, iob2ptr->next()); - EXPECT_EQ(iob4ptr, iob3ptr->next()); - EXPECT_EQ(iob5ptr, iob4ptr->next()); - EXPECT_EQ(iob1.get(), iob5ptr->next()); - - EXPECT_EQ(iob5ptr, iob1->prev()); - EXPECT_EQ(iob1.get(), iob2ptr->prev()); - EXPECT_EQ(iob2ptr, iob3ptr->prev()); - EXPECT_EQ(iob3ptr, iob4ptr->prev()); - EXPECT_EQ(iob4ptr, iob5ptr->prev()); - - EXPECT_TRUE(iob1->isChained()); - EXPECT_TRUE(iob2ptr->isChained()); - EXPECT_TRUE(iob3ptr->isChained()); - EXPECT_TRUE(iob4ptr->isChained()); - EXPECT_TRUE(iob5ptr->isChained()); - - uint64_t fullLength = (iob1->length() + iob2ptr->length() + - iob3ptr->length() + iob4ptr->length() + - iob5ptr->length()); - EXPECT_EQ(5, iob1->countChainElements()); - EXPECT_EQ(fullLength, iob1->computeChainDataLength()); - - // Since iob3 is shared, the entire buffer should report itself as shared - EXPECT_TRUE(iob1->isShared()); - // Unshare just iob3 - iob3ptr->unshareOne(); - EXPECT_FALSE(iob3ptr->isSharedOne()); - // Now everything in the chain should be unshared. - // Check on all members of the chain just for good measure - EXPECT_FALSE(iob1->isShared()); - EXPECT_FALSE(iob2ptr->isShared()); - EXPECT_FALSE(iob3ptr->isShared()); - EXPECT_FALSE(iob4ptr->isShared()); - EXPECT_FALSE(iob5ptr->isShared()); - - - // Clone one of the IOBufs in the chain - unique_ptr iob4clone = iob4ptr->cloneOne(); - gen.seed(fillSeed); - checkBuf(iob1.get(), gen); - checkBuf(iob2ptr, gen); - checkBuf(iob3ptr, gen); - checkBuf(iob4clone.get(), gen); - checkBuf(iob5ptr, gen); - - EXPECT_TRUE(iob1->isShared()); - EXPECT_TRUE(iob2ptr->isShared()); - EXPECT_TRUE(iob3ptr->isShared()); - EXPECT_TRUE(iob4ptr->isShared()); - EXPECT_TRUE(iob5ptr->isShared()); - - EXPECT_FALSE(iob1->isSharedOne()); - EXPECT_FALSE(iob2ptr->isSharedOne()); - EXPECT_FALSE(iob3ptr->isSharedOne()); - EXPECT_TRUE(iob4ptr->isSharedOne()); - EXPECT_FALSE(iob5ptr->isSharedOne()); - - // Unshare that clone - EXPECT_TRUE(iob4clone->isSharedOne()); - iob4clone->unshare(); - EXPECT_FALSE(iob4clone->isSharedOne()); - EXPECT_FALSE(iob4ptr->isSharedOne()); - EXPECT_FALSE(iob1->isShared()); - iob4clone.reset(); - - - // Create a clone of a different IOBuf - EXPECT_FALSE(iob1->isShared()); - EXPECT_FALSE(iob3ptr->isSharedOne()); - - unique_ptr iob3clone = iob3ptr->cloneOne(); - gen.seed(fillSeed); - checkBuf(iob1.get(), gen); - checkBuf(iob2ptr, gen); - checkBuf(iob3clone.get(), gen); - checkBuf(iob4ptr, gen); - checkBuf(iob5ptr, gen); - - EXPECT_TRUE(iob1->isShared()); - EXPECT_TRUE(iob3ptr->isSharedOne()); - EXPECT_FALSE(iob1->isSharedOne()); - - // Delete the clone and make sure the original is unshared - iob3clone.reset(); - EXPECT_FALSE(iob1->isShared()); - EXPECT_FALSE(iob3ptr->isSharedOne()); - - - // Clone the entire chain - unique_ptr chainClone = iob1->clone(); - // Verify that the data is correct. - EXPECT_EQ(fullLength, chainClone->computeChainDataLength()); - gen.seed(fillSeed); - checkChain(chainClone.get(), gen); - - // Check that the buffers report sharing correctly - EXPECT_TRUE(chainClone->isShared()); - EXPECT_TRUE(iob1->isShared()); - - EXPECT_TRUE(iob1->isSharedOne()); - // since iob2 has a small internal buffer, it will never be shared - EXPECT_FALSE(iob2ptr->isSharedOne()); - EXPECT_TRUE(iob3ptr->isSharedOne()); - EXPECT_TRUE(iob4ptr->isSharedOne()); - EXPECT_TRUE(iob5ptr->isSharedOne()); - - // Unshare the cloned chain - chainClone->unshare(); - EXPECT_FALSE(chainClone->isShared()); - EXPECT_FALSE(iob1->isShared()); - - // Make sure the unshared result still has the same data - EXPECT_EQ(fullLength, chainClone->computeChainDataLength()); - gen.seed(fillSeed); - checkChain(chainClone.get(), gen); - - // Destroy this chain - chainClone.reset(); - - - // Clone a new chain - EXPECT_FALSE(iob1->isShared()); - chainClone = iob1->clone(); - EXPECT_TRUE(iob1->isShared()); - EXPECT_TRUE(chainClone->isShared()); - - // Delete the original chain - iob1.reset(); - EXPECT_FALSE(chainClone->isShared()); - - // Coalesce the chain - // - // Coalescing this chain will create a new buffer and release the last - // refcount on the original buffers we created. Also make sure - // that arrayBufFreeCount increases to one to indicate that arrayBuf was - // freed. - EXPECT_EQ(5, chainClone->countChainElements()); - EXPECT_EQ(0, arrayBufFreeCount); - - // Buffer lengths: 1500 20 1234 900 321 - // Coalesce the first 3 buffers - chainClone->gather(1521); - EXPECT_EQ(3, chainClone->countChainElements()); - EXPECT_EQ(0, arrayBufFreeCount); - - // Make sure the data is still the same after coalescing - EXPECT_EQ(fullLength, chainClone->computeChainDataLength()); - gen.seed(fillSeed); - checkChain(chainClone.get(), gen); - - // Coalesce the entire chain - chainClone->coalesce(); - EXPECT_EQ(1, chainClone->countChainElements()); - EXPECT_EQ(1, arrayBufFreeCount); - - // Make sure the data is still the same after coalescing - EXPECT_EQ(fullLength, chainClone->computeChainDataLength()); - gen.seed(fillSeed); - checkChain(chainClone.get(), gen); - - // Make a new chain to test the unlink and pop operations - iob1 = IOBuf::create(1); - iob1->append(1); - IOBuf *iob1ptr = iob1.get(); - iob2 = IOBuf::create(3); - iob2->append(3); - iob2ptr = iob2.get(); - iob3 = IOBuf::create(5); - iob3->append(5); - iob3ptr = iob3.get(); - iob4 = IOBuf::create(7); - iob4->append(7); - iob4ptr = iob4.get(); - iob1->appendChain(std::move(iob2)); - iob1->prev()->appendChain(std::move(iob3)); - iob1->prev()->appendChain(std::move(iob4)); - EXPECT_EQ(4, iob1->countChainElements()); - EXPECT_EQ(16, iob1->computeChainDataLength()); - - // Unlink from the middle of the chain - iob3 = iob3ptr->unlink(); - EXPECT_TRUE(iob3.get() == iob3ptr); - EXPECT_EQ(3, iob1->countChainElements()); - EXPECT_EQ(11, iob1->computeChainDataLength()); - - // Unlink from the end of the chain - iob4 = iob1->prev()->unlink(); - EXPECT_TRUE(iob4.get() == iob4ptr); - EXPECT_EQ(2, iob1->countChainElements()); - EXPECT_TRUE(iob1->next() == iob2ptr); - EXPECT_EQ(4, iob1->computeChainDataLength()); - - // Pop from the front of the chain - iob2 = iob1->pop(); - EXPECT_TRUE(iob1.get() == iob1ptr); - EXPECT_EQ(1, iob1->countChainElements()); - EXPECT_EQ(1, iob1->computeChainDataLength()); - EXPECT_TRUE(iob2.get() == iob2ptr); - EXPECT_EQ(1, iob2->countChainElements()); - EXPECT_EQ(3, iob2->computeChainDataLength()); -} - -TEST(IOBuf, Reserve) { - uint32_t fillSeed = 0x23456789; - boost::mt19937 gen(fillSeed); - - // Reserve does nothing if empty and doesn't have to grow the buffer - { - gen.seed(fillSeed); - unique_ptr iob(IOBuf::create(2000)); - EXPECT_EQ(0, iob->headroom()); - const void* p1 = iob->buffer(); - iob->reserve(5, 15); - EXPECT_LE(5, iob->headroom()); - EXPECT_EQ(p1, iob->buffer()); - } - - // Reserve doesn't reallocate if we have enough total room - { - gen.seed(fillSeed); - unique_ptr iob(IOBuf::create(2000)); - iob->append(100); - fillBuf(iob.get(), gen); - EXPECT_EQ(0, iob->headroom()); - EXPECT_EQ(100, iob->length()); - const void* p1 = iob->buffer(); - const uint8_t* d1 = iob->data(); - iob->reserve(100, 1800); - EXPECT_LE(100, iob->headroom()); - EXPECT_EQ(p1, iob->buffer()); - EXPECT_EQ(d1 + 100, iob->data()); - gen.seed(fillSeed); - checkBuf(iob.get(), gen); - } - - // Reserve reallocates if we don't have enough total room. - // NOTE that, with jemalloc, we know that this won't reallocate in place - // as the size is less than jemallocMinInPlaceExpanadable - { - gen.seed(fillSeed); - unique_ptr iob(IOBuf::create(2000)); - iob->append(100); - fillBuf(iob.get(), gen); - EXPECT_EQ(0, iob->headroom()); - EXPECT_EQ(100, iob->length()); - const void* p1 = iob->buffer(); - const uint8_t* d1 = iob->data(); - iob->reserve(100, 2512); // allocation sizes are multiples of 256 - EXPECT_LE(100, iob->headroom()); - if (folly::usingJEMalloc()) { - EXPECT_NE(p1, iob->buffer()); - } - gen.seed(fillSeed); - checkBuf(iob.get(), gen); - } - - // Test reserve from internal buffer, this used to segfault - { - unique_ptr iob(IOBuf::create(0)); - iob->reserve(0, 2000); - EXPECT_EQ(0, iob->headroom()); - EXPECT_LE(2000, iob->tailroom()); - } -} - -TEST(IOBuf, copyBuffer) { - std::string s("hello"); - auto buf = IOBuf::copyBuffer(s.data(), s.size(), 1, 2); - EXPECT_EQ(1, buf->headroom()); - EXPECT_EQ(s, std::string(reinterpret_cast(buf->data()), - buf->length())); - EXPECT_LE(2, buf->tailroom()); - - buf = IOBuf::copyBuffer(s, 5, 7); - EXPECT_EQ(5, buf->headroom()); - EXPECT_EQ(s, std::string(reinterpret_cast(buf->data()), - buf->length())); - EXPECT_LE(7, buf->tailroom()); - - std::string empty; - buf = IOBuf::copyBuffer(empty, 3, 6); - EXPECT_EQ(3, buf->headroom()); - EXPECT_EQ(0, buf->length()); - EXPECT_LE(6, buf->tailroom()); -} - -TEST(IOBuf, maybeCopyBuffer) { - std::string s("this is a test"); - auto buf = IOBuf::maybeCopyBuffer(s, 1, 2); - EXPECT_EQ(1, buf->headroom()); - EXPECT_EQ(s, std::string(reinterpret_cast(buf->data()), - buf->length())); - EXPECT_LE(2, buf->tailroom()); - - std::string empty; - buf = IOBuf::maybeCopyBuffer("", 5, 7); - EXPECT_EQ(nullptr, buf.get()); - - buf = IOBuf::maybeCopyBuffer(""); - EXPECT_EQ(nullptr, buf.get()); -} - -namespace { - -int customDeleterCount = 0; -int destructorCount = 0; -struct OwnershipTestClass { - explicit OwnershipTestClass(int v = 0) : val(v) { } - ~OwnershipTestClass() { - ++destructorCount; - } - int val; -}; - -typedef std::function CustomDeleter; - -void customDelete(OwnershipTestClass* p) { - ++customDeleterCount; - delete p; -} - -void customDeleteArray(OwnershipTestClass* p) { - ++customDeleterCount; - delete[] p; -} - -} // namespace - -TEST(IOBuf, takeOwnershipUniquePtr) { - destructorCount = 0; - { - std::unique_ptr p(new OwnershipTestClass()); - } - EXPECT_EQ(1, destructorCount); - - destructorCount = 0; - { - std::unique_ptr p(new OwnershipTestClass[2]); - } - EXPECT_EQ(2, destructorCount); - - destructorCount = 0; - { - std::unique_ptr p(new OwnershipTestClass()); - std::unique_ptr buf(IOBuf::takeOwnership(std::move(p))); - EXPECT_EQ(sizeof(OwnershipTestClass), buf->length()); - EXPECT_EQ(0, destructorCount); - } - EXPECT_EQ(1, destructorCount); - - destructorCount = 0; - { - std::unique_ptr p(new OwnershipTestClass[2]); - std::unique_ptr buf(IOBuf::takeOwnership(std::move(p), 2)); - EXPECT_EQ(2 * sizeof(OwnershipTestClass), buf->length()); - EXPECT_EQ(0, destructorCount); - } - EXPECT_EQ(2, destructorCount); - - customDeleterCount = 0; - destructorCount = 0; - { - std::unique_ptr - p(new OwnershipTestClass(), customDelete); - std::unique_ptr buf(IOBuf::takeOwnership(std::move(p))); - EXPECT_EQ(sizeof(OwnershipTestClass), buf->length()); - EXPECT_EQ(0, destructorCount); - } - EXPECT_EQ(1, destructorCount); - EXPECT_EQ(1, customDeleterCount); - - customDeleterCount = 0; - destructorCount = 0; - { - std::unique_ptr - p(new OwnershipTestClass[2], customDeleteArray); - std::unique_ptr buf(IOBuf::takeOwnership(std::move(p), 2)); - EXPECT_EQ(2 * sizeof(OwnershipTestClass), buf->length()); - EXPECT_EQ(0, destructorCount); - } - EXPECT_EQ(2, destructorCount); - EXPECT_EQ(1, customDeleterCount); -} - -TEST(IOBuf, Alignment) { - // max_align_t doesn't exist in gcc 4.6.2 - struct MaxAlign { - char c; - } __attribute__((aligned)); - size_t alignment = alignof(MaxAlign); - - std::vector sizes {0, 1, 64, 256, 1024, 1 << 10}; - for (size_t size : sizes) { - auto buf = IOBuf::create(size); - uintptr_t p = reinterpret_cast(buf->data()); - EXPECT_EQ(0, p & (alignment - 1)) << "size=" << size; - } -} - -TEST(TypedIOBuf, Simple) { - auto buf = IOBuf::create(0); - TypedIOBuf typed(buf.get()); - const uint64_t n = 10000; - typed.reserve(0, n); - EXPECT_LE(n, typed.capacity()); - for (uint64_t i = 0; i < n; i++) { - *typed.writableTail() = i; - typed.append(1); - } - EXPECT_EQ(n, typed.length()); - for (uint64_t i = 0; i < n; i++) { - EXPECT_EQ(i, typed.data()[i]); - } -} - -// chain element size, number of elements in chain, shared -class MoveToFbStringTest - : public ::testing::TestWithParam> { - protected: - void SetUp() { - std::tr1::tie(elementSize_, elementCount_, shared_) = GetParam(); - buf_ = makeBuf(); - for (int i = 0; i < elementCount_ - 1; ++i) { - buf_->prependChain(makeBuf()); - } - EXPECT_EQ(elementCount_, buf_->countChainElements()); - EXPECT_EQ(elementCount_ * elementSize_, buf_->computeChainDataLength()); - if (shared_) { - buf2_ = buf_->clone(); - EXPECT_EQ(elementCount_, buf2_->countChainElements()); - EXPECT_EQ(elementCount_ * elementSize_, buf2_->computeChainDataLength()); - } - } - - std::unique_ptr makeBuf() { - auto buf = IOBuf::create(elementSize_); - memset(buf->writableTail(), 'x', elementSize_); - buf->append(elementSize_); - return buf; - } - - void check(std::unique_ptr& buf) { - fbstring str = buf->moveToFbString(); - EXPECT_EQ(elementCount_ * elementSize_, str.size()); - EXPECT_EQ(elementCount_ * elementSize_, strspn(str.c_str(), "x")); - EXPECT_EQ(0, buf->length()); - EXPECT_EQ(1, buf->countChainElements()); - EXPECT_EQ(0, buf->computeChainDataLength()); - EXPECT_FALSE(buf->isChained()); - } - - int elementSize_; - int elementCount_; - bool shared_; - std::unique_ptr buf_; - std::unique_ptr buf2_; -}; - -TEST_P(MoveToFbStringTest, Simple) { - check(buf_); - if (shared_) { - check(buf2_); - } -} - -INSTANTIATE_TEST_CASE_P( - MoveToFbString, - MoveToFbStringTest, - ::testing::Combine( - ::testing::Values(0, 1, 24, 256, 1 << 10, 1 << 20), // element size - ::testing::Values(1, 2, 10), // element count - ::testing::Bool())); // shared - -int main(int argc, char** argv) { - testing::InitGoogleTest(&argc, argv); - google::ParseCommandLineFlags(&argc, &argv, true); - - return RUN_ALL_TESTS(); -} diff --git a/folly/experimental/io/test/NetworkBenchmark.cpp b/folly/experimental/io/test/NetworkBenchmark.cpp deleted file mode 100644 index 9b8fea72..00000000 --- a/folly/experimental/io/test/NetworkBenchmark.cpp +++ /dev/null @@ -1,172 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "folly/experimental/io/IOBuf.h" - -#include -#include "folly/Benchmark.h" -#include "folly/experimental/io/Cursor.h" - -#include - -using folly::IOBuf; -using std::unique_ptr; -using namespace folly::io; -using namespace std; - -size_t buf_size = 0; -size_t num_bufs = 0; - -BENCHMARK(reserveBenchmark, iters) { - while (--iters) { - unique_ptr iobuf1(IOBuf::create(buf_size)); - iobuf1->append(buf_size); - for (size_t bufs = num_bufs; bufs > 1; bufs --) { - iobuf1->reserve(0, buf_size); - iobuf1->append(buf_size); - } - } -} - -BENCHMARK(chainBenchmark, iters) { - while (--iters) { - unique_ptr iobuf1(IOBuf::create(buf_size)); - iobuf1->append(buf_size); - for (size_t bufs = num_bufs; bufs > 1; bufs --) { - unique_ptr iobufNext(IOBuf::create(buf_size)); - iobuf1->prependChain(std::move(iobufNext)); - } - } -} - -vector> bufPool; -inline unique_ptr poolGetIOBuf() { - if (bufPool.size() > 0) { - unique_ptr ret = std::move(bufPool.back()); - bufPool.pop_back(); - return std::move(ret); - } else { - unique_ptr iobuf(IOBuf::create(buf_size)); - iobuf->append(buf_size); - return std::move(iobuf); - } -} - -inline void poolPutIOBuf(unique_ptr&& buf) { - unique_ptr head = std::move(buf); - while (head) { - unique_ptr next = std::move(head->pop()); - bufPool.push_back(std::move(head)); - head = std::move(next); - } -} - -BENCHMARK(poolBenchmark, iters) { - while (--iters) { - unique_ptr head = std::move(poolGetIOBuf()); - for (size_t bufs = num_bufs; bufs > 1; bufs --) { - unique_ptr iobufNext = std::move(poolGetIOBuf()); - head->prependChain(std::move(iobufNext)); - } - // cleanup - poolPutIOBuf(std::move(head)); - } -} - -void setNumbers(size_t size, size_t num) { - buf_size = size; - num_bufs = num; - bufPool.clear(); - - printf("\nBuffer size: %zu, number of buffers: %zu\n\n", size, num); -} - -/* ------------------------------------------------------------------------------- -reserveBenchmark 100000 9.186 ms 91.86 ns 10.38 M -chainBenchmark 100000 59.44 ms 594.4 ns 1.604 M -poolBenchmark 100000 15.87 ms 158.7 ns 6.01 M - -Buffer size: 100, number of buffers: 10 - -Benchmark Iters Total t t/iter iter/sec ------------------------------------------------------------------------------- -reserveBenchmark 100000 62 ms 620 ns 1.538 M -chainBenchmark 100000 59.48 ms 594.8 ns 1.603 M -poolBenchmark 100000 16.07 ms 160.7 ns 5.933 M - -Buffer size: 2048, number of buffers: 10 - -Benchmark Iters Total t t/iter iter/sec ------------------------------------------------------------------------------- -reserveBenchmark 100000 148.4 ms 1.484 us 658.2 k -chainBenchmark 100000 140.9 ms 1.409 us 693 k -poolBenchmark 100000 16.73 ms 167.3 ns 5.7 M - -Buffer size: 10000, number of buffers: 10 - -Benchmark Iters Total t t/iter iter/sec ------------------------------------------------------------------------------- -reserveBenchmark 100000 234 ms 2.34 us 417.3 k -chainBenchmark 100000 142.3 ms 1.423 us 686.1 k -poolBenchmark 100000 16.78 ms 167.8 ns 5.684 M - -Buffer size: 100000, number of buffers: 10 - -Benchmark Iters Total t t/iter iter/sec ------------------------------------------------------------------------------- -reserveBenchmark 100000 186.5 ms 1.865 us 523.5 k -chainBenchmark 100000 360.5 ms 3.605 us 270.9 k -poolBenchmark 100000 16.52 ms 165.2 ns 5.772 M - -Buffer size: 1000000, number of buffers: 10 - -Benchmark Iters Total t t/iter iter/sec ------------------------------------------------------------------------------- -reserveBenchmark 156 2.084 s 13.36 ms 74.84 -chainBenchmark 30082 2.001 s 66.5 us 14.68 k -poolBenchmark 100000 18.18 ms 181.8 ns 5.244 M - - -Buffer size: 10, number of buffers: 20 - -Benchmark Iters Total t t/iter iter/sec ------------------------------------------------------------------------------- -reserveBenchmark 100000 12.54 ms 125.4 ns 7.603 M -chainBenchmark 100000 118.6 ms 1.186 us 823.2 k -poolBenchmark 100000 32.2 ms 322 ns 2.962 M -*/ -int main(int argc, char** argv) { - google::ParseCommandLineFlags(&argc, &argv, true); - - setNumbers(10, 10); - folly::runBenchmarks(); - setNumbers(100, 10); - folly::runBenchmarks(); - setNumbers(2048, 10); - folly::runBenchmarks(); - setNumbers(10000, 10); - folly::runBenchmarks(); - setNumbers(100000, 10); - folly::runBenchmarks(); - setNumbers(1000000, 10); - folly::runBenchmarks(); - - setNumbers(10, 20); - folly::runBenchmarks(); - - return 0; -} diff --git a/folly/experimental/io/test/StreamTest.cpp b/folly/experimental/io/test/StreamTest.cpp deleted file mode 100644 index f0d3603a..00000000 --- a/folly/experimental/io/test/StreamTest.cpp +++ /dev/null @@ -1,117 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "folly/experimental/io/Stream.h" - -#include -#include - -#include -#include - -#include "folly/Benchmark.h" -#include "folly/experimental/TestUtil.h" - -using namespace folly; - -namespace { - -std::vector streamSplit(const std::string& str, char delimiter, - size_t maxChunkSize = (size_t)-1) { - size_t pos = 0; - auto cb = [&] (ByteRange& sp) mutable -> bool { - if (pos == str.size()) return false; - size_t n = std::min(str.size() - pos, maxChunkSize); - sp.reset(reinterpret_cast(&(str[pos])), n); - pos += n; - return true; - }; - - std::vector result; - for (auto line : makeInputByteStreamSplitter(delimiter, cb)) { - result.push_back(StringPiece(line).str()); - } - - return result; -} - -} // namespace - -TEST(InputByteStreamSplitter, Empty) { - { - auto pieces = streamSplit("", ','); - EXPECT_EQ(0, pieces.size()); - } - - // The last delimiter is eaten, just like std::getline - { - auto pieces = streamSplit(",", ','); - EXPECT_EQ(1, pieces.size()); - EXPECT_EQ("", pieces[0]); - } - - { - auto pieces = streamSplit(",,", ','); - EXPECT_EQ(2, pieces.size()); - EXPECT_EQ("", pieces[0]); - EXPECT_EQ("", pieces[1]); - } -} - -TEST(InputByteStreamSplitter, Simple) { - std::string str = "hello,, world, goodbye, meow"; - - for (size_t chunkSize = 1; chunkSize <= str.size(); ++chunkSize) { - auto pieces = streamSplit(str, ',', chunkSize); - EXPECT_EQ(5, pieces.size()); - EXPECT_EQ("hello", pieces[0]); - EXPECT_EQ("", pieces[1]); - EXPECT_EQ(" world", pieces[2]); - EXPECT_EQ(" goodbye", pieces[3]); - EXPECT_EQ(" meow", pieces[4]); - } -} - -TEST(ByLine, Simple) { - test::TemporaryFile file("ByLine"); - static const std::string lines( - "Hello world\n" - "This is the second line\n" - "\n" - "\n" - "a few empty lines above\n" - "incomplete last line"); - EXPECT_EQ(lines.size(), write(file.fd(), lines.data(), lines.size())); - - auto expected = streamSplit(lines, '\n'); - std::vector found; - for (auto& line : byLine(file.path())) { - found.push_back(StringPiece(line).str()); - } - - EXPECT_TRUE(expected == found); -} - -int main(int argc, char *argv[]) { - testing::InitGoogleTest(&argc, argv); - google::ParseCommandLineFlags(&argc, &argv, true); - auto ret = RUN_ALL_TESTS(); - if (!ret) { - folly::runBenchmarksOnFlag(); - } - return ret; -} - diff --git a/folly/experimental/symbolizer/SymbolizerTest.cpp b/folly/experimental/symbolizer/SymbolizerTest.cpp deleted file mode 100644 index 0eff9389..00000000 --- a/folly/experimental/symbolizer/SymbolizerTest.cpp +++ /dev/null @@ -1,36 +0,0 @@ -/* - * Copyright 2013 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - - - -#include "folly/experimental/symbolizer/Symbolizer.h" - -#include - -using namespace folly; -using namespace folly::symbolizer; - -int main(int argc, char *argv[]) { - google::InitGoogleLogging(argv[0]); - Symbolizer s; - StringPiece name; - Dwarf::LocationInfo location; - CHECK(s.symbolize(reinterpret_cast(main), name, location)); - LOG(INFO) << name << " " << location.file << " " << location.line << " (" - << location.mainFile << ")"; - return 0; -} - diff --git a/folly/experimental/test/FileTest.cpp b/folly/experimental/test/FileTest.cpp deleted file mode 100644 index 6d2dee13..00000000 --- a/folly/experimental/test/FileTest.cpp +++ /dev/null @@ -1,86 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "folly/experimental/File.h" - -#include -#include - -#include "folly/Benchmark.h" -#include "folly/String.h" - -using namespace folly; - -namespace { -void expectWouldBlock(ssize_t r) { - int savedErrno = errno; - EXPECT_EQ(-1, r); - EXPECT_EQ(EAGAIN, savedErrno) << errnoStr(errno); -} -void expectOK(ssize_t r) { - int savedErrno = errno; - EXPECT_LE(0, r) << ": errno=" << errnoStr(errno); -} -} // namespace - -TEST(File, Simple) { - // Open a file, ensure it's indeed open for reading - char buf = 'x'; - { - File f("/etc/hosts"); - EXPECT_NE(-1, f.fd()); - EXPECT_EQ(1, ::read(f.fd(), &buf, 1)); - f.close(); - EXPECT_EQ(-1, f.fd()); - } -} - -TEST(File, OwnsFd) { - // Wrap a file descriptor, make sure that ownsFd works - // We'll test that the file descriptor is closed by closing the writing - // end of a pipe and making sure that a non-blocking read from the reading - // end returns 0. - - char buf = 'x'; - int p[2]; - expectOK(::pipe(p)); - int flags = ::fcntl(p[0], F_GETFL); - expectOK(flags); - expectOK(::fcntl(p[0], F_SETFL, flags | O_NONBLOCK)); - expectWouldBlock(::read(p[0], &buf, 1)); - { - File f(p[1]); - EXPECT_EQ(p[1], f.fd()); - } - // Ensure that moving the file doesn't close it - { - File f(p[1]); - EXPECT_EQ(p[1], f.fd()); - File f1(std::move(f)); - EXPECT_EQ(-1, f.fd()); - EXPECT_EQ(p[1], f1.fd()); - } - expectWouldBlock(::read(p[0], &buf, 1)); // not closed - { - File f(p[1], true); - EXPECT_EQ(p[1], f.fd()); - } - ssize_t r = ::read(p[0], &buf, 1); // eof - expectOK(r); - EXPECT_EQ(0, r); - ::close(p[0]); -} - diff --git a/folly/test/EventFDTest.cpp b/folly/test/EventFDTest.cpp deleted file mode 100644 index c0259fe8..00000000 --- a/folly/test/EventFDTest.cpp +++ /dev/null @@ -1,73 +0,0 @@ -/* - * Copyright 2013 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include -#include -#include "folly/eventfd.h" -#include - -using namespace folly; - -TEST(EventFD, Basic) { - int fd = eventfd(10, EFD_NONBLOCK); - CHECK_ERR(fd); - uint64_t val; - ssize_t r; - // Running this twice -- once with the initial value, and once - // after a write() - for (int attempt = 0; attempt < 2; attempt++) { - val = 0; - r = read(fd, &val, sizeof(val)); - CHECK_ERR(r); - EXPECT_EQ(sizeof(val), r); - EXPECT_EQ(10, val); - r = read(fd, &val, sizeof(val)); - EXPECT_EQ(-1, r); - EXPECT_EQ(EAGAIN, errno); - val = 10; - r = write(fd, &val, sizeof(val)); - CHECK_ERR(r); - EXPECT_EQ(sizeof(val), r); - } - close(fd); -} - -TEST(EventFD, Semaphore) { - int fd = eventfd(10, EFD_NONBLOCK | EFD_SEMAPHORE); - CHECK_ERR(fd); - uint64_t val; - ssize_t r; - // Running this twice -- once with the initial value, and once - // after a write() - for (int attempt = 0; attempt < 2; attempt++) { - val = 0; - for (int i = 0; i < 10; i++) { - r = read(fd, &val, sizeof(val)); - CHECK_ERR(r); - EXPECT_EQ(sizeof(val), r); - EXPECT_EQ(1, val); - } - r = read(fd, &val, sizeof(val)); - EXPECT_EQ(-1, r); - EXPECT_EQ(EAGAIN, errno); - val = 10; - r = write(fd, &val, sizeof(val)); - CHECK_ERR(r); - EXPECT_EQ(sizeof(val), r); - } - close(fd); -} - diff --git a/folly/test/FBStringLibstdcxxStdexceptTest.cpp b/folly/test/FBStringLibstdcxxStdexceptTest.cpp deleted file mode 100644 index 816083cb..00000000 --- a/folly/test/FBStringLibstdcxxStdexceptTest.cpp +++ /dev/null @@ -1,24 +0,0 @@ -/* - * Copyright 2013 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#include "folly/FBString.h" - -#ifdef _GLIBCXX_STDEXCEPT -#error Cannot include in FBString.h\ - (use std::__throw_* from funcexcept.h instead) -#endif - -int main(){} diff --git a/folly/test/SpookyHashTest.cpp b/folly/test/SpookyHashTest.cpp deleted file mode 100644 index 928e5277..00000000 --- a/folly/test/SpookyHashTest.cpp +++ /dev/null @@ -1,530 +0,0 @@ -/* - * Copyright 2012 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -// SpookyHash: a 128-bit noncryptographic hash function -// By Bob Jenkins, public domain -#include "folly/SpookyHash.h" - -#include -#include -#include -#include -#include - -using namespace ::folly::hash; - -static bool failed = false; - -static uint64_t GetTickCount() { - timespec ts; - clock_gettime(CLOCK_REALTIME, &ts); - return ts.tv_sec * 1000 + ts.tv_nsec / 1000000; // milliseconds -} - -class Random -{ -public: - inline uint64_t Value() - { - uint64_t e = m_a - Rot64(m_b, 23); - m_a = m_b ^ Rot64(m_c, 16); - m_b = m_c + Rot64(m_d, 11); - m_c = m_d + e; - m_d = e + m_a; - return m_d; - } - - inline void Init( uint64_t seed) - { - m_a = 0xdeadbeef; - m_b = m_c = m_d = seed; - for (int i=0; i<20; ++i) - (void)Value(); - } - -private: - static inline uint64_t Rot64(uint64_t x, int k) - { - return (x << k) | (x >> (64-(k))); - } - - uint64_t m_a; - uint64_t m_b; - uint64_t m_c; - uint64_t m_d; -}; - -// fastest conceivable hash function (for comparison) -static void Add(const void *data, size_t length, uint64_t *hash1, uint64_t *hash2) -{ - uint64_t *p64 = (uint64_t *)data; - uint64_t *end = p64 + length/8; - uint64_t hash = *hash1 + *hash2; - while (p64 < end) - { - hash += *p64; - ++p64; - } - *hash1 = hash; - *hash2 = hash; -} - -#define BUFSIZE (512) -void TestResults() -{ - printf("\ntesting results ...\n"); - static const uint32_t expected[BUFSIZE] = { - 0xa24295ec, 0xfe3a05ce, 0x257fd8ef, 0x3acd5217, - 0xfdccf85c, 0xc7b5f143, 0x3b0c3ff0, 0x5220f13c, - 0xa6426724, 0x4d5426b4, 0x43e76b26, 0x051bc437, - 0xd8f28a02, 0x23ccc30e, 0x811d1a2d, 0x039128d4, - 0x9cd96a73, 0x216e6a8d, 0x97293fe8, 0xe4fc6d09, - 0x1ad34423, 0x9722d7e4, 0x5a6fdeca, 0x3c94a7e1, - 0x81a9a876, 0xae3f7c0e, 0x624b50ee, 0x875e5771, - 0x0095ab74, 0x1a7333fb, 0x056a4221, 0xa38351fa, - - 0x73f575f1, 0x8fded05b, 0x9097138f, 0xbd74620c, - 0x62d3f5f2, 0x07b78bd0, 0xbafdd81e, 0x0638f2ff, - 0x1f6e3aeb, 0xa7786473, 0x71700e1d, 0x6b4625ab, - 0xf02867e1, 0xb2b2408f, 0x9ce21ce5, 0xa62baaaf, - 0x26720461, 0x434813ee, 0x33bc0f14, 0xaaab098a, - 0x750af488, 0xc31bf476, 0x9cecbf26, 0x94793cf3, - 0xe1a27584, 0xe80c4880, 0x1299f748, 0x25e55ed2, - 0x405e3feb, 0x109e2412, 0x3e55f94f, 0x59575864, - - 0x365c869d, 0xc9852e6a, 0x12c30c62, 0x47f5b286, - 0xb47e488d, 0xa6667571, 0x78220d67, 0xa49e30b9, - 0x2005ef88, 0xf6d3816d, 0x6926834b, 0xe6116805, - 0x694777aa, 0x464af25b, 0x0e0e2d27, 0x0ea92eae, - 0x602c2ca9, 0x1d1d79c5, 0x6364f280, 0x939ee1a4, - 0x3b851bd8, 0x5bb6f19f, 0x80b9ed54, 0x3496a9f1, - 0xdf815033, 0x91612339, 0x14c516d6, 0xa3f0a804, - 0x5e78e975, 0xf408bcd9, 0x63d525ed, 0xa1e459c3, - - 0xfde303af, 0x049fc17f, 0xe7ed4489, 0xfaeefdb6, - 0x2b1b2fa8, 0xc67579a6, 0x5505882e, 0xe3e1c7cb, - 0xed53bf30, 0x9e628351, 0x8fa12113, 0x7500c30f, - 0xde1bee00, 0xf1fefe06, 0xdc759c00, 0x4c75e5ab, - 0xf889b069, 0x695bf8ae, 0x47d6600f, 0xd2a84f87, - 0xa0ca82a9, 0x8d2b750c, 0xe03d8cd7, 0x581fea33, - 0x969b0460, 0x36c7b7de, 0x74b3fd20, 0x2bb8bde6, - 0x13b20dec, 0xa2dcee89, 0xca36229d, 0x06fdb74e, - - - 0x6d9a982d, 0x02503496, 0xbdb4e0d9, 0xbd1f94cf, - 0x6d26f82d, 0xcf5e41cd, 0x88b67b65, 0x3e1b3ee4, - 0xb20e5e53, 0x1d9be438, 0xcef9c692, 0x299bd1b2, - 0xb1279627, 0x210b5f3d, 0x5569bd88, 0x9652ed43, - 0x7e8e0f8c, 0xdfa01085, 0xcd6d6343, 0xb8739826, - 0xa52ce9a0, 0xd33ef231, 0x1b4d92c2, 0xabfa116d, - 0xcdf47800, 0x3a4eefdc, 0xd01f3bcf, 0x30a32f46, - 0xfb54d851, 0x06a98f67, 0xbdcd0a71, 0x21a00949, - - 0xfe7049c9, 0x67ef46d2, 0xa1fabcbc, 0xa4c72db4, - 0x4a8a910d, 0x85a890ad, 0xc37e9454, 0xfc3d034a, - 0x6f46cc52, 0x742be7a8, 0xe94ecbc5, 0x5f993659, - 0x98270309, 0x8d1adae9, 0xea6e035e, 0x293d5fae, - 0x669955b3, 0x5afe23b5, 0x4c74efbf, 0x98106505, - 0xfbe09627, 0x3c00e8df, 0x5b03975d, 0x78edc83c, - 0x117c49c6, 0x66cdfc73, 0xfa55c94f, 0x5bf285fe, - 0x2db49b7d, 0xfbfeb8f0, 0xb7631bab, 0x837849f3, - - 0xf77f3ae5, 0x6e5db9bc, 0xfdd76f15, 0x545abf92, - 0x8b538102, 0xdd5c9b65, 0xa5adfd55, 0xecbd7bc5, - 0x9f99ebdd, 0x67500dcb, 0xf5246d1f, 0x2b0c061c, - 0x927a3747, 0xc77ba267, 0x6da9f855, 0x6240d41a, - 0xe9d1701d, 0xc69f0c55, 0x2c2c37cf, 0x12d82191, - 0x47be40d3, 0x165b35cd, 0xb7db42e1, 0x358786e4, - 0x84b8fc4e, 0x92f57c28, 0xf9c8bbd7, 0xab95a33d, - 0x11009238, 0xe9770420, 0xd6967e2a, 0x97c1589f, - - 0x2ee7e7d3, 0x32cc86da, 0xe47767d1, 0x73e9b61e, - 0xd35bac45, 0x835a62bb, 0x5d9217b0, 0x43f3f0ed, - 0x8a97911e, 0x4ec7eb55, 0x4b5a988c, 0xb9056683, - 0x45456f97, 0x1669fe44, 0xafb861b8, 0x8e83a19c, - 0x0bab08d6, 0xe6a145a9, 0xc31e5fc2, 0x27621f4c, - 0x795692fa, 0xb5e33ab9, 0x1bc786b6, 0x45d1c106, - 0x986531c9, 0x40c9a0ec, 0xff0fdf84, 0xa7359a42, - 0xfd1c2091, 0xf73463d4, 0x51b0d635, 0x1d602fb4, - - - 0xc56b69b7, 0x6909d3f7, 0xa04d68f4, 0x8d1001a7, - 0x8ecace50, 0x21ec4765, 0x3530f6b0, 0x645f3644, - 0x9963ef1e, 0x2b3c70d5, 0xa20c823b, 0x8d26dcae, - 0x05214e0c, 0x1993896d, 0x62085a35, 0x7b620b67, - 0x1dd85da2, 0x09ce9b1d, 0xd7873326, 0x063ff730, - 0xf4ff3c14, 0x09a49d69, 0x532062ba, 0x03ba7729, - 0xbd9a86cc, 0xe26d02a7, 0x7ccbe5d3, 0x4f662214, - 0x8b999a66, 0x3d0b92b4, 0x70b210f0, 0xf5b8f16f, - - 0x32146d34, 0x430b92bf, 0x8ab6204c, 0x35e6e1ff, - 0xc2f6c2fa, 0xa2df8a1a, 0x887413ec, 0x7cb7a69f, - 0x7ac6dbe6, 0x9102d1cb, 0x8892a590, 0xc804fe3a, - 0xdfc4920a, 0xfc829840, 0x8910d2eb, 0x38a210fd, - 0x9d840cc9, 0x7b9c827f, 0x3444ca0c, 0x071735ab, - 0x5e9088e4, 0xc995d60e, 0xbe0bb942, 0x17b089ae, - 0x050e1054, 0xcf4324f7, 0x1e3e64dd, 0x436414bb, - 0xc48fc2e3, 0x6b6b83d4, 0x9f6558ac, 0x781b22c5, - - 0x7147cfe2, 0x3c221b4d, 0xa5602765, 0x8f01a4f0, - 0x2a9f14ae, 0x12158cb8, 0x28177c50, 0x1091a165, - 0x39e4e4be, 0x3e451b7a, 0xd965419c, 0x52053005, - 0x0798aa53, 0xe6773e13, 0x1207f671, 0xd2ef998b, - 0xab88a38f, 0xc77a8482, 0xa88fb031, 0x5199e0cd, - 0x01b30536, 0x46eeb0ef, 0x814259ff, 0x9789a8cf, - 0x376ec5ac, 0x7087034a, 0x948b6bdd, 0x4281e628, - 0x2c848370, 0xd76ce66a, 0xe9b6959e, 0x24321a8e, - - 0xdeddd622, 0xb890f960, 0xea26c00a, 0x55e7d8b2, - 0xeab67f09, 0x9227fb08, 0xeebbed06, 0xcac1b0d1, - 0xb6412083, 0x05d2b0e7, 0x9037624a, 0xc9702198, - 0x2c8d1a86, 0x3e7d416e, 0xc3f1a39f, 0xf04bdce4, - 0xc88cdb61, 0xbdc89587, 0x4d29b63b, 0x6f24c267, - 0x4b529c87, 0x573f5a53, 0xdb3316e9, 0x288eb53b, - 0xd2c074bd, 0xef44a99a, 0x2b404d2d, 0xf6706464, - 0xfe824f4c, 0xc3debaf8, 0x12f44f98, 0x03135e76, - - - 0xb4888e7f, 0xb6b2325d, 0x3a138259, 0x513c83ec, - 0x2386d214, 0x94555500, 0xfbd1522d, 0xda2af018, - 0x15b054c0, 0x5ad654e6, 0xb6ed00aa, 0xa2f2180e, - 0x5f662825, 0xecd11366, 0x1de5e99d, 0x07afd2ad, - 0xcf457b04, 0xe631e10b, 0x83ae8a21, 0x709f0d59, - 0x3e278bf9, 0x246816db, 0x9f5e8fd3, 0xc5b5b5a2, - 0xd54a9d5c, 0x4b6f2856, 0x2eb5a666, 0xfc68bdd4, - 0x1ed1a7f8, 0x98a34b75, 0xc895ada9, 0x2907cc69, - - 0x87b0b455, 0xddaf96d9, 0xe7da15a6, 0x9298c82a, - 0x72bd5cab, 0x2e2a6ad4, 0x7f4b6bb8, 0x525225fe, - 0x985abe90, 0xac1fd6e1, 0xb8340f23, 0x92985159, - 0x7d29501d, 0xe75dc744, 0x687501b4, 0x92077dc3, - 0x58281a67, 0xe7e8e9be, 0xd0e64fd1, 0xb2eb0a30, - 0x0e1feccd, 0xc0dc4a9e, 0x5c4aeace, 0x2ca5b93c, - 0xee0ec34f, 0xad78467b, 0x0830e76e, 0x0df63f8b, - 0x2c2dfd95, 0x9b41ed31, 0x9ff4cddc, 0x1590c412, - - 0x2366fc82, 0x7a83294f, 0x9336c4de, 0x2343823c, - 0x5b681096, 0xf320e4c2, 0xc22b70e2, 0xb5fbfb2a, - 0x3ebc2fed, 0x11af07bd, 0x429a08c5, 0x42bee387, - 0x58629e33, 0xfb63b486, 0x52135fbe, 0xf1380e60, - 0x6355de87, 0x2f0bb19a, 0x167f63ac, 0x507224cf, - 0xf7c99d00, 0x71646f50, 0x74feb1ca, 0x5f9abfdd, - 0x278f7d68, 0x70120cd7, 0x4281b0f2, 0xdc8ebe5c, - 0x36c32163, 0x2da1e884, 0x61877598, 0xbef04402, - - 0x304db695, 0xfa8e9add, 0x503bac31, 0x0fe04722, - 0xf0d59f47, 0xcdc5c595, 0x918c39dd, 0x0cad8d05, - 0x6b3ed1eb, 0x4d43e089, 0x7ab051f8, 0xdeec371f, - 0x0f4816ae, 0xf8a1a240, 0xd15317f6, 0xb8efbf0b, - 0xcdd05df8, 0x4fd5633e, 0x7cf19668, 0x25d8f422, - 0x72d156f2, 0x2a778502, 0xda7aefb9, 0x4f4f66e8, - 0x19db6bff, 0x74e468da, 0xa754f358, 0x7339ec50, - 0x139006f6, 0xefbd0b91, 0x217e9a73, 0x939bd79c - }; - - uint8_t buf[BUFSIZE]; - uint32_t saw[BUFSIZE]; - for (int i=0; i>1); - measure[5][l] = measure[0][l] + measure[1][l]; - measure[5][l] ^= (measure[4][l]>>1); - } - for (int l=0; l<2; ++l) - { - for (int m=0; m maxk) - { - maxk = k; - } - } - } - printf("passed for buffer size %d max %d\n", h, maxk); - } -} -#undef BUFSIZE -#undef TRIES -#undef MEASURES - - -// test that hashing pieces has the same behavior as hashing the whole -#define BUFSIZE 1024 -void TestPieces() -{ - printf("\ntesting pieces ...\n"); - char buf[BUFSIZE]; - for (int i=0; i