From c27255fcbab3a43a6db4f15e5c5eb7109189eb0d Mon Sep 17 00:00:00 2001 From: Keith Marshall Date: Tue, 4 Dec 2018 18:06:30 +0000 Subject: [PATCH] Implement POSIX.1-1996 linked-list queue management API. --- mingwrt/ChangeLog | 12 +++++++ mingwrt/Makefile.in | 5 ++- mingwrt/include/search.h | 5 ++- mingwrt/mingwex/insque.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++ mingwrt/mingwex/remque.c | 77 +++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 176 insertions(+), 4 deletions(-) create mode 100644 mingwrt/mingwex/insque.c create mode 100644 mingwrt/mingwex/remque.c diff --git a/mingwrt/ChangeLog b/mingwrt/ChangeLog index 481e07f..ef1bbcf 100644 --- a/mingwrt/ChangeLog +++ b/mingwrt/ChangeLog @@ -1,3 +1,15 @@ +2018-12-04 Keith Marshall + + Implement POSIX.1-1996 linked-list queue management API. + + * mingwex/insque.c mingwex/remque.c: New files; they implement the + POSIX.1-1996 insque(), and remque() functions, respectively. + + * include/search.h (insque, remque): Declare function prototypes. + + * Makefile.in (libmingwex.a): Add dependencies on... + (insque.$OBJEXT, remque.$OBJEXT): ...these. + 2018-11-25 Keith Marshall Emulate _fseeki64()/_ftelli64() API on legacy platforms. diff --git a/mingwrt/Makefile.in b/mingwrt/Makefile.in index c752b6a..5c308bd 100644 --- a/mingwrt/Makefile.in +++ b/mingwrt/Makefile.in @@ -449,10 +449,9 @@ $(addsuffix fmt.$(OBJEXT),varo crto geto seto crtn getn setn): %.$(OBJEXT): ofmt libmingwex.a: $(addsuffix .$(OBJEXT), mingw-aligned-malloc mingw-fseek) libmingwex.a: $(addsuffix .$(OBJEXT), glob getopt basename dirname nsleep) libmingwex.a: $(addsuffix .$(OBJEXT), clockapi clockres clockset clocktime) -libmingwex.a: $(addsuffix .$(OBJEXT), mkstemp mkdtemp cryptnam setenv) - -libmingwex.a: $(addsuffix .$(OBJEXT), tdelete tfind tsearch twalk) +libmingwex.a: $(addsuffix .$(OBJEXT), insque remque tdelete tfind tsearch twalk) libmingwex.a: $(addsuffix .$(OBJEXT), dirent wdirent dlfcn strerror_r strtok_r) +libmingwex.a: $(addsuffix .$(OBJEXT), mkstemp mkdtemp cryptnam setenv) libmingwex.a: $(addsuffix .$(OBJEXT), getdelim gettimeofday) vpath %.s ${mingwrt_srcdir}/mingwex diff --git a/mingwrt/include/search.h b/mingwrt/include/search.h index ce93ca7..75feb19 100644 --- a/mingwrt/include/search.h +++ b/mingwrt/include/search.h @@ -6,7 +6,7 @@ * $Id$ * * Written by Danny Smith - * Copyright (C) 2003, 2004, 2007, 2016, MinGW.org Project. + * Copyright (C) 2003, 2004, 2007, 2016, 2018, MinGW.org Project. * * * Permission is hereby granted, free of charge, to any person obtaining a @@ -126,6 +126,9 @@ __MINGW_ATTRIB_NONNULL(2) __MINGW_ATTRIB_NONNULL(3); __cdecl void twalk (const void *, void (*)(const void *, VISIT, int)) __MINGW_ATTRIB_NONNULL(1) __MINGW_ATTRIB_NONNULL(2); +__cdecl void insque (void *, void *); +__cdecl void remque (void *); + #endif /* _POSIX_C_SOURCE */ #if !defined _NO_OLDNAMES || defined _POSIX_C_SOURCE diff --git a/mingwrt/mingwex/insque.c b/mingwrt/mingwex/insque.c new file mode 100644 index 0000000..57af74e --- /dev/null +++ b/mingwrt/mingwex/insque.c @@ -0,0 +1,81 @@ +/* + * insque.c + * + * POSIX.1-1996 compatible doubly-linked list management API; provides the + * insque() function, for element insertion at an arbitrary position within + * a linear, or circular, doubly-linked list. + * + * + * $Id$ + * + * Written by Keith Marshall + * Copyright (C) 2018, MinGW.org Project. + * + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice, this permission notice, and the following + * disclaimer shall be included in all copies or substantial portions of + * the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OF OR OTHER + * DEALINGS IN THE SOFTWARE. + * + */ +#include +#include + +/* This private structure definition specifies the minimal layout of a + * doubly-linked list element; client code will typically append extra + * data fields, but the first two fields must be pointers to identical + * structures. + */ +struct qnode { struct qnode *fwdlink, *bkwdlink; }; + +/* Providing the actual implementation as an inline function, with its + * arguments specified as pointers to structures of the preceding type, + * offers a conventient mechanism for mapping the generic pointers of + * the public API to the minimal required form. + */ +__CRT_ALIAS void do_insque( struct qnode *element, struct qnode *pred ) +{ + /* Insert "element" into the list containing "pred", with insertion + * point immediately following "pred"; becomes a no-op, if "element" + * is specified as NULL... + */ + if( element != NULL ) + { + /* ...otherwise, sets the forward link of "element" to the current + * forward link of "pred", (or to NULL, if "pred" is NULL), and the + * backward link of the successor to "pred", if any, to point back + * to "element"... + */ + if( (element->fwdlink = (pred != NULL) ? pred->fwdlink : NULL) != NULL ) + element->fwdlink->bkwdlink = element; + + /* ...and completes the linking, by setting the backward link of + * "element" to point to "pred", and the forward link of "pred", + * (if "pred" isn't NULL), to point to "element". + */ + if( (element->bkwdlink = pred) != NULL ) + pred->fwdlink = element; + } +} + +/* The public API simply expands the inline implementation, mapping + * the generic pointer arguments to the minimally specified structure. + */ +void insque( void *element, void *pred ) +{ do_insque( (struct qnode *)(element), (struct qnode *)(pred) ); } + +/* $RCSfile$: end of file */ diff --git a/mingwrt/mingwex/remque.c b/mingwrt/mingwex/remque.c new file mode 100644 index 0000000..80de2cd --- /dev/null +++ b/mingwrt/mingwex/remque.c @@ -0,0 +1,77 @@ +/* + * remque.c + * + * POSIX.1-1996 compatible doubly-linked list management API; provides the + * remque() function, for removal of an element from an arbitrary position + * within a linear, or circular, doubly-linked list. + * + * + * $Id$ + * + * Written by Keith Marshall + * Copyright (C) 2018, MinGW.org Project. + * + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice, this permission notice, and the following + * disclaimer shall be included in all copies or substantial portions of + * the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OF OR OTHER + * DEALINGS IN THE SOFTWARE. + * + */ +#include +#include + +/* This private structure definition specifies the minimal layout of a + * doubly-linked list element; client code will typically append extra + * data fields, but the first two fields must be pointers to identical + * structures. + */ +struct qnode { struct qnode *fwdlink, *bkwdlink; }; + +/* Providing the actual implementation as an inline function, with its + * argument specified as a pointer to a structure of the preceding type, + * offers a conventient mechanism for mapping the generic pointer of the + * public API to the minimal required form. + */ +__CRT_ALIAS void do_remque( struct qnode *element ) +{ + /* Remove "element" from the list which contains it; becomes a + * no-op, if "element" is NULL... + */ + if( element != NULL ) + { + /* ...otherwise, updates the backward link in the successor of + * "element", if any, to point to the predecessor of "element"... + */ + if( element->fwdlink != NULL ) + element->fwdlink->bkwdlink = element->bkwdlink; + + /* ...and the forward link in the predecessor of "element", if + * any, to point to the successor of "element". + */ + if( element->bkwdlink != NULL ) + element->bkwdlink->fwdlink = element->fwdlink; + } +} + +/* The public API simply expands the inline implementation, mapping + * the generic pointer argument to the minimally specified structure. + */ +void remque( void *element ) +{ do_remque( (struct qnode *)(element) ); } + +/* $RCSfile$: end of file */ -- 2.11.0