Home | History | Annotate | Line # | Download | only in nbperf 
      1 /*	$NetBSD: graph2.h,v 1.2 2021/01/07 16:03:08 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/3-graph routines:
     36  * - build a 2/3-graph with hash-pairs as edges
     37  * - check a 2/3-graph for acyclicness and compute an output order
     38 *
     39  * For each vertex in the 2/3-graph, the incidence lists need to kept.
     40  * Avoid storing the full list by just XORing the indices of the still
     41  * incident edges and the number of such edges as that's all the peeling
     42  * computation needs. This is inspired by:
     43  *   Cache-Oblivious Peeling of Random Hypergraphs by Djamal Belazzougui,
     44  *   Paolo Boldi, Giuseppe Ottaviano, Rossano Venturini, and Sebastiano
     45  *   Vigna. https://arxiv.org/abs/1312.0526
     46  *
     47  * Unlike in the paper, we don't care about external storage and have
     48  * the edge list at hand all the time. As such, no ordering is necessary
     49  * and the vertices of the edge don't have to be copied.
     50  *
     51  * The core observation of the paper above is that for a degree of one,
     52  * the incident edge can be obtained directly.
     53  */
     54 
     55 #ifndef GRAPH_SIZE
     56 #define GRAPH_SIZE 2
     57 #endif
     58 
     59 #define SIZED__(n, i) n ## i
     60 #define SIZED_(n, i) SIZED__(n, i)
     61 #define SIZED(n) SIZED_(n, GRAPH_SIZE)
     62 #define SIZED2__(n, i, m) n ## i ## m
     63 #define SIZED2_(n, i, m) SIZED2__(n, i, m)
     64 #define SIZED2(n) SIZED2_(graph, GRAPH_SIZE, n)
     65 
     66 struct SIZED(vertex) {
     67 	uint32_t degree, edges;
     68 };
     69 
     70 struct SIZED(edge) {
     71 	uint32_t vertices[GRAPH_SIZE];
     72 };
     73 
     74 struct SIZED(graph) {
     75 	struct SIZED(vertex) *verts;
     76 	struct SIZED(edge) *edges;
     77 	uint32_t output_index;
     78 	uint32_t *output_order;
     79 	uint8_t *visited;
     80 	uint32_t e, v;
     81 	int hash_fudge;
     82 };
     83 
     84 void	SIZED2(_setup)(struct SIZED(graph) *, uint32_t, uint32_t);
     85 void	SIZED2(_free)(struct SIZED(graph) *);
     86 
     87 int	SIZED2(_hash)(struct nbperf *, struct SIZED(graph) *);
     88 int	SIZED2(_output_order)(struct SIZED(graph) *graph);
     89