From c40c90cf6fcb4df8984812af9eabedbd46be13a7 Mon Sep 17 00:00:00 2001 From: =?utf8?q?R=C3=A9mi=20Duraffort?= Date: Tue, 7 Dec 2010 14:04:47 +0100 Subject: [PATCH] tsearch functions: check for the presence of search.h and replace tdestroy. If search.h is present but not tdestroy: implement it based on others t* functions If search.h and tdestroy are not present: implement every t* functions. --- compat/tdelete.c | 67 --------- compat/tdestroy.c | 336 ++++++++++++++++++++++++++++++++++++++++-- compat/tfind.c | 48 ------ compat/tsearch.c | 57 ------- compat/twalk.c | 57 ------- configure.ac | 2 +- src/Makefile.am | 1 - src/extras/tdestroy.c | 117 --------------- 8 files changed, 323 insertions(+), 362 deletions(-) delete mode 100644 compat/tdelete.c delete mode 100644 compat/tfind.c delete mode 100644 compat/tsearch.c delete mode 100644 compat/twalk.c delete mode 100644 src/extras/tdestroy.c diff --git a/compat/tdelete.c b/compat/tdelete.c deleted file mode 100644 index b1f6dbc3bf..0000000000 --- a/compat/tdelete.c +++ /dev/null @@ -1,67 +0,0 @@ -/* $NetBSD: tdelete.c,v 1.4 2006/03/19 01:12:08 christos Exp $ */ - -/* - * Tree search generalized from Knuth (6.2.2) Algorithm T just like - * the AT&T man page says. - * - * The node_t structure is for internal use only, lint doesn't grok it. - * - * Written by reading the System V Interface Definition, not the code. - * - * Totally public domain. - */ - -#define _SEARCH_PRIVATE - -#ifdef HAVE_CONFIG_H -# include -#endif - -#include -#include - -/* delete node with given key */ -void * -tdelete(vkey, vrootp, compar) - const void *vkey; /* key to be deleted */ - void **vrootp; /* address of the root of tree */ - int (*compar) (const void *, const void *); -{ - node_t **rootp = (node_t **)vrootp; - node_t *p, *q, *r; - int cmp; - - assert(vkey != NULL); - assert(compar != NULL); - - if (rootp == NULL || (p = *rootp) == NULL) - return NULL; - - while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { - p = *rootp; - rootp = (cmp < 0) ? - &(*rootp)->llink : /* follow llink branch */ - &(*rootp)->rlink; /* follow rlink branch */ - if (*rootp == NULL) - return NULL; /* key not found */ - } - r = (*rootp)->rlink; /* D1: */ - if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ - q = r; - else if (r != NULL) { /* Right link is NULL? */ - if (r->llink == NULL) { /* D2: Find successor */ - r->llink = q; - q = r; - } else { /* D3: Find NULL link */ - for (q = r->llink; q->llink != NULL; q = r->llink) - r = q; - r->llink = q->rlink; - q->llink = (*rootp)->llink; - q->rlink = (*rootp)->rlink; - } - } - if (p != *rootp) - free(*rootp); /* D4: Free node */ - *rootp = q; /* link parent to new node */ - return p; -} diff --git a/compat/tdestroy.c b/compat/tdestroy.c index f943c573d6..7f8b2c7363 100644 --- a/compat/tdestroy.c +++ b/compat/tdestroy.c @@ -1,4 +1,126 @@ -/* $NetBSD: tdestroy.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ +/***************************************************************************** + * tdestroy.c : either implement tdestroy based on existing t* functions + * or implement every t* fuctions (including tdestroy) + *****************************************************************************/ + +#ifdef HAVE_CONFIG_H +# include +#endif + +/** search.h is present so only tdestroy has to be implemented based on the + existing functions */ +#ifdef HAVE_SEARCH_H + +/***************************************************************************** + * Copyright (C) 2009 Rémi Denis-Courmont + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU Lesser General Public License as published by + * the Free Software Foundation; either version 2.1 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 Lesser General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA. + *****************************************************************************/ + +#include +#include + +#include +#include + +static struct +{ + const void **tab; + size_t count; + vlc_mutex_t lock; +} list = { NULL, 0, VLC_STATIC_MUTEX }; + +static void list_nodes (const void *node, const VISIT which, const int depth) +{ + (void) depth; + + if (which != postorder && which != leaf) + return; + + const void **tab = realloc (list.tab, sizeof (*tab) * (list.count + 1)); + if (unlikely(tab == NULL)) + abort (); + + tab[list.count] = *(const void **)node; + list.tab = tab; + list.count++; +} + +static struct +{ + const void *node; + vlc_mutex_t lock; +} smallest = { NULL, VLC_STATIC_MUTEX }; + +static int cmp_smallest (const void *a, const void *b) +{ + if (a == b) + return 0; + if (a == smallest.node) + return -1; + if (likely(b == smallest.node)) + return +1; + abort (); +} + +void tdestroy (void *root, void (*freenode) (void *)) +{ + const void **tab; + size_t count; + + assert (freenode != NULL); + + /* Enumerate nodes in order */ + vlc_mutex_lock (&list.lock); + assert (list.count == 0); + twalk (root, list_nodes); + tab = list.tab; + count = list.count; + list.tab = NULL; + list.count = 0; + vlc_mutex_unlock (&list.lock); + + /* Destroy the tree */ + vlc_mutex_lock (&smallest.lock); + for (size_t i = 0; i < count; i++) + { + smallest.node = tab[i]; + if (tdelete (smallest.node, &root, cmp_smallest) == NULL) + abort (); + } + vlc_mutex_unlock (&smallest.lock); + assert (root == NULL); + + /* Destroy the nodes */ + for (size_t i = 0; i < count; i++) + freenode ((void *)(tab[i])); + free (tab); +} + +/** search.h is not present, so every t* function has to be implemented */ +#else // HAVE_SEARCH_H + +#include +#include + +typedef struct node { + char *key; + struct node *llink, *rlink; +} node_t; + +/* $NetBSD: tdelete.c,v 1.4 2006/03/19 01:12:08 christos Exp $ */ /* * Tree search generalized from Knuth (6.2.2) Algorithm T just like @@ -11,26 +133,74 @@ * Totally public domain. */ -#define _SEARCH_PRIVATE +/* delete node with given key */ +void * +tdelete(vkey, vrootp, compar) + const void *vkey; /* key to be deleted */ + void **vrootp; /* address of the root of tree */ + int (*compar) (const void *, const void *); +{ + node_t **rootp = (node_t **)vrootp; + node_t *p, *q, *r; + int cmp; -#ifdef HAVE_CONFIG_H -# include -#endif + assert(vkey != NULL); + assert(compar != NULL); -// Do not implement tdestroy if that's the only missing t* function -#ifndef HAVE_SEARCH_H + if (rootp == NULL || (p = *rootp) == NULL) + return NULL; + + while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { + p = *rootp; + rootp = (cmp < 0) ? + &(*rootp)->llink : /* follow llink branch */ + &(*rootp)->rlink; /* follow rlink branch */ + if (*rootp == NULL) + return NULL; /* key not found */ + } + r = (*rootp)->rlink; /* D1: */ + if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ + q = r; + else if (r != NULL) { /* Right link is NULL? */ + if (r->llink == NULL) { /* D2: Find successor */ + r->llink = q; + q = r; + } else { /* D3: Find NULL link */ + for (q = r->llink; q->llink != NULL; q = r->llink) + r = q; + r->llink = q->rlink; + q->llink = (*rootp)->llink; + q->rlink = (*rootp)->rlink; + } + } + if (p != *rootp) + free(*rootp); /* D4: Free node */ + *rootp = q; /* link parent to new node */ + return p; +} -#include -#include + +/* $NetBSD: tdestroy.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ + +/* + * Tree search generalized from Knuth (6.2.2) Algorithm T just like + * the AT&T man page says. + * + * The node_t structure is for internal use only, lint doesn't grok it. + * + * Written by reading the System V Interface Definition, not the code. + * + * Totally public domain. + */ /* Walk the nodes of a tree */ static void -trecurse(node_t* root, void (*free_action)(void *)) +tdestroy_recurse(node_t* root, void (*free_action)(void *)) { if (root->llink != NULL) - trecurse(root->llink, free_action); + tdestroy_recurse(root->llink, free_action); if (root->rlink != NULL) - trecurse(root->rlink, free_action); + tdestroy_recurse(root->rlink, free_action); (*free_action) ((void *) root->key); free(root); @@ -44,7 +214,145 @@ tdestroy(vrootp, freefct) node_t *root = (node_t *) vrootp; if (root != NULL) - trecurse(root, freefct); + tdestroy_recurse(root, freefct); } -#endif + +/* $NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $ */ + +/* + * Tree search generalized from Knuth (6.2.2) Algorithm T just like + * the AT&T man page says. + * + * The node_t structure is for internal use only, lint doesn't grok it. + * + * Written by reading the System V Interface Definition, not the code. + * + * Totally public domain. + */ + +/* find a node, or return 0 */ +void * +tfind(vkey, vrootp, compar) + const void *vkey; /* key to be found */ + const void **vrootp; /* address of the tree root */ + int (*compar) (const void *, const void *); +{ + node_t * const *rootp = (node_t * const*)vrootp; + + assert(vkey != NULL); + assert(compar != NULL); + + if (rootp == NULL) + return NULL; + + while (*rootp != NULL) { /* T1: */ + int r; + + if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ + return *rootp; /* key found */ + rootp = (r < 0) ? + &(*rootp)->llink : /* T3: follow left branch */ + &(*rootp)->rlink; /* T4: follow right branch */ + } + return NULL; +} + + +/* $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $ */ + +/* + * Tree search generalized from Knuth (6.2.2) Algorithm T just like + * the AT&T man page says. + * + * The node_t structure is for internal use only, lint doesn't grok it. + * + * Written by reading the System V Interface Definition, not the code. + * + * Totally public domain. + */ + +/* find or insert datum into search tree */ +void * +tsearch(vkey, vrootp, compar) + const void *vkey; /* key to be located */ + void **vrootp; /* address of tree root */ + int (*compar) (const void *, const void *); +{ + node_t *q; + node_t **rootp = (node_t **)vrootp; + + assert(vkey != NULL); + assert(compar != NULL); + + if (rootp == NULL) + return NULL; + + while (*rootp != NULL) { /* Knuth's T1: */ + int r; + + if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ + return *rootp; /* we found it! */ + + rootp = (r < 0) ? + &(*rootp)->llink : /* T3: follow left branch */ + &(*rootp)->rlink; /* T4: follow right branch */ + } + + q = malloc(sizeof(node_t)); /* T5: key not found */ + if (q != 0) { /* make new node */ + *rootp = q; /* link new node to old */ + q->key = (void*)vkey; /* initialize new node */ + q->llink = q->rlink = NULL; + } + return q; +} + + +/* $NetBSD: twalk.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ + +/* + * Tree search generalized from Knuth (6.2.2) Algorithm T just like + * the AT&T man page says. + * + * The node_t structure is for internal use only, lint doesn't grok it. + * + * Written by reading the System V Interface Definition, not the code. + * + * Totally public domain. + */ + +/* Walk the nodes of a tree */ +static void +twalk_recurse(root, action, level) + const node_t *root; /* Root of the tree to be walked */ + void (*action) (const void *, VISIT, int); + int level; +{ + assert(root != NULL); + assert(action != NULL); + + if (root->llink == NULL && root->rlink == NULL) + (*action)(root, leaf, level); + else { + (*action)(root, preorder, level); + if (root->llink != NULL) + twalk_recurse(root->llink, action, level + 1); + (*action)(root, postorder, level); + if (root->rlink != NULL) + twalk_recurse(root->rlink, action, level + 1); + (*action)(root, endorder, level); + } +} + +/* Walk the nodes of a tree */ +void +twalk(vroot, action) + const void *vroot; /* Root of the tree to be walked */ + void (*action) (const void *, VISIT, int); +{ + if (vroot != NULL && action != NULL) + twalk_recurse(vroot, action, 0); +} + +#endif // HAVE_SEARCH_H diff --git a/compat/tfind.c b/compat/tfind.c deleted file mode 100644 index daf69fa884..0000000000 --- a/compat/tfind.c +++ /dev/null @@ -1,48 +0,0 @@ -/* $NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $ */ - -/* - * Tree search generalized from Knuth (6.2.2) Algorithm T just like - * the AT&T man page says. - * - * The node_t structure is for internal use only, lint doesn't grok it. - * - * Written by reading the System V Interface Definition, not the code. - * - * Totally public domain. - */ - -#define _SEARCH_PRIVATE - -#ifdef HAVE_CONFIG_H -# include -#endif - -#include -#include - -/* find a node, or return 0 */ -void * -tfind(vkey, vrootp, compar) - const void *vkey; /* key to be found */ - const void **vrootp; /* address of the tree root */ - int (*compar) (const void *, const void *); -{ - node_t * const *rootp = (node_t * const*)vrootp; - - assert(vkey != NULL); - assert(compar != NULL); - - if (rootp == NULL) - return NULL; - - while (*rootp != NULL) { /* T1: */ - int r; - - if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ - return *rootp; /* key found */ - rootp = (r < 0) ? - &(*rootp)->llink : /* T3: follow left branch */ - &(*rootp)->rlink; /* T4: follow right branch */ - } - return NULL; -} diff --git a/compat/tsearch.c b/compat/tsearch.c deleted file mode 100644 index 625e9b3c90..0000000000 --- a/compat/tsearch.c +++ /dev/null @@ -1,57 +0,0 @@ -/* $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $ */ - -/* - * Tree search generalized from Knuth (6.2.2) Algorithm T just like - * the AT&T man page says. - * - * The node_t structure is for internal use only, lint doesn't grok it. - * - * Written by reading the System V Interface Definition, not the code. - * - * Totally public domain. - */ - -#define _SEARCH_PRIVATE - -#ifdef HAVE_CONFIG_H -# include -#endif - -#include -#include - -/* find or insert datum into search tree */ -void * -tsearch(vkey, vrootp, compar) - const void *vkey; /* key to be located */ - void **vrootp; /* address of tree root */ - int (*compar) (const void *, const void *); -{ - node_t *q; - node_t **rootp = (node_t **)vrootp; - - assert(vkey != NULL); - assert(compar != NULL); - - if (rootp == NULL) - return NULL; - - while (*rootp != NULL) { /* Knuth's T1: */ - int r; - - if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ - return *rootp; /* we found it! */ - - rootp = (r < 0) ? - &(*rootp)->llink : /* T3: follow left branch */ - &(*rootp)->rlink; /* T4: follow right branch */ - } - - q = malloc(sizeof(node_t)); /* T5: key not found */ - if (q != 0) { /* make new node */ - *rootp = q; /* link new node to old */ - q->key = (void*)vkey; /* initialize new node */ - q->llink = q->rlink = NULL; - } - return q; -} diff --git a/compat/twalk.c b/compat/twalk.c deleted file mode 100644 index 9ee946b1d0..0000000000 --- a/compat/twalk.c +++ /dev/null @@ -1,57 +0,0 @@ -/* $NetBSD: twalk.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ - -/* - * Tree search generalized from Knuth (6.2.2) Algorithm T just like - * the AT&T man page says. - * - * The node_t structure is for internal use only, lint doesn't grok it. - * - * Written by reading the System V Interface Definition, not the code. - * - * Totally public domain. - */ - -#define _SEARCH_PRIVATE - -#ifdef HAVE_CONFIG_H -# include -#endif - -#include -#include - -static void trecurse (const node_t *, - void (*action)(const void *, VISIT, int), int level); - -/* Walk the nodes of a tree */ -static void -trecurse(root, action, level) - const node_t *root; /* Root of the tree to be walked */ - void (*action) (const void *, VISIT, int); - int level; -{ - assert(root != NULL); - assert(action != NULL); - - if (root->llink == NULL && root->rlink == NULL) - (*action)(root, leaf, level); - else { - (*action)(root, preorder, level); - if (root->llink != NULL) - trecurse(root->llink, action, level + 1); - (*action)(root, postorder, level); - if (root->rlink != NULL) - trecurse(root->rlink, action, level + 1); - (*action)(root, endorder, level); - } -} - -/* Walk the nodes of a tree */ -void -twalk(vroot, action) - const void *vroot; /* Root of the tree to be walked */ - void (*action) (const void *, VISIT, int); -{ - if (vroot != NULL && action != NULL) - trecurse(vroot, action, 0); -} diff --git a/configure.ac b/configure.ac index cf50be368a..6333e1eb53 100644 --- a/configure.ac +++ b/configure.ac @@ -547,7 +547,7 @@ need_libc=false dnl Check for usual libc functions AC_CHECK_FUNCS([daemon fcntl fdopendir fstatvfs fork getenv getpwuid_r gettimeofday isatty lstat memalign mmap openat posix_fadvise posix_madvise posix_memalign setenv setlocale stricmp strnicmp uselocale]) -AC_REPLACE_FUNCS([asprintf atof atoll getcwd getdelim getpid gmtime_r lldiv localtime_r nrand48 rewind strcasecmp strcasestr strdup strlcpy strncasecmp strndup strnlen strsep strtof strtok_r strtoll swab tdelete tdestroy tfind tsearch twalk vasprintf]) +AC_REPLACE_FUNCS([asprintf atof atoll getcwd getdelim getpid gmtime_r lldiv localtime_r nrand48 rewind strcasecmp strcasestr strdup strlcpy strncasecmp strndup strnlen strsep strtof strtok_r strtoll swab tdestroy vasprintf]) AC_CHECK_FUNCS(fdatasync,, [AC_DEFINE(fdatasync, fsync, [Alias fdatasync() to fsync() if missing.]) ]) diff --git a/src/Makefile.am b/src/Makefile.am index edc4dbe90c..006f5c8b1c 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -455,7 +455,6 @@ SOURCES_libvlc_common = \ misc/xml.c \ misc/media_library.c \ extras/libc.c \ - extras/tdestroy.c \ misc/filter.c \ misc/filter_chain.c \ misc/http_auth.c \ diff --git a/src/extras/tdestroy.c b/src/extras/tdestroy.c deleted file mode 100644 index aeb43bbafc..0000000000 --- a/src/extras/tdestroy.c +++ /dev/null @@ -1,117 +0,0 @@ -/** - * @file tdestroy.c - * @brief replacement for GNU tdestroy() - */ -/***************************************************************************** - * Copyright (C) 2009 Rémi Denis-Courmont - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU Lesser General Public License as published by - * the Free Software Foundation; either version 2.1 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 Lesser General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA. - *****************************************************************************/ - -#ifdef HAVE_CONFIG_H -# include "config.h" -#endif - -#include -#include - -#include - -#ifdef HAVE_TDESTROY -void vlc_tdestroy (void *root, void (*freenode) (void *)) -{ - (void) root; - assert (freenode != NULL); - abort (); -} - -#else -#include - -static struct -{ - const void **tab; - size_t count; - vlc_mutex_t lock; -} list = { NULL, 0, VLC_STATIC_MUTEX }; - -static void list_nodes (const void *node, const VISIT which, const int depth) -{ - (void) depth; - - if (which != postorder && which != leaf) - return; - - const void **tab = realloc (list.tab, sizeof (*tab) * (list.count + 1)); - if (unlikely(tab == NULL)) - abort (); - - tab[list.count] = *(const void **)node; - list.tab = tab; - list.count++; -} - -static struct -{ - const void *node; - vlc_mutex_t lock; -} smallest = { NULL, VLC_STATIC_MUTEX }; - -static int cmp_smallest (const void *a, const void *b) -{ - if (a == b) - return 0; - if (a == smallest.node) - return -1; - if (likely(b == smallest.node)) - return +1; - abort (); -} - -void vlc_tdestroy (void *root, void (*freenode) (void *)) -{ - const void **tab; - size_t count; - - assert (freenode != NULL); - - /* Enumerate nodes in order */ - vlc_mutex_lock (&list.lock); - assert (list.count == 0); - twalk (root, list_nodes); - tab = list.tab; - count = list.count; - list.tab = NULL; - list.count = 0; - vlc_mutex_unlock (&list.lock); - - /* Destroy the tree */ - vlc_mutex_lock (&smallest.lock); - for (size_t i = 0; i < count; i++) - { - smallest.node = tab[i]; - if (tdelete (smallest.node, &root, cmp_smallest) == NULL) - abort (); - } - vlc_mutex_unlock (&smallest.lock); - assert (root == NULL); - - /* Destroy the nodes */ - for (size_t i = 0; i < count; i++) - freenode ((void *)(tab[i])); - free (tab); -} - -#endif -- 2.39.2