You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by am...@apache.org on 2017/11/17 14:32:52 UTC
[trafficserver] branch master updated: Move ts/Vec to ts/Map
This is an automated email from the ASF dual-hosted git repository.
amc pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
The following commit(s) were added to refs/heads/master by this push:
new 84b2e8b Move ts/Vec to ts/Map
84b2e8b is described below
commit 84b2e8b61bcd869536bbf48eb206dcc178a28327
Author: IvanStarodubtsev <we...@users.noreply.github.com>
AuthorDate: Wed Nov 1 19:30:29 2017 +0200
Move ts/Vec to ts/Map
---
lib/ts/Makefile.am | 2 -
lib/ts/Map.h | 1094 ++++++++++++++++++++++++++++++++++++++++++++++++++-
lib/ts/Vec.cc | 210 ----------
lib/ts/Vec.h | 1113 ----------------------------------------------------
lib/ts/test_Vec.cc | 177 ++++++++-
5 files changed, 1265 insertions(+), 1331 deletions(-)
diff --git a/lib/ts/Makefile.am b/lib/ts/Makefile.am
index cf4f82d..c35d703 100644
--- a/lib/ts/Makefile.am
+++ b/lib/ts/Makefile.am
@@ -194,8 +194,6 @@ libtsutil_la_SOURCES = \
Tokenizer.h \
Trie.h \
TsBuffer.h \
- Vec.cc \
- Vec.h \
Version.cc \
X509HostnameValidator.cc \
X509HostnameValidator.h
diff --git a/lib/ts/Map.h b/lib/ts/Map.h
index 05e8b5e..d42c763 100644
--- a/lib/ts/Map.h
+++ b/lib/ts/Map.h
@@ -21,20 +21,1106 @@
limitations under the License.
*/
-#ifndef _map_H_
-#define _map_H_
+#pragma once
#include <stdlib.h>
#include <string.h>
+#include <unistd.h>
+#include <sys/types.h>
+#include "ts/defalloc.h"
#include "ts/ink_assert.h"
+#include "ts/Diags.h"
+
#include "ts/List.h"
-#include "ts/Vec.h"
#define MAP_INTEGRAL_SIZE (1 << (2))
//#define MAP_INITIAL_SHIFT ((2)+1)
//#define MAP_INITIAL_SIZE (1 << MAP_INITIAL_SHIFT)
+// Simple Vector class, also supports open hashed sets
+#define VEC_INTEGRAL_SHIFT_DEFAULT 2 /* power of 2 (1 << VEC_INTEGRAL_SHIFT)*/
+#define VEC_INTEGRAL_SIZE (1 << (S))
+#define VEC_INITIAL_SHIFT ((S) + 1)
+#define VEC_INITIAL_SIZE (1 << VEC_INITIAL_SHIFT)
+
+#define SET_LINEAR_SIZE 4 /* must be <= than VEC_INTEGRAL_SIZE */
+#define SET_INITIAL_INDEX 2
+
+template <class C, class A = DefaultAlloc, int S = VEC_INTEGRAL_SHIFT_DEFAULT> // S must be a power of 2
+class Vec
+{
+public:
+ size_t n;
+ size_t i; // size index for sets, reserve for vectors
+ C *v;
+ C e[VEC_INTEGRAL_SIZE];
+
+ Vec();
+ Vec<C, A, S>(const Vec<C, A, S> &vv);
+ Vec<C, A, S>(const C c);
+ ~Vec();
+
+ C &operator[](int i) const { return v[i]; }
+ C get(size_t i) const;
+ void add(C a);
+ void
+ push_back(C a)
+ {
+ add(a);
+ } // std::vector name
+ bool add_exclusive(C a);
+ C &add();
+ void drop();
+ C pop();
+ void reset();
+ void clear();
+ void free_and_clear();
+ void delete_and_clear();
+ void set_clear();
+ C *set_add(C a);
+ void set_remove(C a); // expensive, use BlockHash for cheaper remove
+ C *set_add_internal(C a);
+ bool set_union(Vec<C, A, S> &v);
+ int set_intersection(Vec<C, A, S> &v);
+ int some_intersection(Vec<C, A, S> &v);
+ int some_disjunction(Vec<C, A, S> &v);
+ int some_difference(Vec<C, A, S> &v);
+ void set_intersection(Vec<C, A, S> &v, Vec<C, A, S> &result);
+ void set_disjunction(Vec<C, A, S> &v, Vec<C, A, S> &result);
+ void set_difference(Vec<C, A, S> &v, Vec<C, A, S> &result);
+ size_t set_count() const;
+ size_t count() const;
+ C *in(C a);
+ C *set_in(C a);
+ C first_in_set();
+ C *set_in_internal(C a);
+ void set_expand();
+ ssize_t index(C a) const;
+ void set_to_vec();
+ void vec_to_set();
+ void move(Vec<C, A, S> &v);
+ void copy(const Vec<C, A, S> &v);
+ void fill(size_t n);
+ void append(const Vec<C> &v);
+ template <typename CountType> void append(const C *src, CountType count);
+ void prepend(const Vec<C> &v);
+ void remove_index(int index);
+ void
+ remove(C a)
+ {
+ int i = index(a);
+ if (i >= 0)
+ remove_index(i);
+ }
+ C &insert(size_t index);
+ void insert(size_t index, Vec<C> &vv);
+ void insert(size_t index, C a);
+ void
+ push(C a)
+ {
+ insert(0, a);
+ }
+ void reverse();
+ void reserve(size_t n);
+ C *
+ end() const
+ {
+ return v + n;
+ }
+ C &
+ first() const
+ {
+ return v[0];
+ }
+ C &
+ last() const
+ {
+ return v[n - 1];
+ }
+ Vec<C, A, S> &
+ operator=(Vec<C, A, S> &v)
+ {
+ this->copy(v);
+ return *this;
+ }
+ unsigned
+ length() const
+ {
+ return n;
+ }
+ // vector::size() intentionally not implemented because it should mean "bytes" not count of elements
+ int write(int fd);
+ int read(int fd);
+ void qsort(bool (*lt)(C, C));
+ void qsort(bool (*lt)(const C &, const C &));
+ static void swap(C *p1, C *p2);
+
+private:
+ void move_internal(Vec<C, A, S> &v);
+ void copy_internal(const Vec<C, A, S> &v);
+ void add_internal(C a);
+ C &add_internal();
+ void addx();
+};
+
+// c -- class, p -- pointer to elements of v, v -- vector
+#define forv_Vec(_c, _p, _v) \
+ if ((_v).n) \
+ for (_c *qq__##_p = (_c *)0, *_p = (_v).v[0]; \
+ ((uintptr_t)(qq__##_p) < (_v).length()) && ((_p = (_v).v[(intptr_t)qq__##_p]), 1); \
+ qq__##_p = (_c *)(((intptr_t)qq__##_p) + 1))
+#define for_Vec(_c, _p, _v) \
+ if ((_v).n) \
+ for (_c *qq__##_p = (_c *)0, _p = (_v).v[0]; \
+ ((uintptr_t)(qq__##_p) < (_v).length()) && ((_p = (_v).v[(intptr_t)qq__##_p]), 1); \
+ qq__##_p = (_c *)(((intptr_t)qq__##_p) + 1))
+#define forvp_Vec(_c, _p, _v) \
+ if ((_v).n) \
+ for (_c *qq__##_p = (_c *)0, *_p = &(_v).v[0]; \
+ ((uintptr_t)(qq__##_p) < (_v).length()) && ((_p = &(_v).v[(intptr_t)qq__##_p]), 1); \
+ qq__##_p = (_c *)(((intptr_t)qq__##_p) + 1))
+
+template <class C, class A = DefaultAlloc, int S = VEC_INTEGRAL_SHIFT_DEFAULT> class Accum
+{
+public:
+ Vec<C, A, S> asset;
+ Vec<C, A, S> asvec;
+ void
+ add(C c)
+ {
+ if (asset.set_add(c))
+ asvec.add(c);
+ }
+ void
+ add(Vec<C, A, S> v)
+ {
+ for (int i = 0; i < v.n; i++)
+ if (v.v[i])
+ add(v.v[i]);
+ }
+ void
+ clear()
+ {
+ asset.clear();
+ asvec.clear();
+ }
+};
+
+const uintptr_t prime2[] = {1, 3, 7, 13, 31, 61, 127, 251, 509, 1021,
+ 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573,
+ 2097143, 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909};
+
+// primes generated with map_mult.c
+const uintptr_t open_hash_primes[256] = {
+ 0x02D4AF27, 0x1865DFC7, 0x47C62B43, 0x35B4889B, 0x210459A1, 0x3CC51CC7, 0x02ADD945, 0x0607C4D7, 0x558E6035, 0x0554224F,
+ 0x5A281657, 0x1C458C7F, 0x7F8BE723, 0x20B9BA99, 0x7218AA35, 0x64B10C2B, 0x548E8983, 0x5951218F, 0x7AADC871, 0x695FA5B1,
+ 0x40D40FCB, 0x20E03CC9, 0x55E9920F, 0x554CE08B, 0x7E78B1D7, 0x7D965DF9, 0x36A520A1, 0x1B0C6C11, 0x33385667, 0x2B0A7B9B,
+ 0x0F35AE23, 0x0BD608FB, 0x2284ADA3, 0x6E6C0687, 0x129B3EED, 0x7E86289D, 0x1143C24B, 0x1B6C7711, 0x1D87BB41, 0x4C7E635D,
+ 0x67577999, 0x0A0113C5, 0x6CF085B5, 0x14A4D0FB, 0x4E93E3A7, 0x5C87672B, 0x67F3CA17, 0x5F944339, 0x4C16DFD7, 0x5310C0E3,
+ 0x2FAD1447, 0x4AFB3187, 0x08468B7F, 0x49E56C51, 0x6280012F, 0x097D1A85, 0x34CC9403, 0x71028BD7, 0x6DEDC7E9, 0x64093291,
+ 0x6D78BB0B, 0x7A03B465, 0x2E044A43, 0x1AE58515, 0x23E495CD, 0x46102A83, 0x51B78A59, 0x051D8181, 0x5352CAC9, 0x57D1312B,
+ 0x2726ED57, 0x2E6BC515, 0x70736281, 0x5938B619, 0x0D4B6ACB, 0x44AB5E2B, 0x0029A485, 0x002CE54F, 0x075B0591, 0x3EACFDA9,
+ 0x0AC03411, 0x53B00F73, 0x2066992D, 0x76E72223, 0x55F62A8D, 0x3FF92EE1, 0x17EE0EB3, 0x5E470AF1, 0x7193EB7F, 0x37A2CCD3,
+ 0x7B44F7AF, 0x0FED8B3F, 0x4CC05805, 0x7352BF79, 0x3B61F755, 0x523CF9A3, 0x1AAFD219, 0x76035415, 0x5BE84287, 0x6D598909,
+ 0x456537E9, 0x407EA83F, 0x23F6FFD5, 0x60256F39, 0x5D8EE59F, 0x35265CEB, 0x1D4AD4EF, 0x676E2E0F, 0x2D47932D, 0x776BB33B,
+ 0x6DE1902B, 0x2C3F8741, 0x5B2DE8EF, 0x686DDB3B, 0x1D7C61C7, 0x1B061633, 0x3229EA51, 0x7FCB0E63, 0x5F22F4C9, 0x517A7199,
+ 0x2A8D7973, 0x10DCD257, 0x41D59B27, 0x2C61CA67, 0x2020174F, 0x71653B01, 0x2FE464DD, 0x3E7ED6C7, 0x164D2A71, 0x5D4F3141,
+ 0x5F7BABA7, 0x50E1C011, 0x140F5D77, 0x34E80809, 0x04AAC6B3, 0x29C42BAB, 0x08F9B6F7, 0x461E62FD, 0x45C2660B, 0x08BF25A7,
+ 0x5494EA7B, 0x0225EBB7, 0x3C5A47CF, 0x2701C333, 0x457ED05B, 0x48CDDE55, 0x14083099, 0x7C69BDAB, 0x7BF163C9, 0x41EE1DAB,
+ 0x258B1307, 0x0FFAD43B, 0x6601D767, 0x214DBEC7, 0x2852CCF5, 0x0009B471, 0x190AC89D, 0x5BDFB907, 0x15D4E331, 0x15D22375,
+ 0x13F388D5, 0x12ACEDA5, 0x3835EA5D, 0x2587CA35, 0x06756643, 0x487C6F55, 0x65C295EB, 0x1029F2E1, 0x10CEF39D, 0x14C2E415,
+ 0x444825BB, 0x24BE0A2F, 0x1D2B7C01, 0x64AE3235, 0x5D2896E5, 0x61BBBD87, 0x4A49E86D, 0x12C277FF, 0x72C81289, 0x5CF42A3D,
+ 0x332FF177, 0x0DAECD23, 0x6000ED1D, 0x203CDDE1, 0x40C62CAD, 0x19B9A855, 0x782020C3, 0x6127D5BB, 0x719889A7, 0x40E4FCCF,
+ 0x2A3C8FF9, 0x07411C7F, 0x3113306B, 0x4D7CA03F, 0x76119841, 0x54CEFBDF, 0x11548AB9, 0x4B0748EB, 0x569966B1, 0x45BC721B,
+ 0x3D5A376B, 0x0D8923E9, 0x6D95514D, 0x0F39A367, 0x2FDAD92F, 0x721F972F, 0x42D0E21D, 0x5C5952DB, 0x7394D007, 0x02692C55,
+ 0x7F92772F, 0x025F8025, 0x34347113, 0x560EA689, 0x0DCC21DF, 0x09ECC7F5, 0x091F3993, 0x0E0B52AB, 0x497CAA55, 0x0A040A49,
+ 0x6D8F0CC5, 0x54F41609, 0x6E0CB8DF, 0x3DCB64C3, 0x16C365CD, 0x6D6B9FB5, 0x02B9382B, 0x6A5BFAF1, 0x1669D75F, 0x13CFD4FD,
+ 0x0FDF316F, 0x21F3C463, 0x6FC58ABF, 0x04E45BE7, 0x1911225B, 0x28CD1355, 0x222084E9, 0x672AD54B, 0x476FC267, 0x6864E16D,
+ 0x20AEF4FB, 0x603C5FB9, 0x55090595, 0x1113B705, 0x24E38493, 0x5291AF97, 0x5F5446D9, 0x13A6F639, 0x3D501313, 0x37E02017,
+ 0x236B0ED3, 0x60F246BF, 0x01E02501, 0x2D2F66BD, 0x6BF23609, 0x16729BAF};
+
+/* IMPLEMENTATION */
+
+template <class C, class A, int S> inline Vec<C, A, S>::Vec() : n(0), i(0), v(0)
+{
+ memset(&e[0], 0, sizeof(e));
+}
+
+template <class C, class A, int S> inline Vec<C, A, S>::Vec(const Vec<C, A, S> &vv)
+{
+ copy(vv);
+}
+
+template <class C, class A, int S> inline Vec<C, A, S>::Vec(C c)
+{
+ n = 1;
+ i = 0;
+ v = &e[0];
+ e[0] = c;
+}
+
+template <class C, class A, int S>
+inline C
+Vec<C, A, S>::get(size_t i) const
+{
+ if (i < n) {
+ return v[i];
+ } else {
+ return C();
+ }
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::add(C a)
+{
+ if (n & (VEC_INTEGRAL_SIZE - 1))
+ v[n++] = a;
+ else if (!v)
+ (v = e)[n++] = a;
+ else
+ add_internal(a);
+}
+
+template <class C, class A, int S>
+inline C &
+Vec<C, A, S>::add()
+{
+ C *ret;
+ if (n & (VEC_INTEGRAL_SIZE - 1))
+ ret = &v[n++];
+ else if (!v)
+ ret = &(v = e)[n++];
+ else
+ ret = &add_internal();
+ return *ret;
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::drop()
+{
+ if (n && 0 == --n)
+ clear();
+}
+
+template <class C, class A, int S>
+inline C
+Vec<C, A, S>::pop()
+{
+ if (!n)
+ return 0;
+ n--;
+ C ret = v[n];
+ if (!n)
+ clear();
+ return ret;
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::set_clear()
+{
+ memset(v, 0, n * sizeof(C));
+}
+
+template <class C, class A, int S>
+inline C *
+Vec<C, A, S>::set_add(C a)
+{
+ if (n < SET_LINEAR_SIZE) {
+ for (C *c = v; c < v + n; c++)
+ if (*c == a)
+ return 0;
+ add(a);
+ return &v[n - 1];
+ }
+ if (n == SET_LINEAR_SIZE) {
+ Vec<C, A, S> vv(*this);
+ clear();
+ for (C *c = vv.v; c < vv.v + vv.n; c++) {
+ set_add_internal(*c);
+ }
+ }
+ return set_add_internal(a);
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::set_remove(C a)
+{
+ Vec<C, A, S> tmp;
+ tmp.move(*this);
+ for (C *c = tmp.v; c < tmp.v + tmp.n; c++)
+ if (*c != a)
+ set_add(a);
+}
+
+template <class C, class A, int S>
+inline size_t
+Vec<C, A, S>::count() const
+{
+ int x = 0;
+ for (C *c = v; c < v + n; c++)
+ if (*c)
+ x++;
+ return x;
+}
+
+template <class C, class A, int S>
+inline C *
+Vec<C, A, S>::in(C a)
+{
+ for (C *c = v; c < v + n; c++)
+ if (*c == a)
+ return c;
+ return NULL;
+}
+
+template <class C, class A, int S>
+inline bool
+Vec<C, A, S>::add_exclusive(C a)
+{
+ if (!in(a)) {
+ add(a);
+ return true;
+ } else
+ return false;
+}
+
+template <class C, class A, int S>
+inline C *
+Vec<C, A, S>::set_in(C a)
+{
+ if (n <= SET_LINEAR_SIZE)
+ return in(a);
+ return set_in_internal(a);
+}
+
+template <class C, class A, int S>
+inline C
+Vec<C, A, S>::first_in_set()
+{
+ for (C *c = v; c < v + n; c++)
+ if (*c)
+ return *c;
+ return 0;
+}
+
+template <class C, class A, int S>
+inline ssize_t
+Vec<C, A, S>::index(C a) const
+{
+ for (C *c = v; c < v + n; c++) {
+ if (*c == a) {
+ return c - v;
+ }
+ }
+ return -1;
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::move_internal(Vec<C, A, S> &vv)
+{
+ n = vv.n;
+ i = vv.i;
+ if (vv.v == &vv.e[0]) {
+ memcpy(e, &vv.e[0], sizeof(e));
+ v = e;
+ } else
+ v = vv.v;
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::move(Vec<C, A, S> &vv)
+{
+ move_internal(vv);
+ vv.v = 0;
+ vv.clear();
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::copy(const Vec<C, A, S> &vv)
+{
+ n = vv.n;
+ i = vv.i;
+ if (vv.v == &vv.e[0]) {
+ memcpy(e, &vv.e[0], sizeof(e));
+ v = e;
+ } else {
+ if (vv.v)
+ copy_internal(vv);
+ else
+ v = 0;
+ }
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::fill(size_t nn)
+{
+ for (size_t i = n; i < nn; i++)
+ add() = 0;
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::append(const Vec<C> &vv)
+{
+ for (C *c = vv.v; c < vv.v + vv.n; c++)
+ if (*c != 0)
+ add(*c);
+}
+
+template <class C, class A, int S>
+template <typename CountType>
+inline void
+Vec<C, A, S>::append(const C *src, CountType count)
+{
+ reserve(length() + count);
+ for (CountType c = 0; c < count; ++c) {
+ add(src[c]);
+ }
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::prepend(const Vec<C> &vv)
+{
+ if (vv.n) {
+ int oldn = n;
+ fill(n + vv.n);
+ if (oldn)
+ memmove(&v[vv.n], &v[0], oldn * sizeof(v[0]));
+ memcpy(&v[0], vv.v, vv.n * sizeof(v[0]));
+ }
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::add_internal(C a)
+{
+ addx();
+ v[n++] = a;
+}
+
+template <class C, class A, int S>
+C &
+Vec<C, A, S>::add_internal()
+{
+ addx();
+ return v[n++];
+}
+
+template <class C, class A, int S>
+C *
+Vec<C, A, S>::set_add_internal(C c)
+{
+ size_t j, k;
+ if (n) {
+ uintptr_t h = (uintptr_t)c;
+ h = h % n;
+ for (k = h, j = 0; j < i + 3; j++) {
+ if (!v[k]) {
+ v[k] = c;
+ return &v[k];
+ } else if (v[k] == c) {
+ return 0;
+ }
+ k = (k + open_hash_primes[j]) % n;
+ }
+ }
+ Vec<C, A, S> vv;
+ vv.move_internal(*this);
+ set_expand();
+ if (vv.v) {
+ set_union(vv);
+ }
+ return set_add(c);
+}
+
+template <class C, class A, int S>
+C *
+Vec<C, A, S>::set_in_internal(C c)
+{
+ size_t j, k;
+ if (n) {
+ uintptr_t h = (uintptr_t)c;
+ h = h % n;
+ for (k = h, j = 0; j < i + 3; j++) {
+ if (!v[k])
+ return 0;
+ else if (v[k] == c)
+ return &v[k];
+ k = (k + open_hash_primes[j]) % n;
+ }
+ }
+ return 0;
+}
+
+template <class C, class A, int S>
+bool
+Vec<C, A, S>::set_union(Vec<C, A, S> &vv)
+{
+ bool changed = false;
+ for (size_t i = 0; i < vv.n; i++) {
+ if (vv.v[i]) {
+ changed = set_add(vv.v[i]) || changed;
+ }
+ }
+ return changed;
+}
+
+template <class C, class A, int S>
+int
+Vec<C, A, S>::set_intersection(Vec<C, A, S> &vv)
+{
+ Vec<C, A, S> tv;
+ tv.move(*this);
+ int changed = 0;
+ for (int i = 0; i < tv.n; i++)
+ if (tv.v[i]) {
+ if (vv.set_in(tv.v[i]))
+ set_add(tv.v[i]);
+ else
+ changed = 1;
+ }
+ return changed;
+}
+
+template <class C, class A, int S>
+int
+Vec<C, A, S>::some_intersection(Vec<C, A, S> &vv)
+{
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (vv.set_in(v[i]))
+ return 1;
+ return 0;
+}
+
+template <class C, class A, int S>
+int
+Vec<C, A, S>::some_disjunction(Vec<C, A, S> &vv)
+{
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (!vv.set_in(v[i]))
+ return 1;
+ for (int i = 0; i < vv.n; i++)
+ if (vv.v[i])
+ if (!set_in(vv.v[i]))
+ return 1;
+ return 0;
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::set_intersection(Vec<C, A, S> &vv, Vec<C, A, S> &result)
+{
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (vv.set_in(v[i]))
+ result.set_add(v[i]);
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::set_disjunction(Vec<C, A, S> &vv, Vec<C, A, S> &result)
+{
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (!vv.set_in(v[i]))
+ result.set_add(v[i]);
+ for (int i = 0; i < vv.n; i++)
+ if (vv.v[i])
+ if (!set_in(vv.v[i]))
+ result.set_add(vv.v[i]);
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::set_difference(Vec<C, A, S> &vv, Vec<C, A, S> &result)
+{
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (!vv.set_in(v[i]))
+ result.set_add(v[i]);
+}
+
+template <class C, class A, int S>
+int
+Vec<C, A, S>::some_difference(Vec<C, A, S> &vv)
+{
+ for (int i = 0; i < n; i++)
+ if (v[i])
+ if (!vv.set_in(v[i]))
+ return 1;
+ return 0;
+}
+
+template <class C, class A, int S>
+size_t
+Vec<C, A, S>::set_count() const
+{
+ size_t x = 0;
+ for (size_t i = 0; i < n; i++) {
+ if (v[i]) {
+ x++;
+ }
+ }
+ return x;
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::set_to_vec()
+{
+ C *x = &v[0], *y = x;
+ for (; y < v + n; y++) {
+ if (*y) {
+ if (x != y)
+ *x = *y;
+ x++;
+ }
+ }
+ if (i) {
+ i = prime2[i]; // convert set allocation to reserve
+ if (i - n > 0)
+ memset(&v[n], 0, (i - n) * (sizeof(C)));
+ } else {
+ i = 0;
+ if (v == &e[0] && VEC_INTEGRAL_SIZE - n > 0)
+ memset(&v[n], 0, (VEC_INTEGRAL_SIZE - n) * (sizeof(C)));
+ }
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::vec_to_set()
+{
+ Vec<C, A, S> vv;
+ vv.move(*this);
+ for (C *c = vv.v; c < vv.v + vv.n; c++)
+ set_add(*c);
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::remove_index(int index)
+{
+ if (n > 1)
+ memmove(&v[index], &v[index + 1], (n - 1 - index) * sizeof(v[0]));
+ n--;
+ if (n <= 0)
+ v = e;
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::insert(size_t index, C a)
+{
+ add();
+ memmove(&v[index + 1], &v[index], (n - index - 1) * sizeof(C));
+ v[index] = a;
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::insert(size_t index, Vec<C> &vv)
+{
+ fill(n + vv.n);
+ memmove(&v[index + vv.n], &v[index], (n - index - 1) * sizeof(C));
+ for (int x = 0; x < vv.n; x++)
+ v[index + x] = vv[x];
+}
+
+template <class C, class A, int S>
+C &
+Vec<C, A, S>::insert(size_t index)
+{
+ add();
+ memmove(&v[index + 1], &v[index], (n - index - 1) * sizeof(C));
+ memset(&v[index], 0, sizeof(C));
+ return v[index];
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::reverse()
+{
+ for (int i = 0; i < n / 2; i++) {
+ C *s = &v[i], *e = &v[n - 1 - i];
+ C t;
+ memcpy(&t, s, sizeof(t));
+ memcpy(s, e, sizeof(t));
+ memcpy(e, &t, sizeof(t));
+ }
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::copy_internal(const Vec<C, A, S> &vv)
+{
+ int l = n, nl = (1 + VEC_INITIAL_SHIFT);
+ l = l >> VEC_INITIAL_SHIFT;
+ while (l) {
+ l = l >> 1;
+ nl++;
+ }
+ nl = 1 << nl;
+ v = (C *)A::alloc(nl * sizeof(C));
+ memcpy(v, vv.v, n * sizeof(C));
+ memset(v + n, 0, (nl - n) * sizeof(C));
+ if (i > n) // reset reserve
+ i = 0;
+}
+
+template <class C, class A, int S>
+void
+Vec<C, A, S>::set_expand()
+{
+ if (!n)
+ i = SET_INITIAL_INDEX;
+ else
+ i = i + 1;
+ n = prime2[i];
+ v = (C *)A::alloc(n * sizeof(C));
+ memset(v, 0, n * sizeof(C));
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::reserve(size_t x)
+{
+ if (x <= n)
+ return;
+ unsigned xx = 1 << VEC_INITIAL_SHIFT;
+ while (xx < x)
+ xx *= 2;
+ i = xx;
+ void *vv = (void *)v;
+ v = (C *)A::alloc(i * sizeof(C));
+ if (vv && n)
+ memcpy(v, vv, n * sizeof(C));
+ memset(&v[n], 0, (i - n) * sizeof(C));
+ if (vv && vv != e)
+ A::free(vv);
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::addx()
+{
+ if (!v) {
+ v = e;
+ return;
+ }
+ if (v == e) {
+ v = (C *)A::alloc(VEC_INITIAL_SIZE * sizeof(C));
+ memcpy(v, &e[0], n * sizeof(C));
+ ink_assert(n < VEC_INITIAL_SIZE);
+ memset(&v[n], 0, (VEC_INITIAL_SIZE - n) * sizeof(C));
+ } else {
+ if ((n & (n - 1)) == 0) {
+ size_t nl = n * 2;
+ if (nl <= i) {
+ return;
+ } else {
+ i = 0;
+ }
+ void *vv = (void *)v;
+ v = (C *)A::alloc(nl * sizeof(C));
+ memcpy(v, vv, n * sizeof(C));
+ memset(&v[n], 0, n * sizeof(C));
+ A::free(vv);
+ }
+ }
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::reset()
+{
+ v = NULL;
+ n = 0;
+ i = 0;
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::clear()
+{
+ if (v && v != e)
+ A::free(v);
+ reset();
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::free_and_clear()
+{
+ for (size_t x = 0; x < (n); x++)
+ A::free((void *)v[x]);
+ clear();
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::delete_and_clear()
+{
+ for (size_t x = 0; x < n; x++) {
+ if (v[x]) {
+ delete v[x];
+ }
+ }
+ clear();
+}
+
+template <class C, class A, int S> inline Vec<C, A, S>::~Vec()
+{
+ if (v && v != e)
+ A::free(v);
+}
+
+template <class C, class A, int S>
+inline int
+marshal_size(Vec<C, A, S> &v)
+{
+ int l = sizeof(int) * 2;
+ for (int x = 0; x < v.n; x++)
+ l += ::marshal_size(v.v[x]);
+ return l;
+}
+
+template <class C, class A, int S>
+inline int
+marshal(Vec<C, A, S> &v, char *buf)
+{
+ char *x = buf;
+ *(int *)x = v.n;
+ x += sizeof(int);
+ *(int *)x = v.i;
+ x += sizeof(int);
+ for (int i = 0; i < v.n; i++)
+ x += ::marshal(v.v[i], x);
+ return x - buf;
+}
+
+template <class C, class A, int S>
+inline int
+unmarshal(Vec<C, A, S> &v, char *buf)
+{
+ char *x = buf;
+ v.n = *(int *)x;
+ x += sizeof(int);
+ v.i = *(int *)x;
+ x += sizeof(int);
+ if (v.n) {
+ v.v = (C *)A::alloc(sizeof(C) * v.n);
+ memset(v.v, 0, sizeof(C) * v.n);
+ } else
+ v.v = v.e;
+ for (int i = 0; i < v.n; i++)
+ x += ::unmarshal(v.v[i], x);
+ return x - buf;
+}
+
+template <class C, class A, int S>
+inline int
+Vec<C, A, S>::write(int fd)
+{
+ int r = 0, t = 0;
+ if ((r = ::write(fd, this, sizeof(*this))) < 0)
+ return r;
+ t += r;
+ if ((r = ::write(fd, v, n * sizeof(C))) < 0)
+ return r;
+ t += r;
+ return t;
+}
+
+template <class C, class A, int S>
+inline int
+Vec<C, A, S>::read(int fd)
+{
+ int r = 0, t = 0;
+ if ((r = ::read(fd, this, sizeof(*this))) < 0)
+ return r;
+ t += r;
+ v = (C *)A::alloc(sizeof(C) * n);
+ memset(v, 0, sizeof(C) * n);
+ if ((r = ::read(fd, v, n * sizeof(C))) < 0)
+ return r;
+ t += r;
+ return t;
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::swap(C *p1, C *p2)
+{
+ C t = *p1;
+ *p1 = *p2;
+ *p2 = t;
+}
+
+template <class C>
+inline void
+qsort_Vec(C *left, C *right, bool (*lt)(C, C))
+{
+ if (right - left < 5) {
+ for (C *y = right - 1; y > left; y--) {
+ for (C *x = left; x < y; x++) {
+ if (lt(x[1], x[0])) {
+ C t = x[0];
+ x[0] = x[1];
+ x[1] = t;
+ }
+ }
+ }
+ } else {
+ C *center = left + ((right - left) / 2);
+ C median;
+
+ // find the median
+ if (lt(*center, *left)) { // order left and center
+ Vec<C>::swap(center, left);
+ }
+ if (lt(*(right - 1), *left)) { // order left and right
+ Vec<C>::swap(right - 1, left);
+ }
+ if (lt(*(right - 1), *center)) { // order right and center
+ Vec<C>::swap((right - 1), center);
+ }
+ Vec<C>::swap(center, right - 2); // stash the median one from the right for now
+ median = *(right - 2); // the median of left, center and right values
+
+ // now partition, pivoting on the median value
+ // l ptr is +1 b/c we already put the lowest of the incoming left, center
+ // and right in there, ignore it for now
+ // r ptr is -2 b/c we already put the biggest of the 3 values in (right-1)
+ // and the median in (right -2)
+ C *l = left + 1, *r = right - 2;
+
+ // move l and r until they have something to do
+ while (lt(median, *(r - 1))) {
+ r--;
+ }
+ while (l < r && lt(*l, median)) {
+ l++;
+ }
+ // until l and r meet,
+ // compare l and median
+ // swap l for r if l is larger than median
+ while (l < r) {
+ if (lt(*l, median)) {
+ l++;
+ } else {
+ Vec<C>::swap(l, r - 1);
+ r--;
+ }
+ }
+
+ Vec<C>::swap(l, right - 2); // restore median to its rightful place
+
+ // recurse for the littles (left segment)
+ qsort_Vec<C>(left, l, lt);
+ // recurse for the bigs (right segment)
+ qsort_Vec<C>(l + 1, right, lt);
+ }
+}
+
+template <class C>
+inline void
+qsort_VecRef(C *left, C *right, bool (*lt)(const C &, const C &), unsigned int *p_ctr)
+{
+ if (right - left < 5) {
+ for (C *y = right - 1; y > left; y--) {
+ for (C *x = left; x < y; x++) {
+ if (lt(x[1], x[0])) {
+ C t = x[0];
+ x[0] = x[1];
+ x[1] = t;
+ }
+ }
+ }
+ } else {
+ C *center = left + ((right - left) / 2);
+ C median;
+
+ // find the median
+ if (lt(*center, *left)) { // order left and center
+ Vec<C>::swap(center, left);
+ }
+ if (lt(*(right - 1), *left)) { // order left and right
+ Vec<C>::swap(right - 1, left);
+ }
+ if (lt(*(right - 1), *center)) { // order right and center
+ Vec<C>::swap((right - 1), center);
+ }
+ Vec<C>::swap(center, right - 2); // stash the median one from the right for now
+ median = *(right - 2); // the median of left, center and right values
+
+ // now partition, pivoting on the median value
+ // l ptr is +1 b/c we already put the lowest of the incoming left, center
+ // and right in there, ignore it for now
+ // r ptr is -2 b/c we already put the biggest of the 3 values in (right-1)
+ // and the median in (right -2)
+ C *l = left + 1, *r = right - 2;
+
+ // move l and r until they have something to do
+ while (lt(median, *(r - 1))) {
+ r--;
+ }
+ while (l < r && lt(*l, median)) {
+ l++;
+ }
+ // until l and r meet,
+ // compare l and median
+ // swap l for r if l is larger than median
+ while (l < r) {
+ if (lt(*l, median)) {
+ l++;
+ } else {
+ Vec<C>::swap(l, r - 1);
+ r--;
+ }
+ }
+
+ Vec<C>::swap(l, right - 2); // restore median to its rightful place
+
+ // recurse for the littles (left segment)
+ qsort_VecRef<C>(left, l, lt, p_ctr);
+ // recurse for the bigs (right segment)
+ qsort_VecRef<C>(l + 1, right, lt, p_ctr);
+ }
+ (*p_ctr)++;
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::qsort(bool (*lt)(C, C))
+{
+ if (n)
+ qsort_Vec<C>(&v[0], end(), lt);
+}
+
+template <class C, class A, int S>
+inline void
+Vec<C, A, S>::qsort(bool (*lt)(const C &, const C &))
+{
+ static unsigned int ctr = 0;
+ if (n)
+ qsort_VecRef<C>(&v[0], end(), lt, &ctr);
+ Debug("qsort", "took %u iterations to sort %ld elements", ctr, n);
+}
+void test_vec();
+
typedef const char cchar;
template <class A>
@@ -1132,5 +2218,3 @@ TSHashTable<H>::expand()
}
/* ---------------------------------------------------------------------------------------------- */
-
-#endif
diff --git a/lib/ts/Vec.cc b/lib/ts/Vec.cc
deleted file mode 100644
index 1076683..0000000
--- a/lib/ts/Vec.cc
+++ /dev/null
@@ -1,210 +0,0 @@
-/* -*-Mode: c++;-*-
- Various vector related code.
-
- @section license License
-
- Licensed to the Apache Software Foundation (ASF) under one
- or more contributor license agreements. See the NOTICE file
- distributed with this work for additional information
- regarding copyright ownership. The ASF licenses this file
- to you 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.
-*/
-
-/* UnionFind after Tarjan */
-
-#include <cstdint>
-#include "ts/Vec.h"
-
-const uintptr_t prime2[] = {1, 3, 7, 13, 31, 61, 127, 251, 509, 1021,
- 2039, 4093, 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573,
- 2097143, 4194301, 8388593, 16777213, 33554393, 67108859, 134217689, 268435399, 536870909};
-
-// primes generated with map_mult.c
-const uintptr_t open_hash_primes[256] = {
- 0x02D4AF27, 0x1865DFC7, 0x47C62B43, 0x35B4889B, 0x210459A1, 0x3CC51CC7, 0x02ADD945, 0x0607C4D7, 0x558E6035, 0x0554224F,
- 0x5A281657, 0x1C458C7F, 0x7F8BE723, 0x20B9BA99, 0x7218AA35, 0x64B10C2B, 0x548E8983, 0x5951218F, 0x7AADC871, 0x695FA5B1,
- 0x40D40FCB, 0x20E03CC9, 0x55E9920F, 0x554CE08B, 0x7E78B1D7, 0x7D965DF9, 0x36A520A1, 0x1B0C6C11, 0x33385667, 0x2B0A7B9B,
- 0x0F35AE23, 0x0BD608FB, 0x2284ADA3, 0x6E6C0687, 0x129B3EED, 0x7E86289D, 0x1143C24B, 0x1B6C7711, 0x1D87BB41, 0x4C7E635D,
- 0x67577999, 0x0A0113C5, 0x6CF085B5, 0x14A4D0FB, 0x4E93E3A7, 0x5C87672B, 0x67F3CA17, 0x5F944339, 0x4C16DFD7, 0x5310C0E3,
- 0x2FAD1447, 0x4AFB3187, 0x08468B7F, 0x49E56C51, 0x6280012F, 0x097D1A85, 0x34CC9403, 0x71028BD7, 0x6DEDC7E9, 0x64093291,
- 0x6D78BB0B, 0x7A03B465, 0x2E044A43, 0x1AE58515, 0x23E495CD, 0x46102A83, 0x51B78A59, 0x051D8181, 0x5352CAC9, 0x57D1312B,
- 0x2726ED57, 0x2E6BC515, 0x70736281, 0x5938B619, 0x0D4B6ACB, 0x44AB5E2B, 0x0029A485, 0x002CE54F, 0x075B0591, 0x3EACFDA9,
- 0x0AC03411, 0x53B00F73, 0x2066992D, 0x76E72223, 0x55F62A8D, 0x3FF92EE1, 0x17EE0EB3, 0x5E470AF1, 0x7193EB7F, 0x37A2CCD3,
- 0x7B44F7AF, 0x0FED8B3F, 0x4CC05805, 0x7352BF79, 0x3B61F755, 0x523CF9A3, 0x1AAFD219, 0x76035415, 0x5BE84287, 0x6D598909,
- 0x456537E9, 0x407EA83F, 0x23F6FFD5, 0x60256F39, 0x5D8EE59F, 0x35265CEB, 0x1D4AD4EF, 0x676E2E0F, 0x2D47932D, 0x776BB33B,
- 0x6DE1902B, 0x2C3F8741, 0x5B2DE8EF, 0x686DDB3B, 0x1D7C61C7, 0x1B061633, 0x3229EA51, 0x7FCB0E63, 0x5F22F4C9, 0x517A7199,
- 0x2A8D7973, 0x10DCD257, 0x41D59B27, 0x2C61CA67, 0x2020174F, 0x71653B01, 0x2FE464DD, 0x3E7ED6C7, 0x164D2A71, 0x5D4F3141,
- 0x5F7BABA7, 0x50E1C011, 0x140F5D77, 0x34E80809, 0x04AAC6B3, 0x29C42BAB, 0x08F9B6F7, 0x461E62FD, 0x45C2660B, 0x08BF25A7,
- 0x5494EA7B, 0x0225EBB7, 0x3C5A47CF, 0x2701C333, 0x457ED05B, 0x48CDDE55, 0x14083099, 0x7C69BDAB, 0x7BF163C9, 0x41EE1DAB,
- 0x258B1307, 0x0FFAD43B, 0x6601D767, 0x214DBEC7, 0x2852CCF5, 0x0009B471, 0x190AC89D, 0x5BDFB907, 0x15D4E331, 0x15D22375,
- 0x13F388D5, 0x12ACEDA5, 0x3835EA5D, 0x2587CA35, 0x06756643, 0x487C6F55, 0x65C295EB, 0x1029F2E1, 0x10CEF39D, 0x14C2E415,
- 0x444825BB, 0x24BE0A2F, 0x1D2B7C01, 0x64AE3235, 0x5D2896E5, 0x61BBBD87, 0x4A49E86D, 0x12C277FF, 0x72C81289, 0x5CF42A3D,
- 0x332FF177, 0x0DAECD23, 0x6000ED1D, 0x203CDDE1, 0x40C62CAD, 0x19B9A855, 0x782020C3, 0x6127D5BB, 0x719889A7, 0x40E4FCCF,
- 0x2A3C8FF9, 0x07411C7F, 0x3113306B, 0x4D7CA03F, 0x76119841, 0x54CEFBDF, 0x11548AB9, 0x4B0748EB, 0x569966B1, 0x45BC721B,
- 0x3D5A376B, 0x0D8923E9, 0x6D95514D, 0x0F39A367, 0x2FDAD92F, 0x721F972F, 0x42D0E21D, 0x5C5952DB, 0x7394D007, 0x02692C55,
- 0x7F92772F, 0x025F8025, 0x34347113, 0x560EA689, 0x0DCC21DF, 0x09ECC7F5, 0x091F3993, 0x0E0B52AB, 0x497CAA55, 0x0A040A49,
- 0x6D8F0CC5, 0x54F41609, 0x6E0CB8DF, 0x3DCB64C3, 0x16C365CD, 0x6D6B9FB5, 0x02B9382B, 0x6A5BFAF1, 0x1669D75F, 0x13CFD4FD,
- 0x0FDF316F, 0x21F3C463, 0x6FC58ABF, 0x04E45BE7, 0x1911225B, 0x28CD1355, 0x222084E9, 0x672AD54B, 0x476FC267, 0x6864E16D,
- 0x20AEF4FB, 0x603C5FB9, 0x55090595, 0x1113B705, 0x24E38493, 0x5291AF97, 0x5F5446D9, 0x13A6F639, 0x3D501313, 0x37E02017,
- 0x236B0ED3, 0x60F246BF, 0x01E02501, 0x2D2F66BD, 0x6BF23609, 0x16729BAF};
-
-// binary search over intervals
-static int
-i_find(const Intervals *i, int x)
-{
- ink_assert(i->n);
- int l = 0, h = i->n;
-Lrecurse:
- if (h <= l + 2) {
- if (h <= l) {
- return -(l + 1);
- }
- if (x < i->v[l] || x > i->v[l + 1]) {
- return -(l + 1);
- }
- return h;
- }
- int m = (((h - l) / 4) * 2) + l;
- if (x > i->v[m + 1]) {
- l = m;
- goto Lrecurse;
- }
- if (x < i->v[m]) {
- h = m;
- goto Lrecurse;
- }
- return (l + 1);
-}
-
-bool
-Intervals::in(int x) const
-{
- if (!n) {
- return false;
- }
- if (i_find(this, x) > 0) {
- return true;
- }
- return false;
-}
-
-// insert into interval with merge
-void
-Intervals::insert(int x)
-{
- if (!n) {
- add(x);
- add(x);
- return;
- }
- int l = i_find(this, x);
- if (l > 0) {
- return;
- }
- l = -l - 1;
-
- if (x > v[l + 1]) {
- if (x == v[l + 1] + 1) {
- v[l + 1]++;
- goto Lmerge;
- }
- l += 2;
- if (l < (int)n) {
- if (x == v[l] - 1) {
- v[l]--;
- goto Lmerge;
- }
- }
- goto Lmore;
- } else {
- ink_assert(x < v[l]);
- if (x == v[l] - 1) {
- v[l]--;
- goto Lmerge;
- }
- if (!l) {
- goto Lmore;
- }
- l -= 2;
- if (x == v[l + 1] + 1) {
- v[l + 1]++;
- goto Lmerge;
- }
- }
-Lmore:
- fill(n + 2);
- if (n - 2 - l > 0) {
- memmove(v + l + 2, v + l, sizeof(int) * (n - 2 - l));
- }
- v[l] = x;
- v[l + 1] = x;
- return;
-Lmerge:
- if (l) {
- if (v[l] - v[l - 1] < 2) {
- l -= 2;
- goto Ldomerge;
- }
- }
- if (l < (int)(n - 2)) {
- if (v[l + 2] - v[l + 1] < 2) {
- goto Ldomerge;
- }
- }
- return;
-Ldomerge:
- memmove(v + l + 1, v + l + 3, sizeof(int) * (n - 3 - l));
- n -= 2;
- goto Lmerge;
-}
-
-void
-UnionFind::size(int s)
-{
- size_t nn = n;
- fill(s);
- for (size_t i = nn; i < n; i++) {
- v[i] = -1;
- }
-}
-
-int
-UnionFind::find(int n)
-{
- int i, t;
- for (i = n; v[i] >= 0; i = v[i]) {
- ;
- }
- while (v[n] >= 0) {
- t = n;
- n = v[n];
- v[t] = i;
- }
- return i;
-}
-
-void
-UnionFind::unify(int n, int m)
-{
- n = find(n);
- m = find(m);
- if (n != m) {
- if (v[m] < v[n]) {
- v[m] += (v[n] - 1);
- v[n] = m;
- } else {
- v[n] += (v[m] - 1);
- v[m] = n;
- }
- }
-}
diff --git a/lib/ts/Vec.h b/lib/ts/Vec.h
deleted file mode 100644
index d3f6ac5..0000000
--- a/lib/ts/Vec.h
+++ /dev/null
@@ -1,1113 +0,0 @@
-/** @file
-
- Vector and Set templates with qsort.
-
- @section license License
-
- Licensed to the Apache Software Foundation (ASF) under one
- or more contributor license agreements. See the NOTICE file
- distributed with this work for additional information
- regarding copyright ownership. The ASF licenses this file
- to you 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 _vec_H_
-#define _vec_H_
-
-#include <string.h>
-#include <stdlib.h>
-#include <unistd.h>
-#include <sys/types.h>
-#include "ts/defalloc.h"
-#include "ts/ink_assert.h"
-#include "ts/Diags.h"
-
-// Simple Vector class, also supports open hashed sets
-
-#define VEC_INTEGRAL_SHIFT_DEFAULT 2 /* power of 2 (1 << VEC_INTEGRAL_SHIFT)*/
-#define VEC_INTEGRAL_SIZE (1 << (S))
-#define VEC_INITIAL_SHIFT ((S) + 1)
-#define VEC_INITIAL_SIZE (1 << VEC_INITIAL_SHIFT)
-
-#define SET_LINEAR_SIZE 4 /* must be <= than VEC_INTEGRAL_SIZE */
-#define SET_INITIAL_INDEX 2
-
-template <class C, class A = DefaultAlloc, int S = VEC_INTEGRAL_SHIFT_DEFAULT> // S must be a power of 2
-class Vec
-{
-public:
- size_t n;
- size_t i; // size index for sets, reserve for vectors
- C *v;
- C e[VEC_INTEGRAL_SIZE];
-
- Vec();
- Vec<C, A, S>(const Vec<C, A, S> &vv);
- Vec<C, A, S>(const C c);
- ~Vec();
-
- C &operator[](int i) const { return v[i]; }
- C get(size_t i) const;
- void add(C a);
- void
- push_back(C a)
- {
- add(a);
- } // std::vector name
- bool add_exclusive(C a);
- C &add();
- void drop();
- C pop();
- void reset();
- void clear();
- void free_and_clear();
- void delete_and_clear();
- void set_clear();
- C *set_add(C a);
- void set_remove(C a); // expensive, use BlockHash for cheaper remove
- C *set_add_internal(C a);
- bool set_union(Vec<C, A, S> &v);
- int set_intersection(Vec<C, A, S> &v);
- int some_intersection(Vec<C, A, S> &v);
- int some_disjunction(Vec<C, A, S> &v);
- int some_difference(Vec<C, A, S> &v);
- void set_intersection(Vec<C, A, S> &v, Vec<C, A, S> &result);
- void set_disjunction(Vec<C, A, S> &v, Vec<C, A, S> &result);
- void set_difference(Vec<C, A, S> &v, Vec<C, A, S> &result);
- size_t set_count() const;
- size_t count() const;
- C *in(C a);
- C *set_in(C a);
- C first_in_set();
- C *set_in_internal(C a);
- void set_expand();
- ssize_t index(C a) const;
- void set_to_vec();
- void vec_to_set();
- void move(Vec<C, A, S> &v);
- void copy(const Vec<C, A, S> &v);
- void fill(size_t n);
- void append(const Vec<C> &v);
- template <typename CountType> void append(const C *src, CountType count);
- void prepend(const Vec<C> &v);
- void remove_index(int index);
- void
- remove(C a)
- {
- int i = index(a);
- if (i >= 0)
- remove_index(i);
- }
- C &insert(size_t index);
- void insert(size_t index, Vec<C> &vv);
- void insert(size_t index, C a);
- void
- push(C a)
- {
- insert(0, a);
- }
- void reverse();
- void reserve(size_t n);
- C *
- end() const
- {
- return v + n;
- }
- C &
- first() const
- {
- return v[0];
- }
- C &
- last() const
- {
- return v[n - 1];
- }
- Vec<C, A, S> &
- operator=(Vec<C, A, S> &v)
- {
- this->copy(v);
- return *this;
- }
- unsigned
- length() const
- {
- return n;
- }
- // vector::size() intentionally not implemented because it should mean "bytes" not count of elements
- int write(int fd);
- int read(int fd);
- void qsort(bool (*lt)(C, C));
- void qsort(bool (*lt)(const C &, const C &));
- static void swap(C *p1, C *p2);
-
-private:
- void move_internal(Vec<C, A, S> &v);
- void copy_internal(const Vec<C, A, S> &v);
- void add_internal(C a);
- C &add_internal();
- void addx();
-};
-
-// c -- class, p -- pointer to elements of v, v -- vector
-#define forv_Vec(_c, _p, _v) \
- if ((_v).n) \
- for (_c *qq__##_p = (_c *)0, *_p = (_v).v[0]; \
- ((uintptr_t)(qq__##_p) < (_v).length()) && ((_p = (_v).v[(intptr_t)qq__##_p]), 1); \
- qq__##_p = (_c *)(((intptr_t)qq__##_p) + 1))
-#define for_Vec(_c, _p, _v) \
- if ((_v).n) \
- for (_c *qq__##_p = (_c *)0, _p = (_v).v[0]; \
- ((uintptr_t)(qq__##_p) < (_v).length()) && ((_p = (_v).v[(intptr_t)qq__##_p]), 1); \
- qq__##_p = (_c *)(((intptr_t)qq__##_p) + 1))
-#define forvp_Vec(_c, _p, _v) \
- if ((_v).n) \
- for (_c *qq__##_p = (_c *)0, *_p = &(_v).v[0]; \
- ((uintptr_t)(qq__##_p) < (_v).length()) && ((_p = &(_v).v[(intptr_t)qq__##_p]), 1); \
- qq__##_p = (_c *)(((intptr_t)qq__##_p) + 1))
-
-template <class C, class A = DefaultAlloc, int S = VEC_INTEGRAL_SHIFT_DEFAULT> class Accum
-{
-public:
- Vec<C, A, S> asset;
- Vec<C, A, S> asvec;
- void
- add(C c)
- {
- if (asset.set_add(c))
- asvec.add(c);
- }
- void
- add(Vec<C, A, S> v)
- {
- for (int i = 0; i < v.n; i++)
- if (v.v[i])
- add(v.v[i]);
- }
- void
- clear()
- {
- asset.clear();
- asvec.clear();
- }
-};
-
-// Intervals store sets in interval format (e.g. [1..10][12..12]).
-// Inclusion test is by binary search on intervals.
-// Deletion is not supported
-class Intervals : public Vec<int>
-{
-public:
- void insert(int n);
- bool in(int n) const;
-};
-
-// UnionFind supports fast unify and finding of
-// 'representitive elements'.
-// Elements are numbered from 0 to N-1.
-class UnionFind : public Vec<int>
-{
-public:
- // set number of elements, initialized to singletons, may be called repeatedly to increase size
- void size(int n);
- // return representitive element
- int find(int n);
- // unify the sets containing the two elements
- void unify(int n, int m);
-};
-
-extern const uintptr_t prime2[];
-extern const uintptr_t open_hash_primes[256];
-
-/* IMPLEMENTATION */
-
-template <class C, class A, int S> inline Vec<C, A, S>::Vec() : n(0), i(0), v(0)
-{
- memset(&e[0], 0, sizeof(e));
-}
-
-template <class C, class A, int S> inline Vec<C, A, S>::Vec(const Vec<C, A, S> &vv)
-{
- copy(vv);
-}
-
-template <class C, class A, int S> inline Vec<C, A, S>::Vec(C c)
-{
- n = 1;
- i = 0;
- v = &e[0];
- e[0] = c;
-}
-
-template <class C, class A, int S>
-inline C
-Vec<C, A, S>::get(size_t i) const
-{
- if (i < n) {
- return v[i];
- } else {
- return C();
- }
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::add(C a)
-{
- if (n & (VEC_INTEGRAL_SIZE - 1))
- v[n++] = a;
- else if (!v)
- (v = e)[n++] = a;
- else
- add_internal(a);
-}
-
-template <class C, class A, int S>
-inline C &
-Vec<C, A, S>::add()
-{
- C *ret;
- if (n & (VEC_INTEGRAL_SIZE - 1))
- ret = &v[n++];
- else if (!v)
- ret = &(v = e)[n++];
- else
- ret = &add_internal();
- return *ret;
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::drop()
-{
- if (n && 0 == --n)
- clear();
-}
-
-template <class C, class A, int S>
-inline C
-Vec<C, A, S>::pop()
-{
- if (!n)
- return 0;
- n--;
- C ret = v[n];
- if (!n)
- clear();
- return ret;
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::set_clear()
-{
- memset(v, 0, n * sizeof(C));
-}
-
-template <class C, class A, int S>
-inline C *
-Vec<C, A, S>::set_add(C a)
-{
- if (n < SET_LINEAR_SIZE) {
- for (C *c = v; c < v + n; c++)
- if (*c == a)
- return 0;
- add(a);
- return &v[n - 1];
- }
- if (n == SET_LINEAR_SIZE) {
- Vec<C, A, S> vv(*this);
- clear();
- for (C *c = vv.v; c < vv.v + vv.n; c++) {
- set_add_internal(*c);
- }
- }
- return set_add_internal(a);
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::set_remove(C a)
-{
- Vec<C, A, S> tmp;
- tmp.move(*this);
- for (C *c = tmp.v; c < tmp.v + tmp.n; c++)
- if (*c != a)
- set_add(a);
-}
-
-template <class C, class A, int S>
-inline size_t
-Vec<C, A, S>::count() const
-{
- int x = 0;
- for (C *c = v; c < v + n; c++)
- if (*c)
- x++;
- return x;
-}
-
-template <class C, class A, int S>
-inline C *
-Vec<C, A, S>::in(C a)
-{
- for (C *c = v; c < v + n; c++)
- if (*c == a)
- return c;
- return NULL;
-}
-
-template <class C, class A, int S>
-inline bool
-Vec<C, A, S>::add_exclusive(C a)
-{
- if (!in(a)) {
- add(a);
- return true;
- } else
- return false;
-}
-
-template <class C, class A, int S>
-inline C *
-Vec<C, A, S>::set_in(C a)
-{
- if (n <= SET_LINEAR_SIZE)
- return in(a);
- return set_in_internal(a);
-}
-
-template <class C, class A, int S>
-inline C
-Vec<C, A, S>::first_in_set()
-{
- for (C *c = v; c < v + n; c++)
- if (*c)
- return *c;
- return 0;
-}
-
-template <class C, class A, int S>
-inline ssize_t
-Vec<C, A, S>::index(C a) const
-{
- for (C *c = v; c < v + n; c++) {
- if (*c == a) {
- return c - v;
- }
- }
- return -1;
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::move_internal(Vec<C, A, S> &vv)
-{
- n = vv.n;
- i = vv.i;
- if (vv.v == &vv.e[0]) {
- memcpy(e, &vv.e[0], sizeof(e));
- v = e;
- } else
- v = vv.v;
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::move(Vec<C, A, S> &vv)
-{
- move_internal(vv);
- vv.v = 0;
- vv.clear();
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::copy(const Vec<C, A, S> &vv)
-{
- n = vv.n;
- i = vv.i;
- if (vv.v == &vv.e[0]) {
- memcpy(e, &vv.e[0], sizeof(e));
- v = e;
- } else {
- if (vv.v)
- copy_internal(vv);
- else
- v = 0;
- }
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::fill(size_t nn)
-{
- for (size_t i = n; i < nn; i++)
- add() = 0;
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::append(const Vec<C> &vv)
-{
- for (C *c = vv.v; c < vv.v + vv.n; c++)
- if (*c != 0)
- add(*c);
-}
-
-template <class C, class A, int S>
-template <typename CountType>
-inline void
-Vec<C, A, S>::append(const C *src, CountType count)
-{
- reserve(length() + count);
- for (CountType c = 0; c < count; ++c) {
- add(src[c]);
- }
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::prepend(const Vec<C> &vv)
-{
- if (vv.n) {
- int oldn = n;
- fill(n + vv.n);
- if (oldn)
- memmove(&v[vv.n], &v[0], oldn * sizeof(v[0]));
- memcpy(&v[0], vv.v, vv.n * sizeof(v[0]));
- }
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::add_internal(C a)
-{
- addx();
- v[n++] = a;
-}
-
-template <class C, class A, int S>
-C &
-Vec<C, A, S>::add_internal()
-{
- addx();
- return v[n++];
-}
-
-template <class C, class A, int S>
-C *
-Vec<C, A, S>::set_add_internal(C c)
-{
- size_t j, k;
- if (n) {
- uintptr_t h = (uintptr_t)c;
- h = h % n;
- for (k = h, j = 0; j < i + 3; j++) {
- if (!v[k]) {
- v[k] = c;
- return &v[k];
- } else if (v[k] == c) {
- return 0;
- }
- k = (k + open_hash_primes[j]) % n;
- }
- }
- Vec<C, A, S> vv;
- vv.move_internal(*this);
- set_expand();
- if (vv.v) {
- set_union(vv);
- }
- return set_add(c);
-}
-
-template <class C, class A, int S>
-C *
-Vec<C, A, S>::set_in_internal(C c)
-{
- size_t j, k;
- if (n) {
- uintptr_t h = (uintptr_t)c;
- h = h % n;
- for (k = h, j = 0; j < i + 3; j++) {
- if (!v[k])
- return 0;
- else if (v[k] == c)
- return &v[k];
- k = (k + open_hash_primes[j]) % n;
- }
- }
- return 0;
-}
-
-template <class C, class A, int S>
-bool
-Vec<C, A, S>::set_union(Vec<C, A, S> &vv)
-{
- bool changed = false;
- for (size_t i = 0; i < vv.n; i++) {
- if (vv.v[i]) {
- changed = set_add(vv.v[i]) || changed;
- }
- }
- return changed;
-}
-
-template <class C, class A, int S>
-int
-Vec<C, A, S>::set_intersection(Vec<C, A, S> &vv)
-{
- Vec<C, A, S> tv;
- tv.move(*this);
- int changed = 0;
- for (int i = 0; i < tv.n; i++)
- if (tv.v[i]) {
- if (vv.set_in(tv.v[i]))
- set_add(tv.v[i]);
- else
- changed = 1;
- }
- return changed;
-}
-
-template <class C, class A, int S>
-int
-Vec<C, A, S>::some_intersection(Vec<C, A, S> &vv)
-{
- for (int i = 0; i < n; i++)
- if (v[i])
- if (vv.set_in(v[i]))
- return 1;
- return 0;
-}
-
-template <class C, class A, int S>
-int
-Vec<C, A, S>::some_disjunction(Vec<C, A, S> &vv)
-{
- for (int i = 0; i < n; i++)
- if (v[i])
- if (!vv.set_in(v[i]))
- return 1;
- for (int i = 0; i < vv.n; i++)
- if (vv.v[i])
- if (!set_in(vv.v[i]))
- return 1;
- return 0;
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::set_intersection(Vec<C, A, S> &vv, Vec<C, A, S> &result)
-{
- for (int i = 0; i < n; i++)
- if (v[i])
- if (vv.set_in(v[i]))
- result.set_add(v[i]);
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::set_disjunction(Vec<C, A, S> &vv, Vec<C, A, S> &result)
-{
- for (int i = 0; i < n; i++)
- if (v[i])
- if (!vv.set_in(v[i]))
- result.set_add(v[i]);
- for (int i = 0; i < vv.n; i++)
- if (vv.v[i])
- if (!set_in(vv.v[i]))
- result.set_add(vv.v[i]);
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::set_difference(Vec<C, A, S> &vv, Vec<C, A, S> &result)
-{
- for (int i = 0; i < n; i++)
- if (v[i])
- if (!vv.set_in(v[i]))
- result.set_add(v[i]);
-}
-
-template <class C, class A, int S>
-int
-Vec<C, A, S>::some_difference(Vec<C, A, S> &vv)
-{
- for (int i = 0; i < n; i++)
- if (v[i])
- if (!vv.set_in(v[i]))
- return 1;
- return 0;
-}
-
-template <class C, class A, int S>
-size_t
-Vec<C, A, S>::set_count() const
-{
- size_t x = 0;
- for (size_t i = 0; i < n; i++) {
- if (v[i]) {
- x++;
- }
- }
- return x;
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::set_to_vec()
-{
- C *x = &v[0], *y = x;
- for (; y < v + n; y++) {
- if (*y) {
- if (x != y)
- *x = *y;
- x++;
- }
- }
- if (i) {
- i = prime2[i]; // convert set allocation to reserve
- if (i - n > 0)
- memset(&v[n], 0, (i - n) * (sizeof(C)));
- } else {
- i = 0;
- if (v == &e[0] && VEC_INTEGRAL_SIZE - n > 0)
- memset(&v[n], 0, (VEC_INTEGRAL_SIZE - n) * (sizeof(C)));
- }
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::vec_to_set()
-{
- Vec<C, A, S> vv;
- vv.move(*this);
- for (C *c = vv.v; c < vv.v + vv.n; c++)
- set_add(*c);
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::remove_index(int index)
-{
- if (n > 1)
- memmove(&v[index], &v[index + 1], (n - 1 - index) * sizeof(v[0]));
- n--;
- if (n <= 0)
- v = e;
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::insert(size_t index, C a)
-{
- add();
- memmove(&v[index + 1], &v[index], (n - index - 1) * sizeof(C));
- v[index] = a;
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::insert(size_t index, Vec<C> &vv)
-{
- fill(n + vv.n);
- memmove(&v[index + vv.n], &v[index], (n - index - 1) * sizeof(C));
- for (int x = 0; x < vv.n; x++)
- v[index + x] = vv[x];
-}
-
-template <class C, class A, int S>
-C &
-Vec<C, A, S>::insert(size_t index)
-{
- add();
- memmove(&v[index + 1], &v[index], (n - index - 1) * sizeof(C));
- memset(&v[index], 0, sizeof(C));
- return v[index];
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::reverse()
-{
- for (int i = 0; i < n / 2; i++) {
- C *s = &v[i], *e = &v[n - 1 - i];
- C t;
- memcpy(&t, s, sizeof(t));
- memcpy(s, e, sizeof(t));
- memcpy(e, &t, sizeof(t));
- }
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::copy_internal(const Vec<C, A, S> &vv)
-{
- int l = n, nl = (1 + VEC_INITIAL_SHIFT);
- l = l >> VEC_INITIAL_SHIFT;
- while (l) {
- l = l >> 1;
- nl++;
- }
- nl = 1 << nl;
- v = (C *)A::alloc(nl * sizeof(C));
- memcpy(v, vv.v, n * sizeof(C));
- memset(v + n, 0, (nl - n) * sizeof(C));
- if (i > n) // reset reserve
- i = 0;
-}
-
-template <class C, class A, int S>
-void
-Vec<C, A, S>::set_expand()
-{
- if (!n)
- i = SET_INITIAL_INDEX;
- else
- i = i + 1;
- n = prime2[i];
- v = (C *)A::alloc(n * sizeof(C));
- memset(v, 0, n * sizeof(C));
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::reserve(size_t x)
-{
- if (x <= n)
- return;
- unsigned xx = 1 << VEC_INITIAL_SHIFT;
- while (xx < x)
- xx *= 2;
- i = xx;
- void *vv = (void *)v;
- v = (C *)A::alloc(i * sizeof(C));
- if (vv && n)
- memcpy(v, vv, n * sizeof(C));
- memset(&v[n], 0, (i - n) * sizeof(C));
- if (vv && vv != e)
- A::free(vv);
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::addx()
-{
- if (!v) {
- v = e;
- return;
- }
- if (v == e) {
- v = (C *)A::alloc(VEC_INITIAL_SIZE * sizeof(C));
- memcpy(v, &e[0], n * sizeof(C));
- ink_assert(n < VEC_INITIAL_SIZE);
- memset(&v[n], 0, (VEC_INITIAL_SIZE - n) * sizeof(C));
- } else {
- if ((n & (n - 1)) == 0) {
- size_t nl = n * 2;
- if (nl <= i) {
- return;
- } else {
- i = 0;
- }
- void *vv = (void *)v;
- v = (C *)A::alloc(nl * sizeof(C));
- memcpy(v, vv, n * sizeof(C));
- memset(&v[n], 0, n * sizeof(C));
- A::free(vv);
- }
- }
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::reset()
-{
- v = NULL;
- n = 0;
- i = 0;
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::clear()
-{
- if (v && v != e)
- A::free(v);
- reset();
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::free_and_clear()
-{
- for (size_t x = 0; x < (n); x++)
- A::free((void *)v[x]);
- clear();
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::delete_and_clear()
-{
- for (size_t x = 0; x < n; x++) {
- if (v[x]) {
- delete v[x];
- }
- }
- clear();
-}
-
-template <class C, class A, int S> inline Vec<C, A, S>::~Vec()
-{
- if (v && v != e)
- A::free(v);
-}
-
-template <class C, class A, int S>
-inline int
-marshal_size(Vec<C, A, S> &v)
-{
- int l = sizeof(int) * 2;
- for (int x = 0; x < v.n; x++)
- l += ::marshal_size(v.v[x]);
- return l;
-}
-
-template <class C, class A, int S>
-inline int
-marshal(Vec<C, A, S> &v, char *buf)
-{
- char *x = buf;
- *(int *)x = v.n;
- x += sizeof(int);
- *(int *)x = v.i;
- x += sizeof(int);
- for (int i = 0; i < v.n; i++)
- x += ::marshal(v.v[i], x);
- return x - buf;
-}
-
-template <class C, class A, int S>
-inline int
-unmarshal(Vec<C, A, S> &v, char *buf)
-{
- char *x = buf;
- v.n = *(int *)x;
- x += sizeof(int);
- v.i = *(int *)x;
- x += sizeof(int);
- if (v.n) {
- v.v = (C *)A::alloc(sizeof(C) * v.n);
- memset(v.v, 0, sizeof(C) * v.n);
- } else
- v.v = v.e;
- for (int i = 0; i < v.n; i++)
- x += ::unmarshal(v.v[i], x);
- return x - buf;
-}
-
-template <class C, class A, int S>
-inline int
-Vec<C, A, S>::write(int fd)
-{
- int r = 0, t = 0;
- if ((r = ::write(fd, this, sizeof(*this))) < 0)
- return r;
- t += r;
- if ((r = ::write(fd, v, n * sizeof(C))) < 0)
- return r;
- t += r;
- return t;
-}
-
-template <class C, class A, int S>
-inline int
-Vec<C, A, S>::read(int fd)
-{
- int r = 0, t = 0;
- if ((r = ::read(fd, this, sizeof(*this))) < 0)
- return r;
- t += r;
- v = (C *)A::alloc(sizeof(C) * n);
- memset(v, 0, sizeof(C) * n);
- if ((r = ::read(fd, v, n * sizeof(C))) < 0)
- return r;
- t += r;
- return t;
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::swap(C *p1, C *p2)
-{
- C t = *p1;
- *p1 = *p2;
- *p2 = t;
-}
-
-template <class C>
-inline void
-qsort_Vec(C *left, C *right, bool (*lt)(C, C))
-{
- if (right - left < 5) {
- for (C *y = right - 1; y > left; y--) {
- for (C *x = left; x < y; x++) {
- if (lt(x[1], x[0])) {
- C t = x[0];
- x[0] = x[1];
- x[1] = t;
- }
- }
- }
- } else {
- C *center = left + ((right - left) / 2);
- C median;
-
- // find the median
- if (lt(*center, *left)) { // order left and center
- Vec<C>::swap(center, left);
- }
- if (lt(*(right - 1), *left)) { // order left and right
- Vec<C>::swap(right - 1, left);
- }
- if (lt(*(right - 1), *center)) { // order right and center
- Vec<C>::swap((right - 1), center);
- }
- Vec<C>::swap(center, right - 2); // stash the median one from the right for now
- median = *(right - 2); // the median of left, center and right values
-
- // now partition, pivoting on the median value
- // l ptr is +1 b/c we already put the lowest of the incoming left, center
- // and right in there, ignore it for now
- // r ptr is -2 b/c we already put the biggest of the 3 values in (right-1)
- // and the median in (right -2)
- C *l = left + 1, *r = right - 2;
-
- // move l and r until they have something to do
- while (lt(median, *(r - 1))) {
- r--;
- }
- while (l < r && lt(*l, median)) {
- l++;
- }
- // until l and r meet,
- // compare l and median
- // swap l for r if l is larger than median
- while (l < r) {
- if (lt(*l, median)) {
- l++;
- } else {
- Vec<C>::swap(l, r - 1);
- r--;
- }
- }
-
- Vec<C>::swap(l, right - 2); // restore median to its rightful place
-
- // recurse for the littles (left segment)
- qsort_Vec<C>(left, l, lt);
- // recurse for the bigs (right segment)
- qsort_Vec<C>(l + 1, right, lt);
- }
-}
-
-template <class C>
-inline void
-qsort_VecRef(C *left, C *right, bool (*lt)(const C &, const C &), unsigned int *p_ctr)
-{
- if (right - left < 5) {
- for (C *y = right - 1; y > left; y--) {
- for (C *x = left; x < y; x++) {
- if (lt(x[1], x[0])) {
- C t = x[0];
- x[0] = x[1];
- x[1] = t;
- }
- }
- }
- } else {
- C *center = left + ((right - left) / 2);
- C median;
-
- // find the median
- if (lt(*center, *left)) { // order left and center
- Vec<C>::swap(center, left);
- }
- if (lt(*(right - 1), *left)) { // order left and right
- Vec<C>::swap(right - 1, left);
- }
- if (lt(*(right - 1), *center)) { // order right and center
- Vec<C>::swap((right - 1), center);
- }
- Vec<C>::swap(center, right - 2); // stash the median one from the right for now
- median = *(right - 2); // the median of left, center and right values
-
- // now partition, pivoting on the median value
- // l ptr is +1 b/c we already put the lowest of the incoming left, center
- // and right in there, ignore it for now
- // r ptr is -2 b/c we already put the biggest of the 3 values in (right-1)
- // and the median in (right -2)
- C *l = left + 1, *r = right - 2;
-
- // move l and r until they have something to do
- while (lt(median, *(r - 1))) {
- r--;
- }
- while (l < r && lt(*l, median)) {
- l++;
- }
- // until l and r meet,
- // compare l and median
- // swap l for r if l is larger than median
- while (l < r) {
- if (lt(*l, median)) {
- l++;
- } else {
- Vec<C>::swap(l, r - 1);
- r--;
- }
- }
-
- Vec<C>::swap(l, right - 2); // restore median to its rightful place
-
- // recurse for the littles (left segment)
- qsort_VecRef<C>(left, l, lt, p_ctr);
- // recurse for the bigs (right segment)
- qsort_VecRef<C>(l + 1, right, lt, p_ctr);
- }
- (*p_ctr)++;
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::qsort(bool (*lt)(C, C))
-{
- if (n)
- qsort_Vec<C>(&v[0], end(), lt);
-}
-
-template <class C, class A, int S>
-inline void
-Vec<C, A, S>::qsort(bool (*lt)(const C &, const C &))
-{
- static unsigned int ctr = 0;
- if (n)
- qsort_VecRef<C>(&v[0], end(), lt, &ctr);
- Debug("qsort", "took %u iterations to sort %ld elements", ctr, n);
-}
-void test_vec();
-
-#endif
diff --git a/lib/ts/test_Vec.cc b/lib/ts/test_Vec.cc
index e1c7f02..6eab32f 100644
--- a/lib/ts/test_Vec.cc
+++ b/lib/ts/test_Vec.cc
@@ -25,7 +25,182 @@
#include <cstdint>
#include <cstdio>
#include "ts/ink_assert.h"
-#include "ts/Vec.h"
+#include "ts/Map.h"
+
+// Intervals store sets in interval format (e.g. [1..10][12..12]).
+// Inclusion test is by binary search on intervals.
+// Deletion is not supported
+class Intervals : public Vec<int>
+{
+public:
+ void insert(int n);
+ bool in(int n) const;
+};
+
+// UnionFind supports fast unify and finding of
+// 'representitive elements'.
+// Elements are numbered from 0 to N-1.
+class UnionFind : public Vec<int>
+{
+public:
+ // set number of elements, initialized to singletons, may be called repeatedly to increase size
+ void size(int n);
+ // return representitive element
+ int find(int n);
+ // unify the sets containing the two elements
+ void unify(int n, int m);
+};
+
+// binary search over intervals
+static int
+i_find(const Intervals *i, int x)
+{
+ ink_assert(i->n);
+ int l = 0, h = i->n;
+Lrecurse:
+ if (h <= l + 2) {
+ if (h <= l) {
+ return -(l + 1);
+ }
+ if (x < i->v[l] || x > i->v[l + 1]) {
+ return -(l + 1);
+ }
+ return h;
+ }
+ int m = (((h - l) / 4) * 2) + l;
+ if (x > i->v[m + 1]) {
+ l = m;
+ goto Lrecurse;
+ }
+ if (x < i->v[m]) {
+ h = m;
+ goto Lrecurse;
+ }
+ return (l + 1);
+}
+
+bool
+Intervals::in(int x) const
+{
+ if (!n) {
+ return false;
+ }
+ if (i_find(this, x) > 0) {
+ return true;
+ }
+ return false;
+}
+
+// insert into interval with merge
+void
+Intervals::insert(int x)
+{
+ if (!n) {
+ add(x);
+ add(x);
+ return;
+ }
+ int l = i_find(this, x);
+ if (l > 0) {
+ return;
+ }
+ l = -l - 1;
+
+ if (x > v[l + 1]) {
+ if (x == v[l + 1] + 1) {
+ v[l + 1]++;
+ goto Lmerge;
+ }
+ l += 2;
+ if (l < (int)n) {
+ if (x == v[l] - 1) {
+ v[l]--;
+ goto Lmerge;
+ }
+ }
+ goto Lmore;
+ } else {
+ ink_assert(x < v[l]);
+ if (x == v[l] - 1) {
+ v[l]--;
+ goto Lmerge;
+ }
+ if (!l) {
+ goto Lmore;
+ }
+ l -= 2;
+ if (x == v[l + 1] + 1) {
+ v[l + 1]++;
+ goto Lmerge;
+ }
+ }
+Lmore:
+ fill(n + 2);
+ if (n - 2 - l > 0) {
+ memmove(v + l + 2, v + l, sizeof(int) * (n - 2 - l));
+ }
+ v[l] = x;
+ v[l + 1] = x;
+ return;
+Lmerge:
+ if (l) {
+ if (v[l] - v[l - 1] < 2) {
+ l -= 2;
+ goto Ldomerge;
+ }
+ }
+ if (l < (int)(n - 2)) {
+ if (v[l + 2] - v[l + 1] < 2) {
+ goto Ldomerge;
+ }
+ }
+ return;
+Ldomerge:
+ memmove(v + l + 1, v + l + 3, sizeof(int) * (n - 3 - l));
+ n -= 2;
+ goto Lmerge;
+}
+
+void
+UnionFind::size(int s)
+{
+ size_t nn = n;
+ fill(s);
+ for (size_t i = nn; i < n; i++) {
+ v[i] = -1;
+ }
+}
+
+int
+UnionFind::find(int n)
+{
+ int i, t;
+ for (i = n; v[i] >= 0; i = v[i]) {
+ ;
+ }
+ while (v[n] >= 0) {
+ t = n;
+ n = v[n];
+ v[t] = i;
+ }
+ return i;
+}
+
+void
+UnionFind::unify(int n, int m)
+{
+ n = find(n);
+ m = find(m);
+ if (n != m) {
+ if (v[m] < v[n]) {
+ v[m] += (v[n] - 1);
+ v[n] = m;
+ } else {
+ v[n] += (v[m] - 1);
+ v[m] = n;
+ }
+ }
+}
static void
test_append()
--
To stop receiving notification emails like this one, please contact
['"commits@trafficserver.apache.org" <co...@trafficserver.apache.org>'].