1 /**************************************************************************/ 2 /* */ 3 /* EXPORTED FUNCTIONS: */ 4 /* */ 5 /* void */ 6 /* init_hash_values (); */ 7 /* */ 8 /* unsigned long */ 9 /* cut_hash_value (), */ 10 /* comb_hash_value (), */ 11 /* clique_hash_value (); */ 12 /* */ 13 /**************************************************************************/ 14 15 #include "machdefs.h" 16 #include "util.h" 17 #include "Xsubtour.h" 18 19 20 /* 21 This code needs two fields added to a node. They are unsigned long rand1 22 and unsigned long rand2. 23 */ 24 25 static unsigned long hashfunc1[256]; 26 static unsigned long hashfunc2[256]; 27 static unsigned long hashfunc3[256]; 28 static unsigned long hashfunc4[256]; 29 30 #define TOOTHHASHFUNC(x) (hashfunc1[(x)&0xff] ^ hashfunc2[((x)>>8)&0xff] ^ \ 31 hashfunc3[((x)>>16)&0xff] ^ hashfunc4[((x)>>24)&0xff]) 32 33 #ifdef CC_PROTOTYPE_ANSI Xinit_hash_values(Xgraph * G)34void Xinit_hash_values (Xgraph *G) 35 #else 36 void Xinit_hash_values (G) 37 Xgraph *G; 38 #endif 39 { 40 int i; 41 42 for (i = 0; i < G->nnodes; i++) { 43 G->nodelist[i].rand1 = (int) CCutil_lprand (); 44 G->nodelist[i].rand2 = (int) CCutil_lprand (); 45 } 46 for (i = 0; i < 256; i++) { 47 hashfunc1[i] = CCutil_lprand (); 48 hashfunc2[i] = CCutil_lprand (); 49 hashfunc3[i] = CCutil_lprand (); 50 hashfunc4[i] = CCutil_lprand (); 51 } 52 } 53 54 55 #ifdef CC_PROTOTYPE_ANSI Xcut_hash_value(Xnodeptr * h)56unsigned long Xcut_hash_value (Xnodeptr *h) 57 #else 58 unsigned long Xcut_hash_value (h) 59 Xnodeptr *h; 60 #endif 61 { 62 Xnodeptr *p; 63 unsigned long hashval = 0; 64 65 for (p = h; p; p = p->next) 66 hashval ^= p->this->rand1; 67 68 return hashval; 69 } 70 71 #ifdef CC_PROTOTYPE_ANSI Xcomb_hash_value(Xnodeptr * h,Xnodeptrptr * t)72unsigned long Xcomb_hash_value (Xnodeptr *h, Xnodeptrptr *t) 73 #else 74 unsigned long Xcomb_hash_value (h, t) 75 Xnodeptr *h; 76 Xnodeptrptr *t; 77 #endif 78 { 79 Xnodeptr *p; 80 Xnodeptrptr *q; 81 unsigned long hashval = 0; 82 unsigned long toothhash; 83 84 for (p = h; p; p = p->next) 85 hashval ^= p->this->rand1; 86 for (q = t; q; q = q->next) { 87 toothhash = 0; 88 for (p = q->this; p; p = p->next) 89 toothhash ^= p->this->rand2; 90 hashval ^= TOOTHHASHFUNC (toothhash); 91 } 92 return hashval; 93 } 94 95 #ifdef CC_PROTOTYPE_ANSI Xclique_hash_value(Xnodeptrptr * h,Xnodeptrptr * t)96unsigned long Xclique_hash_value (Xnodeptrptr *h, Xnodeptrptr *t) 97 #else 98 unsigned long Xclique_hash_value (h, t) 99 Xnodeptrptr *h; 100 Xnodeptrptr *t; 101 #endif 102 { 103 Xnodeptr *p; 104 Xnodeptrptr *q; 105 unsigned long hashval = 0; 106 unsigned long toothhash; 107 unsigned long handlehash; 108 109 for (q = h; q; q = q->next) { 110 handlehash = 0; 111 for (p = q->this; p; p = p->next) 112 handlehash ^= p->this->rand1; 113 hashval ^= TOOTHHASHFUNC (handlehash); 114 } 115 for (q = t; q; q = q->next) { 116 toothhash = 0; 117 for (p = q->this; p; p = p->next) 118 toothhash ^= p->this->rand2; 119 hashval ^= TOOTHHASHFUNC (toothhash); 120 } 121 return hashval; 122 } 123