From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on dcvr.yhbt.net X-Spam-Level: X-Spam-Status: No, score=-3.6 required=3.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, DKIM_INVALID,DKIM_SIGNED,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_MED, RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_PASS shortcircuit=no autolearn=ham autolearn_force=no version=3.4.2 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dcvr.yhbt.net (Postfix) with ESMTPS id B94AE1F4B4 for ; Sat, 10 Oct 2020 20:58:13 +0000 (UTC) Received: from localhost ([::1]:45904 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1kRLwS-0000xl-8J for normalperson@yhbt.net; Sat, 10 Oct 2020 16:58:12 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:53914) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1kRLtl-00068T-Nx for bug-gnulib@gnu.org; Sat, 10 Oct 2020 16:55:26 -0400 Received: from mail-ej1-x632.google.com ([2a00:1450:4864:20::632]:33359) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1kRLte-0000J8-Rs for bug-gnulib@gnu.org; Sat, 10 Oct 2020 16:55:25 -0400 Received: by mail-ej1-x632.google.com with SMTP id c22so17995064ejx.0 for ; Sat, 10 Oct 2020 13:55:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=sender:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=83bAFGUW007Vq4EeKdbDbu5npdWBffrZWPSEGKTOTDA=; b=BT3XjMz4vb9juP8FTEMUiPA+YoN32gNRdHQlsC/0Kj76uzAK2kIV0k0K5Q5VPFyI3e LkGBZhJk4fYLOZFz6ib+lOqZgwQcHa+5xWkXocY+0PZf6yhWH69M38TY7lTXaOVad+9z YgZYnx69v6iw06LRMb8ELB9XhSU4nlcYp4ekxefoOD7YvAUO3qOodEVUP8urYJnM7oce IPqk8aCZqey4Zcbsb9g+HBDJLs8AojXRs/m0ks11ptnMSFa0FXl6qUCqRnVmRSH+eho9 LNX/y++acFfxKdaq6XjwZpShe/Tim1mq+GrRVQ8asC11EI+xB0MfPXROjCilPe4ipHoX acvA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:from:to:cc:subject:date:message-id :mime-version:content-transfer-encoding; bh=83bAFGUW007Vq4EeKdbDbu5npdWBffrZWPSEGKTOTDA=; b=k/nvCqtYcVtXqvWt9j6EGAW5bZ7WZ2c5zqiFuletCB3SW3r3zAp9gO60tBrJMdsKEU 3FqG0AMEAqrkt/KZL7U6cYjg9OHHNQLLgw1lOIGtfQLZwBN8xnwlx0jodJDSu4zXpn05 CCWx9oTD/b22f0fAbwXrQabEqki0oJnYiCuh/lcha4KZHRAwwvxMMUUvLpzxO8USrukk MSoQ45DTxk+VFSW05XABPLDyvM+V7KfV3iQfVbU3BV9/RSzQDpJM6JFOpdoKSEnGj0F0 FkoS3gcIDzIyUkRAhBuhuaGVSVR6AfI/SVa80EyjgiPT3Erw+YrD3I4QqumFCN6/NMm6 FD5Q== X-Gm-Message-State: AOAM531whJATiyQ4JGRUjGKbWtk2Qp7p993Mp6PCeTdJp6s9Aeazx+qe flPCJe8Zr3iVuew3AVVUGu08UZyE9eglfA== X-Google-Smtp-Source: ABdhPJwc9SdTO+9NSjED2shU9PMYX8Xae99stMz3Y2nW30bjpuitwysloJNfwVCLdFjV+xrOBK2LIg== X-Received: by 2002:a17:906:6d0c:: with SMTP id m12mr20770490ejr.498.1602363316039; Sat, 10 Oct 2020 13:55:16 -0700 (PDT) Received: from caesar.mshome.net (ipbcc3f9d0.dynamic.kabel-deutschland.de. [188.195.249.208]) by smtp.gmail.com with ESMTPSA id ba6sm8284866edb.61.2020.10.10.13.55.15 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 10 Oct 2020 13:55:15 -0700 (PDT) From: =?UTF-8?q?Marc=20Nieper-Wi=C3=9Fkirchen?= To: bug-gnulib@gnu.org Subject: [PATCH] stack: New module. Date: Sat, 10 Oct 2020 22:55:12 +0200 Message-Id: <20201010205512.3121887-1-marc.nieper+gnu@gmail.com> X-Mailer: git-send-email 2.25.1 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Received-SPF: pass client-ip=2a00:1450:4864:20::632; envelope-from=marc.nieper+gnu@gmail.com; helo=mail-ej1-x632.google.com X-detected-operating-system: by eggs.gnu.org: No matching host in p0f cache. That's all we know. X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: bug-gnulib@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Gnulib discussion list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: =?UTF-8?q?Marc=20Nieper-Wi=C3=9Fkirchen?= Errors-To: bug-gnulib-bounces+normalperson=yhbt.net@gnu.org Sender: "bug-gnulib" From: Marc Nieper-Wißkirchen * MODULES.html.sh: Add entry for the stack module. * modules/stack: New file. * modules/stack-tests: New file. * lib/stack.h: New file. * tests/test-stack.c: New file. --- ChangeLog | 9 +++ MODULES.html.sh | 1 + lib/stack.h | 165 ++++++++++++++++++++++++++++++++++++++++++++ modules/stack | 25 +++++++ modules/stack-tests | 13 ++++ tests/test-stack.c | 74 ++++++++++++++++++++ 6 files changed, 287 insertions(+) create mode 100644 lib/stack.h create mode 100644 modules/stack create mode 100644 modules/stack-tests create mode 100644 tests/test-stack.c diff --git a/ChangeLog b/ChangeLog index b479cf0c7..f496c8345 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2020-10-10 Marc Nieper-Wißkirchen + + stack: New module. + * MODULES.html.sh: Add entry for the stack module. + * modules/stack: New file. + * modules/stack-tests: New file. + * lib/stack.h: New file. + * tests/test-stack.c: New file. + 2020-10-10 Paul Eggert attribute: improve const, pure doc diff --git a/MODULES.html.sh b/MODULES.html.sh index a8a629e29..7e7cdae3e 100755 --- a/MODULES.html.sh +++ b/MODULES.html.sh @@ -2031,6 +2031,7 @@ func_all_modules () func_module readline func_module readtokens func_module readtokens0 + func_module stack func_module strverscmp func_module filevercmp func_end_table diff --git a/lib/stack.h b/lib/stack.h new file mode 100644 index 000000000..5d803901c --- /dev/null +++ b/lib/stack.h @@ -0,0 +1,165 @@ +/* Type-safe stack data type. + Copyright (C) 2020 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ + +/* Written by Marc Nieper-Wißkirchen , 2020. */ + +/* This header file does not have include-guards as it is meant to be + includeable multiple times as long as the necessary defines have + been set up. + + A stack is implemented with a homogenous array of elements in + memory, which will be resized (and moved) as needed. Elements are + passed by value and it is the responsibility of the user-code to + free any resources associated with individual elements. + + The exported names are all prefixed by ‘stack’ (e.g. stack_init), + but this can be changed by setting an appropriate define. + Type: stack_type + Initialization: stack_init (&stack); + De-initialization: stack_destroy (&stack); + Predicate: bool res = stack_empty (&stack); + Introspection: ELEMENT *base = stack_base (&stack); + Pushing: stack_push (&stack, element); + Popping: ELEMENT element = stack_pop (&stack); + Discarding: stack_discard (&stack); + Top-of-stack: ELEMENT element = stack_top (&stack); + Size: size_t size = stack_size (&stack); + + Here, ELEMENT is the type to which GL_STACK_ELEMENT was defined when + this file was included. +*/ + +/* Before including this file, you need to define: + GL_STACK_ELEMENT The type of the elements on the stack. + GL_STACK_STORAGECLASS (Optional) The storage class specifier (e.g. static) + to use in the function definitions. + GL_STACK_NAME (Optional) The prefix to use for the type names + and functions definitions instead of the default + ‘stack’. + + After including this file, these names will be undefined. + + Before including this file, you also need to include: + #include "" + #include "" + #include "assure.h" + #include "xalloc.h" +*/ + +#ifndef GL_STACK_ELEMENT +# error "Please define GL_STACK_ELEMENT first." +#endif + +#ifndef GL_STACK_STORAGECLASS +# define GL_STACK_STORAGECLASS +#endif + +#ifndef GL_STACK_NAME +# define GL_STACK_NAME stack +#endif + +#define _GL_STACK_PREFIX(name) _GL_CONCAT(GL_STACK_NAME, _GL_CONCAT(_, name)) +#define _GL_STACK_TYPE _GL_STACK_PREFIX(type) + +typedef struct +{ + GL_STACK_ELEMENT *base; + size_t size; + size_t allocated; +} _GL_STACK_TYPE; + +/* Initialize a stack. */ +GL_STACK_STORAGECLASS void +_GL_STACK_PREFIX (init) (_GL_STACK_TYPE *stack) +{ + stack->base = NULL; + stack->size = 0; + stack->allocated = 0; +} + +/* Destroy a stack by freeing the allocated space. */ +GL_STACK_STORAGECLASS void +_GL_STACK_PREFIX (destroy) (_GL_STACK_TYPE *stack) +{ + free (stack->base); +} + +/* Return true if the stack currently holds no element. */ +GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE bool +_GL_STACK_PREFIX (empty) (const _GL_STACK_TYPE *stack) +{ + return stack->size == 0; +} + +/* Return the current address of the array of stack elements. + + The result is invalidated as soon as an element is added or removed + from the stack. */ +GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE GL_STACK_ELEMENT * +_GL_STACK_PREFIX (current_base) (const _GL_STACK_TYPE *stack) +{ + return stack->base; +} + +/* Push an element to the top of the stack. */ +GL_STACK_STORAGECLASS void +_GL_STACK_PREFIX (push) (_GL_STACK_TYPE *stack, GL_STACK_ELEMENT item) +{ + if (stack->size == stack->allocated) + stack->base = x2nrealloc (stack->base, &stack->allocated, + sizeof (GL_STACK_ELEMENT)); + stack->base [stack->size++] = item; +} + +/* Pop the element from the top of the stack, which must be non-empty, + and return it. */ +GL_STACK_STORAGECLASS GL_STACK_ELEMENT +_GL_STACK_PREFIX (pop) (_GL_STACK_TYPE *stack) +{ + affirm (!_GL_STACK_PREFIX (empty) (stack)); + return stack->base [--stack->size]; +} + +/* Pop the element from the top of the stack, which must be + non-empty. */ +GL_STACK_STORAGECLASS void +_GL_STACK_PREFIX (discard) (_GL_STACK_TYPE *stack) +{ + affirm (!_GL_STACK_PREFIX (empty) (stack)); + --stack->size; +} + +/* Return the element from the top of the stack, which must be + non-empty. */ +GL_STACK_STORAGECLASS GL_STACK_ELEMENT +_GL_STACK_PREFIX (top) (const _GL_STACK_TYPE *stack) +{ + affirm (!_GL_STACK_PREFIX (empty) (stack)); + return stack->base [stack->size - 1]; +} + +/* Return the currently stored number of elements in the stack. */ +GL_STACK_STORAGECLASS _GL_ATTRIBUTE_PURE size_t +_GL_STACK_PREFIX (size) (const _GL_STACK_TYPE *stack) +{ + return stack->size; +} + +#undef GL_STACK_ELEMENT +#undef GL_STACK_STORAGECLASS +#undef GL_STACK_NAME +#undef _GL_STACK_PREFIX +#undef _GL_STACK_TYPE diff --git a/modules/stack b/modules/stack new file mode 100644 index 000000000..95f2ce9b9 --- /dev/null +++ b/modules/stack @@ -0,0 +1,25 @@ +Description: +Type-safe stack data type. + +Files: +lib/stack.h + +Depends-on: +assure +stdbool +stdlib +xalloc + +configure.ac: + +Makefile.am: +lib_SOURCES += stack.h + +Include: +"stack.h" + +License: +GPL + +Maintainer: +Marc Nieper-Wißkirchen diff --git a/modules/stack-tests b/modules/stack-tests new file mode 100644 index 000000000..308d7258e --- /dev/null +++ b/modules/stack-tests @@ -0,0 +1,13 @@ +Files: +tests/test-stack.c +tests/macros.h + +Depends-on: +string + +configure.ac: + +Makefile.am: +TESTS += test-stack +check_PROGRAMS += test-stack +test_stack_SOURCES = test-stack.c diff --git a/tests/test-stack.c b/tests/test-stack.c new file mode 100644 index 000000000..dbf4e19a3 --- /dev/null +++ b/tests/test-stack.c @@ -0,0 +1,74 @@ +/* Test of the type-safe stack data type. + Copyright (C) 2020 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . */ + +/* Written by Marc Nieper-Wißkirchen , 2020. */ + +#include + +#include +#include +#include +#include "assure.h" +#include "xalloc.h" + +#include "macros.h" + +#define GL_STACK_ELEMENT int +#define GL_STACK_STORAGECLASS static +#include "stack.h" + +#define GL_STACK_ELEMENT const char * +#define GL_STACK_STORAGECLASS static +#define GL_STACK_NAME string_stack +#include "stack.h" + +int +main (void) +{ + stack_type int_stack; + stack_init (&int_stack); + ASSERT (stack_size (&int_stack) == 0); + ASSERT (stack_empty (&int_stack)); + stack_push (&int_stack, 0); + stack_push (&int_stack, 1); + stack_push (&int_stack, 2); + stack_push (&int_stack, 3); + stack_push (&int_stack, 4); + stack_push (&int_stack, 5); + stack_push (&int_stack, 6); + stack_push (&int_stack, 7); + stack_push (&int_stack, 8); + stack_push (&int_stack, 9); + ASSERT (stack_size (&int_stack) == 10); + ASSERT (!stack_empty (&int_stack)); + ASSERT (stack_top (&int_stack) == 9); + ASSERT (stack_size (&int_stack) == 10); + ASSERT (stack_pop (&int_stack) == 9); + ASSERT (stack_size (&int_stack) == 9); + stack_discard (&int_stack); + ASSERT (stack_size (&int_stack) == 8); + ASSERT (stack_top (&int_stack) == 7); + stack_destroy (&int_stack); + + string_stack_type string_stack [1]; + string_stack_init (string_stack); + string_stack_push (string_stack, "foo"); + ASSERT (STREQ (string_stack_pop (string_stack), "foo")); + ASSERT (string_stack_empty (string_stack)); + string_stack_destroy (string_stack); + + return EXIT_SUCCESS; +} -- 2.25.1