From ea03112dbfc5c3e2bd1036cae5b8a2bbd59bcefc Mon Sep 17 00:00:00 2001 From: robert Date: Wed, 16 Oct 2002 14:00:46 +0000 Subject: - Remove the old insque() and remque() functions and their manual page from the compatibility library. - Add new implementations of insque() and remque() which conform to IEEE Std 1003.1-2001 to libc. Add a new manual page for them and connect them to the build. - Add the prototypes of insque() and remque() to the search.h header. --- include/search.h | 10 +++-- lib/libc/stdlib/Makefile.inc | 11 +++--- lib/libc/stdlib/insque.3 | 59 +++++++++++++++++++++++++++++ lib/libc/stdlib/insque.c | 48 ++++++++++++++++++++++++ lib/libc/stdlib/remque.c | 31 +++++++++++++++ lib/libcompat/4.3/insque.3 | 89 -------------------------------------------- lib/libcompat/4.3/insque.c | 59 ----------------------------- lib/libcompat/4.3/remque.c | 57 ---------------------------- lib/libcompat/Makefile | 4 +- 9 files changed, 152 insertions(+), 216 deletions(-) create mode 100644 lib/libc/stdlib/insque.3 create mode 100644 lib/libc/stdlib/insque.c create mode 100644 lib/libc/stdlib/remque.c delete mode 100644 lib/libcompat/4.3/insque.3 delete mode 100644 lib/libcompat/4.3/insque.c delete mode 100644 lib/libcompat/4.3/remque.c diff --git a/include/search.h b/include/search.h index a62f772..566aac8 100644 --- a/include/search.h +++ b/include/search.h @@ -38,21 +38,25 @@ typedef struct node { char *key; struct node *llink, *rlink; } node_t; + +struct que_elem { + struct que_elem *next; + struct que_elem *prev; +}; #endif __BEGIN_DECLS int hcreate(size_t); void hdestroy(void); ENTRY *hsearch(ENTRY, ACTION); +void insque(void *, void *); +void remque(void *); void *tdelete(const void * __restrict, void ** __restrict, int (*)(const void *, const void *)); void *tfind(const void *, void * const *, int (*)(const void *, const void *)); void *tsearch(const void *, void **, int (*)(const void *, const void *)); void twalk(const void *, void (*)(const void *, VISIT, int)); -/* - * XXX missing insque(), lsearch(), remque(). - */ __END_DECLS #endif /* !_SEARCH_H_ */ diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc index a65ef1e..b04c2da 100644 --- a/lib/libc/stdlib/Makefile.inc +++ b/lib/libc/stdlib/Makefile.inc @@ -6,12 +6,12 @@ MISRCS+=_Exit.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \ bsearch.c calloc.c div.c exit.c getenv.c getopt.c getopt_long.c \ - getsubopt.c hcreate.c heapsort.c imaxabs.c imaxdiv.c \ + getsubopt.c hcreate.c heapsort.c imaxabs.c imaxdiv.c insque.c \ labs.c ldiv.c llabs.c lldiv.c malloc.c merge.c putenv.c \ qsort.c qsort_r.c radixsort.c rand.c random.c reallocf.c realpath.c \ - setenv.c strfmon.c strhash.c strtod.c strtoimax.c strtol.c strtoll.c \ - strtoq.c strtoul.c strtoull.c strtoumax.c strtouq.c system.c \ - tdelete.c tfind.c tsearch.c twalk.c + remque.c setenv.c strfmon.c strhash.c strtod.c strtoimax.c strtol.c \ + strtoll.c strtoq.c strtoul.c strtoull.c strtoumax.c strtouq.c \ + system.c tdelete.c tfind.c tsearch.c twalk.c # machine-dependent stdlib sources .if exists(${.CURDIR}/../libc/${MACHINE_ARCH}/stdlib/Makefile.inc) @@ -21,7 +21,7 @@ MISRCS+=_Exit.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \ .if ${LIB} == "c" MAN+= abort.3 abs.3 alloca.3 atexit.3 atof.3 atoi.3 atol.3 bsearch.3 \ div.3 exit.3 getenv.3 getopt.3 getopt_long.3 getsubopt.3 hcreate.3 \ - imaxabs.3 imaxdiv.3 labs.3 ldiv.3 llabs.3 lldiv.3 \ + imaxabs.3 imaxdiv.3 insque.3 labs.3 ldiv.3 llabs.3 lldiv.3 \ malloc.3 memory.3 qsort.3 radixsort.3 rand.3 random.3 \ realpath.3 strfmon.3 strtod.3 strtol.3 strtoul.3 system.3 tsearch.3 @@ -29,6 +29,7 @@ MLINKS+=atol.3 atoll.3 MLINKS+=exit.3 _Exit.3 MLINKS+=getenv.3 putenv.3 getenv.3 setenv.3 getenv.3 unsetenv.3 MLINKS+=hcreate.3 hdestroy.3 hcreate.3 hsearch.3 +MLINKS+=insque.3 remque.3 MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 qsort.3 qsort_r.3 MLINKS+=rand.3 rand_r.3 rand.3 srand.3 rand.3 sranddev.3 MLINKS+=random.3 initstate.3 random.3 setstate.3 random.3 srandom.3 \ diff --git a/lib/libc/stdlib/insque.3 b/lib/libc/stdlib/insque.3 new file mode 100644 index 0000000..7df48f0 --- /dev/null +++ b/lib/libc/stdlib/insque.3 @@ -0,0 +1,59 @@ +.\" +.\" Initial implementation: +.\" Copyright (c) 2002 Robert Drehmel +.\" All rights reserved. +.\" +.\" As long as the above copyright statement and this notice remain +.\" unchanged, you can do what ever you want with this file. +.\" +.\" $FreeBSD$ +.\" +.Dd October 10, 2002 +.Dt INSQUE 3 +.Os +.Sh NAME +.Nm insque , +.Nm remque +.Nd doubly-linked list management +.Sh LIBRARY +.Lb libc +.Sh SYNOPSIS +.In search.h +.Ft void +.Fn insque "void *element1" "void *pred" +.Ft void +.Fn remque "void *element" +.Sh DESCRIPTION +.Pp +The +.Fn insque +and +.Fn remque +functions encapsulate the ever-repeating task of doing insertion and +removal operations on doubly linked lists. The functions expect their +arguments to point to a structure whose first and second members are +pointers to the next and previous element, respectively. +The +.Fn insque +functions also allows the +.Fa pred +argument to be a NULL pointer for the initialization of a new list's +head element. +.Sh HISTORY +The +.Fn insque +and +.Fn remque +functions appeared in +.Bx 4.2 . +In +.Fx 5.0 , +they reappeared conforming to +.St -p1003.1-2001 . +.Sh STANDARDS +The +.Fn insque +and +.Fn remque +functions conform to +.St -p1003.1-2001 . diff --git a/lib/libc/stdlib/insque.c b/lib/libc/stdlib/insque.c new file mode 100644 index 0000000..08d179a --- /dev/null +++ b/lib/libc/stdlib/insque.c @@ -0,0 +1,48 @@ +/* + * Initial implementation: + * Copyright (c) 2002 Robert Drehmel + * All rights reserved. + * + * As long as the above copyright statement and this notice remain + * unchanged, you can do what ever you want with this file. + * + * $FreeBSD$ + */ +#include +__FBSDID("$FreeBSD$"); + +#define _SEARCH_PRIVATE +#include +#ifdef DEBUG +#include +#else +#include /* for NULL */ +#endif + +void insque(void *element, void *pred) +{ + struct que_elem *prev, *next, *elem; + + elem = (struct que_elem *)element; + prev = (struct que_elem *)pred; + + if (prev == NULL) { + elem->prev = elem->next = NULL; + return; + } + + next = prev->next; + if (next != NULL) { +#ifdef DEBUG + if (next->prev != prev) { + fprintf(stderr, "insque: Inconsistency detected:" + " next(%p)->prev(%p) != prev(%p)\n", + next, next->prev, prev); + } +#endif + next->prev = elem; + } + prev->next = elem; + elem->prev = prev; + elem->next = next; +} diff --git a/lib/libc/stdlib/remque.c b/lib/libc/stdlib/remque.c new file mode 100644 index 0000000..2341188 --- /dev/null +++ b/lib/libc/stdlib/remque.c @@ -0,0 +1,31 @@ +/* + * Initial implementation: + * Copyright (c) 2002 Robert Drehmel + * All rights reserved. + * + * As long as the above copyright statement and this notice remain + * unchanged, you can do what ever you want with this file. + * + * $FreeBSD$ + */ +#include +__FBSDID("$FreeBSD$"); + +#define _SEARCH_PRIVATE +#include +#include /* for NULL */ + +void remque(void *element) +{ + struct que_elem *prev, *next, *elem; + + elem = (struct que_elem *)element; + + prev = elem->prev; + next = elem->next; + + if (prev != NULL) + prev->next = next; + if (next != NULL) + next->prev = prev; +} diff --git a/lib/libcompat/4.3/insque.3 b/lib/libcompat/4.3/insque.3 deleted file mode 100644 index 2744dae..0000000 --- a/lib/libcompat/4.3/insque.3 +++ /dev/null @@ -1,89 +0,0 @@ -.\" Copyright (c) 1983, 1991, 1993 -.\" The Regents of the University of California. All rights reserved. -.\" -.\" 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. -.\" 3. All advertising materials mentioning features or use of this software -.\" must display the following acknowledgement: -.\" This product includes software developed by the University of -.\" California, Berkeley and its contributors. -.\" 4. Neither the name of the University nor the names of its contributors -.\" may be used to endorse or promote products derived from this software -.\" without specific prior written permission. -.\" -.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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. -.\" -.\" @(#)insque.3 8.2 (Berkeley) 12/11/93 -.\" $FreeBSD$ -.\" -.Dd December 11, 1993 -.Dt INSQUE 3 -.Os -.Sh NAME -.Nm insque , -.Nm remque -.Nd insert/remove element from a queue -.Sh LIBRARY -.Lb libcompat -.Sh SYNOPSIS -.Bd -literal -struct qelem { - struct qelem *q_forw; - struct qelem *q_back; - char q_data[]; -}; -.Ed -.Pp -.Ft void -.Fn insque "struct qelem *elem" "struct qelem *pred" -.Ft void -.Fn remque "struct qelem *elem" -.Sh DESCRIPTION -.Bf -symbolic -The insque and remque functions are considered obsolete. -.Ef -.Pp -The -.Fn insque -and -.Fn remque -functions -manipulate queues built from doubly linked lists. Each -element in the queue must be in the form of -.Dq Li struct qelem . -The function -.Fn insque -inserts -.Fa elem -in a queue immediately after -.Fa pred ; -.Fn remque -removes an entry -.Fa elem -from a queue. -.Sh SEE ALSO -.%T "VAX Architecture Handbook" , -pp. 228-235. -.Sh HISTORY -The -.Fn insque -and -.Fn remque -functions appeared in -.Bx 4.2 . diff --git a/lib/libcompat/4.3/insque.c b/lib/libcompat/4.3/insque.c deleted file mode 100644 index d290860..0000000 --- a/lib/libcompat/4.3/insque.c +++ /dev/null @@ -1,59 +0,0 @@ -/* - * Copyright (c) 1987, 1993 - * The Regents of the University of California. All rights reserved. - * - * 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. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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 defined(LIBC_SCCS) && !defined(lint) -static char sccsid[] = "@(#)insque.c 8.1 (Berkeley) 6/4/93"; -#endif /* LIBC_SCCS and not lint */ -#include -__FBSDID("$FreeBSD$"); - -/* - * insque -- vax insque instruction - * - * NOTE: this implementation is non-atomic!! - */ - -struct vaxque { /* queue format expected by VAX queue instructions */ - struct vaxque *vq_next; - struct vaxque *vq_prev; -}; - -void -insque(e, prev) - struct vaxque *e, *prev; -{ - e->vq_prev = prev; - e->vq_next = prev->vq_next; - prev->vq_next->vq_prev = e; - prev->vq_next = e; -} diff --git a/lib/libcompat/4.3/remque.c b/lib/libcompat/4.3/remque.c deleted file mode 100644 index b57046c..0000000 --- a/lib/libcompat/4.3/remque.c +++ /dev/null @@ -1,57 +0,0 @@ -/* - * Copyright (c) 1987, 1993 - * The Regents of the University of California. All rights reserved. - * - * 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. - * 3. All advertising materials mentioning features or use of this software - * must display the following acknowledgement: - * This product includes software developed by the University of - * California, Berkeley and its contributors. - * 4. Neither the name of the University nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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 defined(LIBC_SCCS) && !defined(lint) -static char sccsid[] = "@(#)remque.c 8.1 (Berkeley) 6/4/93"; -#endif /* LIBC_SCCS and not lint */ -#include -__FBSDID("$FreeBSD$"); - -/* - * remque -- vax remque instruction - * - * NOTE: this implementation is non-atomic!! - */ - -struct vaxque { /* queue format expected by VAX queue instructions */ - struct vaxque *vq_next; - struct vaxque *vq_prev; -}; - -void -remque(e) - struct vaxque *e; -{ - e->vq_prev->vq_next = e->vq_next; - e->vq_next->vq_prev = e->vq_prev; -} diff --git a/lib/libcompat/Makefile b/lib/libcompat/Makefile index 668f7b6..bd1dd9e 100644 --- a/lib/libcompat/Makefile +++ b/lib/libcompat/Makefile @@ -24,14 +24,12 @@ MLINKS+=cftime.3 ascftime.3 # compat 4.3 sources # XXX MISSING: ecvt.c gcvt.c sibuf.c sobuf.c strout.c SRCS+= cfree.c lsearch.c regex.c rexec.c -SRCS+= insque.c remque.c # XXX MISSING: ecvt.0 -MAN+= 4.3/cfree.3 4.3/insque.3 4.3/lsearch.3 4.3/re_comp.3 4.3/rexec.3 +MAN+= 4.3/cfree.3 4.3/lsearch.3 4.3/re_comp.3 4.3/rexec.3 # XXX MISSING: ecvt.3, so can't MLINK #MLINKS+=ecvt.3 fcvt.3 ecvt.3 gcvt.3 -MLINKS+=insque.3 remque.3 MLINKS+=re_comp.3 re_exec.3 MLINKS+=lsearch.3 lfind.3 -- cgit v1.1