summaryrefslogtreecommitdiffstats
path: root/web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx
diff options
context:
space:
mode:
Diffstat (limited to 'web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx')
-rw-r--r--web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx295
1 files changed, 0 insertions, 295 deletions
diff --git a/web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx b/web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx
deleted file mode 100644
index b366e43a0..000000000
--- a/web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx
+++ /dev/null
@@ -1,295 +0,0 @@
-/**
- * This is a JSX version of shellinford library:
- * https://code.google.com/p/shellinford/
- *
- * License: http://shibu.mit-license.org/
- */
-
-import "binary-util.jsx";
-
-class BitVector
-{
- static const SMALL_BLOCK_SIZE : int = 32;
- static const LARGE_BLOCK_SIZE : int = 256;
- static const BLOCK_RATE : int = 8;
-
- var _v : number[];
- var _r : number[];
- var _size : int;
- var _size1 : int;
-
- function constructor ()
- {
- this._r = [] : number[];
- this._v = [] : number[];
- this.clear();
- }
-
- function build () : void
- {
- this._size1 = 0;
- for (var i = 0; i < this._v.length; i++)
- {
- if (i % BitVector.BLOCK_RATE == 0)
- {
- this._r.push(this.size(true));
- }
- this._size1 += this._rank32(this._v[i], BitVector.SMALL_BLOCK_SIZE, true);
- }
- }
-
- function clear () : void
- {
- this._v.length = 0;
- this._r.length = 0;
- this._size = 0;
- this._size1 = 0;
- }
-
- function size () : int
- {
- return this._size;
- }
-
- function size (b : boolean) : int
- {
- return b ? (this._size1) : (this._size - this._size1);
- }
-
- function set (value : int) : void
- {
- this.set(value, true);
- }
-
- function set (value : int, flag : boolean) : void
- {
- if (value >= this.size())
- {
- this._size = value + 1;
- }
- var q : int = value / BitVector.SMALL_BLOCK_SIZE;
- var r : int = value % BitVector.SMALL_BLOCK_SIZE;
- while (q >= this._v.length)
- {
- this._v.push(0);
- }
- var m : int = 0x1 << r;
- if (flag)
- {
- this._v[q] |= m;
- }
- else
- {
- this._v[q] &= ~m;
- }
- }
-
- function get (value : int) : boolean
- {
- if (value >= this.size())
- {
- throw new Error("BitVector.get() : range error");
- }
- var q : int = value / BitVector.SMALL_BLOCK_SIZE;
- var r : int = value % BitVector.SMALL_BLOCK_SIZE;
- var m : int = 0x1 << r;
- return (this._v[q] & m) as boolean;
- }
-
- function rank (i : int) : int
- {
- return this.rank(i, true);
- }
-
- function rank (i : int, b : boolean) : int
- {
- if (i > this.size())
- {
- throw new Error("BitVector.rank() : range error");
- }
- if (i == 0)
- {
- return 0;
- }
- i--;
- var q_large : int = Math.floor(i / BitVector.LARGE_BLOCK_SIZE);
- var q_small : int = Math.floor(i / BitVector.SMALL_BLOCK_SIZE);
- var r : int = Math.floor(i % BitVector.SMALL_BLOCK_SIZE);
- var rank : int = this._r[q_large];
- if (!b)
- {
- rank = q_large * BitVector.LARGE_BLOCK_SIZE - rank;
- }
- var begin = q_large * BitVector.BLOCK_RATE;
- for (var j = begin; j < q_small; j++)
- {
- rank += this._rank32(this._v[j], BitVector.SMALL_BLOCK_SIZE, b);
- }
- rank += this._rank32(this._v[q_small], r + 1, b);
- return rank;
- }
-
- function select(i : int) : int
- {
- return this.select(i, true);
- }
-
- function select(i : int, b : boolean) : int
- {
- if (i >= this.size(b))
- {
- throw new Error("BitVector.select() : range error");
- }
-
- var left = 0;
- var right = this._r.length;
- while (left < right)
- {
- var pivot = Math.floor((left + right) / 2);
- var rank = this._r[pivot];
- if (!b)
- {
- rank = pivot * BitVector.LARGE_BLOCK_SIZE - rank;
- }
- if (i < rank)
- {
- right = pivot;
- }
- else
- {
- left = pivot + 1;
- }
- }
- right--;
-
- if (b)
- {
- i -= this._r[right];
- }
- else
- {
- i -= right * BitVector.LARGE_BLOCK_SIZE - this._r[right];
- }
- var j = right * BitVector.BLOCK_RATE;
- while (1)
- {
- var rank = this._rank32(this._v[j], BitVector.SMALL_BLOCK_SIZE, b);
- if (i < rank)
- {
- break;
- }
- j++;
- i -= rank;
- }
- return j * BitVector.SMALL_BLOCK_SIZE + this._select32(this._v[j], i, b);
- }
-
- function _rank32 (x : int, i : int, b : boolean) : int
- {
- if (!b)
- {
- x = ~x;
- }
- x <<= (BitVector.SMALL_BLOCK_SIZE - i);
- x = ((x & 0xaaaaaaaa) >>> 1)
- + (x & 0x55555555);
- x = ((x & 0xcccccccc) >>> 2)
- + (x & 0x33333333);
- x = ((x & 0xf0f0f0f0) >>> 4)
- + (x & 0x0f0f0f0f);
- x = ((x & 0xff00ff00) >>> 8)
- + (x & 0x00ff00ff);
- x = ((x & 0xffff0000) >>> 16)
- + (x & 0x0000ffff);
- return x;
- }
-
- function _select32(x : int, i : int, b : boolean) : int
- {
- if (!b)
- {
- x = ~x;
- }
- var x1 = ((x & 0xaaaaaaaa) >>> 1)
- + (x & 0x55555555);
- var x2 = ((x1 & 0xcccccccc) >>> 2)
- + (x1 & 0x33333333);
- var x3 = ((x2 & 0xf0f0f0f0) >>> 4)
- + (x2 & 0x0f0f0f0f);
- var x4 = ((x3 & 0xff00ff00) >>> 8)
- + (x3 & 0x00ff00ff);
- var x5 = ((x4 & 0xffff0000) >>> 16)
- + (x4 & 0x0000ffff);
- i++;
- var pos = 0;
- var v5 = x5 & 0xffffffff;
- if (i > v5)
- {
- i -= v5;
- pos += 32;
- }
- var v4 = (x4 >>> pos) & 0x0000ffff;
- if (i > v4)
- {
- i -= v4;
- pos += 16;
- }
- var v3 = (x3 >>> pos) & 0x000000ff;
- if (i > v3)
- {
- i -= v3;
- pos += 8;
- }
- var v2 = (x2 >>> pos) & 0x0000000f;
- if (i > v2)
- {
- i -= v2;
- pos += 4;
- }
- var v1 = (x1 >>> pos) & 0x00000003;
- if (i > v1)
- {
- i -= v1;
- pos += 2;
- }
- var v0 = (x >>> pos) & 0x00000001;
- if (i > v0)
- {
- i -= v0;
- pos += 1;
- }
- return pos;
- }
-
- function dump () : string
- {
- var contents = [] : string[];
- contents.push(Binary.dump32bitNumber(this._size));
- contents.push(Binary.dump32bitNumberList(this._v));
- return contents.join('');
- }
-
- function dump (report : CompressionReport) : string
- {
- var contents = [] : string[];
- contents.push(Binary.dump32bitNumber(this._size));
- report.add(2, 2);
- contents.push(Binary.dump32bitNumberList(this._v, report));
- return contents.join('');
- }
-
- function load (data : string) : int
- {
- return this.load(data, 0);
- }
-
- function load (data : string, offset : int) : int
- {
- this.clear();
- this._size = Binary.load32bitNumber(data, offset);
- var result = Binary.load32bitNumberList(data, offset + 2);
- this._v = result.result;
- this.build();
- return result.offset;
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-02 18:15:37 +0000