/*      $NetBSD: graph2.c,v 1.7 2026/03/10 21:59:30 andvar Exp $        */
/*-
 * Copyright (c) 2009 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by Joerg Sonnenberger.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#if HAVE_NBTOOL_CONFIG_H
#include "nbtool_config.h"
#endif

#include <sys/cdefs.h>
__RCSID("$NetBSD: graph2.c,v 1.7 2026/03/10 21:59:30 andvar Exp $");

#include <err.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "nbperf.h"
#include "graph2.h"

void
SIZED2(_setup)(struct SIZED(graph) *graph, uint32_t v, uint32_t e)
{
        graph->v = v;
        graph->e = e;

        graph->verts = calloc(sizeof(*graph->verts), v);
        graph->edges = calloc(sizeof(*graph->edges), e);
        graph->output_order = calloc(sizeof(uint32_t), e);

        if (graph->verts == NULL || graph->edges == NULL ||
            graph->output_order == NULL)
                err(1, "malloc failed");
}

void
SIZED2(_free)(struct SIZED(graph) *graph)
{
        free(graph->verts);
        free(graph->edges);
        free(graph->output_order);

        graph->verts = NULL;
        graph->edges = NULL;
        graph->output_order = NULL;
}

static struct nbperf *sorting_nbperf;
static struct SIZED(graph) *sorting_graph;
static int sorting_found;

static int sorting_cmp(const void *a_, const void *b_)
{
        const uint32_t *a = a_, *b = b_;
        int i;
        const struct SIZED(edge) *ea = &sorting_graph->edges[*a],
            *eb = &sorting_graph->edges[*b];
        for (i = 0; i < GRAPH_SIZE; ++i) {
                if (ea->vertices[i] < eb->vertices[i])
                        return -1;
                if (ea->vertices[i] > eb->vertices[i])
                        return 1;
        }
        if (sorting_nbperf->keylens[*a] < sorting_nbperf->keylens[*b])
                return -1;
        if (sorting_nbperf->keylens[*a] > sorting_nbperf->keylens[*b])
                return 1;
        i = memcmp(sorting_nbperf->keys[*a], sorting_nbperf->keys[*b],
            sorting_nbperf->keylens[*a]);
        if (i == 0)
                sorting_found = 1;
        return i;
}

static int
SIZED2(_check_duplicates)(struct nbperf *nbperf, struct SIZED(graph) *graph)
{
        size_t i;
        uint32_t *key_index = calloc(sizeof(*key_index), graph->e);

        if (key_index == NULL)
                err(1, "malloc failed");
        for (i = 0; i < graph->e; ++i)
                key_index[i] = i;

        sorting_nbperf = nbperf;
        sorting_graph = graph;
        sorting_found = 0;
        qsort(key_index, graph->e, sizeof(*key_index), sorting_cmp);
        if (sorting_found)
                goto found_dups;
        /*
         * Any duplicate must have been found as part of the qsort,
         * as it can't sort consecutive elements in the output without
         * comparing them at least once.
         */

        free(key_index);
        return 0;
 found_dups:
        nbperf->has_duplicates = 1;
        return -1;
}

static inline void
SIZED2(_add_edge)(struct SIZED(graph) *graph, uint32_t edge)
{
        struct SIZED(edge) *e = graph->edges + edge;
        struct SIZED(vertex) *v;
        size_t i;

        for (i = 0; i < GRAPH_SIZE; ++i) {
                v = graph->verts + e->vertices[i];
                v->edges ^= edge;
                ++v->degree;
        }
}

static inline void
SIZED2(_remove_edge)(struct SIZED(graph) *graph, uint32_t edge)
{
        struct SIZED(edge) *e = graph->edges + edge;
        struct SIZED(vertex) *v;
        size_t i;

        for (i = 0; i < GRAPH_SIZE; ++i) {
                v = graph->verts + e->vertices[i];
                v->edges ^= edge;
                --v->degree;
        }
}

static inline void
SIZED2(_remove_vertex)(struct SIZED(graph) *graph, uint32_t vertex)
{
        struct SIZED(vertex) *v = graph->verts + vertex;
        uint32_t e;

        if (v->degree == 1) {
                e = v->edges;
                graph->output_order[--graph->output_index] = e;
                SIZED2(_remove_edge)(graph, e);
        }
}

int
SIZED2(_hash)(struct nbperf *nbperf, struct SIZED(graph) *graph)
{
        struct SIZED(edge) *e;
        uint32_t hashes[NBPERF_MAX_HASH_SIZE];
        size_t i, j;

#if GRAPH_SIZE == 2
        if (nbperf->allow_hash_fudging && (graph->v & 1) != 0)
                errx(1, "vertex count must have lowest bit clear");
#else
        if (nbperf->allow_hash_fudging && (graph->v & 3) != 0)
                errx(1, "vertex count must have lowest 2 bits clear");
#endif


        memset(graph->verts, 0, sizeof(*graph->verts) * graph->v);
        graph->hash_fudge = 0;

        for (i = 0; i < graph->e; ++i) {
                (*nbperf->compute_hash)(nbperf,
                    nbperf->keys[i], nbperf->keylens[i], hashes);
                e = graph->edges + i;
                for (j = 0; j < GRAPH_SIZE; ++j) {
                        e->vertices[j] = hashes[j] % graph->v;
                        if (j == 1 && e->vertices[0] == e->vertices[1]) {
                                if (!nbperf->allow_hash_fudging)
                                        return -1;
                                e->vertices[1] ^= 1; /* toggle bit to differ */
                                graph->hash_fudge |= 1;
                        }
#if GRAPH_SIZE == 3
                        if (j == 2 && (e->vertices[0] == e->vertices[2] ||
                            e->vertices[1] == e->vertices[2])) {
                                if (!nbperf->allow_hash_fudging)
                                        return -1;
                                graph->hash_fudge |= 2;
                                e->vertices[2] ^= 1;
                                e->vertices[2] ^= 2 * (e->vertices[0] == e->vertices[2] ||
                                    e->vertices[1] == e->vertices[2]);
                        }
#endif
                }
        }

        for (i = 0; i < graph->e; ++i)
                SIZED2(_add_edge)(graph, i);

        if (nbperf->check_duplicates) {
                nbperf->check_duplicates = 0;
                return SIZED2(_check_duplicates)(nbperf, graph);
        }

        return 0;
}

int
SIZED2(_output_order)(struct SIZED(graph) *graph)
{
        size_t i, j;
        struct SIZED(edge) *e2;

        graph->output_index = graph->e;

        for (i = 0; i < graph->v; ++i)
                SIZED2(_remove_vertex)(graph, i);

        for (i = graph->e; graph->output_index > 0 && i > graph->output_index;) {
                e2 = graph->edges + graph->output_order[--i];
                for (j = 0; j < GRAPH_SIZE; ++j)
                        SIZED2(_remove_vertex)(graph, e2->vertices[j]);
        }

        if (graph->output_index != 0) {
                return -1;
        }

        return 0;
}