Branch data Line data Source code
1 : : #include "bdz_ph.h"
2 : : #include "cmph_structs.h"
3 : : #include "bdz_structs_ph.h"
4 : : #include "hash.h"
5 : : #include "bitbool.h"
6 : :
7 : : #include <math.h>
8 : : #include <stdlib.h>
9 : : #include <stdio.h>
10 : : #include <assert.h>
11 : : #include <string.h>
12 : : #include <errno.h>
13 : : //#define DEBUG
14 : : #include "debug.h"
15 : : #define UNASSIGNED 3
16 : : #define NULL_EDGE 0xffffffff
17 : :
18 : :
19 : : static cmph_uint8 pow3_table[5] = {1,3,9,27,81};
20 : : static cmph_uint8 lookup_table[5][256] = {
21 : : {0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0},
22 : : {0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1},
23 : : {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1},
24 : : {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
25 : : {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
26 : : };
27 : :
28 : : typedef struct
29 : : {
30 : : cmph_uint32 vertices[3];
31 : : cmph_uint32 next_edges[3];
32 : : }bdz_ph_edge_t;
33 : :
34 : : typedef cmph_uint32 * bdz_ph_queue_t;
35 : :
36 : 0 : static void bdz_ph_alloc_queue(bdz_ph_queue_t * queuep, cmph_uint32 nedges)
37 : : {
38 : 0 : (*queuep)=malloc(nedges*sizeof(cmph_uint32));
39 : 0 : };
40 : 0 : static void bdz_ph_free_queue(bdz_ph_queue_t * queue)
41 : : {
42 : 0 : free(*queue);
43 : 0 : };
44 : :
45 : : typedef struct
46 : : {
47 : : cmph_uint32 nedges;
48 : : bdz_ph_edge_t * edges;
49 : : cmph_uint32 * first_edge;
50 : : cmph_uint8 * vert_degree;
51 : : }bdz_ph_graph3_t;
52 : :
53 : :
54 : 0 : static void bdz_ph_alloc_graph3(bdz_ph_graph3_t * graph3, cmph_uint32 nedges, cmph_uint32 nvertices)
55 : : {
56 : 0 : graph3->edges=malloc(nedges*sizeof(bdz_ph_edge_t));
57 : 0 : graph3->first_edge=malloc(nvertices*sizeof(cmph_uint32));
58 : 0 : graph3->vert_degree=malloc((size_t)nvertices);
59 : 0 : };
60 : 0 : static void bdz_ph_init_graph3(bdz_ph_graph3_t * graph3, cmph_uint32 nedges, cmph_uint32 nvertices)
61 : : {
62 : 0 : memset(graph3->first_edge,0xff,nvertices*sizeof(cmph_uint32));
63 : 0 : memset(graph3->vert_degree,0,(size_t)nvertices);
64 : 0 : graph3->nedges=0;
65 : 0 : };
66 : 0 : static void bdz_ph_free_graph3(bdz_ph_graph3_t *graph3)
67 : : {
68 : 0 : free(graph3->edges);
69 : 0 : free(graph3->first_edge);
70 : 0 : free(graph3->vert_degree);
71 : 0 : };
72 : :
73 : 0 : static void bdz_ph_partial_free_graph3(bdz_ph_graph3_t *graph3)
74 : : {
75 : 0 : free(graph3->first_edge);
76 : 0 : free(graph3->vert_degree);
77 : 0 : graph3->first_edge = NULL;
78 : 0 : graph3->vert_degree = NULL;
79 : 0 : };
80 : :
81 : 0 : static void bdz_ph_add_edge(bdz_ph_graph3_t * graph3, cmph_uint32 v0, cmph_uint32 v1, cmph_uint32 v2)
82 : : {
83 : 0 : graph3->edges[graph3->nedges].vertices[0]=v0;
84 : 0 : graph3->edges[graph3->nedges].vertices[1]=v1;
85 : 0 : graph3->edges[graph3->nedges].vertices[2]=v2;
86 : 0 : graph3->edges[graph3->nedges].next_edges[0]=graph3->first_edge[v0];
87 : 0 : graph3->edges[graph3->nedges].next_edges[1]=graph3->first_edge[v1];
88 : 0 : graph3->edges[graph3->nedges].next_edges[2]=graph3->first_edge[v2];
89 : 0 : graph3->first_edge[v0]=graph3->first_edge[v1]=graph3->first_edge[v2]=graph3->nedges;
90 : 0 : graph3->vert_degree[v0]++;
91 : 0 : graph3->vert_degree[v1]++;
92 : 0 : graph3->vert_degree[v2]++;
93 : 0 : graph3->nedges++;
94 : 0 : };
95 : :
96 : 0 : static void bdz_ph_dump_graph(bdz_ph_graph3_t* graph3, cmph_uint32 nedges, cmph_uint32 nvertices)
97 : : {
98 : : cmph_uint32 i;
99 : 0 : for(i=0;i<nedges;i++){
100 : 0 : printf("\nedge %d %d %d %d ",i,graph3->edges[i].vertices[0],
101 : 0 : graph3->edges[i].vertices[1],graph3->edges[i].vertices[2]);
102 : 0 : printf(" nexts %d %d %d",graph3->edges[i].next_edges[0],
103 : 0 : graph3->edges[i].next_edges[1],graph3->edges[i].next_edges[2]);
104 : : };
105 : :
106 : 0 : for(i=0;i<nvertices;i++){
107 : 0 : printf("\nfirst for vertice %d %d ",i,graph3->first_edge[i]);
108 : :
109 : : };
110 : 0 : };
111 : :
112 : 0 : static void bdz_ph_remove_edge(bdz_ph_graph3_t * graph3, cmph_uint32 curr_edge)
113 : : {
114 : 0 : cmph_uint32 i,j=0,vert,edge1,edge2;
115 : 0 : for(i=0;i<3;i++){
116 : 0 : vert=graph3->edges[curr_edge].vertices[i];
117 : 0 : edge1=graph3->first_edge[vert];
118 : 0 : edge2=NULL_EDGE;
119 : 0 : while(edge1!=curr_edge&&edge1!=NULL_EDGE){
120 : 0 : edge2=edge1;
121 : 0 : if(graph3->edges[edge1].vertices[0]==vert){
122 : 0 : j=0;
123 : 0 : } else if(graph3->edges[edge1].vertices[1]==vert){
124 : 0 : j=1;
125 : : } else
126 : 0 : j=2;
127 : 0 : edge1=graph3->edges[edge1].next_edges[j];
128 : : };
129 : 0 : if(edge1==NULL_EDGE){
130 : 0 : printf("\nerror remove edge %d dump graph",curr_edge);
131 : 0 : bdz_ph_dump_graph(graph3,graph3->nedges,graph3->nedges+graph3->nedges/4);
132 : 0 : exit(-1);
133 : : };
134 : :
135 : 0 : if(edge2!=NULL_EDGE){
136 : 0 : graph3->edges[edge2].next_edges[j] =
137 : 0 : graph3->edges[edge1].next_edges[i];
138 : : } else
139 : 0 : graph3->first_edge[vert]=
140 : 0 : graph3->edges[edge1].next_edges[i];
141 : 0 : graph3->vert_degree[vert]--;
142 : : };
143 : :
144 : 0 : };
145 : :
146 : 0 : static int bdz_ph_generate_queue(cmph_uint32 nedges, cmph_uint32 nvertices, bdz_ph_queue_t queue, bdz_ph_graph3_t* graph3)
147 : : {
148 : : cmph_uint32 i,v0,v1,v2;
149 : 0 : cmph_uint32 queue_head=0,queue_tail=0;
150 : : cmph_uint32 curr_edge;
151 : : cmph_uint32 tmp_edge;
152 : 0 : cmph_uint8 * marked_edge =malloc((size_t)(nedges >> 3) + 1);
153 : 0 : memset(marked_edge, 0, (size_t)(nedges >> 3) + 1);
154 : :
155 : 0 : for(i=0;i<nedges;i++){
156 : 0 : v0=graph3->edges[i].vertices[0];
157 : 0 : v1=graph3->edges[i].vertices[1];
158 : 0 : v2=graph3->edges[i].vertices[2];
159 : 0 : if(graph3->vert_degree[v0]==1 ||
160 : 0 : graph3->vert_degree[v1]==1 ||
161 : 0 : graph3->vert_degree[v2]==1){
162 : 0 : if(!GETBIT(marked_edge,i)) {
163 : 0 : queue[queue_head++]=i;
164 : 0 : SETBIT(marked_edge,i);
165 : : }
166 : : };
167 : : };
168 : 0 : while(queue_tail!=queue_head){
169 : 0 : curr_edge=queue[queue_tail++];
170 : 0 : bdz_ph_remove_edge(graph3,curr_edge);
171 : 0 : v0=graph3->edges[curr_edge].vertices[0];
172 : 0 : v1=graph3->edges[curr_edge].vertices[1];
173 : 0 : v2=graph3->edges[curr_edge].vertices[2];
174 : 0 : if(graph3->vert_degree[v0]==1 ) {
175 : 0 : tmp_edge=graph3->first_edge[v0];
176 : 0 : if(!GETBIT(marked_edge,tmp_edge)) {
177 : 0 : queue[queue_head++]=tmp_edge;
178 : 0 : SETBIT(marked_edge,tmp_edge);
179 : : };
180 : :
181 : : };
182 : 0 : if(graph3->vert_degree[v1]==1) {
183 : 0 : tmp_edge=graph3->first_edge[v1];
184 : 0 : if(!GETBIT(marked_edge,tmp_edge)){
185 : 0 : queue[queue_head++]=tmp_edge;
186 : 0 : SETBIT(marked_edge,tmp_edge);
187 : : };
188 : :
189 : : };
190 : 0 : if(graph3->vert_degree[v2]==1){
191 : 0 : tmp_edge=graph3->first_edge[v2];
192 : 0 : if(!GETBIT(marked_edge,tmp_edge)){
193 : 0 : queue[queue_head++]=tmp_edge;
194 : 0 : SETBIT(marked_edge,tmp_edge);
195 : : };
196 : : };
197 : : };
198 : 0 : free(marked_edge);
199 : 0 : return (int)queue_head - (int)nedges;/* returns 0 if successful otherwies return negative number*/
200 : : };
201 : :
202 : : static int bdz_ph_mapping(cmph_config_t *mph, bdz_ph_graph3_t* graph3, bdz_ph_queue_t queue);
203 : : static void assigning(bdz_ph_config_data_t *bdz_ph, bdz_ph_graph3_t* graph3, bdz_ph_queue_t queue);
204 : : static void bdz_ph_optimization(bdz_ph_config_data_t *bdz_ph);
205 : :
206 : 0 : bdz_ph_config_data_t *bdz_ph_config_new(void)
207 : : {
208 : : bdz_ph_config_data_t *bdz_ph;
209 : 0 : bdz_ph = (bdz_ph_config_data_t *)malloc(sizeof(bdz_ph_config_data_t));
210 : 0 : assert(bdz_ph);
211 : 0 : memset(bdz_ph, 0, sizeof(bdz_ph_config_data_t));
212 : 0 : bdz_ph->hashfunc = CMPH_HASH_JENKINS;
213 : 0 : bdz_ph->g = NULL;
214 : 0 : bdz_ph->hl = NULL;
215 : 0 : return bdz_ph;
216 : : }
217 : :
218 : 0 : void bdz_ph_config_destroy(cmph_config_t *mph)
219 : : {
220 : 0 : bdz_ph_config_data_t *data = (bdz_ph_config_data_t *)mph->data;
221 : : DEBUGP("Destroying algorithm dependent data\n");
222 : 0 : free(data);
223 : 0 : }
224 : :
225 : 0 : void bdz_ph_config_set_hashfuncs(cmph_config_t *mph, CMPH_HASH *hashfuncs)
226 : : {
227 : 0 : bdz_ph_config_data_t *bdz_ph = (bdz_ph_config_data_t *)mph->data;
228 : 0 : CMPH_HASH *hashptr = hashfuncs;
229 : 0 : cmph_uint32 i = 0;
230 : 0 : while(*hashptr != CMPH_HASH_COUNT)
231 : : {
232 : 0 : if (i >= 1) break; //bdz_ph only uses one linear hash function
233 : 0 : bdz_ph->hashfunc = *hashptr;
234 : 0 : ++i, ++hashptr;
235 : : }
236 : 0 : }
237 : :
238 : 0 : cmph_t *bdz_ph_new(cmph_config_t *mph, double c)
239 : : {
240 : 0 : cmph_t *mphf = NULL;
241 : 0 : bdz_ph_data_t *bdz_phf = NULL;
242 : : cmph_uint32 iterations;
243 : : bdz_ph_queue_t edges;
244 : : bdz_ph_graph3_t graph3;
245 : 0 : bdz_ph_config_data_t *bdz_ph = (bdz_ph_config_data_t *)mph->data;
246 : : #ifdef CMPH_TIMING
247 : : double construction_time_begin = 0.0;
248 : : double construction_time = 0.0;
249 : : ELAPSED_TIME_IN_SECONDS(&construction_time_begin);
250 : : #endif
251 : :
252 : :
253 : 0 : if (c == 0) c = 1.23; // validating restrictions over parameter c.
254 : : DEBUGP("c: %f\n", c);
255 : 0 : bdz_ph->m = mph->key_source->nkeys;
256 : 0 : bdz_ph->r = (cmph_uint32)ceil((c * mph->key_source->nkeys)/3);
257 : 0 : if ((bdz_ph->r % 2) == 0) bdz_ph->r += 1;
258 : 0 : bdz_ph->n = 3*bdz_ph->r;
259 : :
260 : :
261 : 0 : bdz_ph_alloc_graph3(&graph3, bdz_ph->m, bdz_ph->n);
262 : 0 : bdz_ph_alloc_queue(&edges,bdz_ph->m);
263 : : DEBUGP("Created hypergraph\n");
264 : :
265 : : DEBUGP("m (edges): %u n (vertices): %u r: %u c: %f \n", bdz_ph->m, bdz_ph->n, bdz_ph->r, c);
266 : :
267 : : // Mapping step
268 : 0 : iterations = 100;
269 : 0 : if (mph->verbosity)
270 : : {
271 : 0 : fprintf(stderr, "Entering mapping step for mph creation of %u keys with graph sized %u\n", bdz_ph->m, bdz_ph->n);
272 : : }
273 : : while(1)
274 : 0 : {
275 : : int ok;
276 : : DEBUGP("linear hash function \n");
277 : 0 : bdz_ph->hl = hash_state_new(bdz_ph->hashfunc, 15);
278 : :
279 : 0 : ok = bdz_ph_mapping(mph, &graph3, edges);
280 : 0 : if (!ok)
281 : : {
282 : 0 : --iterations;
283 : 0 : hash_state_destroy(bdz_ph->hl);
284 : 0 : bdz_ph->hl = NULL;
285 : : DEBUGP("%u iterations remaining\n", iterations);
286 : 0 : if (mph->verbosity)
287 : : {
288 : 0 : fprintf(stderr, "acyclic graph creation failure - %u iterations remaining\n", iterations);
289 : : }
290 : 0 : if (iterations == 0) break;
291 : : }
292 : 0 : else break;
293 : : }
294 : :
295 : 0 : if (iterations == 0)
296 : : {
297 : : // free(bdz_ph->g);
298 : 0 : bdz_ph_free_queue(&edges);
299 : 0 : bdz_ph_free_graph3(&graph3);
300 : 0 : return NULL;
301 : : }
302 : 0 : bdz_ph_partial_free_graph3(&graph3);
303 : : // Assigning step
304 : 0 : if (mph->verbosity)
305 : : {
306 : 0 : fprintf(stderr, "Entering assigning step for mph creation of %u keys with graph sized %u\n", bdz_ph->m, bdz_ph->n);
307 : : }
308 : 0 : assigning(bdz_ph, &graph3, edges);
309 : :
310 : 0 : bdz_ph_free_queue(&edges);
311 : 0 : bdz_ph_free_graph3(&graph3);
312 : :
313 : 0 : if (mph->verbosity)
314 : : {
315 : 0 : fprintf(stderr, "Starting optimization step\n");
316 : : }
317 : :
318 : 0 : bdz_ph_optimization(bdz_ph);
319 : :
320 : : #ifdef CMPH_TIMING
321 : : ELAPSED_TIME_IN_SECONDS(&construction_time);
322 : : #endif
323 : 0 : mphf = (cmph_t *)malloc(sizeof(cmph_t));
324 : 0 : mphf->algo = mph->algo;
325 : 0 : bdz_phf = (bdz_ph_data_t *)malloc(sizeof(bdz_ph_data_t));
326 : 0 : bdz_phf->g = bdz_ph->g;
327 : 0 : bdz_ph->g = NULL; //transfer memory ownership
328 : 0 : bdz_phf->hl = bdz_ph->hl;
329 : 0 : bdz_ph->hl = NULL; //transfer memory ownership
330 : 0 : bdz_phf->n = bdz_ph->n;
331 : 0 : bdz_phf->m = bdz_ph->m;
332 : 0 : bdz_phf->r = bdz_ph->r;
333 : 0 : mphf->data = bdz_phf;
334 : 0 : mphf->size = bdz_ph->n;
335 : :
336 : : DEBUGP("Successfully generated minimal perfect hash\n");
337 : 0 : if (mph->verbosity)
338 : : {
339 : 0 : fprintf(stderr, "Successfully generated minimal perfect hash function\n");
340 : : }
341 : :
342 : : #ifdef CMPH_TIMING
343 : : register cmph_uint32 space_usage = bdz_ph_packed_size(mphf)*8;
344 : : register cmph_uint32 keys_per_bucket = 1;
345 : : construction_time = construction_time - construction_time_begin;
346 : : fprintf(stdout, "%u\t%.2f\t%u\t%.4f\t%.4f\n", bdz_ph->m, bdz_ph->m/(double)bdz_ph->n, keys_per_bucket, construction_time, space_usage/(double)bdz_ph->m);
347 : : #endif
348 : :
349 : 0 : return mphf;
350 : : }
351 : :
352 : :
353 : 0 : static int bdz_ph_mapping(cmph_config_t *mph, bdz_ph_graph3_t* graph3, bdz_ph_queue_t queue)
354 : : {
355 : : cmph_uint32 e;
356 : 0 : int cycles = 0;
357 : : cmph_uint32 hl[3];
358 : :
359 : 0 : bdz_ph_config_data_t *bdz_ph = (bdz_ph_config_data_t *)mph->data;
360 : 0 : bdz_ph_init_graph3(graph3, bdz_ph->m, bdz_ph->n);
361 : 0 : mph->key_source->rewind(mph->key_source->data);
362 : 0 : for (e = 0; e < mph->key_source->nkeys; ++e)
363 : : {
364 : : cmph_uint32 h0, h1, h2;
365 : : cmph_uint32 keylen;
366 : 0 : char *key = NULL;
367 : 0 : mph->key_source->read(mph->key_source->data, &key, &keylen);
368 : 0 : hash_vector(bdz_ph->hl, key, keylen, hl);
369 : 0 : h0 = hl[0] % bdz_ph->r;
370 : 0 : h1 = hl[1] % bdz_ph->r + bdz_ph->r;
371 : 0 : h2 = hl[2] % bdz_ph->r + (bdz_ph->r << 1);
372 : 0 : mph->key_source->dispose(mph->key_source->data, key, keylen);
373 : 0 : bdz_ph_add_edge(graph3,h0,h1,h2);
374 : : }
375 : 0 : cycles = bdz_ph_generate_queue(bdz_ph->m, bdz_ph->n, queue, graph3);
376 : 0 : return (cycles == 0);
377 : : }
378 : :
379 : 0 : static void assigning(bdz_ph_config_data_t *bdz_ph, bdz_ph_graph3_t* graph3, bdz_ph_queue_t queue)
380 : : {
381 : : cmph_uint32 i;
382 : 0 : cmph_uint32 nedges=graph3->nedges;
383 : : cmph_uint32 curr_edge;
384 : : cmph_uint32 v0,v1,v2;
385 : 0 : cmph_uint8 * marked_vertices =malloc((size_t)(bdz_ph->n >> 3) + 1);
386 : 0 : cmph_uint32 sizeg = (cmph_uint32)ceil(bdz_ph->n/4.0);
387 : 0 : bdz_ph->g = (cmph_uint8 *)calloc((size_t)sizeg, sizeof(cmph_uint8));
388 : 0 : memset(marked_vertices, 0, (size_t)(bdz_ph->n >> 3) + 1);
389 : : //memset(bdz_ph->g, 0xff, sizeg);
390 : :
391 : 0 : for(i=nedges-1;i+1>=1;i--){
392 : 0 : curr_edge=queue[i];
393 : 0 : v0=graph3->edges[curr_edge].vertices[0];
394 : 0 : v1=graph3->edges[curr_edge].vertices[1];
395 : 0 : v2=graph3->edges[curr_edge].vertices[2];
396 : : DEBUGP("B:%u %u %u -- %u %u %u\n", v0, v1, v2, GETVALUE(bdz_ph->g, v0), GETVALUE(bdz_ph->g, v1), GETVALUE(bdz_ph->g, v2));
397 : 0 : if(!GETBIT(marked_vertices, v0)){
398 : 0 : if(!GETBIT(marked_vertices,v1))
399 : : {
400 : : //SETVALUE(bdz_ph->g, v1, UNASSIGNED);
401 : 0 : SETBIT(marked_vertices, v1);
402 : : }
403 : 0 : if(!GETBIT(marked_vertices,v2))
404 : : {
405 : : //SETVALUE(bdz_ph->g, v2, UNASSIGNED);
406 : 0 : SETBIT(marked_vertices, v2);
407 : : }
408 : 0 : SETVALUE0(bdz_ph->g, v0, (6-(GETVALUE(bdz_ph->g, v1) + GETVALUE(bdz_ph->g,v2)))%3);
409 : 0 : SETBIT(marked_vertices, v0);
410 : 0 : } else if(!GETBIT(marked_vertices, v1)) {
411 : 0 : if(!GETBIT(marked_vertices, v2))
412 : : {
413 : : //SETVALUE(bdz_ph->g, v2, UNASSIGNED);
414 : 0 : SETBIT(marked_vertices, v2);
415 : : }
416 : 0 : SETVALUE0(bdz_ph->g, v1, (7 - (GETVALUE(bdz_ph->g, v0)+GETVALUE(bdz_ph->g, v2)))%3);
417 : 0 : SETBIT(marked_vertices, v1);
418 : : }else {
419 : 0 : SETVALUE0(bdz_ph->g, v2, (8-(GETVALUE(bdz_ph->g,v0)+GETVALUE(bdz_ph->g, v1)))%3);
420 : 0 : SETBIT(marked_vertices, v2);
421 : : }
422 : : DEBUGP("A:%u %u %u -- %u %u %u\n", v0, v1, v2, GETVALUE(bdz_ph->g, v0), GETVALUE(bdz_ph->g, v1), GETVALUE(bdz_ph->g, v2));
423 : : };
424 : 0 : free(marked_vertices);
425 : 0 : }
426 : :
427 : 0 : static void bdz_ph_optimization(bdz_ph_config_data_t *bdz_ph)
428 : : {
429 : : cmph_uint32 i;
430 : 0 : cmph_uint8 byte = 0;
431 : 0 : cmph_uint32 sizeg = (cmph_uint32)ceil(bdz_ph->n/5.0);
432 : 0 : cmph_uint8 * new_g = (cmph_uint8 *)calloc((size_t)sizeg, sizeof(cmph_uint8));
433 : : cmph_uint8 value;
434 : : cmph_uint32 idx;
435 : 0 : for(i = 0; i < bdz_ph->n; i++)
436 : : {
437 : 0 : idx = i/5;
438 : 0 : byte = new_g[idx];
439 : 0 : value = GETVALUE(bdz_ph->g, i);
440 : 0 : byte = (cmph_uint8) (byte + value*pow3_table[i%5U]);
441 : 0 : new_g[idx] = byte;
442 : : }
443 : 0 : free(bdz_ph->g);
444 : 0 : bdz_ph->g = new_g;
445 : 0 : }
446 : :
447 : :
448 : 0 : int bdz_ph_dump(cmph_t *mphf, FILE *fd)
449 : : {
450 : 0 : char *buf = NULL;
451 : : cmph_uint32 buflen;
452 : 0 : cmph_uint32 sizeg = 0;
453 : : register size_t nbytes;
454 : 0 : bdz_ph_data_t *data = (bdz_ph_data_t *)mphf->data;
455 : : #ifdef DEBUG
456 : : cmph_uint32 i;
457 : : #endif
458 : :
459 : 0 : __cmph_dump(mphf, fd);
460 : :
461 : 0 : hash_state_dump(data->hl, &buf, &buflen);
462 : : DEBUGP("Dumping hash state with %u bytes to disk\n", buflen);
463 : 0 : nbytes = fwrite(&buflen, sizeof(cmph_uint32), (size_t)1, fd);
464 : 0 : nbytes = fwrite(buf, (size_t)buflen, (size_t)1, fd);
465 : 0 : free(buf);
466 : :
467 : 0 : nbytes = fwrite(&(data->n), sizeof(cmph_uint32), (size_t)1, fd);
468 : 0 : nbytes = fwrite(&(data->m), sizeof(cmph_uint32), (size_t)1, fd);
469 : 0 : nbytes = fwrite(&(data->r), sizeof(cmph_uint32), (size_t)1, fd);
470 : 0 : sizeg = (cmph_uint32)ceil(data->n/5.0);
471 : 0 : nbytes = fwrite(data->g, sizeof(cmph_uint8)*sizeg, (size_t)1, fd);
472 : :
473 : 0 : if (nbytes == 0 && ferror(fd)) {
474 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
475 : 0 : return 0;
476 : : }
477 : : #ifdef DEBUG
478 : : fprintf(stderr, "G: ");
479 : : for (i = 0; i < data->n; ++i) fprintf(stderr, "%u ", GETVALUE(data->g, i));
480 : : fprintf(stderr, "\n");
481 : : #endif
482 : 0 : return 1;
483 : : }
484 : :
485 : 0 : void bdz_ph_load(FILE *f, cmph_t *mphf)
486 : : {
487 : 0 : char *buf = NULL;
488 : : cmph_uint32 buflen;
489 : 0 : cmph_uint32 sizeg = 0;
490 : : register size_t nbytes;
491 : 0 : bdz_ph_data_t *bdz_ph = (bdz_ph_data_t *)malloc(sizeof(bdz_ph_data_t));
492 : :
493 : : DEBUGP("Loading bdz_ph mphf\n");
494 : 0 : mphf->data = bdz_ph;
495 : :
496 : 0 : nbytes = fread(&buflen, sizeof(cmph_uint32), (size_t)1, f);
497 : : DEBUGP("Hash state has %u bytes\n", buflen);
498 : 0 : buf = (char *)malloc((size_t)buflen);
499 : 0 : nbytes = fread(buf, (size_t)buflen, (size_t)1, f);
500 : 0 : bdz_ph->hl = hash_state_load(buf, buflen);
501 : 0 : free(buf);
502 : :
503 : :
504 : : DEBUGP("Reading m and n\n");
505 : 0 : nbytes = fread(&(bdz_ph->n), sizeof(cmph_uint32), (size_t)1, f);
506 : 0 : nbytes = fread(&(bdz_ph->m), sizeof(cmph_uint32), (size_t)1, f);
507 : 0 : nbytes = fread(&(bdz_ph->r), sizeof(cmph_uint32), (size_t)1, f);
508 : 0 : sizeg = (cmph_uint32)ceil(bdz_ph->n/5.0);
509 : 0 : bdz_ph->g = (cmph_uint8 *)calloc((size_t)sizeg, sizeof(cmph_uint8));
510 : 0 : nbytes = fread(bdz_ph->g, sizeg*sizeof(cmph_uint8), (size_t)1, f);
511 : :
512 : 0 : if (nbytes == 0 && ferror(f)) {
513 : 0 : fprintf(stderr, "ERROR: %s\n", strerror(errno));
514 : : }
515 : 0 : return;
516 : : }
517 : :
518 : :
519 : 0 : cmph_uint32 bdz_ph_search(cmph_t *mphf, const char *key, cmph_uint32 keylen)
520 : : {
521 : 0 : register bdz_ph_data_t *bdz_ph = mphf->data;
522 : : cmph_uint32 hl[3];
523 : : register cmph_uint8 byte0, byte1, byte2;
524 : : register cmph_uint32 vertex;
525 : :
526 : 0 : hash_vector(bdz_ph->hl, key, keylen,hl);
527 : 0 : hl[0] = hl[0] % bdz_ph->r;
528 : 0 : hl[1] = hl[1] % bdz_ph->r + bdz_ph->r;
529 : 0 : hl[2] = hl[2] % bdz_ph->r + (bdz_ph->r << 1);
530 : :
531 : 0 : byte0 = bdz_ph->g[hl[0]/5];
532 : 0 : byte1 = bdz_ph->g[hl[1]/5];
533 : 0 : byte2 = bdz_ph->g[hl[2]/5];
534 : :
535 : 0 : byte0 = lookup_table[hl[0]%5U][byte0];
536 : 0 : byte1 = lookup_table[hl[1]%5U][byte1];
537 : 0 : byte2 = lookup_table[hl[2]%5U][byte2];
538 : 0 : vertex = hl[(byte0 + byte1 + byte2)%3];
539 : :
540 : 0 : return vertex;
541 : : }
542 : :
543 : :
544 : 0 : void bdz_ph_destroy(cmph_t *mphf)
545 : : {
546 : 0 : bdz_ph_data_t *data = (bdz_ph_data_t *)mphf->data;
547 : 0 : free(data->g);
548 : 0 : hash_state_destroy(data->hl);
549 : 0 : free(data);
550 : 0 : free(mphf);
551 : 0 : }
552 : :
553 : : /** \fn void bdz_ph_pack(cmph_t *mphf, void *packed_mphf);
554 : : * \brief Support the ability to pack a perfect hash function into a preallocated contiguous memory space pointed by packed_mphf.
555 : : * \param mphf pointer to the resulting mphf
556 : : * \param packed_mphf pointer to the contiguous memory area used to store the resulting mphf. The size of packed_mphf must be at least cmph_packed_size()
557 : : */
558 : 0 : void bdz_ph_pack(cmph_t *mphf, void *packed_mphf)
559 : : {
560 : 0 : bdz_ph_data_t *data = (bdz_ph_data_t *)mphf->data;
561 : 0 : cmph_uint8 * ptr = packed_mphf;
562 : : cmph_uint32 sizeg;
563 : :
564 : : // packing hl type
565 : 0 : CMPH_HASH hl_type = hash_get_type(data->hl);
566 : 0 : *((cmph_uint32 *) ptr) = hl_type;
567 : 0 : ptr += sizeof(cmph_uint32);
568 : :
569 : : // packing hl
570 : 0 : hash_state_pack(data->hl, ptr);
571 : 0 : ptr += hash_state_packed_size(hl_type);
572 : :
573 : : // packing r
574 : 0 : *((cmph_uint32 *) ptr) = data->r;
575 : 0 : ptr += sizeof(data->r);
576 : :
577 : : // packing g
578 : 0 : sizeg = (cmph_uint32)ceil(data->n/5.0);
579 : 0 : memcpy(ptr, data->g, sizeof(cmph_uint8)*sizeg);
580 : 0 : }
581 : :
582 : : /** \fn cmph_uint32 bdz_ph_packed_size(cmph_t *mphf);
583 : : * \brief Return the amount of space needed to pack mphf.
584 : : * \param mphf pointer to a mphf
585 : : * \return the size of the packed function or zero for failures
586 : : */
587 : 0 : cmph_uint32 bdz_ph_packed_size(cmph_t *mphf)
588 : : {
589 : 0 : bdz_ph_data_t *data = (bdz_ph_data_t *)mphf->data;
590 : 0 : CMPH_HASH hl_type = hash_get_type(data->hl);
591 : 0 : cmph_uint32 sizeg = (cmph_uint32)ceil(data->n/5.0);
592 : 0 : return (cmph_uint32) (sizeof(CMPH_ALGO) + hash_state_packed_size(hl_type) + 2*sizeof(cmph_uint32) + sizeof(cmph_uint8)*sizeg);
593 : : }
594 : :
595 : : /** cmph_uint32 bdz_ph_search(void *packed_mphf, const char *key, cmph_uint32 keylen);
596 : : * \brief Use the packed mphf to do a search.
597 : : * \param packed_mphf pointer to the packed mphf
598 : : * \param key key to be hashed
599 : : * \param keylen key length in bytes
600 : : * \return The mphf value
601 : : */
602 : 0 : cmph_uint32 bdz_ph_search_packed(void *packed_mphf, const char *key, cmph_uint32 keylen)
603 : : {
604 : :
605 : 0 : register CMPH_HASH hl_type = *(cmph_uint32 *)packed_mphf;
606 : 0 : register cmph_uint8 *hl_ptr = (cmph_uint8 *)(packed_mphf) + 4;
607 : :
608 : 0 : register cmph_uint8 * ptr = hl_ptr + hash_state_packed_size(hl_type);
609 : :
610 : 0 : register cmph_uint32 r = *((cmph_uint32*) ptr);
611 : 0 : register cmph_uint8 * g = ptr + 4;
612 : :
613 : : cmph_uint32 hl[3];
614 : : register cmph_uint8 byte0, byte1, byte2;
615 : : register cmph_uint32 vertex;
616 : :
617 : 0 : hash_vector_packed(hl_ptr, hl_type, key, keylen, hl);
618 : :
619 : 0 : hl[0] = hl[0] % r;
620 : 0 : hl[1] = hl[1] % r + r;
621 : 0 : hl[2] = hl[2] % r + (r << 1);
622 : :
623 : 0 : byte0 = g[hl[0]/5];
624 : 0 : byte1 = g[hl[1]/5];
625 : 0 : byte2 = g[hl[2]/5];
626 : :
627 : 0 : byte0 = lookup_table[hl[0]%5][byte0];
628 : 0 : byte1 = lookup_table[hl[1]%5][byte1];
629 : 0 : byte2 = lookup_table[hl[2]%5][byte2];
630 : 0 : vertex = hl[(byte0 + byte1 + byte2)%3];
631 : :
632 : 0 : return vertex;
633 : : }
|
