X-Authentication-Warning: delorie.com: mail set sender to djgpp-workers-bounces using -f
From: <ams AT ludd DOT ltu DOT se>
Message-Id: <200501031721.j03HLTPV012989@speedy.ludd.ltu.se>
Subject: lsearch() and lfind() patch
To: DJGPP-WORKERS <djgpp-workers AT delorie DOT com>
Date: Mon, 3 Jan 2005 18:21:29 +0100 (CET)
X-Mailer: ELM [version 2.4ME+ PL78 (25)]
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset=US-ASCII
X-ltu-MailScanner-Information: Please contact the ISP for more information
X-ltu-MailScanner: Found to be clean
X-ltu-MailScanner-SpamScore: ssss
X-MailScanner-From: ams AT ludd DOT ltu DOT se
Reply-To: djgpp-workers AT delorie DOT com

Hello.

Here's my patch to add lfind() and lsearch().

Personally, I think these functions are almost useless. It's easier to
code your own functions and they were hard to use correctly (my test
program had several bugs before I got it to work).


Right,

						MartinS

Index: djgpp/include/search.h
===================================================================
RCS file: /cvs/djgpp/djgpp/include/search.h,v
retrieving revision 1.4
diff -p -u -r1.4 search.h
--- djgpp/include/search.h	4 Feb 2003 20:24:05 -0000	1.4
+++ djgpp/include/search.h	3 Jan 2005 17:18:28 -0000
@@ -10,6 +10,13 @@ extern "C" {
 
 #ifndef __dj_ENFORCE_ANSI_FREESTANDING
 
+#include <sys/djtypes.h>
+
+#ifndef _SIZE_T
+__DJ_size_t
+#define _SIZE_T
+#endif
+
 #if (defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L) \
   || !defined(__STRICT_ANSI__)
 
@@ -17,6 +24,11 @@ extern "C" {
 
 #ifndef __STRICT_ANSI__
 
+void * lfind(const void *_key, void *_base, size_t *_nelp, size_t _width,
+	     int(*_compar)(const void *, const void *));
+void * lsearch(const void *_key, void *_base, size_t *_nelp, size_t _width,
+	       int(*_compar)(const void *, const void *));
+
 #ifndef _POSIX_SOURCE
 
 typedef struct qelem {
Index: djgpp/src/libc/posix/search/lfind.c
===================================================================
RCS file: djgpp/src/libc/posix/search/lfind.c
diff -N djgpp/src/libc/posix/search/lfind.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ djgpp/src/libc/posix/search/lfind.c	3 Jan 2005 17:18:36 -0000
@@ -0,0 +1,57 @@
+/*
+ * File lfind.c.
+ *
+ * Copyright (C) 2005 Martin Str@"omberg <ams AT ludd DOT ltu DOT se>.
+ *
+ * This software may be used freely so long as this copyright notice is
+ * left intact. There is no warranty on this software.
+ *
+ */
+
+#include <search.h>
+#include <stdlib.h>
+
+/* Local helper function that does the real work. */
+static void *
+l_general(const void *key, void *base, size_t *nelp, size_t width, 
+	  int(*compar)(const void *, const void *), int add)
+{
+  size_t i = 0;
+
+  while( i < *nelp && (*compar)(base, key) )
+  {
+    base = ((unsigned char *)base) + width;
+    i++;
+  }
+
+  if( i < *nelp )
+  {
+    return base;
+  }
+
+  if( add )
+  {
+    memcpy(base, key, width);
+    (*nelp)++;
+    return base;
+  }
+
+  return NULL;
+}
+
+
+void *
+lfind(const void *key, void *base, size_t *nelp, size_t width, 
+      int(*compar)(const void *, const void *))
+{
+  return l_general(key, base, nelp, width, compar, 0);
+}
+
+
+void *
+lsearch(const void *key, void *base, size_t *nelp, size_t width, 
+	int(*compar)(const void *, const void *))
+{
+  return l_general(key, base, nelp, width, compar, 1);
+}
+
Index: djgpp/src/libc/posix/search/lfind.txh
===================================================================
RCS file: djgpp/src/libc/posix/search/lfind.txh
diff -N djgpp/src/libc/posix/search/lfind.txh
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ djgpp/src/libc/posix/search/lfind.txh	3 Jan 2005 17:18:36 -0000
@@ -0,0 +1,133 @@
+@ignore
+ * File lfind.txh.
+ *
+ * Copyright (C) 2005 Martin Str@"omberg <ams AT ludd DOT luth DOT se>.
+ *
+ * This software may be used freely so long as this copyright notice is
+ * left intact. There is no warranty on this software.
+ *
+@end ignore
+
+@node lfind, misc
+@findex lfind
+@subheading Syntax
+
+@example
+#include <search.h>
+
+void * lfind(const void *key, void *base, size_t *nelp, size_t width, 
+             int (*compar)(const void *, const void *));  
+@end example
+
+@subheading Description
+
+This function searches the array @var{base} of elements of size
+@var{width}, currently containing @var{nelp} elements, for the element
+identified by @var{key} using the comparision function @var{compar}.  
+
+@subheading Return Value
+
+A pointer to the found element or @code{NULL} if not present.  
+
+@subheading Portability
+
+@portability !ansi, posix
+
+@subheading Example
+
+@example
+#include <search.h>
+#include <stdio.h>
+#include <string.h>
+
+#define N_ELEM       50
+#define ELEM_SIZE    50
+#define COMPARE_FUN  (int (*)(const void *, const void *)) strcmp
+
+char arr[N_ELEM][ELEM_SIZE];
+size_t n_arr = 0;
+
+int main(void)
+@{
+  char *entry;
+  size_t i;
+
+  entry = lfind("Anyone there?", arr, &n_arr, ELEM_SIZE, COMPARE_FUN);
+  if( entry )
+  @{
+    printf("Someone there: %s!\n", entry);
+  @}
+  else
+  @{
+    printf("Noone there...\n");
+  @}
+
+  return 0;
+@}
+
+@end example
+
+
+@node lsearch, misc
+@findex lsearch
+@subheading Syntax
+
+@example
+#include <search.h>
+
+void * lsearch(const void *key, void *base, size_t *nelp, size_t width, 
+               int (*compar)(const void *, const void *));
+@end example
+
+@subheading Description
+
+This function searches the array @var{base} of elements of size
+@var{width}, currently containing @var{nelp} elements, for the element
+identified by @var{key} using the comparision function @var{compar}.  
+
+If the @var{key} isn't found it is added to the array @var{base} and
+@var{*nelp} is incremented.  
+
+It is the caller's responsibility that the array has enough room for
+an additional element.  
+
+@subheading Return Value
+
+A pointer to the found or inserted element.  
+
+@subheading Portability
+
+@portability !ansi, posix
+
+@subheading Example
+
+@example
+#include <search.h>
+#include <stdio.h>
+#include <string.h>
+
+#define N_ELEM       50
+#define ELEM_SIZE    50
+#define COMPARE_FUN  (int (*)(const void *, const void *)) strcmp
+
+char arr[N_ELEM][ELEM_SIZE];
+size_t n_arr = 0;
+
+int main(void)
+@{
+  char *entry;
+
+  entry = lsearch("Anyone there?", arr, &n_arr, ELEM_SIZE, COMPARE_FUN);
+  if( entry )
+  @{
+    printf("Someone there: %s, %ld\n", entry, n_arr);
+  @}
+  else
+  @{
+    printf("Error, noone there: %ld...\n", n_arr);
+  @}
+
+  return 0;
+@}
+
+@end example
Index: djgpp/src/libc/posix/search/makefile
===================================================================
RCS file: djgpp/src/libc/posix/search/makefile
diff -N djgpp/src/libc/posix/search/makefile
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ djgpp/src/libc/posix/search/makefile	3 Jan 2005 17:18:36 -0000
@@ -0,0 +1,7 @@
+# Copyright (C) 2005 DJ Delorie, see COPYING.DJ for details
+
+TOP=../..
+
+SRC += lfind.c
+
+include $(TOP)/../makefile.inc
Index: djgpp/tests/libc/posix/search/lfind.c
===================================================================
RCS file: djgpp/tests/libc/posix/search/lfind.c
diff -N djgpp/tests/libc/posix/search/lfind.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ djgpp/tests/libc/posix/search/lfind.c	3 Jan 2005 17:18:37 -0000
@@ -0,0 +1,121 @@
+/*
+ * File lfind.c.
+ *
+ * Copyright (C) 2005 Martin Str@"omberg <ams AT ludd DOT ltu DOT se>.
+ *
+ * This software may be used freely so long as this copyright notice is
+ * left intact. There is no warranty on this software.
+ *
+ */
+
+#include <search.h>
+#include <stdio.h>
+#include <string.h>
+
+#define N_ELEM       50
+#define ELEM_SIZE    50
+#define COMPARE_FUN  (int (*)(const void *, const void *)) strcmp
+
+char arr[N_ELEM][ELEM_SIZE];
+size_t n_arr = 0;
+
+int main(void)
+{
+  char *entry;
+  size_t i;
+
+  /* Add entries. */
+  entry = lsearch("Adam", arr, &n_arr, ELEM_SIZE, COMPARE_FUN);
+  if( !entry || n_arr != 1 )
+  {
+    printf("Error: failed to insert 'Adam': entry = %p, n_arr = %ld.\n", 
+	   entry, n_arr);
+    exit(1);
+  }
+  entry = lsearch("Bravo", arr, &n_arr, ELEM_SIZE, COMPARE_FUN);
+  if( !entry || n_arr != 2 )
+  {
+    printf("Error: failed to insert 'Bravo': entry = %p, n_arr = %ld.\n", 
+	   entry, n_arr);
+    exit(1);
+  }
+  entry = lsearch("Caesar", arr, &n_arr, ELEM_SIZE, COMPARE_FUN);
+  if( !entry || n_arr != 3 )
+  {
+    printf("Error: failed to insert 'Caesar': entry = %p, n_arr = %ld.\n", 
+	   entry, n_arr);
+    exit(1);
+  }
+
+  /* Print out table. */
+  printf("Array now contains:\n");
+  for( i = 0; i < n_arr; i++ )
+  {
+    printf("\tIndex %ld: '%s'\n", i, arr[i]);
+  }
+
+  /* Search for the added entries. */
+  entry = lfind("Bravo", arr, &n_arr, ELEM_SIZE, COMPARE_FUN);
+  if( n_arr != 3 )
+  {
+    printf("Error: n_arr = %ld, expected 3.\n", n_arr);
+    exit(1);
+  }
+  if( !entry || strcmp("Bravo", entry) )
+  {
+    printf("Error: failed to find 'Bravo': entry = %p->'%s', n_arr = %ld.\n", 
+	   entry, entry?entry:"NULL pointer!", n_arr);
+    exit(1);
+  }
+  entry = lfind("Caesar", arr, &n_arr, ELEM_SIZE, COMPARE_FUN);
+  if( n_arr != 3 )
+  {
+    printf("Error: n_arr = %ld, expected 3.\n", n_arr);
+    exit(1);
+  }
+  if( !entry || strcmp("Caesar", entry) )
+  {
+    printf("Error: failed to find 'Caeasar': entry = %p->'%s', n_arr = %ld.\n", 
+	   entry, entry?entry:"NULL pointer!", n_arr);
+    exit(1);
+  }
+  entry = lfind("Adam", arr, &n_arr, ELEM_SIZE, COMPARE_FUN);
+  if( n_arr != 3 )
+  {
+    printf("Error: n_arr = %ld, expected 3.\n", n_arr);
+    exit(1);
+  }
+  if( !entry || strcmp("Adam", entry) )
+  {
+    printf("Error: failed to find 'Adam': entry = %p->'%s', n_arr = %ld.\n", 
+	   entry, entry?entry:"NULL pointer!", n_arr);
+    exit(1);
+  }
+
+  /* Search for something not there. */
+  entry = lfind("Zebra", arr, &n_arr, ELEM_SIZE, COMPARE_FUN);
+  if( n_arr != 3 )
+  {
+    printf("Error: n_arr = %ld, expected 3.\n", n_arr);
+    exit(1);
+  }
+  if( entry )
+  {
+    printf("Error: found 'Zebra': entry = %p->'%s', n_arr = %ld.\n", 
+	   entry, entry, n_arr);
+    exit(1);
+  }
+
+  /* Try to add one already present. */
+  entry = lsearch("Bravo", arr, &n_arr, ELEM_SIZE, COMPARE_FUN);
+  if( !entry || n_arr != 3 )
+  {
+    printf("Error: failed to NOT insert 'Bravo': entry = %p, n_arr = %ld.\n", 
+	   entry, n_arr);
+    exit(1);
+  }
+
+
+  printf("All tests successful.\n");
+  exit(0);
+}
Index: djgpp/tests/libc/posix/search/makefile
===================================================================
RCS file: djgpp/tests/libc/posix/search/makefile
diff -N djgpp/tests/libc/posix/search/makefile
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ djgpp/tests/libc/posix/search/makefile	3 Jan 2005 17:18:37 -0000
@@ -0,0 +1,5 @@
+TOP=../..
+
+SRC += lfind.c
+
+include $(TOP)/../makefile.inc