From ac40436aef43e055e0671bc48b9cc4be7f3e6dda Mon Sep 17 00:00:00 2001 From: Matthew Fernandez Date: Thu, 8 Dec 2022 08:24:53 -0800 Subject: [PATCH] sparse: replace 'IntStack' with generic list implementation MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Apart from reducing the amount of code to maintain going forwards, this removes several warts: 1. `IntStack_push` returned a value indicating whether it succeeded or failed. The caller was ignoring this. We now exit on push failure. 2. `IntStack_pop` used an awkward flag-based protocol to detect an empty stack. We now use a cleaner “is empty” guard on the pop call. 3. Iterating over all stack elements sometimes used < length and sometimes ≤ last. There were reasons for this (`SIZE_MAX` was used as a sentinel last value, and length was calculated based on last). But it led to code that was harder than necessary to understand at the call site. --- ci/clang_format.py | 2 - lib/sparse/BinaryHeap.c | 29 ++++++------- lib/sparse/BinaryHeap.h | 6 ++- lib/sparse/CMakeLists.txt | 2 - lib/sparse/IntStack.c | 64 ----------------------------- lib/sparse/IntStack.h | 43 ------------------- lib/sparse/Makefile.am | 4 +- lib/sparse/gvsparse.vcxproj | 1 - lib/sparse/gvsparse.vcxproj.filters | 3 -- 9 files changed, 21 insertions(+), 133 deletions(-) delete mode 100644 lib/sparse/IntStack.c delete mode 100644 lib/sparse/IntStack.h diff --git a/ci/clang_format.py b/ci/clang_format.py index b69fc5c60..c52102ef6 100644 --- a/ci/clang_format.py +++ b/ci/clang_format.py @@ -575,8 +575,6 @@ EXCLUDE = ( "lib/sparse/BinaryHeap.h", "lib/sparse/DotIO.c", "lib/sparse/DotIO.h", - "lib/sparse/IntStack.c", - "lib/sparse/IntStack.h", "lib/sparse/LinkedList.c", "lib/sparse/LinkedList.h", "lib/sparse/QuadTree.c", diff --git a/lib/sparse/BinaryHeap.c b/lib/sparse/BinaryHeap.c index 757845a11..08558154a 100644 --- a/lib/sparse/BinaryHeap.c +++ b/lib/sparse/BinaryHeap.c @@ -26,7 +26,7 @@ BinaryHeap BinaryHeap_new(int (*cmp)(void*item1, void*item2)){ for (size_t i = 0; i < max_len; i++) h->id_to_pos[i] = SIZE_MAX; h->pos_to_id = CALLOC(max_len, sizeof(h->pos_to_id[0])); - h->id_stack = IntStack_new(); + h->id_stack = (int_stack_t){0}; h->cmp = cmp; return h; } @@ -36,7 +36,7 @@ void BinaryHeap_delete(BinaryHeap h, void (*del)(void* item)){ if (!h) return; free(h->id_to_pos); free(h->pos_to_id); - IntStack_delete(h->id_stack); + int_stack_free(&h->id_stack); if (del) for (size_t i = 0; i < h->len; i++) del((h->heap)[i]); free(h->heap); free(h); @@ -137,16 +137,17 @@ static size_t siftDown(BinaryHeap h, size_t nodePos){ int BinaryHeap_insert(BinaryHeap h, void *item){ size_t len = h->len; assert(len <= (size_t)INT_MAX); - int id = (int)len, flag; + int id = (int)len; /* insert an item, and return its ID. This ID can be used later to extract the item */ if (len > h->max_len - 1) { if (BinaryHeap_realloc(h) == NULL) return BinaryHeap_error_malloc; } - /* check if we have IDs in the stack to reuse. If no, then assign the last pos as the ID */ - id = IntStack_pop(h->id_stack, &flag); - if (flag) id = (int)len; + // check if we have IDs in the stack to reuse + if (!int_stack_is_empty(&h->id_stack)) { + id = int_stack_pop(&h->id_stack); + } h->heap[len] = item; h->id_to_pos[id] = len; @@ -189,7 +190,7 @@ void* BinaryHeap_extract_item(BinaryHeap h, int id){ item = (h->heap)[pos]; - IntStack_push(h->id_stack, id); + int_stack_push(&h->id_stack, id); if (pos < h->len - 1){/* move the last item to occupy the position of extracted item */ swap(h, pos, h->len - 1); @@ -245,11 +246,11 @@ void BinaryHeap_sanity_check(BinaryHeap h){ assert((h->cmp)(heap[i], heap[parentPos]) >= 0); } - mask = CALLOC(h->len + IntStack_get_length(h->id_stack), sizeof(mask[0])); + mask = CALLOC(h->len + int_stack_size(&h->id_stack), sizeof(mask[0])); /* check that spare keys has negative id_to_pos mapping */ - for (size_t i = 0; i <= h->id_stack->last; i++) { - int key_spare = h->id_stack->stack[i]; + for (size_t i = 0; i < int_stack_size(&h->id_stack); i++) { + int key_spare = int_stack_get(&h->id_stack, i); assert(h->id_to_pos[key_spare] == SIZE_MAX); mask[key_spare] = 1;/* mask spare ID */ } @@ -265,7 +266,7 @@ void BinaryHeap_sanity_check(BinaryHeap h){ } /* all IDs, spare or in use, are accounted for and give a contiguous set */ - for (size_t i = 0; i < h->len + IntStack_get_length(h->id_stack); i++) + for (size_t i = 0; i < h->len + int_stack_size(&h->id_stack); i++) assert(mask[i] != 0); free(mask); @@ -282,9 +283,9 @@ void BinaryHeap_print(BinaryHeap h, void (*pnt)(void*)){ } } fprintf(stderr, "\nSpare keys ="); - for (size_t i = 0; i <= h->id_stack->last; i++) { - fprintf(stderr, "%d(%" PRISIZE_T ") ", h->id_stack->stack[i], - h->id_to_pos[h->id_stack->stack[i]]); + for (size_t i = 0; i < int_stack_size(&h->id_stack); i++) { + fprintf(stderr, "%d(%" PRISIZE_T ") ", int_stack_get(&h->id_stack, i), + h->id_to_pos[int_stack_get(&h->id_stack, i)]); } fprintf(stderr, "\n"); } diff --git a/lib/sparse/BinaryHeap.h b/lib/sparse/BinaryHeap.h index d634aa87e..2275cc8c8 100644 --- a/lib/sparse/BinaryHeap.h +++ b/lib/sparse/BinaryHeap.h @@ -10,14 +10,16 @@ #pragma once +#include #include -#include #include #ifdef __cplusplus extern "C" { #endif +DEFINE_LIST(int_stack, int) + /* binary heap code. Caution: items inserted should be kept untouched, e.g., the value of the item should be kepted unchanged while the heap is still in use! To change the valud of am item, use BinaryHeap_reset @@ -35,7 +37,7 @@ struct BinaryHeap_struct { pos_to_id[id_to_pos[i]] = i, for i not in the id_stack & i < length(id_stack)+len id_to_pos[pos_to_id[i]] = i, 0 <= i < len */ - IntStack id_stack;/* a stack that store IDs that is no longer used, to + int_stack_t id_stack;/* a stack that store IDs that is no longer used, to be assigned to newly inserted elements. For sanity check, the union of items in the id_stack, and that is pos_to_id[1:len], diff --git a/lib/sparse/CMakeLists.txt b/lib/sparse/CMakeLists.txt index 94293f032..5887d3862 100644 --- a/lib/sparse/CMakeLists.txt +++ b/lib/sparse/CMakeLists.txt @@ -6,7 +6,6 @@ add_library(sparse STATIC colorutil.h DotIO.h general.h - IntStack.h LinkedList.h mq.h QuadTree.h @@ -19,7 +18,6 @@ add_library(sparse STATIC colorutil.c DotIO.c general.c - IntStack.c LinkedList.c mq.c QuadTree.c diff --git a/lib/sparse/IntStack.c b/lib/sparse/IntStack.c deleted file mode 100644 index e992533c5..000000000 --- a/lib/sparse/IntStack.c +++ /dev/null @@ -1,64 +0,0 @@ -/************************************************************************* - * Copyright (c) 2011 AT&T Intellectual Property - * All rights reserved. This program and the accompanying materials - * are made available under the terms of the Eclipse Public License v1.0 - * which accompanies this distribution, and is available at - * http://www.eclipse.org/legal/epl-v10.html - * - * Contributors: Details at https://graphviz.org - *************************************************************************/ - -#include -#include -#include -#include - -IntStack IntStack_new(void){ - IntStack s; - size_t max_len = 1<<5; - - s = MALLOC(sizeof(struct IntStack_struct)); - s->max_len = max_len; - s->last = SIZE_MAX; - s->stack = MALLOC(sizeof(int)*max_len); - return s; -} - -void IntStack_delete(IntStack s){ - if (s){ - free(s->stack); - free(s); - } -} - -static IntStack IntStack_realloc(IntStack s){ - size_t max_len = s->max_len; - - max_len += MAX(10, max_len / 5); - s->max_len = max_len; - s->stack = REALLOC(s->stack, sizeof(int)*max_len); - if (!s->stack) return NULL; - return s; -} - -size_t IntStack_push(IntStack s, int i){ - // add an item and return the pos. Return SIZE_MAX if malloc failed - if (s->last != SIZE_MAX && s->last >= s->max_len - 1) { - if (!IntStack_realloc(s)) return SIZE_MAX; - } - s->stack[++s->last] = i; - return s->last; -} -int IntStack_pop(IntStack s, int *flag){ - /* remove the last item. If none exist, return -1 */ - *flag = 0; - if (s->last == SIZE_MAX) { - *flag = -1; - return -1; - } - return s->stack[s->last--]; -} -void IntStack_print(IntStack s){ - for (size_t i = 0; i <= s->last; i++) fprintf(stderr, "%d,", s->stack[i]); - fprintf(stderr,"\n"); -} diff --git a/lib/sparse/IntStack.h b/lib/sparse/IntStack.h deleted file mode 100644 index 68a219d07..000000000 --- a/lib/sparse/IntStack.h +++ /dev/null @@ -1,43 +0,0 @@ -/************************************************************************* - * Copyright (c) 2011 AT&T Intellectual Property - * All rights reserved. This program and the accompanying materials - * are made available under the terms of the Eclipse Public License v1.0 - * which accompanies this distribution, and is available at - * http://www.eclipse.org/legal/epl-v10.html - * - * Contributors: Details at https://graphviz.org - *************************************************************************/ - -#pragma once - -#include - -#ifdef __cplusplus -extern "C" { -#endif - -/* last in first out integer stack */ -struct IntStack_struct{ - size_t last; // position of the last element, If empty, last = SIZE_MAX - size_t max_len; - int *stack; -}; - -typedef struct IntStack_struct* IntStack; - -IntStack IntStack_new(void); - -void IntStack_delete(IntStack s); - -#define IntStack_get_length(s) (1+(s)->last) - -size_t IntStack_push(IntStack s, int i); // add an item and return the pos - // Return SIZE_MAX if malloc failed - -int IntStack_pop(IntStack s, int *flag);/* remove the last item. If none exist, flag = -1, and return -1. */ - -void IntStack_print(IntStack s); - -#ifdef __cplusplus -} -#endif diff --git a/lib/sparse/Makefile.am b/lib/sparse/Makefile.am index 2c3d2a18e..8c591430b 100644 --- a/lib/sparse/Makefile.am +++ b/lib/sparse/Makefile.am @@ -6,12 +6,12 @@ AM_CPPFLAGS = \ -I$(top_srcdir)/lib/cgraph \ -I$(top_srcdir)/lib/cdt -noinst_HEADERS = SparseMatrix.h general.h BinaryHeap.h IntStack.h DotIO.h \ +noinst_HEADERS = SparseMatrix.h general.h BinaryHeap.h DotIO.h \ LinkedList.h colorutil.h color_palette.h mq.h clustering.h QuadTree.h noinst_LTLIBRARIES = libsparse_C.la -libsparse_C_la_SOURCES = SparseMatrix.c general.c BinaryHeap.c IntStack.c DotIO.c \ +libsparse_C_la_SOURCES = SparseMatrix.c general.c BinaryHeap.c DotIO.c \ LinkedList.c colorutil.c color_palette.c mq.c clustering.c QuadTree.c EXTRA_DIST = gvsparse.vcxproj* diff --git a/lib/sparse/gvsparse.vcxproj b/lib/sparse/gvsparse.vcxproj index 5a5073358..438044e5c 100644 --- a/lib/sparse/gvsparse.vcxproj +++ b/lib/sparse/gvsparse.vcxproj @@ -85,7 +85,6 @@ - diff --git a/lib/sparse/gvsparse.vcxproj.filters b/lib/sparse/gvsparse.vcxproj.filters index a4a6481d8..3c9bf48ce 100644 --- a/lib/sparse/gvsparse.vcxproj.filters +++ b/lib/sparse/gvsparse.vcxproj.filters @@ -38,9 +38,6 @@ Source Files - - Source Files - Source Files -- 2.50.1