1 /* $NetBSD: graph2.h,v 1.1 2009/08/15 16:21:05 joerg Exp $ */ 2 /*- 3 * Copyright (c) 2009 The NetBSD Foundation, Inc. 4 * All rights reserved. 5 * 6 * This code is derived from software contributed to The NetBSD Foundation 7 * by Joerg Sonnenberger. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 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 18 * distribution. 19 * 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 31 * SUCH DAMAGE. 32 */ 33 34 /* 35 * Implementation of common 2-graph routines: 36 * - build a 2-graph with hash-pairs as edges 37 * - check a 2-graph for acyclicness and compute an output order 38 */ 39 40 struct vertex2 { 41 uint32_t l_edge, r_edge; 42 }; 43 44 struct edge2 { 45 uint32_t left, right; 46 uint32_t l_prev, l_next; 47 uint32_t r_prev, r_next; 48 }; 49 50 struct graph2 { 51 struct vertex2 *verts; 52 struct edge2 *edges; 53 uint32_t output_index; 54 uint32_t *output_order; 55 uint8_t *visited; 56 uint32_t e, v; 57 }; 58 59 void graph2_setup(struct graph2 *, uint32_t, uint32_t); 60 void graph2_free(struct graph2 *); 61 62 int graph2_hash(struct nbperf *, struct graph2 *); 63 int graph2_output_order(struct graph2 *graph); 64