git.iko.soy/bridge
on c19b2a8 help sign in
bridge/src/nockjs/hamt.js
137 lines 2.7 kB history raw
1/* keys can be any noun, values aren't constrained */
3function Slot() {
4}
6function Node() {
7 Slot.call(this);
8 this.slots = new Array(32);
9}
10Node.prototype = Object.create(Slot.prototype);
11Node.prototype.constructor = Node;
13Node.prototype.insert = function(key, val, lef, rem) {
14 var inx;
15 lef -= 5;
16 inx = rem >>> lef;
17 rem &= ((1 << lef) - 1);
19 this.slots[inx] = ( undefined === this.slots[inx] )
20 ? new Single(key, val)
21 : this.slots[inx].insert(key, val, lef, rem);
22 return this;
23};
25Node.prototype.get = function(key, lef, rem) {
26 var inx, sot;
27 lef -= 5;
28 inx = rem >>> lef;
29 rem &= ((1 << lef) - 1);
30 sot = this.slots[inx];
32 return ( undefined === sot ) ? undefined : sot.get(key, lef, rem);
33};
35function Bucket() {
36 this.singles = [];
38Bucket.prototype = Object.create(Slot.prototype);
39Bucket.prototype.constructor = Bucket;
41Bucket.prototype.insert = function(key, val, lef, rem) {
42 var s, a = this.singles;
44 for ( var i = 0; i < a.length; ++i ) {
45 s = a[i];
46 if ( s.key.equals(key) ) {
47 s.val = val;
48 return this;
49 }
50 }
51 a.push(new Single(key, val));
52 return this;
53};
55Bucket.prototype.get = function(key, lef, rem) {
56 var s, a = this.singles;
58 for ( var i = 0; i < a.length; ++i ) {
59 s = a[i];
60 if ( s.key.equals(key) ) {
61 return s.val;
62 }
63 }
65 return undefined;
66};
68function Single(key, val) {
69 Slot.call(this);
70 this.key = key;
71 this.val = val;
73Single.prototype = Object.create(Slot.prototype);
74Single.prototype.constructor = Single;
76Single.prototype.insert = function(key, val, lef, rem) {
77 if ( this.key.equals(key) ) {
78 this.val = val;
79 return this;
80 }
81 else {
82 var n, rom = this.key.mug() & ((1 << lef) - 1);
84 if ( lef > 0 ) {
85 n = new Node();
86 }
87 else {
88 n = new Bucket();
89 }
90 n.insert(this.key, this.val, lef, rom);
91 n.insert(key, val, lef, rem);
92 return n;
93 }
94};
96Single.prototype.get = function(key, lef, rem) {
97 if ( this.key.equals(key) ) {
98 return this.val;
99 }
100 else {
101 return undefined;
102 }
103};
105function NounMap() {
106 this.slots = new Array(64);
109NounMap.prototype.insert = function(key, val) {
110 var m = key.mug();
111 var inx = m >>> 25;
112 var sot = this.slots;
113 if ( undefined === sot[inx] ) {
114 sot[inx] = new Single(key, val);
115 }
116 else {
117 var rem = m & ((1 << 25) - 1);
118 sot[inx] = sot[inx].insert(key, val, 25, rem);
119 }
120};
122NounMap.prototype.get = function(key) {
123 var m = key.mug();
124 var inx = m >>> 25;
125 var sot = this.slots[inx];
126 if ( undefined === sot ) {
127 return undefined;
128 }
129 else {
130 var rem = m & ((1 << 25) - 1);
131 return sot.get(key, 25, rem);
132 }
133};
135module.exports = {
136 NounMap: NounMap
137};