1*c75851fcSLionel Sambuc /* $NetBSD: graph2.h,v 1.1 2009/08/15 16:21:05 joerg Exp $ */ 2*c75851fcSLionel Sambuc /*- 3*c75851fcSLionel Sambuc * Copyright (c) 2009 The NetBSD Foundation, Inc. 4*c75851fcSLionel Sambuc * All rights reserved. 5*c75851fcSLionel Sambuc * 6*c75851fcSLionel Sambuc * This code is derived from software contributed to The NetBSD Foundation 7*c75851fcSLionel Sambuc * by Joerg Sonnenberger. 8*c75851fcSLionel Sambuc * 9*c75851fcSLionel Sambuc * Redistribution and use in source and binary forms, with or without 10*c75851fcSLionel Sambuc * modification, are permitted provided that the following conditions 11*c75851fcSLionel Sambuc * are met: 12*c75851fcSLionel Sambuc * 13*c75851fcSLionel Sambuc * 1. Redistributions of source code must retain the above copyright 14*c75851fcSLionel Sambuc * notice, this list of conditions and the following disclaimer. 15*c75851fcSLionel Sambuc * 2. Redistributions in binary form must reproduce the above copyright 16*c75851fcSLionel Sambuc * notice, this list of conditions and the following disclaimer in 17*c75851fcSLionel Sambuc * the documentation and/or other materials provided with the 18*c75851fcSLionel Sambuc * distribution. 19*c75851fcSLionel Sambuc * 20*c75851fcSLionel Sambuc * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21*c75851fcSLionel Sambuc * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 22*c75851fcSLionel Sambuc * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 23*c75851fcSLionel Sambuc * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 24*c75851fcSLionel Sambuc * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 25*c75851fcSLionel Sambuc * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING, 26*c75851fcSLionel Sambuc * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 27*c75851fcSLionel Sambuc * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED 28*c75851fcSLionel Sambuc * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 29*c75851fcSLionel Sambuc * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 30*c75851fcSLionel Sambuc * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31*c75851fcSLionel Sambuc * SUCH DAMAGE. 32*c75851fcSLionel Sambuc */ 33*c75851fcSLionel Sambuc 34*c75851fcSLionel Sambuc /* 35*c75851fcSLionel Sambuc * Implementation of common 2-graph routines: 36*c75851fcSLionel Sambuc * - build a 2-graph with hash-pairs as edges 37*c75851fcSLionel Sambuc * - check a 2-graph for acyclicness and compute an output order 38*c75851fcSLionel Sambuc */ 39*c75851fcSLionel Sambuc 40*c75851fcSLionel Sambuc struct vertex2 { 41*c75851fcSLionel Sambuc uint32_t l_edge, r_edge; 42*c75851fcSLionel Sambuc }; 43*c75851fcSLionel Sambuc 44*c75851fcSLionel Sambuc struct edge2 { 45*c75851fcSLionel Sambuc uint32_t left, right; 46*c75851fcSLionel Sambuc uint32_t l_prev, l_next; 47*c75851fcSLionel Sambuc uint32_t r_prev, r_next; 48*c75851fcSLionel Sambuc }; 49*c75851fcSLionel Sambuc 50*c75851fcSLionel Sambuc struct graph2 { 51*c75851fcSLionel Sambuc struct vertex2 *verts; 52*c75851fcSLionel Sambuc struct edge2 *edges; 53*c75851fcSLionel Sambuc uint32_t output_index; 54*c75851fcSLionel Sambuc uint32_t *output_order; 55*c75851fcSLionel Sambuc uint8_t *visited; 56*c75851fcSLionel Sambuc uint32_t e, v; 57*c75851fcSLionel Sambuc }; 58*c75851fcSLionel Sambuc 59*c75851fcSLionel Sambuc void graph2_setup(struct graph2 *, uint32_t, uint32_t); 60*c75851fcSLionel Sambuc void graph2_free(struct graph2 *); 61*c75851fcSLionel Sambuc 62*c75851fcSLionel Sambuc int graph2_hash(struct nbperf *, struct graph2 *); 63*c75851fcSLionel Sambuc int graph2_output_order(struct graph2 *graph); 64