Othello
 All Classes Files Functions Variables Macros
othello.h
Go to the documentation of this file.
1 #pragma once
2 
7 #include <vector>
8 #include <iostream>
9 #include <array>
10 #include <queue>
11 #include <cstring>
12 #include <list>
13 #include "hash.h"
14 #include "io_helper.h"
15 #include "disjointset.h"
16 #include <set>
17 using namespace std;
18 
24 template< class keyType>
25 class Othello
26 {
27  typedef uint64_t valueType;
28 #define MAX_REHASH 20
29 public:
30  vector<valueType> mem;
31  uint32_t L;
32 // uint32_t LMASK; return value must be within [0..2^L-1], i.e., LMASK==((1<<L)-1);
33 #define LMASK ((L==64)?(~0ULL):((1ULL<<L)-1))
34  uint32_t ma;
35  uint32_t mb;
36  Hasher32<keyType> Ha; //<! hash function Ha
37  Hasher32<keyType> Hb; //<! hash function Hb
38  bool build = false;
39  uint32_t trycount = 0;
40  DisjointSet disj;
41  vector<uint32_t> fillcount;
42  uint32_t mykeycount;
43 #define FILLCNTLEN (sizeof(uint32_t)*8)
44  uint32_t allowed_conflicts;
45  vector<keyType> removedKeys;
46 private:
47  bool autoclear = false;
48  keyType *keys;
49 
54  inline valueType get(uint32_t loc) { //
55  uint64_t st = ((uint64_t) loc) * L;
56  uint32_t mx = st & 0x3F; //mx = st % 64
57  if ( L & (L-1) ) {
58  //L &(L-1) !=0 ==> L is NOT some power of 2 ==> value may cross the uint64_t barrier.
59  if ( (mx + L) > 64 ) {
60  //mx+L > 64 means the value cross the barrier.
61  //The highest (64-mx) bits of mem[st>>6],
62  //the lowest L-(64-mx) bits of mem[(st>>6)+1], shl (64-mx)
63  return ((mem[st>>6]>>mx) | (mem[(st>>6)+1]<<(64-mx)));
64  };
65  }
66  return (mem[st>>6]>>mx);
67  }
68 
69 
70 
71  valueType inline set(uint32_t loc, valueType &value) {
72  value &= LMASK;
73  uint64_t st = ((uint64_t) loc) * L;
74  uint32_t mx = st & 0x3F; //mx = st % 64
75  if ( L & (L-1) ) {
76  if ( (mx + L) > 64 ) {
77  mem[st>>6] &= ((UINT64_MAX) >> (64-mx));
78  mem[st>>6] |= (value << mx);
79  mem[(st>>6)+1] &= (UINT64_MAX << ((mx+L)-64));
80  mem[(st>>6)+1] |= (value >> (64-mx));
81  return value;
82  };
83  }
84  mem[st>>6] &= (~(LMASK << mx));
85  mem[st>>6] |= (value << mx);
86  return value;
87  }
88 
89 
90  inline valueType getrand(valueType &v) {
91  valueType va = rand();
92  va <<=28;
93  va ^= rand();
94  va <<=28;
95  v = (va ^ rand());
96  }
97 
98  void newHash() {
99  uint32_t s1 = rand();
100  uint32_t s2 = rand();
101 #ifdef HASHSEED1
102  s1 = HASHSEED1;
103  s2 = HASHSEED2;
104 #endif
105  Ha.setMaskSeed(ma-1,s1);
106  Hb.setMaskSeed(mb-1,s2);
107  trycount++;
108  if (trycount>1) printf("NewHash for the %d time\n", trycount);
109  }
110 
111  vector<int32_t> *first = NULL, *nxt1 = NULL, *nxt2 = NULL;
112  bool testHash(uint32_t keycount);
113  vector<bool> filled;
114 
123  void fillvalue(void *values, uint32_t keycount, size_t valuesize);
124  void fillvalueBFS(void *values, size_t valuesize,int root, bool usepublicFilled);
125  bool trybuild(void *values, uint32_t keycount, size_t valuesize) {
126  bool succ;
127  disj.setLength(ma+mb);
128  if (succ = testHash(keycount)) {
129  fillvalue(values, keycount,valuesize);
130  }
131  if (autoclear || (!succ))
132  finishBuild();
133  //forbid using disj any more.
134  disj.setLength(1);
135  return succ;
136  }
137 public:
150  Othello(uint8_t _L, keyType *_keys, uint32_t keycount, bool _autoclear = true, void *_values = NULL, size_t _valuesize = 0, int32_t _allowed_conflicts = -1 ) {
151  mykeycount = keycount;
152  allowed_conflicts = _allowed_conflicts;
153  L = _L;
154  autoclear = _autoclear;
155  keys = _keys;
156  int hl1 = 8; //start from ma=64
157  int hl2 = 7; //start from mb=64
158  while ((1UL<<hl2) < keycount * 1) hl2++;
159  while ((1UL<<hl1) < keycount* 1.333334) hl1++;
160  ma = (1UL<<hl1);
161  mb = (1UL<<hl2);
162  mem.resize(1);
163  if (allowed_conflicts<0) {
164  allowed_conflicts = (ma<20)?0:ma-20;
165  }
166  uint64_t bitcnt = (ma+mb);
167  bitcnt *= L;
168  while (bitcnt % (sizeof(valueType)*8)) bitcnt++;
169  bitcnt /= (sizeof(valueType)*8);
170  mem.resize(bitcnt,0ULL);
171  while ( ((uint64_t)mem.size())*sizeof(mem[0])*8ULL<(ma+mb)*((uint64_t)L) )
172  mem.push_back(0);
173 
174 
175  cout << "Building" <<endl;
176  trycount = 0;
177  while ( (!build) && (hl1<=31&&hl2<=31)) {
178  while ((!build) && (trycount<MAX_REHASH)) {
179  newHash();
180  build = trybuild( _values, keycount, _valuesize);
181  }
182  if (!build) {
183  if (hl1 == hl2) hl1++;
184  else hl2++;
185  ma = (1UL<<hl1);
186  mb = (1UL<<hl2);
187  mem.resize(1);
188  uint64_t bitcnt = (ma+mb);
189  bitcnt *= L;
190  while (bitcnt % (sizeof(valueType)*8)) bitcnt++;
191  bitcnt /= (sizeof(valueType)*8);
192  mem.resize(bitcnt,0ULL);
193  while ( ((uint64_t)mem.size())*sizeof(mem[0])*8ULL<(ma+mb)*((uint64_t)L) )
194  mem.push_back(0);
195 
196  cout << "Extend Othello Length to" << human(keycount) <<" Keys, ma/mb = " << human(ma) <<"/"<<human(mb) <<" keyT"<< sizeof(keyType)*8<<"b valueT" << sizeof(valueType)*8<<"b"<<" L="<<(int) L<<endl;
197  trycount = 0;
198  }
199  }
200  printf("%08x %08x\n", Ha.s, Hb.s);
201  if (build)
202  cout << "Succ " << human(keycount) <<" Keys, ma/mb = " << human(ma) <<"/"<<human(mb) <<" keyT"<< sizeof(keyType)*8<<"b valueT" << sizeof(valueType)*8<<"b"<<" L="<<(int) L <<" After "<<trycount << "tries"<< endl;
203 
204  else
205  cout << "Build Fail!" << endl;
206  }
208  template<typename VT>
209  Othello(uint8_t _L, vector<keyType> &keys, vector<VT> &values, bool _autoclear = true, int32_t allowed_conflicts = -1) :
210  Othello(_L, & (keys[0]),keys.size(), _autoclear, &(values[0]), sizeof(VT), allowed_conflicts)
211  {
212  }
213 
215  void finishBuild() {
216  delete nxt1;
217  delete nxt2;
218  delete first;
219  nxt1 = nxt2 = first= NULL;
220  disj.finish();
221  filled.clear();
222  }
223 
235  void exportInfo(unsigned char * v) {
236  memset(v,0,0x20);
237  uint32_t s1 = Ha.s;
238  uint32_t s2 = Hb.s;
239  memcpy(v,&L, sizeof(uint32_t));
240  memcpy(v+4,&s1,sizeof(uint32_t));
241  memcpy(v+8,&s2,sizeof(uint32_t));
242  int hl1 = 0, hl2 = 0;
243  if (ma == 0 || mb ==0) {
244  hl1 = hl2 = 0;
245  }
246  else {
247  while ((1<<hl1)!= ma) hl1++;
248  while ((1<<hl2)!= mb) hl2++;
249  }
250  memcpy(v+0x10,&hl1, sizeof(uint32_t));
251  memcpy(v+0x14,&hl2,sizeof(uint32_t));
252  }
257  Othello(unsigned char *v) {
258  int32_t hl1,hl2;
259  int32_t s1,s2;
260  memcpy(&(L),v,sizeof(uint32_t));
261  memcpy(&(s1),v+4,sizeof(uint32_t));
262  memcpy(&(s2),v+8,sizeof(uint32_t));
263  memcpy(&hl1, v+0x10, sizeof(uint32_t));
264  memcpy(&hl2, v+0x14, sizeof(uint32_t));
265  if (hl1 > 0 && hl2 >0) {
266  ma = (1<<hl1);
267  mb = (1<<hl2);
268  mem.resize(1);
269  uint64_t bitcnt = (ma+mb);
270  bitcnt *= L;
271  while (bitcnt % (sizeof(valueType)*8)) bitcnt++;
272  bitcnt /= (sizeof(valueType)*8);
273  mem.resize(bitcnt,0ULL);
274  while ( ((uint64_t)mem.size())*sizeof(mem[0])*8ULL<(ma+mb)*((uint64_t)L) )
275  mem.push_back(0);
276  Ha.setMaskSeed(ma-1,s1);
277  Hb.setMaskSeed(mb-1,s2);
278  }
279  else
280  ma = mb =0;
281  }
285  void addkeys(int newkeys, void *values, uint32_t valuesize) {
286  nxt1->resize(mykeycount+newkeys);
287  nxt2->resize(mykeycount+newkeys);
288 
289  for (int i = mykeycount; i< mykeycount+newkeys; i++){
290  uint32_t ha,hb;
291  get_hash(keys[i],ha,hb);
292  if (testConnected(ha,hb)) {
293  mykeycount += newkeys;
294  trybuild(values, mykeycount, L);
295  }
296  else {
297  (*nxt1)[i] = (*first)[ha];
298  (*first)[ha] = i;
299  (*nxt2)[i] = (*first)[hb];
300  (*first)[hb] = i;
301  fillvalueBFS(values, valuesize, ha, false);
302  }
303  }
304  mykeycount += newkeys;
305  }
306 
310  uint64_t queryInt(const keyType &k) {
311  uint32_t ha,hb;
312  return query(k,ha,hb);
313  }
314 
315 
316 
317  void printValueTSize() {
318  std::cout << sizeof(valueType) << std::endl;
319  }
320 
321 
322  vector<uint32_t> getCnt();
323  vector<double> getRatio();
324 
325  void randomflip();
326 
331  void setAlienPreference(double ideal = 1.0);
332 private:
333  void inline get_hash_1(const keyType &v, uint32_t &ret1) {
334  ret1 = (Ha)(v);
335  }
336 public:
344  inline valueType query(const keyType &k, uint32_t &ha, uint32_t &hb) {
345  get_hash_1(k,ha);
346  valueType aa = get(ha);
347  get_hash_2(k,hb);
348  valueType bb = get(hb);
349  //printf("%llx [%x] %x ^ [%x] %x = %x\n", k,ha,aa&LMASK,hb,bb&LMASK,(aa^bb)&LMASK);
350  return LMASK & (aa^bb);
351  }
352  void inline get_hash_2(const keyType &v, uint32_t &ret1) {
353  ret1 = (Hb)(v);
354  ret1 += ma;
355  }
356  void inline get_hash(const keyType &v, uint32_t &ret1, uint32_t &ret2) {
357  get_hash_1(v,ret1);
358  get_hash_2(v,ret2);
359  }
364  void loadDataFromBinaryFile(FILE *pF) {
365  fread(&(mem[0]),sizeof(mem[0]), mem.size(), pF);
366  }
370  void writeDataToBinaryFile(FILE *pF) {
371  fwrite(&(mem[0]),sizeof(mem[0]), mem.size(), pF);
372  }
373 private:
374  void padd (vector<int32_t> &A, valueType &t) {
375  const valueType one = 1;
376  for (int i = 0; i <L; i++)
377  if (t & (one<<i))
378  A[i]++;
379  }
380 
381  void pdiff(vector<int32_t> &A, valueType &t) {
382  const valueType one = 1;
383  for (int i = 0; i <L; i++)
384  if (t & (one<<i))
385  A[i]--;
386  else A[i]++;
387  }
388 //these three functions are for add and removal
389  bool testConnected(int32_t ha, int32_t hb);
390 public:
397  void removeOneKey(uint32_t kid);
401  void updatevalue(uint32_t kid, void * values, uint32_t valuesize) {
402  uint32_t ha,hb;
403  get_hash(keys[kid],ha,hb);
404  fillvalueBFS(values, valuesize, ha, false);
405  }
406 };
407 
408 /*
409 template<size_t L, class valueType>
410 
411 template<size_t L>
412 std::array<uint8_t,L> operator ^ (const std::array<uint8_t,L> &A,const std::array<uint8_t,L> &B) {
413  std::array<uint8_t, L> v = A;
414  for (int i = 0; i < L; i++) v[i]^=B[i];
415  return v;
416 
417 }
418 
419 */
420 
421 template< class keyType>
422 bool Othello<keyType>::testHash(uint32_t keycount) {
423  uint32_t ha, hb;
424  if (nxt1 == NULL) nxt1 = new vector<int32_t> (keycount);
425  if (nxt2 == NULL) nxt2 = new vector<int32_t> (keycount);
426  if (first == NULL) first = new vector<int32_t> (ma+mb, -1);
427  removedKeys.clear();
428  disj.clear();
429  for (int i = 0; i < keycount; i++) {
430  if (i>1048576) if ((i & (i-1)) == 0) printf("Tesing keys # %d\n",i);
431  get_hash(keys[i], ha, hb);
432 
433  if (disj.sameset(ha,hb)) {
434  removedKeys.push_back(keys[i]);
435  if (removedKeys.size()> allowed_conflicts)
436  return false;
437  continue;
438  }
439  (*nxt1)[i] = (*first)[ha];
440  (*first)[ha] = i;
441  (*nxt2)[i] = (*first)[hb];
442  (*first)[hb] = i;
443  disj.merge(ha,hb);
444  }
445  return true;
446 }
447 
448 template< class keyType>
449 bool Othello<keyType>::testConnected(int ha0, int hb0) {
450  list<int32_t> q;
451  int t = (*first)[ha0];
452  while (t>=0) {
453  q.push_back(t); //edges from A to B: >0
454  t = (*nxt1)[t];
455  }
456  while (!q.empty()) {
457  int kid = q.front();
458  bool isAtoB = (kid>0);
459  if (kid <0) kid = -kid;
460  q.pop_front();
461  uint32_t ha,hb;
462  get_hash(keys[kid], ha, hb);
463  if (hb == hb0) return true;
464  int t = (*first)[hb];
465  if (isAtoB) {
466  int t = (*first)[hb];
467  while (t>=0) {
468  if (t!=kid) q.push_back(-t);
469  t = (*nxt2)[t];
470  }
471  }
472  else {
473  int t = (*first)[ha];
474  while (t>=0) {
475  if (t!=kid) q.push_back(t);
476  t = (*nxt1)[t];
477  }
478  }
479  }
480  return false;
481 }
482 
483 template< class keyType>
484 void Othello<keyType>::removeOneKey(uint32_t kid) {
485  uint32_t ha, hb;
486  get_hash(keys[kid],ha,hb);
487  mykeycount --;
488  keys[kid] = keys[mykeycount];
489  uint32_t hal, hbl;
490  get_hash(keys[mykeycount], hal, hbl);
491 
492  //(*first)[ha] , (*nxt1) ...
493  if ((*first).at(ha) == kid) {
494  (*first).at(ha) = (*nxt1)[kid];
495  } else {
496  int t = (*first)[ha];
497  while ((*nxt1)[t] != kid) t = (*nxt1)[t];
498  (*nxt1)[t] = (*nxt1)[(*nxt1)[t]];
499  }
500  (*nxt1)[kid] = (*nxt1)[mykeycount];
501 
502  if ((*first)[hal] == mykeycount) {
503  (*first)[hal] = kid;
504  } else {
505  int t = (*first)[hal];
506  while ((*nxt1)[t] != mykeycount) t = (*nxt1)[t];
507  (*nxt1)[t] = kid;
508  }
509 
510  if ((*first)[hb] == kid) {
511  (*first)[hb] = (*nxt2)[kid];
512  } else {
513  int t = (*first)[hb];
514  while ((*nxt2)[t] !=kid) t = (*nxt2)[t];
515  (*nxt2)[t] = (*nxt2)[(*nxt2)[t]];
516  }
517  (*nxt2)[kid] = (*nxt2)[mykeycount];
518  if ((*first)[hbl] == mykeycount) {
519  (*first)[hbl] = kid;
520  }
521  else {
522  int t = (*first)[hbl];
523  while ((*nxt2)[t] != kid) t= (*nxt2)[t];
524  (*nxt2)[t] = kid;
525  }
526 }
527 
528 template< class keyType>
529 void Othello<keyType>::fillvalueBFS(void *values, size_t valuesize, int root, bool usepublicFilled) {
530 
531  vector<int32_t> *nxt;
532  list<uint32_t> Q;
533  while (!Q.empty()) Q.pop_front();
534  Q.push_back(root);
535  std::set<uint32_t> s;
536  if (usepublicFilled)
537  filled[root] = true;
538  else
539  s.insert(root);
540  while (!Q.empty())
541  {
542  uint32_t nodeid = (*Q.begin());
543  Q.pop_front();
544  if (nodeid < ma) nxt = nxt1;
545  else nxt = nxt2;
546  int32_t kid = first->at(nodeid);
547  while (kid >=0) {
548  uint32_t ha,hb;
549  get_hash(keys[kid],ha,hb);
550  if (usepublicFilled) {
551  if (filled[ha] && filled[hb]) {
552  kid = nxt->at(kid);
553  continue;
554  }
555  }
556  else {
557  if (s.find(ha)!=s.end() && s.find(hb)!=s.end()) {
558  kid = nxt->at(kid);
559  continue;
560  }
561  }
562 
563  bool isfa = (usepublicFilled)?filled[ha]:(s.find(ha)!=s.end());
564  int helse = isfa ? hb : ha;
565  int hthis = isfa ? ha : hb;
567  valueType valueKid = 0;
568  if (values != NULL) {
569  uint8_t * loc = (uint8_t *) values;
570  loc += (kid * valuesize);
571  memcpy(&valueKid, loc, valuesize);
572  }
573  //valueKid = values[kid];
574  else {
576  valueKid = (hthis == ha)?1:0;
577  fillcount[helse/FILLCNTLEN] |= (1<<(helse % FILLCNTLEN));
578  }
579 
580  valueType newvalue = valueKid ^ get(hthis);
581  // printf("%x %x %x===", valueKid, get(hthis), newvalue);
582  set(helse, newvalue);
583  //printf("k%llx ha/hb %lx %lx: %x ^ %x = %x ^ %x = %x (%x), helse%x ,i%x, %d\n",
584  //keys[kid], ha, hb, get(hthis) & LMASK, newvalue & LMASK, get(ha) &LMASK, get(hb) &LMASK, (get(ha)^get(hb)) & LMASK, valueKid &LMASK, helse ,hthis ,(bool)((valueKid &LMASK)==((get(ha)^(get(hb)))&LMASK)));
585  Q.push_back(helse);
586  if (usepublicFilled)
587  filled[helse] = true;
588  else
589  s.insert(helse);
590  kid = nxt->at(kid);
591  }
592 
593  }
594 }
595 template< class keyType>
596 void Othello<keyType>::fillvalue(void *values, uint32_t keycount, size_t valuesize) {
597  filled.resize(ma+mb);
598  fill(filled.begin(), filled.end(), false);
599  if (values == NULL) {
600  fillcount.resize((ma+mb)/32);
601  fill(fillcount.begin(),fillcount.end(),0);
602  }
603  for (int i = 0; i< ma+mb; i++)
604  if (disj.isroot(i)) {
605  valueType vv;
606  getrand(vv);
607  set(i,vv);
608  fillvalueBFS(values, valuesize, i, true);
609  }
610 }
611 
612 template< class keyType>
613 vector<uint32_t> Othello<keyType>::getCnt() {
614  vector<uint32_t> cnt;
615  cnt.resize(L+L);
616  for (int i = 0; i < ma; i++) {
617  valueType gv = get(i);
618  uint8_t *vv;
619  vv = (uint8_t*) ((void *) &gv);
620  for (int p = 0; p < L; p++) {
621  uint8_t tv;
622  tv = ((*vv) >> (p & 7));
623  if (tv & 1) cnt[p]++;
624  if ((p & 7) == 7) vv++;
625  }
626  }
627  for (int i = ma; i < ma+mb; i++) {
628  valueType gv = get(i);
629  uint8_t *vv;
630  vv = (uint8_t*) ((void *) &gv);
631  for (int p = 0; p < L; p++) {
632  uint8_t tv;
633  tv = ((*vv) >> (p & 7));
634  if (tv & 1) cnt[L+p]++;
635  if ((p & 7) == 7) vv++;
636  }
637  }
638  return cnt;
639 }
640 
641 
642 template< class keyType>
643 vector<double> Othello<keyType>::getRatio() {
644  vector<uint32_t> cnt = getCnt();
645  vector<double> ret;
646  ret.resize(L);
647  for (int i = 0; i < L; i++) {
648  double p1 = 1.0 * cnt[i] / ma;
649  double p2 = 1.0 * cnt[i+L] / mb;
650  ret[i] = p1*(1-p2)+p2*(1-p1);
651  }
652  return ret;
653 
654 }
655 
656 template< class keyType>
657 void Othello<keyType>::randomflip() {
658  if (filled.size() <=1) return;
659  printf("Random flip\n");
660  valueType vv;
661  vector<list<uint32_t> > VL(ma+mb, list<uint32_t>());
662  for (int i = 0; i< ma+mb; i++)
663  if (!filled[i]) {
664  valueType vv;
665  getrand(vv);
666  set(i,vv);
667  }
668  else {
669  VL[disj.getfa(i)].push_back(i);
670  }
671  for (int i = 0; i < ma+mb; i++) {
672  getrand(vv);
673  for (auto j = VL[i].begin(); j!=VL[i].end(); j++) {
674  valueType newvalue = get(*j)^vv;
675  set(*j, newvalue);
676  }
677 
678  }
679 }
680 double getrate(uint32_t ma, uint32_t mb, uint32_t da, uint32_t db) {
681  double pa = da*1.0/ma;
682  double pb = db*1.0/mb;
683  double ret = pa*(1-pb)+pb*(1-pa);
684  return ret;
685 }
686 
687 
688 template< class keyType>
689 void Othello<keyType>::setAlienPreference(double ideal) {
690  int da[] = {1,1,0,-1,-1,-1,0,1};
691  int db[] = {0,1,1,1,0,-1,-1,-1};
692  vector< array<int32_t,8> > sa (L, array<int32_t,8>());
693  vector< array<int32_t,8> > sb (L, array<int32_t,8>());
694  for (int i = 0; i < 8; i++)
695  for (int j =0; j <L; j++)
696  sa[j][i] = sb[j][i] =0;
697  vector<int32_t> na(L,0),nb(L,0);
698  //for (int j =0; j <L; j++) na[j]=nb[j] =0;
699  int emptyA = 0;
700  int emptyB = 0;
701  if (filled.size() <=1) return;
702  printf("Adjust bitmap goal: return 1 with rate %.3lf\n",ideal);
703  valueType vv;
704  vector<list<uint32_t> > VL(ma+mb, list<uint32_t>());
705  for (int i = 0; i< ma+mb; i++) {
706  if (!filled[i]) {
707  valueType vv;
708  if (i<ma) emptyA++;
709  else emptyB++;
710  }
711  else {
712  VL[disj.getfa(i)].push_back(i);
713  valueType cur = get(i);
714  if (i<ma) padd(na, cur);
715  else padd(nb,cur);
716  }
717  }
718  for (int i = 0; i < ma+mb; i++) {
719  vector<int32_t> diffa(L,0),diffb(L,0);
720 // for (int j = 0; j< L; j++) diffa[j]=diffb[j] =0;
721  for (auto j = VL[i].begin(); j!=VL[i].end(); j++) {
722  valueType cur = get(*j);
723  if (*j < ma) pdiff(diffa,cur);
724  else pdiff(diffb, cur);
725  }
726  for (int bitID = 0; bitID<L; bitID++)
727  for (int j = 0; j <8; j++)
728  if (da[j]*diffa[bitID] + db[j] *diffb[bitID] > 0)
729  {
730  sa[bitID][j]+=diffa[bitID];
731  sb[bitID][j]+=diffb[bitID];
732  }
733 
734  }
735  vector<int32_t> direction(L,0);
736  for (int bitID = 0; bitID <L; bitID++) {
737  double ratemin = 1.0;
738  for (int dir = 0; dir <8*4; dir++) {
739  int setA = ((dir & 8) !=0);
740  int setB = ((dir & 16)!=0);
741  double rate = getrate(ma,mb,na[bitID]+setA*emptyA+sa[bitID][dir & 0x7], nb[bitID]+setB*emptyB+sb[bitID][dir & 0x7]);
742  if ((rate-ideal)*(rate-ideal) < ratemin) {
743  ratemin = (rate-ideal)*(rate-ideal);
744  direction[bitID] = dir;
745  }
746  }
747  }
748  valueType veA=0, veB=0;
749 
750  for (int bitID = 0; bitID<L; bitID++) {
751  veA |= ((direction[bitID] & 8) ? (1<<bitID) : 0);
752  veB |= ((direction[bitID] & 16) ? (1<<bitID) : 0);
753  }
754  for (int i = 0; i < ma; i++) if (!filled[i])
755  set(i,veA);
756  for (int i = ma; i <ma+mb; i++) if (!filled[i])
757  set(i,veB);
758 
759  for (int i = 0; i < ma+mb; i++) {
760  vector<int32_t> diffa(L,0),diffb(L,0);
761  for (auto j = VL[i].begin(); j!=VL[i].end(); j++) {
762  valueType cur = get(*j);
763  if (*j < ma) pdiff(diffa,cur);
764  else pdiff(diffb, cur);
765  }
766  valueType vv =0;
767  for (int bitID = 0; bitID<L; bitID++)
768  if (da[direction[bitID] &7 ] * diffa[bitID] + db[direction[bitID] &7] * diffb[bitID] > 0)
769  vv |= (1<<bitID);
770 
771  for (auto j = VL[i].begin(); j!=VL[i].end(); j++) {
772  valueType newvalue = get(*j)^vv;
773  set(*j, newvalue);
774  }
775 
776  }
777 
778 
779 
780 
781 }
Othello::getRatio
vector< double > getRatio()
returns vector, length = L. position x: the probability that query return 1 on the x-th lowest bit...
Definition: othello.h:643
Othello::mem
vector< valueType > mem
actual memory space for arrayA and arrayB.
Definition: othello.h:30
Othello::fillcount
vector< uint32_t > fillcount
Enabled only when the values of the query is not pre-defined. This supports othelloIndex query...
Definition: othello.h:41
Othello::mb
uint32_t mb
length of arrayB
Definition: othello.h:35
Hasher32
A hash function that hashes keyType to uint32_t. When SSE4.2 support is found, use sse4...
Definition: hash.h:10
Othello::addkeys
void addkeys(int newkeys, void *values, uint32_t valuesize)
after putting some keys into keys, call this function to add keys into Othello. values shall be store...
Definition: othello.h:285
Othello::writeDataToBinaryFile
void writeDataToBinaryFile(FILE *pF)
write array to binary file.
Definition: othello.h:370
Othello::loadDataFromBinaryFile
void loadDataFromBinaryFile(FILE *pF)
load the array from file.
Definition: othello.h:364
Othello::randomflip
void randomflip()
adjust the array so that for random alien query, returns 0 or 1 with equal probability on each bit...
Definition: othello.h:657
MAX_REHASH
#define MAX_REHASH
Maximum number of rehash tries before report an error. If this limit is reached, Othello build fails...
Definition: othello.h:28
Othello
Describes the data structure l-Othello. It classifies keys of keyType into 2^L classes.
Definition: othello.h:25
Othello::allowed_conflicts
uint32_t allowed_conflicts
The number of keys that can be skipped during construction.
Definition: othello.h:44
Othello::queryInt
uint64_t queryInt(const keyType &k)
returns a 64-bit integer query value for a key.
Definition: othello.h:310
Othello::Othello
Othello(uint8_t _L, vector< keyType > &keys, vector< VT > &values, bool _autoclear=true, int32_t allowed_conflicts=-1)
Construct othello with vectors.
Definition: othello.h:209
Othello::finishBuild
void finishBuild()
release memory space used during construction and forbid future modification of arrayA and arrayB...
Definition: othello.h:215
Othello::disj
DisjointSet disj
Disjoint Set data structure that helps to test the acyclicity.
Definition: othello.h:40
io_helper.h
Othello::Othello
Othello(uint8_t _L, keyType *_keys, uint32_t keycount, bool _autoclear=true, void *_values=NULL, size_t _valuesize=0, int32_t _allowed_conflicts=-1)
Construct l-Othello.
Definition: othello.h:150
Othello::exportInfo
void exportInfo(unsigned char *v)
export the information of the Othello, not including the array, to a memory space.
Definition: othello.h:235
Othello::removeOneKey
void removeOneKey(uint32_t kid)
remove one key with the particular index from the keylist.
Definition: othello.h:484
Othello::setAlienPreference
void setAlienPreference(double ideal=1.0)
adjust the array so that for random alien query, return 1 with probability that is close to the ideal...
Definition: othello.h:689
Othello::query
valueType query(const keyType &k, uint32_t &ha, uint32_t &hb)
compute the hash value of key and return query value.
Definition: othello.h:344
human
std::string human(uint64_t word)
convert a 64-bit Integer to human-readable format in K/M/G. e.g, 102400 is converted to "100K"...
Definition: io_helper.h:122
Othello::Othello
Othello(unsigned char *v)
load the infomation of the Othello from memory.
Definition: othello.h:257
Othello::getCnt
vector< uint32_t > getCnt()
returns vector, length = 2L. position x: the number of 1s on the x-th lowest bit, for array A...
Definition: othello.h:613
Othello::L
uint32_t L
the length of return value.
Definition: othello.h:31
Othello::removedKeys
vector< keyType > removedKeys
The list of removed keys.
Definition: othello.h:45
Othello::updatevalue
void updatevalue(uint32_t kid, void *values, uint32_t valuesize)
update the value for one particular key.
Definition: othello.h:401
DisjointSet
Disjoint Set data structure. Helps to test the acyclicity of the graph during construction.
Definition: disjointset.h:10
Othello::ma
uint32_t ma
length of arrayA.
Definition: othello.h:34