1 /* $NetBSD: graph2.c,v 1.4 2011/10/21 23:47:11 joerg Exp $ */
3 * Copyright (c) 2009 The NetBSD Foundation, Inc.
6 * This code is derived from software contributed to The NetBSD Foundation
7 * by Joerg Sonnenberger.
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
28 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
29 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
30 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34 #if HAVE_NBTOOL_CONFIG_H
35 #include "nbtool_config.h"
38 #include <sys/cdefs.h>
39 __RCSID("$NetBSD: graph2.c,v 1.4 2011/10/21 23:47:11 joerg Exp $");
50 static const uint32_t unused
= 0xffffffffU
;
53 graph2_setup(struct graph2
*graph
, uint32_t v
, uint32_t e
)
58 graph
->verts
= calloc(sizeof(struct vertex2
), v
);
59 graph
->edges
= calloc(sizeof(struct edge2
), e
);
60 graph
->output_order
= calloc(sizeof(uint32_t), e
);
62 if (graph
->verts
== NULL
|| graph
->edges
== NULL
||
63 graph
->output_order
== NULL
)
64 err(1, "malloc failed");
68 graph2_free(struct graph2
*graph
)
72 free(graph
->output_order
);
76 graph
->output_order
= NULL
;
80 graph2_check_duplicates(struct nbperf
*nbperf
, struct graph2
*graph
)
86 for (i
= 0; i
< graph
->e
; ++i
) {
88 v
= &graph
->verts
[e
->left
];
90 e2
= &graph
->edges
[j
];
92 if (i
< j
&& e
->right
== e2
->right
&&
93 nbperf
->keylens
[i
] == nbperf
->keylens
[j
] &&
94 memcmp(nbperf
->keys
[i
], nbperf
->keys
[j
],
95 nbperf
->keylens
[i
]) == 0) {
96 nbperf
->has_duplicates
= 1;
99 if (e2
->l_next
== unused
)
102 e2
= &graph
->edges
[j
];
109 graph2_hash(struct nbperf
*nbperf
, struct graph2
*graph
)
112 uint32_t hashes
[NBPERF_MAX_HASH_SIZE
];
115 for (i
= 0; i
< graph
->e
; ++i
) {
116 (*nbperf
->compute_hash
)(nbperf
,
117 nbperf
->keys
[i
], nbperf
->keylens
[i
], hashes
);
118 graph
->edges
[i
].left
= hashes
[0] % graph
->v
;
119 graph
->edges
[i
].right
= hashes
[1] % graph
->v
;
120 if (graph
->edges
[i
].left
== graph
->edges
[i
].right
)
124 for (i
= 0; i
< graph
->v
; ++i
) {
125 graph
->verts
[i
].l_edge
= unused
;
126 graph
->verts
[i
].r_edge
= unused
;
129 for (i
= 0; i
< graph
->e
; ++i
) {
130 v
= &graph
->verts
[graph
->edges
[i
].left
];
131 if (v
->l_edge
!= unused
)
132 graph
->edges
[v
->l_edge
].l_prev
= i
;
133 graph
->edges
[i
].l_next
= v
->l_edge
;
134 graph
->edges
[i
].l_prev
= unused
;
137 v
= &graph
->verts
[graph
->edges
[i
].right
];
138 if (v
->r_edge
!= unused
)
139 graph
->edges
[v
->r_edge
].r_prev
= i
;
140 graph
->edges
[i
].r_next
= v
->r_edge
;
141 graph
->edges
[i
].r_prev
= unused
;
145 if (nbperf
->first_round
) {
146 nbperf
->first_round
= 0;
147 return graph2_check_duplicates(nbperf
, graph
);
154 graph2_remove_vertex(struct graph2
*graph
, struct vertex2
*v
)
160 if (v
->l_edge
!= unused
&& v
->r_edge
!= unused
)
162 if (v
->l_edge
== unused
&& v
->r_edge
== unused
)
165 if (v
->l_edge
!= unused
) {
166 e
= &graph
->edges
[v
->l_edge
];
167 if (e
->l_next
!= unused
)
169 v
->l_edge
= unused
; /* No other elements possible! */
170 v2
= &graph
->verts
[e
->right
];
171 if (e
->r_prev
== unused
)
172 v2
->r_edge
= e
->r_next
;
174 graph
->edges
[e
->r_prev
].r_next
= e
->r_next
;
175 if (e
->r_next
!= unused
)
176 graph
->edges
[e
->r_next
].r_prev
= e
->r_prev
;
179 e
= &graph
->edges
[v
->r_edge
];
180 if (e
->r_next
!= unused
)
182 v
->r_edge
= unused
; /* No other elements possible! */
183 v2
= &graph
->verts
[e
->left
];
184 if (e
->l_prev
== unused
)
185 v2
->l_edge
= e
->l_next
;
187 graph
->edges
[e
->l_prev
].l_next
= e
->l_next
;
188 if (e
->l_next
!= unused
)
189 graph
->edges
[e
->l_next
].l_prev
= e
->l_prev
;
193 graph
->output_order
[--graph
->output_index
] = e
- graph
->edges
;
198 graph2_output_order(struct graph2
*graph
)
202 graph
->output_index
= graph
->e
;
204 for (i
= 0; i
< graph
->v
; ++i
)
205 graph2_remove_vertex(graph
, &graph
->verts
[i
]);
207 if (graph
->output_index
!= 0)