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)34 void 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)56 unsigned 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)72 unsigned 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)96 unsigned 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