commit: r421 - in vendor/stdutil/current: . src src/stdutil src/stdutil/private
[email protected] Thu, 04 Jun 2009 16:38:26 -0400
| Newsgroups | gmane.network.spread.cvs |
|---|---|
| Message-ID | <[email protected]> |
Author: jonathan Date: 2009-06-04 16:38:26 -0400 (Thu, 04 Jun 2009) New Revision: 421 Added: vendor/stdutil/current/CHANGELOG Modified: vendor/stdutil/current/Makefile vendor/stdutil/current/README vendor/stdutil/current/STDUTIL_LICENSE vendor/stdutil/current/configure vendor/stdutil/current/configure.in vendor/stdutil/current/src/Makefile.in vendor/stdutil/current/src/stdarr.c vendor/stdutil/current/src/stdcarr.c vendor/stdutil/current/src/stddll.c vendor/stdutil/current/src/stderror.c vendor/stdutil/current/src/stdfd.c vendor/stdutil/current/src/stdhash.c vendor/stdutil/current/src/stdit.c vendor/stdutil/current/src/stdskl.c vendor/stdutil/current/src/stdthread.c vendor/stdutil/current/src/stdtime.c vendor/stdutil/current/src/stdutil.c vendor/stdutil/current/src/stdutil/private/stdarch.h vendor/stdutil/current/src/stdutil/private/stdarch_autoconf.h.in vendor/stdutil/current/src/stdutil/private/stdarch_wintel32.h vendor/stdutil/current/src/stdutil/private/stdarr_p.h vendor/stdutil/current/src/stdutil/private/stdcarr_p.h vendor/stdutil/current/src/stdutil/private/stddll_p.h vendor/stdutil/current/src/stdutil/private/stdhash_p.h vendor/stdutil/current/src/stdutil/private/stdit_p.h vendor/stdutil/current/src/stdutil/private/stdskl_p.h vendor/stdutil/current/src/stdutil/private/stdthread_p.h vendor/stdutil/current/src/stdutil/stdarr.h vendor/stdutil/current/src/stdutil/stdcarr.h vendor/stdutil/current/src/stdutil/stddefines.h vendor/stdutil/current/src/stdutil/stddll.h vendor/stdutil/current/src/stdutil/stderror.h vendor/stdutil/current/src/stdutil/stdfd.h vendor/stdutil/current/src/stdutil/stdhash.h vendor/stdutil/current/src/stdutil/stdit.h vendor/stdutil/current/src/stdutil/stdskl.h vendor/stdutil/current/src/stdutil/stdthread.h vendor/stdutil/current/src/stdutil/stdtime.h vendor/stdutil/current/src/stdutil/stdutil.h Log: Update to Stdutil 1.1.0 release Added: vendor/stdutil/current/CHANGELOG =================================================================== --- vendor/stdutil/current/CHANGELOG (rev 0) +++ vendor/stdutil/current/CHANGELOG 2009-06-04 20:38:26 UTC (rev 421) @@ -0,0 +1,14 @@ +v1.1.0, May 2009 + +Changed the build so that the functions in stdthread.h are always defined, but most will simply +return error codes when not built in a reentrant manner. Added a "null mutex" that does nothing +to allow user programs to always successfully call at least the mutex functions even in a +non-reentrant build. + +v1.0.1, November 2007 + +Fixed a few minor bugs. + +v1.0.0, November 2006 + +First major release of StdUtil library. Modified: vendor/stdutil/current/Makefile =================================================================== --- vendor/stdutil/current/Makefile 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/Makefile 2009-06-04 20:38:26 UTC (rev 421) @@ -1,5 +1,5 @@ all: - cd src; $(MAKE) + cd src; $(MAKE) all clean: rm -f *~ core* Modified: vendor/stdutil/current/README =================================================================== --- vendor/stdutil/current/README 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/README 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -This is the v1.0.0 (November 2006) distribution of the StdUtil library. +This is the v1.1.0 (May 2009) distribution of the StdUtil library. DESCRIPTION: @@ -14,13 +14,15 @@ Documentation is currently incomplete but will be available in a subsequent release in HTML format in the docs directory. The -documentation will also be available at +documentation will also be available at: + http://www.cnds.jhu.edu/software/stdutil/docs BUILDING: StdUtil uses the standard configure/make process for building on unix -type systems. +type systems, although it builds in place and does not have a make install +option. PROBLEMS: @@ -30,4 +32,4 @@ Enjoy, John Schultz <[email protected]> -November 2006 +May 2009 Modified: vendor/stdutil/current/STDUTIL_LICENSE =================================================================== --- vendor/stdutil/current/STDUTIL_LICENSE 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/STDUTIL_LICENSE 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The Original Software is: Modified: vendor/stdutil/current/configure =================================================================== --- vendor/stdutil/current/configure 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/configure 2009-06-04 20:38:26 UTC (rev 421) @@ -2768,14 +2768,14 @@ SHLDFLAGS="$SHLDFLAGS $LDFLAGS" SHLIBS=$LIBS DYNLIBEXT=dylib - STANDARD_LIBS="\$(STATIC_THREADED_RELEASE_LIB) \$(SHARED_THREADED_RELEASE_LIB)" + STANDARD_LIBS="\$(STATIC_THREADED_DEBUG_LIB) \$(STATIC_THREADED_RELEASE_LIB) \$(SHARED_THREADED_DEBUG_LIB) \$(SHARED_THREADED_RELEASE_LIB)" SHARED_LIBS="\$(SHARED_LIBS)" ;; mips-sgi-irix*) CC=cc CFLAGS="-n32 -signed" DYNLIBEXT= - STANDARD_LIBS="\$(STATIC_THREADED_RELEASE_LIB)" + STANDARD_LIBS="\$(STATIC_THREADED_DEBUG_LIB) \$(STATIC_THREADED_RELEASE_LIB)" SHARED_LIBS= ;; *-*-*) @@ -2786,7 +2786,7 @@ SHLDFLAGS="$SHLDFLAGS $LDFLAGS" SHLIBS=$LIBS DYNLIBEXT=so - STANDARD_LIBS="\$(STATIC_THREADED_RELEASE_LIB) \$(SHARED_THREADED_RELEASE_LIB)" + STANDARD_LIBS="\$(STATIC_THREADED_DEBUG_LIB) \$(STATIC_THREADED_RELEASE_LIB) \$(SHARED_THREADED_DEBUG_LIB) \$(SHARED_THREADED_RELEASE_LIB)" SHARED_LIBS="\$(SHARED_LIBS)" ;; esac Modified: vendor/stdutil/current/configure.in =================================================================== --- vendor/stdutil/current/configure.in 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/configure.in 2009-06-04 20:38:26 UTC (rev 421) @@ -55,14 +55,14 @@ SHLDFLAGS="$SHLDFLAGS $LDFLAGS" SHLIBS=$LIBS DYNLIBEXT=dylib - STANDARD_LIBS="\$(STATIC_THREADED_RELEASE_LIB) \$(SHARED_THREADED_RELEASE_LIB)" + STANDARD_LIBS="\$(STATIC_THREADED_DEBUG_LIB) \$(STATIC_THREADED_RELEASE_LIB) \$(SHARED_THREADED_DEBUG_LIB) \$(SHARED_THREADED_RELEASE_LIB)" SHARED_LIBS="\$(SHARED_LIBS)" ;; mips-sgi-irix*) CC=cc CFLAGS="-n32 -signed" DYNLIBEXT= - STANDARD_LIBS="\$(STATIC_THREADED_RELEASE_LIB)" + STANDARD_LIBS="\$(STATIC_THREADED_DEBUG_LIB) \$(STATIC_THREADED_RELEASE_LIB)" SHARED_LIBS= ;; *-*-*) @@ -73,7 +73,7 @@ SHLDFLAGS="$SHLDFLAGS $LDFLAGS" SHLIBS=$LIBS DYNLIBEXT=so - STANDARD_LIBS="\$(STATIC_THREADED_RELEASE_LIB) \$(SHARED_THREADED_RELEASE_LIB)" + STANDARD_LIBS="\$(STATIC_THREADED_DEBUG_LIB) \$(STATIC_THREADED_RELEASE_LIB) \$(SHARED_THREADED_DEBUG_LIB) \$(SHARED_THREADED_RELEASE_LIB)" SHARED_LIBS="\$(SHARED_LIBS)" ;; esac Modified: vendor/stdutil/current/src/Makefile.in =================================================================== --- vendor/stdutil/current/src/Makefile.in 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/Makefile.in 2009-06-04 20:38:26 UTC (rev 421) @@ -1,7 +1,7 @@ .SUFFIXES: .do .to .tdo .lo .ldo .lto .ltdo .PHONY: all standard libdir clean distclean uberclean -LIBVERSION=1.0 +LIBVERSION=1.1 ############################################ PROGRAMS ######################################### @@ -89,6 +89,7 @@ $(STATIC_THREADED_DEBUG_LIB): $(STATIC_THREADED_DEBUG_OBJS) $(AR) rvs $@ $(STATIC_THREADED_DEBUG_OBJS) + $(SOFTLINK) -f $@ $(LIBDIR)/libstdutil-debug.a $(SHARED_NOTHREAD_RELEASE_LIB): $(SHARED_NOTHREAD_RELEASE_OBJS) $(SHLD) $(SHLDFLAGS) -o $@ $(SHARED_NOTHREAD_RELEASE_OBJS) $(SHLIBS) @@ -102,9 +103,10 @@ $(SHARED_THREADED_DEBUG_LIB): $(SHARED_THREADED_DEBUG_OBJS) $(SHLD) $(SHLDFLAGS) -o $@ $(SHARED_THREADED_DEBUG_OBJS) $(SHLIBS) $(THLIBS) + $(SOFTLINK) -f $@ $(LIBDIR)/libstdutil-debug.@DYNLIBEXT@ clean: - rm -f *.o *.do *.to *.tdo *.lo *.ldo *.lto *.ltdo core* *~ $(ALLTARGETS) $(LIBDIR)/libstdutil.a $(LIBDIR)/libstdutil.@DYNLIBEXT@ + rm -f *.o *.do *.to *.tdo *.lo *.ldo *.lto *.ltdo core* *~ stdutil/*~ stdutil/private/*~ $(ALLTARGETS) $(LIBDIR)/libstdutil.a $(LIBDIR)/libstdutil.@DYNLIBEXT@ $(LIBDIR)/libstdutil-debug.a $(LIBDIR)/libstdutil-debug.@DYNLIBEXT@ distclean: clean rm -f Makefile stdutil/private/stdarch_autoconf.h Modified: vendor/stdutil/current/src/stdarr.c =================================================================== --- vendor/stdutil/current/src/stdarr.c 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdarr.c 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdcarr.c =================================================================== --- vendor/stdutil/current/src/stdcarr.c 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdcarr.c 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stddll.c =================================================================== --- vendor/stdutil/current/src/stddll.c 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stddll.c 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). @@ -216,8 +216,9 @@ { stddll_node * curr = erase_end->prev; stddll_node * prev; + stdsize ne = num_erase; - while (num_erase-- != 0) { + while (ne-- != 0) { STDBOUNDS_CHECK(curr != STDDLL_LEND(l)); /* check for an illegal erasure */ prev = curr; curr = curr->prev; Modified: vendor/stdutil/current/src/stderror.c =================================================================== --- vendor/stdutil/current/src/stderror.c 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stderror.c 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdfd.c =================================================================== --- vendor/stdutil/current/src/stdfd.c 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdfd.c 2009-06-04 20:38:26 UTC (rev 421) @@ -1,366 +1,366 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University - * All rights reserved. - * - * The contents of this file are subject to a license (the ``License''). - * You may not use this file except in compliance with the License. The - * specific language governing the rights and limitations of the License - * can be found in the file ``STDUTIL_LICENSE'' found in this - * distribution. - * - * Software distributed under the License is distributed on an AS IS - * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. - * - * The Original Software is: - * The Stdutil Library - * - * Contributors: - * Creator - John Lane Schultz ([email protected]) - * The Center for Networking and Distributed Systems - * (CNDS - http://www.cnds.jhu.edu) - */ - -#include <fcntl.h> -#include <sys/types.h> -#include <sys/stat.h> - -#include <stdutil/stderror.h> -#include <stdutil/stdfd.h> - -#ifdef __cplusplus -extern "C" { -#endif - -#if defined(_WIN32) -# include <io.h> -# include <sys/locking.h> -# define STDFILENO(s) _fileno(s) -# define STDFSYNC(fd) _commit(fd) -#else -# include <unistd.h> -# define STDFILENO(s) fileno(s) -# define STDFSYNC(fd) fsync(fd) -#endif - -/************************************************************************************************ - * stdfd_open: Open a file descriptor. - ***********************************************************************************************/ - -STDINLINE stdcode stdfd_open(stdfd *fd, const char *path, stdfd_access_type mode) -{ - stdcode ret = STDESUCCESS; - const char * fopen_mode; - - switch (mode) { - case STDFD_READ_ONLY: - fopen_mode = "rb"; - break; - - case STDFD_READ_WRITE_EXISTING: - fopen_mode = "rb+"; - break; - - case STDFD_WRITE_ONLY: - fopen_mode = "wb"; - break; - - case STDFD_READ_WRITE_NEW: - fopen_mode = "wb+"; - break; - - case STDFD_APPEND_ONLY: - fopen_mode = "ab"; - break; - - case STDFD_READ_APPEND: - fopen_mode = "ab+"; - break; - - default: - ret = STDEINVAL; - goto stdfd_open_end; - } - - if ((fd->stream = fopen(path, fopen_mode)) != NULL) { - fd->fd = STDFILENO(fd->stream); - - } else { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - } - - stdfd_open_end: - return ret; -} - -/************************************************************************************************ - * stdfd_close: Close a file descriptor. - ***********************************************************************************************/ - -STDINLINE stdcode stdfd_close(stdfd *fd) -{ - stdcode ret = STDESUCCESS; - - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - if (fclose(fd->stream) != 0) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - } - - fd->stream = NULL; - fd->fd = -1; - - return ret; -} - -/************************************************************************************************ - * stdfd_read: Read 'nmemb' entries of 'nsize' bytes each from a file - * descriptor into 'ptr.' - ***********************************************************************************************/ - -STDINLINE stdcode stdfd_read(stdfd *fd, void *ptr, stdsize nsize, stdsize nmemb, stdsize *num) -{ - stdcode ret; - - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - if ((*num = fread(ptr, nsize, nmemb, fd->stream)) == nmemb) { - ret = STDESUCCESS; - - } else if (feof(fd->stream)) { - ret = STDEOF; - - } else if (ferror(fd->stream)) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - - } else { - ret = STDEINTR; /* wrong count but not EOF or error? alert user! */ - } - - return ret; -} - -/************************************************************************************************ - * stdfd_write: Write 'nmemb' entries of 'nsize' bytes each from 'ptr' - * to a file descriptor. - ***********************************************************************************************/ - -STDINLINE stdcode stdfd_write(stdfd *fd, const void *ptr, stdsize nsize, stdsize nmemb, stdsize *num) -{ - stdcode ret; - - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - if ((*num = fwrite(ptr, nsize, nmemb, fd->stream)) == nmemb) { - ret = STDESUCCESS; - - } else if (feof(fd->stream)) { - ret = STDEOF; - - } else if (ferror(fd->stream)) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - - } else { - ret = STDEINTR; /* wrong count but not EOF or error? alert user! */ - } - - return ret; -} - -/************************************************************************************************ - * stdfd_flush: Flush any user space data on a file descriptor to the OS. - ***********************************************************************************************/ - -STDINLINE stdcode stdfd_flush(stdfd *fd) -{ - stdcode ret = STDESUCCESS; - - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - if (fflush(fd->stream) != 0) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - } - - return ret; -} - -/************************************************************************************************ - * stdfd_sync: Flush user space data to the OS and force the OS to - * flush all data to disk. - ***********************************************************************************************/ - -STDINLINE stdcode stdfd_sync(stdfd *fd) -{ - stdcode ret = STDESUCCESS; - - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - if (fflush(fd->stream) != 0 || STDFSYNC(fd->fd) != 0) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - } - - return ret; -} - -/************************************************************************************************ - * stdfd_seek: Move the read/write head position of a file descriptor. - ***********************************************************************************************/ - -STDINLINE stdcode stdfd_seek(stdfd *fd, long offset, stdfd_whence whence) -{ - stdcode ret = STDESUCCESS; - - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - if (fseek(fd->stream, offset, whence) != 0) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - } - - return ret; -} - -/************************************************************************************************ - * stdfd_tell: Get the read/write head position of a file descriptor. - ***********************************************************************************************/ - -STDINLINE stdcode stdfd_tell(stdfd *fd, long *pos) -{ - stdcode ret = STDESUCCESS; - - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - if ((*pos = ftell(fd->stream)) == -1) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - } - - return ret; -} - -/************************************************************************************************ - * stdfd_eof: Return whether or not the EOF indicator on a file descriptor is set. - ***********************************************************************************************/ - -STDINLINE stdbool stdfd_eof(stdfd *fd) -{ - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - return (feof(fd->stream) != 0); -} - -/************************************************************************************************ - * stdfd_err: Return whether or not an error indicator on a file descriptor is set. - ***********************************************************************************************/ - -STDINLINE stdbool stdfd_err(stdfd *fd) -{ - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - return (ferror(fd->stream) != 0); -} - -/************************************************************************************************ - * stdfd_clr_err: Clear any error indicator on a file descriptor. - ***********************************************************************************************/ - -STDINLINE void stdfd_clr_err(stdfd *fd) -{ - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - clearerr(fd->stream); -} - -/************************************************************************************************ - * stdfd_trylock: Try to acquire an advisory lock on a file - * descriptor's underlying file. - ***********************************************************************************************/ - -STDINLINE stdcode stdfd_trylock(stdfd *fd) -#if defined(_WIN32) -{ - stdcode ret = STDESUCCESS; - - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - if (_locking(fd->fd, _LK_NBLCK, 1) != 0) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - } - - return ret; -} -#else -{ - struct flock lock = { 0 }; - stdcode ret = STDESUCCESS; - - lock.l_type = F_WRLCK; - - if (fcntl(fd->fd, F_SETLK, &lock) != 0) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - } - - return ret; -} -#endif - -/************************************************************************************************ - * stdfd_unlock: Release an advisory lock on a file descriptor's - * underlying file. - ***********************************************************************************************/ - -STDINLINE stdcode stdfd_unlock(stdfd *fd) -#if defined(_WIN32) -{ - stdcode ret = STDESUCCESS; - - STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); - - if (_locking(fd->fd, _LK_UNLCK, 1) != 0) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - } - - return ret; -} -#else -{ - struct flock lock = { 0 }; - stdcode ret = STDESUCCESS; - - lock.l_type = F_UNLCK; - - if (fcntl(fd->fd, F_SETLK, &lock) != 0) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - } - - return ret; - } -#endif - -/************************************************************************************************ - * stdfile_unlink: Erase a file. - ***********************************************************************************************/ - -STDINLINE stdcode stdfile_unlink(const char *path) -{ - stdcode ret = STDESUCCESS; - - if (remove(path) != 0) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - } - - return ret; -} - -#ifdef __cplusplus -} -#endif +/* Copyright (c) 2000-2009, The Johns Hopkins University + * All rights reserved. + * + * The contents of this file are subject to a license (the ``License''). + * You may not use this file except in compliance with the License. The + * specific language governing the rights and limitations of the License + * can be found in the file ``STDUTIL_LICENSE'' found in this + * distribution. + * + * Software distributed under the License is distributed on an AS IS + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. + * + * The Original Software is: + * The Stdutil Library + * + * Contributors: + * Creator - John Lane Schultz ([email protected]) + * The Center for Networking and Distributed Systems + * (CNDS - http://www.cnds.jhu.edu) + */ + +#include <fcntl.h> +#include <sys/types.h> +#include <sys/stat.h> + +#include <stdutil/stderror.h> +#include <stdutil/stdfd.h> + +#ifdef __cplusplus +extern "C" { +#endif + +#if defined(_WIN32) +# include <io.h> +# include <sys/locking.h> +# define STDFILENO(s) _fileno(s) +# define STDFSYNC(fd) _commit(fd) +#else +# include <unistd.h> +# define STDFILENO(s) fileno(s) +# define STDFSYNC(fd) fsync(fd) +#endif + +/************************************************************************************************ + * stdfd_open: Open a file descriptor. + ***********************************************************************************************/ + +STDINLINE stdcode stdfd_open(stdfd *fd, const char *path, stdfd_access_type mode) +{ + stdcode ret = STDESUCCESS; + const char * fopen_mode; + + switch (mode) { + case STDFD_READ_ONLY: + fopen_mode = "rb"; + break; + + case STDFD_READ_WRITE_EXISTING: + fopen_mode = "rb+"; + break; + + case STDFD_WRITE_ONLY: + fopen_mode = "wb"; + break; + + case STDFD_READ_WRITE_NEW: + fopen_mode = "wb+"; + break; + + case STDFD_APPEND_ONLY: + fopen_mode = "ab"; + break; + + case STDFD_READ_APPEND: + fopen_mode = "ab+"; + break; + + default: + ret = STDEINVAL; + goto stdfd_open_end; + } + + if ((fd->stream = fopen(path, fopen_mode)) != NULL) { + fd->fd = STDFILENO(fd->stream); + + } else { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + } + + stdfd_open_end: + return ret; +} + +/************************************************************************************************ + * stdfd_close: Close a file descriptor. + ***********************************************************************************************/ + +STDINLINE stdcode stdfd_close(stdfd *fd) +{ + stdcode ret = STDESUCCESS; + + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + if (fclose(fd->stream) != 0) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + } + + fd->stream = NULL; + fd->fd = -1; + + return ret; +} + +/************************************************************************************************ + * stdfd_read: Read 'nmemb' entries of 'nsize' bytes each from a file + * descriptor into 'ptr.' + ***********************************************************************************************/ + +STDINLINE stdcode stdfd_read(stdfd *fd, void *ptr, stdsize nsize, stdsize nmemb, stdsize *num) +{ + stdcode ret; + + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + if ((*num = fread(ptr, nsize, nmemb, fd->stream)) == nmemb) { + ret = STDESUCCESS; + + } else if (feof(fd->stream)) { + ret = STDEOF; + + } else if (ferror(fd->stream)) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + + } else { + ret = STDEINTR; /* wrong count but not EOF or error? alert user! */ + } + + return ret; +} + +/************************************************************************************************ + * stdfd_write: Write 'nmemb' entries of 'nsize' bytes each from 'ptr' + * to a file descriptor. + ***********************************************************************************************/ + +STDINLINE stdcode stdfd_write(stdfd *fd, const void *ptr, stdsize nsize, stdsize nmemb, stdsize *num) +{ + stdcode ret; + + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + if ((*num = fwrite(ptr, nsize, nmemb, fd->stream)) == nmemb) { + ret = STDESUCCESS; + + } else if (feof(fd->stream)) { + ret = STDEOF; + + } else if (ferror(fd->stream)) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + + } else { + ret = STDEINTR; /* wrong count but not EOF or error? alert user! */ + } + + return ret; +} + +/************************************************************************************************ + * stdfd_flush: Flush any user space data on a file descriptor to the OS. + ***********************************************************************************************/ + +STDINLINE stdcode stdfd_flush(stdfd *fd) +{ + stdcode ret = STDESUCCESS; + + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + if (fflush(fd->stream) != 0) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + } + + return ret; +} + +/************************************************************************************************ + * stdfd_sync: Flush user space data to the OS and force the OS to + * flush all data to disk. + ***********************************************************************************************/ + +STDINLINE stdcode stdfd_sync(stdfd *fd) +{ + stdcode ret = STDESUCCESS; + + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + if (fflush(fd->stream) != 0 || STDFSYNC(fd->fd) != 0) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + } + + return ret; +} + +/************************************************************************************************ + * stdfd_seek: Move the read/write head position of a file descriptor. + ***********************************************************************************************/ + +STDINLINE stdcode stdfd_seek(stdfd *fd, long offset, stdfd_whence whence) +{ + stdcode ret = STDESUCCESS; + + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + if (fseek(fd->stream, offset, whence) != 0) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + } + + return ret; +} + +/************************************************************************************************ + * stdfd_tell: Get the read/write head position of a file descriptor. + ***********************************************************************************************/ + +STDINLINE stdcode stdfd_tell(stdfd *fd, long *pos) +{ + stdcode ret = STDESUCCESS; + + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + if ((*pos = ftell(fd->stream)) == -1) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + } + + return ret; +} + +/************************************************************************************************ + * stdfd_eof: Return whether or not the EOF indicator on a file descriptor is set. + ***********************************************************************************************/ + +STDINLINE stdbool stdfd_eof(stdfd *fd) +{ + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + return (feof(fd->stream) != 0); +} + +/************************************************************************************************ + * stdfd_err: Return whether or not an error indicator on a file descriptor is set. + ***********************************************************************************************/ + +STDINLINE stdbool stdfd_err(stdfd *fd) +{ + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + return (ferror(fd->stream) != 0); +} + +/************************************************************************************************ + * stdfd_clr_err: Clear any error indicator on a file descriptor. + ***********************************************************************************************/ + +STDINLINE void stdfd_clr_err(stdfd *fd) +{ + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + clearerr(fd->stream); +} + +/************************************************************************************************ + * stdfd_trylock: Try to acquire an advisory lock on a file + * descriptor's underlying file. + ***********************************************************************************************/ + +STDINLINE stdcode stdfd_trylock(stdfd *fd) +#if defined(_WIN32) +{ + stdcode ret = STDESUCCESS; + + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + if (_locking(fd->fd, _LK_NBLCK, 1) != 0) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + } + + return ret; +} +#else +{ + struct flock lock = { 0 }; + stdcode ret = STDESUCCESS; + + lock.l_type = F_WRLCK; + + if (fcntl(fd->fd, F_SETLK, &lock) != 0) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + } + + return ret; +} +#endif + +/************************************************************************************************ + * stdfd_unlock: Release an advisory lock on a file descriptor's + * underlying file. + ***********************************************************************************************/ + +STDINLINE stdcode stdfd_unlock(stdfd *fd) +#if defined(_WIN32) +{ + stdcode ret = STDESUCCESS; + + STDSAFETY_CHECK(fd->stream != NULL && fd->fd >= 0); + + if (_locking(fd->fd, _LK_UNLCK, 1) != 0) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + } + + return ret; +} +#else +{ + struct flock lock = { 0 }; + stdcode ret = STDESUCCESS; + + lock.l_type = F_UNLCK; + + if (fcntl(fd->fd, F_SETLK, &lock) != 0) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + } + + return ret; + } +#endif + +/************************************************************************************************ + * stdfile_unlink: Erase a file. + ***********************************************************************************************/ + +STDINLINE stdcode stdfile_unlink(const char *path) +{ + stdcode ret = STDESUCCESS; + + if (remove(path) != 0) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + } + + return ret; +} + +#ifdef __cplusplus +} +#endif Modified: vendor/stdutil/current/src/stdhash.c =================================================================== --- vendor/stdutil/current/src/stdhash.c 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdhash.c 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdit.c =================================================================== --- vendor/stdutil/current/src/stdit.c 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdit.c 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdskl.c =================================================================== --- vendor/stdutil/current/src/stdskl.c 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdskl.c 2009-06-04 20:38:26 UTC (rev 421) @@ -1,1192 +1,1197 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University - * All rights reserved. - * - * The contents of this file are subject to a license (the ``License''). - * You may not use this file except in compliance with the License. The - * specific language governing the rights and limitations of the License - * can be found in the file ``STDUTIL_LICENSE'' found in this - * distribution. - * - * Software distributed under the License is distributed on an AS IS - * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. - * - * The Original Software is: - * The Stdutil Library - * - * Contributors: - * Creator - John Lane Schultz ([email protected]) - * The Center for Networking and Distributed Systems - * (CNDS - http://www.cnds.jhu.edu) - */ - -#include <stdlib.h> -#include <string.h> - -#include <stdutil/stdutil.h> -#include <stdutil/stderror.h> -#include <stdutil/stdtime.h> -#include <stdutil/stdskl.h> - -#ifdef __cplusplus -extern "C" { -#endif - -/* TODO: consider shrinking end_node's arrays when the top level - becomes empty (down to some minimum height like 4 or 5); this is - easy to detect: if the node being removed has the same height as - the end_node and his top level prev and next are the end node then - the level is about to become empty; alternatively after removal you - can just check the top levels for self reference; also might not - want to make end_node taller than the tallest node on insert -- - don't know how big an effect on find this will have as find as it - will simply run down end_node's nexts array while next equals - end_node not doing any real work -*/ - -#define STDSKL_MAX_HEIGHT 31 - -#define STDSKL_IS_LEGAL(l) ((l)->end_node != NULL && (l)->ksize != 0 && (l)->bits_left >= 0 && (l)->bits_left < 32) -#define STDSKL_IT_IS_LEGAL(l, i) ((i)->ksize == (l)->ksize && (i)->vsize == (l)->vsize) -#define STDIT_SKL_IS_LEGAL(i) (((i)->type_id == STDSKL_IT_ID || (i)->type_id == STDSKL_IT_KEY_ID) && \ - (i)->impl.skl.node != NULL && (i)->impl.skl.ksize != 0) - -#define STDSKL_NKEY(node) ((node)->key) -#define STDSKL_NVAL(node) ((node)->val) - -/************************************************************************************************ - * stdskl_low_key_cmp: Compares 2 keys, uses memcmp if no comparison fcn defined. - ***********************************************************************************************/ - -STDINLINE static int stdskl_low_key_cmp(const stdskl *l, const void *k1, const void *k2) -{ - return (l->cmp_fcn == NULL ? memcmp(k1, k2, l->ksize) : l->cmp_fcn(k1, k2)); -} - -/************************************************************************************************ - * stdskl_low_create_node: Create a node to be inserted into 'l.' - * - * For random height generation, a node is promoted to a higher height - * w/ 25% chance. The optimum promotion chance for a skiplist is - * somewhere between 28% and 37% depending on the analysis used. 25% - * gives nearly optimal performance while using less memory and not - * requiring excessive random bit generation. - ***********************************************************************************************/ - -STDINLINE static stdskl_node *stdskl_low_create_node(stdskl *l, stdint8 height, const void *key, const void *val) -{ - stdskl_node * node; - stdsize mem_tot; - stdsize prevs_off; - stdsize nexts_off; - stdsize key_off; - stdsize val_off; - - if (height == -1) { /* height generation requested */ - stdbool keep_going = STDTRUE; - - for (; keep_going && height < STDSKL_MAX_HEIGHT; ++height) { /* loop while random height increases */ - - if (l->bits_left == 0) { /* out of random bits */ - l->rand_bits = stdrand32(l->seed); /* generate 32 new ones */ - l->bits_left = 32; - } - - keep_going = ((l->rand_bits & 0x3) == 0x3); /* continue loop w/ 25% chance */ - l->bits_left -= 2; /* remove used bits */ - l->rand_bits >>= 2; - } - } - - /* calculate memory needed for node and pointer arrays and the offsets for the pointers in the node */ - - mem_tot = sizeof(stdskl_node); /* memory for node structure */ - prevs_off = mem_tot; /* structure is already aligned for void*'s -> good enough alignment */ - - mem_tot += (height + 1) * sizeof(stdskl_node*); /* memory for prevs array */ - nexts_off = mem_tot; /* structure is already aligned for void*'s -> good enough alignment */ - - mem_tot += (height + 1) * sizeof(stdskl_node*); /* memory for nexts array */ - mem_tot = STDARCH_PADDED_SIZE(mem_tot); /* pad memory for key */ - key_off = mem_tot; - - mem_tot += STDARCH_PADDED_SIZE(l->ksize); /* memory for key and padding for value */ - val_off = mem_tot; - - mem_tot += l->vsize; /* memory for value */ - - /* allocate the node and extra memory */ - - if ((node = (stdskl_node*) malloc(mem_tot)) == NULL) { - goto stdskl_low_create_node_end; - } - - /* init node: set height, point pointers to appropriate offsets in allocated memory block */ - - node->height = height; - node->prevs = (stdskl_node**) ((char*) node + prevs_off); - node->nexts = (stdskl_node**) ((char*) node + nexts_off); - node->key = (char*) node + key_off; - node->val = (char*) node + val_off; - - /* copy key + value if given */ - - if (key != NULL) { - memcpy((void*) STDSKL_NKEY(node), key, l->ksize); - memcpy(STDSKL_NVAL(node), val, l->vsize); - } - - stdskl_low_create_node_end: - return node; -} - -/************************************************************************************************ - * stdskl_low_find_right: Search 'l' for 'key' from left to right. - * - * If (find_any) immediately return on any match. Otherwise if 'key' - * exists in 'l' return the "leftmost" (least) match if multiple - * matches exist. On no match, returns the "leftmost" (least) entry - * in 'l' with a greater key, or end if no such entry exists. - ***********************************************************************************************/ - -STDINLINE static stdbool stdskl_low_find_right(const stdskl *l, const void *key, - stdbool find_any, stdskl_node **pos) -{ - const stdskl_node * next = NULL; - const stdskl_node * curr = l->end_node; - stdint8 lvl = l->end_node->height; - int cmp = -1; /* get rid of compiler warning */ - - /* run down to bottom level list */ - - while (lvl > 0) { - next = curr->nexts[lvl]; - - /* run right at this level while key is greater than next's key */ - - while (next != l->end_node && - (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) { - curr = next; - next = next->nexts[lvl]; - } - - /* if we found a match and any match will do */ - - if (find_any && next != l->end_node && cmp == 0) { - *pos = (stdskl_node*) next; - return STDTRUE; - } - - /* run down curr's levels while they equal next */ - - for (--lvl; lvl > 0 && curr->nexts[lvl] == next; --lvl); - } - - /* lvl is zero: run right on bottom level list trying to match key */ - - curr = curr->nexts[0]; - - if (curr != next) { - - while (curr != l->end_node && - (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(curr))) > 0) { - curr = curr->nexts[0]; - } - } /* else we already compared key to curr above */ - - *pos = (stdskl_node*) curr; - - return (curr != l->end_node && cmp == 0); -} - -/************************************************************************************************ - * stdskl_low_find_left: Search 'l' for 'key' from right to left. - * - * If (find_any) immediately return on any match. Otherwise if 'key' - * exists in 'l' return the "rightmost" (greatest) match if multiple - * matches exist. On no match, returns the "rightmost" (greatest) - * entry in 'l' with a lesser key, or end if no such entry exists. - ***********************************************************************************************/ - -STDINLINE static stdbool stdskl_low_find_left(const stdskl *l, const void *key, - stdbool find_any, stdskl_node **pos) -{ - const stdskl_node * prev = NULL; - const stdskl_node * curr = l->end_node; - stdint8 lvl = l->end_node->height; - int cmp = -1; /* get rid of compiler warning */ - - /* run down to bottom level list */ - - while (lvl > 0) { - prev = curr->prevs[lvl]; - - /* run left at this level while key is less than prev's key */ - - while (prev != l->end_node && - (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev))) < 0) { - curr = prev; - prev = prev->prevs[lvl]; - } - - /* if we found a match and any match will do */ - - if (find_any && prev != l->end_node && cmp == 0) { - *pos = (stdskl_node*) prev; - return STDTRUE; - } - - /* run down curr's prevs levels while they equal prev */ - - for (--lvl; lvl > 0 && curr->prevs[lvl] == prev; --lvl); - } - - /* run left on bottom level list trying to match key */ - - curr = curr->prevs[0]; - - if (curr != prev) { - - while (curr != l->end_node && - (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(curr))) < 0) { - curr = curr->prevs[0]; - } - } /* else we already compared key to curr above */ - - *pos = (stdskl_node*) curr; - - return (curr != l->end_node && cmp == 0); -} - -/************************************************************************************************ - * stdskl_low_link_right: Link 'node' into entries greater than or - * equal to 'ins_pos' in 'l.' - ***********************************************************************************************/ - -STDINLINE static void stdskl_low_link_right(const stdskl *l, stdskl_node *ins_pos, stdskl_node *node) -{ - stdskl_node * next = ins_pos; - stdint8 height = node->height; - stdint8 lvl = 0; - - node->nexts[0] = next; - next->prevs[0] = node; - - while (lvl != height) { - - /* if we've maxed out next's height, then find a later, taller node on this lvl */ - - while (lvl == next->height) { /* NOTE: node->height <= end_node->height -> lvl < end_node->height here */ - next = next->nexts[lvl]; /* so we can't erroneously wrap around past sentinel end node here */ - } - - ++lvl; - node->nexts[lvl] = next; - next->prevs[lvl] = node; - } -} - -/************************************************************************************************ - * stdskl_low_link_left: Link in 'node' to entries less than 'ins_pos' - * in 'l.' - ***********************************************************************************************/ - -STDINLINE static void stdskl_low_link_left(const stdskl *l, stdskl_node *ins_pos, stdskl_node *node) -{ - stdskl_node * prev = ins_pos->prevs[0]; /* NOTE: this is why we must link_left b4 link_right in insert! */ - stdint8 height = node->height; - stdint8 lvl = 0; - - node->prevs[0] = prev; - prev->nexts[0] = node; - - while (lvl != height) { - - /* if we've maxed out prev's height, then find an earlier, taller node on this lvl */ - - while (lvl == prev->height) { /* NOTE: node->height <= end_node->height -> lvl < end_node->height here */ - prev = prev->prevs[lvl]; /* so we can't erroneously wrap around past sentinel end node here */ - } - - ++lvl; - node->prevs[lvl] = prev; - prev->nexts[lvl] = node; - } -} - -/************************************************************************************************ - * stdskl_low_insert: Insert multiple keys and values into a list - * using an iterator sequence with various options. - ***********************************************************************************************/ - -STDINLINE static stdcode stdskl_low_insert(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdsize num_ins, - stdbool hint, stdbool overwrite, stdbool advance) -{ - stdcode ret = STDESUCCESS; - stdskl_node * node; - stdskl_node * prev; - stdskl_node * next = (it != NULL ? it->impl.skl.node : l->end_node); - stdskl_node * first_ins = NULL; - stdit src_it = *b; - stdbool keyed = (stdit_key_size(b) != 0); - stdint8 lvl; - const void * key; - const void * val; - int cmp; - - /* loop over input sequence defined either by [b, b+num_ins) or [b, e) */ - - while (num_ins-- != 0 && (e == NULL || !stdit_eq(&src_it, e))) { - - /* get pointers to the key and value we are about to insert */ - - val = stdit_val(&src_it); - key = (keyed ? stdit_key(&src_it) : val); - cmp = -1; - - /* get insertion position for this key: next */ - - if (hint) { /* 'next' is a potential insertion point -> verify! */ - prev = next->prevs[0]; - - if ((next != l->end_node && (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) || - (prev != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev)) < 0)) { - - prev = next; - next = next->nexts[0]; /* next was inappropriate; try ++next */ - cmp = -1; - - if ((next != l->end_node && (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) || - (prev != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev)) < 0)) { - hint = STDFALSE; /* both next and ++next were inappropriate: do a full search */ - } - } - } - - if (!hint) { - cmp = !stdskl_low_find_right(l, key, STDTRUE, &next); - } - - hint = STDTRUE; /* use next as a hint for following iteration (optimize for nearly contiguous, sorted inserts) */ - - /* create + insert new node; or overwrite pre-existing match if so instructed and appropriate */ - - if (!overwrite || next == l->end_node || cmp != 0) { /* create new node to insert */ - - if ((node = stdskl_low_create_node(l, -1, key, val)) == NULL) { /* create a node with a random height */ - ret = STDENOMEM; - goto stdskl_low_insert_end; - } - - /* ensure that l->end_node is at least as tall as the new node */ - - if (node->height > l->end_node->height) { - stdskl_node * new_end; - - /* ratchet up new end_node's height to be at least 1 level higher (usually 2) than before */ - - lvl = node->height; /* 0 <= node->height <= STDSKL_MAX_HEIGHT */ - - if (lvl < STDSKL_MAX_HEIGHT) { - ++lvl; - } - - if ((new_end = stdskl_low_create_node(l, lvl, NULL, NULL)) == NULL) { - ret = STDENOMEM; - goto stdskl_low_insert_fail; - } - - /* set new_end's nexts and prevs and update nodes ref'ing end_node to now point to new_end */ - /* loop while we haven't updated all levels of the lists AND end_node is NOT self-referring */ - - lvl = 0; - do { - - if (l->end_node->prevs[lvl] == l->end_node) { /* break on end_node referring to itself -> */ - break; /* all prevs, nexts of this and higher lvls are self-referring */ - } - - new_end->prevs[lvl] = l->end_node->prevs[lvl]; - l->end_node->prevs[lvl]->nexts[lvl] = new_end; - - new_end->nexts[lvl] = l->end_node->nexts[lvl]; - l->end_node->nexts[lvl]->prevs[lvl] = new_end; - - } while (lvl++ != l->end_node->height); - - /* set additional lvls in new_end to be self-referencing. NOTE: new_end is at least 1 lvl taller than end_node */ - - do { - new_end->prevs[lvl] = new_end; - new_end->nexts[lvl] = new_end; - - } while (lvl++ != new_end->height); - - /* correct next if it referenced the end_node */ - - if (next == l->end_node) { - next = new_end; - } - - free(l->end_node); - l->end_node = new_end; - } - - /* link 'node' into list before next */ - - stdskl_low_link_left(l, next, node); /* NOTE: we must link_left before we link_right due to loss of information */ - stdskl_low_link_right(l, next, node); - - ++l->size; - - } else { /* overwrite existing match */ - node = next; - memcpy((void*) STDSKL_NKEY(node), key, l->ksize); /* overwrite */ - memcpy(STDSKL_NVAL(node), val, l->vsize); - } - - /* remember first insertion/overwrite */ - - if (first_ins == NULL) { - first_ins = node; - } - - /* advance 'src_it' if so instructed */ - - if (advance) { - stdit_next(&src_it); - } - } - - goto stdskl_low_insert_end; - - /* error handling and return */ - - stdskl_low_insert_fail: - free(node); - - stdskl_low_insert_end: - if (it != NULL) { - it->type_id = STDSKL_IT_ID; - it->impl.skl.node = (first_ins != NULL ? first_ins : l->end_node); /* point to end if no insert/overwrite occurred */ - it->impl.skl.ksize = l->ksize; - it->impl.skl.vsize = l->vsize; - } - - return ret; -} - -/************************************************************************************************ - * stdskl_low_erase: Erase multiple key-value pairs from a list using - * either an iterator sequence to delete or a number of elements to - * erase. - ***********************************************************************************************/ - -STDINLINE static void stdskl_low_erase(stdskl *l, stdit *b, stdit *e, stdsize num_erase) -{ - stdskl_node * ers; - stdskl_node * prev = b->impl.skl.node->prevs[0]; - stdskl_node * next = b->impl.skl.node; - stdskl_node * end_node = (e != NULL ? e->impl.skl.node : NULL); - stdint8 max_lvl = 0; - stdsize erased; - stdint8 lvl; - - /* go through [b, b+num_erase) or [b, e) free'ing nodes -- record - max height of free'd nodes and how many nodes we erased - */ - - for (erased = 0; erased != num_erase && next != end_node; ++erased) { - STDBOUNDS_CHECK(next != l->end_node); - - if (next->height > max_lvl) { - max_lvl = next->height; - } - - ers = next; - next = next->nexts[0]; - free(ers); - } - - /* update list size */ - - l->size -= num_erase; - - /* stitch together the left and right portions of the list */ - - ers = next; /* remember where erasure stopped */ - prev->nexts[0] = next; /* perform base re-linkage */ - next->prevs[0] = prev; - - for (lvl = 0; lvl != max_lvl; ) { /* run left and run right up to max_lvl height nodes re-linking */ - - while (lvl == prev->height) { - prev = prev->prevs[lvl]; - } - - while (lvl == next->height) { - next = next->nexts[lvl]; - } - - ++lvl; - prev->nexts[lvl] = next; - next->prevs[lvl] = prev; - } - - /* advance 'b' and 'e' */ - - b->impl.skl.node = ers; - - if (e != NULL) { - e->impl.skl.node = ers; - } -} - -/************************************************************************************************ - * stdskl_construct: Construct an initially empty list. - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_construct(stdskl *l, stdsize ksize, stdsize vsize, stdcmp_fcn kcmp) -{ - stdcode ret = STDESUCCESS; - stdint8 lvl; - stdtime t; - - if (ksize == 0) { - ret = STDEINVAL; - goto stdskl_construct_fail; - } - - l->size = 0; - l->ksize = ksize; - l->vsize = vsize; - l->cmp_fcn = kcmp; - - /* initialize randomization using current system time w/ subsecond precision */ - - stdtime_now(&t); - stdrand32_dseed(l->seed, stdhcode_sfh(&t, sizeof(t))); - l->bits_left = 0; - - /* allocate and init end_node -- NOTE: rest of list must be initialized b4 calling this fcn */ - - if ((l->end_node = stdskl_low_create_node(l, 4, NULL, NULL)) == NULL) { - ret = STDENOMEM; - goto stdskl_construct_fail; - } - - /* make end_node reference itself */ - - lvl = l->end_node->height; - - do { - l->end_node->nexts[lvl] = l->end_node; - l->end_node->prevs[lvl] = l->end_node; - - } while (lvl-- != 0); - - goto stdskl_construct_end; - - /* error handling and return */ - - stdskl_construct_fail: - l->end_node = NULL; - l->ksize = 0; /* make STDSKL_IS_LEGAL(l) false */ - - stdskl_construct_end: - return ret; -} - -/************************************************************************************************ - * stdskl_copy_construct: Construct a copy of a list. - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_copy_construct(stdskl *dst, const stdskl *src) -{ - stdcode ret; - stdit it; - - STDSAFETY_CHECK(STDSKL_IS_LEGAL(src)); - - if ((ret = stdskl_construct(dst, src->ksize, src->vsize, src->cmp_fcn)) != STDESUCCESS) { - goto stdskl_copy_construct_fail; - } - - if ((ret = stdskl_insert_seq_n(dst, NULL, stdskl_begin(src, &it), src->size, STDFALSE)) != STDESUCCESS) { - goto stdskl_copy_construct_fail2; - } - - goto stdskl_copy_construct_end; - - /* error handling and return */ - - stdskl_copy_construct_fail2: - stdskl_destruct(dst); - - stdskl_copy_construct_fail: - dst->end_node = NULL; - dst->ksize = 0; /* make STDSKL_IS_LEGAL(dst) false */ - - stdskl_copy_construct_end: - return ret; -} - -/************************************************************************************************ - * stdskl_destruct: Reclaim a list's resources and invalidate it. - ***********************************************************************************************/ - -STDINLINE void stdskl_destruct(stdskl *l) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - stdskl_clear(l); - free(l->end_node); - - l->end_node = NULL; - l->ksize = 0; /* make STDSKL_IS_LEGAL(l) false */ -} - -/************************************************************************************************ - * stdskl_set_eq: Set a list to contain the same contents as another. - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_set_eq(stdskl *dst, const stdskl *src) -{ - stdcode ret = STDESUCCESS; - stdskl cpy; - - STDSAFETY_CHECK(STDSKL_IS_LEGAL(dst) && STDSKL_IS_LEGAL(src) && - dst->ksize == src->ksize && dst->vsize == src->vsize && - dst->cmp_fcn == src->cmp_fcn); - - /* TODO: an improvement would be to resize the number of nodes in - the table as needed: just slice off or splice on an appropriate - sequence of nodes to the begin or end of the list and overwrite - all nodes: this would cut down on "unnecessary" memory - allocs/frees - */ - - if (dst == src) { - goto stdskl_set_eq_end; - } - - if ((ret = stdskl_copy_construct(&cpy, src)) != STDESUCCESS) { - goto stdskl_set_eq_end; - } - - stdskl_swap(dst, &cpy); - stdskl_destruct(&cpy); - - stdskl_set_eq_end: - return ret; -} - -/************************************************************************************************ - * stdskl_swap: Set a l1 to reference l2's sequence and vice versa. - ***********************************************************************************************/ - -STDINLINE void stdskl_swap(stdskl *l1, stdskl *l2) -{ - stdskl cpy; - - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l1) && STDSKL_IS_LEGAL(l2)); - - STDSWAP(*l1, *l2, cpy); -} - -/************************************************************************************************ - * stdskl_begin: Get an iterator to the beginning of a list. - ***********************************************************************************************/ - -STDINLINE stdit *stdskl_begin(const stdskl *l, stdit *it) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - it->type_id = STDSKL_IT_ID; - it->impl.skl.node = l->end_node->nexts[0]; - it->impl.skl.ksize = l->ksize; - it->impl.skl.vsize = l->vsize; - - return it; -} - -/************************************************************************************************ - * stdskl_last: Get an iterator to the last element of a list. - ***********************************************************************************************/ - -STDINLINE stdit *stdskl_last(const stdskl *l, stdit *it) -{ - STDBOUNDS_CHECK(l->size != 0); - - return stdit_prev(stdskl_end(l, it)); -} - -/************************************************************************************************ - * stdskl_end: Get an iterator to the sentinel end of a list. - ***********************************************************************************************/ - -STDINLINE stdit *stdskl_end(const stdskl *l, stdit *it) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - it->type_id = STDSKL_IT_ID; - it->impl.skl.node = l->end_node; - it->impl.skl.ksize = l->ksize; - it->impl.skl.vsize = l->vsize; - - return it; -} - -/************************************************************************************************ - * stdskl_get: Get an iterator to an element of a list. - ***********************************************************************************************/ - -STDINLINE stdit *stdskl_get(const stdskl *l, stdit *it, stdsize elem_num) -{ - STDBOUNDS_CHECK(elem_num <= l->size); - - if (elem_num < (l->size >> 1)) { - stdskl_it_advance(stdskl_begin(l, it), elem_num); - - } else { - stdskl_it_retreat(stdskl_end(l, it), l->size - elem_num); - } - - return it; -} - -/************************************************************************************************ - * stdskl_is_begin: Return whether or not an iterator refers to the beginning of a list. - ***********************************************************************************************/ - -STDINLINE stdbool stdskl_is_begin(const stdskl *l, const stdit *it) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl)); - - return it->impl.skl.node == l->end_node->nexts[0]; -} - -/************************************************************************************************ - * stdskl_is_end: Return whether or not an iterator refers to the end of a list. - ***********************************************************************************************/ - -STDINLINE stdbool stdskl_is_end(const stdskl *l, const stdit *it) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl)); - - return it->impl.skl.node == l->end_node; -} - -/************************************************************************************************ - * stdskl_size: Return the number of key-value pairs a list contains. - ***********************************************************************************************/ - -STDINLINE stdsize stdskl_size(const stdskl *l) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - return l->size; -} - -/************************************************************************************************ - * stdskl_empty: Return whether or not a list's size is zero. - ***********************************************************************************************/ - -STDINLINE stdbool stdskl_empty(const stdskl *l) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - return l->size == 0; -} - -/************************************************************************************************ - * stdskl_clear: Set a lists size to zero. - ***********************************************************************************************/ - -STDINLINE void stdskl_clear(stdskl *l) -{ - stdskl_node * curr; - stdskl_node * prev; - stdint8 lvl; - - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - /* run through list destroying all nodes */ - - for (curr = l->end_node->nexts[0]; curr != l->end_node; ) { - prev = curr; - curr = curr->nexts[0]; - free(prev); - } - - /* fix list entries: end_node needs to self reference at all levels and size */ - - curr = l->end_node; - lvl = l->end_node->height; - - do { - curr->prevs[lvl] = curr; - curr->nexts[lvl] = curr; - - } while (lvl-- != 0); - - l->size = 0; -} - -/************************************************************************************************ - * stdskl_find: Find a key-value pair in a list. - ***********************************************************************************************/ - -STDINLINE stdit *stdskl_find(const stdskl *l, stdit *it, const void *key) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - if (!stdskl_low_find_right(l, key, STDTRUE, &it->impl.skl.node)) { - it->impl.skl.node = l->end_node; - } - - it->type_id = STDSKL_IT_ID; - it->impl.skl.ksize = l->ksize; - it->impl.skl.vsize = l->vsize; - - return it; -} - -/************************************************************************************************ - * stdskl_lowerb: Find the least element for which kcmp(key, elem) >= 0. - ***********************************************************************************************/ - -STDINLINE stdit *stdskl_lowerb(const stdskl *l, stdit *it, const void *key) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - stdskl_low_find_right(l, key, STDFALSE, &it->impl.skl.node); - - it->type_id = STDSKL_IT_ID; - it->impl.skl.ksize = l->ksize; - it->impl.skl.vsize = l->vsize; - - return it; -} - -/************************************************************************************************ - * stdskl_upperb: Find the least element for which kcmp(key, elem) > 0. - ***********************************************************************************************/ - -STDINLINE stdit *stdskl_upperb(const stdskl *l, stdit *it, const void *key) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - stdskl_low_find_left(l, key, STDFALSE, &it->impl.skl.node); - it->impl.skl.node = it->impl.skl.node->nexts[0]; /* found either the last entry for key or the prev entry if none: so get next */ - - it->type_id = STDSKL_IT_ID; - it->impl.skl.ksize = l->ksize; - it->impl.skl.vsize = l->vsize; - - return it; -} - -/************************************************************************************************ - * stdskl_contains: Return whether or not a list contains a certain key. - ***********************************************************************************************/ - -STDINLINE stdbool stdskl_contains(const stdskl *l, const void *key) -{ - stdskl_node * n; - - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - return stdskl_low_find_right(l, key, STDTRUE, &n); -} - -/************************************************************************************************ - * stdskl_put: If 'key' already exists in the list, overwrite such an - * entry with 'key' and 'value;' otherwise insert 'key' and 'value' - * into the list. - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_put(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint) -{ - return stdskl_put_n(l, it, key, val, 1, hint); -} - -/************************************************************************************************ - * stdskl_put_n: For each (key, val) in [(keys, vals), (keys+num_put, vals+num_put)) - * perform stdskl_put(l, it, key, val). - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_put_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_put, stdbool hint) -{ - stdit b; - - return stdskl_put_seq_n(l, it, stdit_pptr(&b, keys, vals, l->ksize, l->vsize), num_put, hint); -} - -/************************************************************************************************ - * stdskl_put_seq: For each (key, val) in [b, e) perform - * stdskl_put(l, it, key, val). - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_put_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && (stdit_eq(b, e) || STDTRUE) && - (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) && - (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) && - (stdit_val_size(b) == l->vsize || l->vsize == 0)); - - return stdskl_low_insert(l, it, b, e, (stdsize) -1, hint, STDTRUE, STDTRUE); -} - -/************************************************************************************************ - * stdskl_put_seq_n: For each (key, val) in [b, b+num_put) perform - * stdskl_put(l, it, key, val). - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_put_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_put, stdbool hint) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && - (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) && - (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) && - (stdit_val_size(b) == l->vsize || l->vsize == 0)); - - return stdskl_low_insert(l, it, b, NULL, num_put, hint, STDTRUE, STDTRUE); -} - -/************************************************************************************************ - * stdskl_insert: Insert a key and value into a list. - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_insert(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint) -{ - return stdskl_insert_n(l, it, key, val, 1, hint); -} - -/************************************************************************************************ - * stdskl_insert_n: Insert multiple keys and values into a list. - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_insert_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_insert, stdbool hint) -{ - stdit b; - - return stdskl_insert_seq_n(l, it, stdit_pptr(&b, keys, vals, l->ksize, l->vsize), num_insert, hint); -} - -/************************************************************************************************ - * stdskl_insert_seq: Insert a sequence of key-value pairs into a list. - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_insert_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && (stdit_eq(b, e) || STDTRUE) && - (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) && - (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) && - (stdit_val_size(b) == l->vsize || l->vsize == 0)); - - return stdskl_low_insert(l, it, b, e, (stdsize) -1, hint, STDFALSE, STDTRUE); -} - -/************************************************************************************************ - * stdskl_insert_seq_n: Insert a sequence of key-value pairs into a list. - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_insert_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_insert, stdbool hint) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && - (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) && - (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) && - (stdit_val_size(b) == l->vsize || l->vsize == 0)); - - return stdskl_low_insert(l, it, b, NULL, num_insert, hint, STDFALSE, STDTRUE); -} - -/************************************************************************************************ - * stdskl_insert_rep: Repeatedly insert a key-value pair into a list. - ***********************************************************************************************/ - -STDINLINE stdcode stdskl_insert_rep(stdskl *l, stdit *it, const void *key, const void *val, stdsize num_times, stdbool hint) -{ - stdit b; - - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && - (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl)))); - - return stdskl_low_insert(l, it, stdit_pptr(&b, key, val, l->ksize, l->vsize), NULL, num_times, hint, STDFALSE, STDFALSE); -} - -/************************************************************************************************ - * stdskl_erase: Erase a key-value pair from a list. - ***********************************************************************************************/ - -STDINLINE void stdskl_erase(stdskl *l, stdit *it) -{ - stdskl_erase_n(l, it, 1); -} - -/************************************************************************************************ - * stdskl_erase_n: Erase multiple key-value pairs from a list. - ***********************************************************************************************/ - -STDINLINE void stdskl_erase_n(stdskl *l, stdit *it, stdsize num_erase) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl)); - - stdskl_low_erase(l, it, NULL, num_erase); -} - -/************************************************************************************************ - * stdskl_erase_seq: Erase a sequence from a list. - ***********************************************************************************************/ - -STDINLINE void stdskl_erase_seq(stdskl *l, stdit *b, stdit *e) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(b) && STDSKL_IT_IS_LEGAL(l, &b->impl.skl) && (stdit_eq(b, e) || STDTRUE)); - - stdskl_low_erase(l, b, e, (stdsize) -1); -} - -/************************************************************************************************ - * stdskl_erase_key: Erase all entries of a key from a list. - ***********************************************************************************************/ - -STDINLINE void stdskl_erase_key(stdskl *l, const void *key) -{ - stdit it; - - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - stdskl_lowerb(l, &it, key); - - while (it.impl.skl.node != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(it.impl.skl.node)) == 0) { - stdskl_erase(l, &it); /* advances 'it' */ - } -} - -/************************************************************************************************ - * stdskl_dseed: Set a skiplist's random number generator with a deterministic value. - ***********************************************************************************************/ - -STDINLINE void stdskl_dseed(stdskl *l, const void *seed, stdsize sizeof_seed) -{ - STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); - - stdrand32_dseed(l->seed, stdhcode_sfh(seed, sizeof_seed)); - l->bits_left = 0; -} - -/************************************************************************************************ - * stdskl_it_key: Get a key from an iterator. - ***********************************************************************************************/ - -STDINLINE const void *stdskl_it_key(const stdit *it) -{ - STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); - - return STDSKL_NKEY(it->impl.skl.node); -} - -/************************************************************************************************ - * stdskl_it_key_size: Get the size in bytes of the keys to which 'it' refers. - ***********************************************************************************************/ - -STDINLINE stdsize stdskl_it_key_size(const stdit *it) -{ - STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); - - return it->impl.skl.ksize; -} - -/************************************************************************************************ - * stdskl_it_val: Get a value from an iterator. - ***********************************************************************************************/ - -STDINLINE void *stdskl_it_val(const stdit *it) -{ - STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); - - return (void*) (it->type_id == STDSKL_IT_ID ? STDSKL_NVAL(it->impl.skl.node) : STDSKL_NKEY(it->impl.skl.node)); -} - -/************************************************************************************************ - * stdskl_it_val_size: Get the size in bytes of the values to which 'it' refers. - ***********************************************************************************************/ - -STDINLINE stdsize stdskl_it_val_size(const stdit *it) -{ - STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); - - return (it->type_id == STDSKL_IT_ID ? it->impl.skl.vsize : it->impl.skl.ksize); -} - -/************************************************************************************************ - * stdskl_it_eq: Compare two iterators for equality (refer to the same element). - ***********************************************************************************************/ - -STDINLINE stdbool stdskl_it_eq(const stdit *it1, const stdit *it2) -{ - STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it1) && STDIT_SKL_IS_LEGAL(it2) && - it1->impl.skl.ksize == it2->impl.skl.ksize && - it1->impl.skl.vsize == it2->impl.skl.vsize); - - return it1->impl.skl.node == it2->impl.skl.node; -} - -/************************************************************************************************ - * stdskl_it_next: Advance 'it' towards end by one position. - ***********************************************************************************************/ - -STDINLINE stdit *stdskl_it_next(stdit *it) -{ - STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); - - it->impl.skl.node = it->impl.skl.node->nexts[0]; - - return it; -} - -/************************************************************************************************ - * stdskl_it_advance: Advance 'it' towards end by 'num_advance' positions. - ***********************************************************************************************/ - -STDINLINE stdit *stdskl_it_advance(stdit *it, stdsize num_advance) -{ - STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); - - while (num_advance-- != 0) { - it->impl.skl.node = it->impl.skl.node->nexts[0]; - } - - return it; -} - -/************************************************************************************************ - * stdskl_it_prev: Advance 'it' towards begin by one position. - ***********************************************************************************************/ - -STDINLINE stdit *stdskl_it_prev(stdit *it) -{ - STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); - - it->impl.skl.node = it->impl.skl.node->prevs[0]; - - return it; -} - -/************************************************************************************************ - * stdskl_it_retreat: Advance 'it' towards end by 'num_retreat' positions. - ***********************************************************************************************/ - -STDINLINE stdit *stdskl_it_retreat(stdit *it, stdsize num_retreat) -{ - STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); - - while (num_retreat-- != 0) { - it->impl.skl.node = it->impl.skl.node->prevs[0]; - } - - return it; -} - -#ifdef __cplusplus -} -#endif +/* Copyright (c) 2000-2009, The Johns Hopkins University + * All rights reserved. + * + * The contents of this file are subject to a license (the ``License''). + * You may not use this file except in compliance with the License. The + * specific language governing the rights and limitations of the License + * can be found in the file ``STDUTIL_LICENSE'' found in this + * distribution. + * + * Software distributed under the License is distributed on an AS IS + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. + * + * The Original Software is: + * The Stdutil Library + * + * Contributors: + * Creator - John Lane Schultz ([email protected]) + * The Center for Networking and Distributed Systems + * (CNDS - http://www.cnds.jhu.edu) + */ + +#include <stdlib.h> +#include <string.h> + +#include <stdutil/stdutil.h> +#include <stdutil/stderror.h> +#include <stdutil/stdtime.h> +#include <stdutil/stdskl.h> + +#ifdef __cplusplus +extern "C" { +#endif + +/* TODO: consider shrinking end_node's arrays when the top level + becomes empty (down to some minimum height like 4 or 5); this is + easy to detect: if the node being removed has the same height as + the end_node and his top level prev and next are the end node then + the level is about to become empty; alternatively after removal you + can just check the top levels for self reference; also might not + want to make end_node taller than the tallest node on insert -- + don't know how big an effect on find this will have as find as it + will simply run down end_node's nexts array while next equals + end_node not doing any real work +*/ + +#define STDSKL_MAX_HEIGHT 31 + +#define STDSKL_IS_LEGAL(l) ((l)->end_node != NULL && (l)->ksize != 0 && (l)->bits_left >= 0 && (l)->bits_left < 32) +#define STDSKL_IT_IS_LEGAL(l, i) ((i)->ksize == (l)->ksize && (i)->vsize == (l)->vsize) +#define STDIT_SKL_IS_LEGAL(i) (((i)->type_id == STDSKL_IT_ID || (i)->type_id == STDSKL_IT_KEY_ID) && \ + (i)->impl.skl.node != NULL && (i)->impl.skl.ksize != 0) + +#define STDSKL_NKEY(node) ((node)->key) +#define STDSKL_NVAL(node) ((node)->val) + +/************************************************************************************************ + * stdskl_low_key_cmp: Compares 2 keys, uses memcmp if no comparison fcn defined. + ***********************************************************************************************/ + +STDINLINE static int stdskl_low_key_cmp(const stdskl *l, const void *k1, const void *k2) +{ + return (l->cmp_fcn == NULL ? memcmp(k1, k2, l->ksize) : l->cmp_fcn(k1, k2)); +} + +/************************************************************************************************ + * stdskl_low_create_node: Create a node to be inserted into 'l.' + * + * For random height generation, a node is promoted to a higher height + * w/ 25% chance. The optimum promotion chance for a skiplist is + * somewhere between 28% and 37% depending on the analysis used. 25% + * gives nearly optimal performance while using less memory and not + * requiring excessive random bit generation. + ***********************************************************************************************/ + +STDINLINE static stdskl_node *stdskl_low_create_node(stdskl *l, stdint8 height, const void *key, const void *val) +{ + stdskl_node * node; + stdsize mem_tot; + stdsize prevs_off; + stdsize nexts_off; + stdsize key_off; + stdsize val_off; + + if (height == -1) { /* height generation requested */ + stdbool keep_going = STDTRUE; + + for (; keep_going && height < STDSKL_MAX_HEIGHT; ++height) { /* loop while random height increases */ + + if (l->bits_left == 0) { /* out of random bits */ + l->rand_bits = stdrand32(l->seed); /* generate 32 new ones */ + l->bits_left = 32; + } + + keep_going = ((l->rand_bits & 0x3) == 0x3); /* continue loop w/ 25% chance */ + l->bits_left -= 2; /* remove used bits */ + l->rand_bits >>= 2; + } + } + + /* calculate memory needed for node and pointer arrays and the offsets for the pointers in the node */ + + mem_tot = sizeof(stdskl_node); /* memory for node structure */ + prevs_off = mem_tot; /* structure is already aligned for void*'s -> good enough alignment */ + + mem_tot += (height + 1) * sizeof(stdskl_node*); /* memory for prevs array */ + nexts_off = mem_tot; /* structure is already aligned for void*'s -> good enough alignment */ + + mem_tot += (height + 1) * sizeof(stdskl_node*); /* memory for nexts array */ + mem_tot = STDARCH_PADDED_SIZE(mem_tot); /* pad memory for key */ + key_off = mem_tot; + + mem_tot += STDARCH_PADDED_SIZE(l->ksize); /* memory for key and padding for value */ + val_off = mem_tot; + + mem_tot += l->vsize; /* memory for value */ + + /* allocate the node and extra memory */ + + if ((node = (stdskl_node*) malloc(mem_tot)) == NULL) { + goto stdskl_low_create_node_end; + } + + /* init node: set height, point pointers to appropriate offsets in allocated memory block */ + + node->height = height; + node->prevs = (stdskl_node**) ((char*) node + prevs_off); + node->nexts = (stdskl_node**) ((char*) node + nexts_off); + node->key = (char*) node + key_off; + node->val = (char*) node + val_off; + + /* copy key + value if given */ + + if (key != NULL) { + memcpy((void*) STDSKL_NKEY(node), key, l->ksize); + memcpy(STDSKL_NVAL(node), val, l->vsize); + } + + stdskl_low_create_node_end: + return node; +} + +/************************************************************************************************ + * stdskl_low_find_right: Search 'l' for 'key' from left to right. + * + * If (find_any) immediately return on any match. Otherwise if 'key' + * exists in 'l' return the "leftmost" (least) match if multiple + * matches exist. On no match, returns the "leftmost" (least) entry + * in 'l' with a greater key, or end if no such entry exists. + ***********************************************************************************************/ + +STDINLINE static stdbool stdskl_low_find_right(const stdskl *l, const void *key, + stdbool find_any, stdskl_node **pos) +{ + const stdskl_node * next = NULL; + const stdskl_node * curr = l->end_node; + stdint8 lvl = l->end_node->height; + int cmp = -1; /* get rid of compiler warning */ + + /* run down to bottom level list */ + + while (lvl > 0) { + next = curr->nexts[lvl]; + + /* run right at this level while key is greater than next's key */ + + while (next != l->end_node && + (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) { + curr = next; + next = next->nexts[lvl]; + } + + /* if we found a match and any match will do */ + + if (find_any && next != l->end_node && cmp == 0) { + *pos = (stdskl_node*) next; + return STDTRUE; + } + + /* run down curr's levels while they equal next */ + + for (--lvl; lvl > 0 && curr->nexts[lvl] == next; --lvl); + } + + /* lvl is zero: run right on bottom level list trying to match key */ + + curr = curr->nexts[0]; + + if (curr != next) { + + while (curr != l->end_node && + (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(curr))) > 0) { + curr = curr->nexts[0]; + } + } /* else we already compared key to curr above */ + + *pos = (stdskl_node*) curr; + + return (curr != l->end_node && cmp == 0); +} + +/************************************************************************************************ + * stdskl_low_find_left: Search 'l' for 'key' from right to left. + * + * If (find_any) immediately return on any match. Otherwise if 'key' + * exists in 'l' return the "rightmost" (greatest) match if multiple + * matches exist. On no match, returns the "rightmost" (greatest) + * entry in 'l' with a lesser key, or end if no such entry exists. + ***********************************************************************************************/ + +STDINLINE static stdbool stdskl_low_find_left(const stdskl *l, const void *key, + stdbool find_any, stdskl_node **pos) +{ + const stdskl_node * prev = NULL; + const stdskl_node * curr = l->end_node; + stdint8 lvl = l->end_node->height; + int cmp = -1; /* get rid of compiler warning */ + + /* run down to bottom level list */ + + while (lvl > 0) { + prev = curr->prevs[lvl]; + + /* run left at this level while key is less than prev's key */ + + while (prev != l->end_node && + (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev))) < 0) { + curr = prev; + prev = prev->prevs[lvl]; + } + + /* if we found a match and any match will do */ + + if (find_any && prev != l->end_node && cmp == 0) { + *pos = (stdskl_node*) prev; + return STDTRUE; + } + + /* run down curr's prevs levels while they equal prev */ + + for (--lvl; lvl > 0 && curr->prevs[lvl] == prev; --lvl); + } + + /* run left on bottom level list trying to match key */ + + curr = curr->prevs[0]; + + if (curr != prev) { + + while (curr != l->end_node && + (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(curr))) < 0) { + curr = curr->prevs[0]; + } + } /* else we already compared key to curr above */ + + *pos = (stdskl_node*) curr; + + return (curr != l->end_node && cmp == 0); +} + +/************************************************************************************************ + * stdskl_low_link_right: Link 'node' into entries greater than or + * equal to 'ins_pos' in 'l.' + ***********************************************************************************************/ + +STDINLINE static void stdskl_low_link_right(const stdskl *l, stdskl_node *ins_pos, stdskl_node *node) +{ + stdskl_node * next = ins_pos; + stdint8 height = node->height; + stdint8 lvl = 0; + + node->nexts[0] = next; + next->prevs[0] = node; + + while (lvl != height) { + + /* if we've maxed out next's height, then find a later, taller node on this lvl */ + + while (lvl == next->height) { /* NOTE: node->height <= end_node->height -> lvl < end_node->height here */ + next = next->nexts[lvl]; /* so we can't erroneously wrap around past sentinel end node here */ + } + + ++lvl; + node->nexts[lvl] = next; + next->prevs[lvl] = node; + } +} + +/************************************************************************************************ + * stdskl_low_link_left: Link in 'node' to entries less than 'ins_pos' + * in 'l.' + ***********************************************************************************************/ + +STDINLINE static void stdskl_low_link_left(const stdskl *l, stdskl_node *ins_pos, stdskl_node *node) +{ + stdskl_node * prev = ins_pos->prevs[0]; /* NOTE: this is why we must link_left b4 link_right in insert! */ + stdint8 height = node->height; + stdint8 lvl = 0; + + node->prevs[0] = prev; + prev->nexts[0] = node; + + while (lvl != height) { + + /* if we've maxed out prev's height, then find an earlier, taller node on this lvl */ + + while (lvl == prev->height) { /* NOTE: node->height <= end_node->height -> lvl < end_node->height here */ + prev = prev->prevs[lvl]; /* so we can't erroneously wrap around past sentinel end node here */ + } + + ++lvl; + node->prevs[lvl] = prev; + prev->nexts[lvl] = node; + } +} + +/************************************************************************************************ + * stdskl_low_insert: Insert multiple keys and values into a list + * using an iterator sequence with various options. + ***********************************************************************************************/ + +STDINLINE static stdcode stdskl_low_insert(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdsize num_ins, + stdbool hint, stdbool overwrite, stdbool advance) +{ + stdcode ret = STDESUCCESS; + stdskl_node * node; + stdskl_node * prev; + stdskl_node * next = (it != NULL ? it->impl.skl.node : l->end_node); + stdskl_node * first_ins = NULL; + stdit src_it = *b; + stdbool keyed = (stdit_key_size(b) != 0); + stdint8 lvl; + const void * key; + const void * val; + int cmp; + + /* loop over input sequence defined either by [b, b+num_ins) or [b, e) */ + + while (num_ins-- != 0 && (e == NULL || !stdit_eq(&src_it, e))) { + + /* get pointers to the key and value we are about to insert */ + + val = stdit_val(&src_it); + key = (keyed ? stdit_key(&src_it) : val); + cmp = -1; + + /* get insertion position for this key: next */ + + if (hint) { /* 'next' is a potential insertion point -> verify! */ + prev = next->prevs[0]; + + if ((next != l->end_node && (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) || + (prev != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev)) < 0)) { + + prev = next; + next = next->nexts[0]; /* next was inappropriate; try ++next */ + cmp = -1; + + if ((next != l->end_node && (cmp = stdskl_low_key_cmp(l, key, STDSKL_NKEY(next))) > 0) || + (prev != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(prev)) < 0)) { + hint = STDFALSE; /* both next and ++next were inappropriate: do a full search */ + } + } + } + + if (!hint) { + cmp = !stdskl_low_find_right(l, key, STDTRUE, &next); + } + + hint = STDTRUE; /* use next as a hint for following iteration (optimize for nearly contiguous, sorted inserts) */ + + /* create + insert new node; or overwrite pre-existing match if so instructed and appropriate */ + + if (!overwrite || next == l->end_node || cmp != 0) { /* create new node to insert */ + + if ((node = stdskl_low_create_node(l, -1, key, val)) == NULL) { /* create a node with a random height */ + ret = STDENOMEM; + goto stdskl_low_insert_end; + } + + /* ensure that l->end_node is at least as tall as the new node */ + + if (node->height > l->end_node->height) { + stdskl_node * new_end; + + /* ratchet up new end_node's height to be at least 1 level higher (usually 2) than before */ + + lvl = node->height; /* 0 <= node->height <= STDSKL_MAX_HEIGHT */ + + if (lvl < STDSKL_MAX_HEIGHT) { + ++lvl; + } + + if ((new_end = stdskl_low_create_node(l, lvl, NULL, NULL)) == NULL) { + ret = STDENOMEM; + goto stdskl_low_insert_fail; + } + + /* set new_end's nexts and prevs and update nodes ref'ing end_node to now point to new_end */ + /* loop while we haven't updated all levels of the lists AND end_node is NOT self-referring */ + + lvl = 0; + do { + + if (l->end_node->prevs[lvl] == l->end_node) { /* break on end_node referring to itself -> */ + break; /* all prevs, nexts of this and higher lvls are self-referring */ + } + + new_end->prevs[lvl] = l->end_node->prevs[lvl]; + l->end_node->prevs[lvl]->nexts[lvl] = new_end; + + new_end->nexts[lvl] = l->end_node->nexts[lvl]; + l->end_node->nexts[lvl]->prevs[lvl] = new_end; + + } while (lvl++ != l->end_node->height); + + /* set additional lvls in new_end to be self-referencing. NOTE: new_end is at least 1 lvl taller than end_node */ + + do { + new_end->prevs[lvl] = new_end; + new_end->nexts[lvl] = new_end; + + } while (lvl++ != new_end->height); + + /* correct next if it referenced the end_node */ + + if (next == l->end_node) { + next = new_end; + } + + free(l->end_node); + l->end_node = new_end; + } + + /* link 'node' into list before next */ + + stdskl_low_link_left(l, next, node); /* NOTE: we must link_left before we link_right due to loss of information */ + stdskl_low_link_right(l, next, node); + + ++l->size; + + } else { /* overwrite existing match */ + node = next; + memcpy((void*) STDSKL_NKEY(node), key, l->ksize); /* overwrite */ + memcpy(STDSKL_NVAL(node), val, l->vsize); + } + + /* remember first insertion/overwrite */ + + if (first_ins == NULL) { + first_ins = node; + } + + /* advance 'src_it' if so instructed */ + + if (advance) { + stdit_next(&src_it); + } + } + + goto stdskl_low_insert_end; + + /* error handling and return */ + + stdskl_low_insert_fail: + free(node); + + stdskl_low_insert_end: + if (it != NULL) { + it->type_id = STDSKL_IT_ID; + it->impl.skl.node = (first_ins != NULL ? first_ins : l->end_node); /* point to end if no insert/overwrite occurred */ + it->impl.skl.ksize = l->ksize; + it->impl.skl.vsize = l->vsize; + } + + return ret; +} + +/************************************************************************************************ + * stdskl_low_erase: Erase multiple key-value pairs from a list using + * either an iterator sequence to delete or a number of elements to + * erase. + ***********************************************************************************************/ + +STDINLINE static stdsize stdskl_low_erase(stdskl *l, stdit *b, stdit *e, stdsize num_erase) +{ + stdskl_node * ers; + stdskl_node * prev = b->impl.skl.node->prevs[0]; + stdskl_node * next = b->impl.skl.node; + stdskl_node * end_node = (e != NULL ? e->impl.skl.node : NULL); + stdint8 max_lvl = 0; + stdsize erased; + stdint8 lvl; + + /* go through [b, b+num_erase) or [b, e) free'ing nodes -- record + max height of free'd nodes and how many nodes we erased + */ + + for (erased = 0; erased != num_erase && next != end_node; ++erased) { + STDBOUNDS_CHECK(next != l->end_node); + + if (next->height > max_lvl) { + max_lvl = next->height; + } + + ers = next; + next = next->nexts[0]; + free(ers); + } + + /* update list size */ + + l->size -= erased; + + /* stitch together the left and right portions of the list */ + + ers = next; /* remember where erasure stopped */ + prev->nexts[0] = next; /* perform base re-linkage */ + next->prevs[0] = prev; + + for (lvl = 0; lvl != max_lvl; ) { /* run left and run right up to max_lvl height nodes re-linking */ + + while (lvl == prev->height) { + prev = prev->prevs[lvl]; + } + + while (lvl == next->height) { + next = next->nexts[lvl]; + } + + ++lvl; + prev->nexts[lvl] = next; + next->prevs[lvl] = prev; + } + + /* advance 'b' and 'e' */ + + b->impl.skl.node = ers; + + if (e != NULL) { + e->impl.skl.node = ers; + } + + return erased; +} + +/************************************************************************************************ + * stdskl_construct: Construct an initially empty list. + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_construct(stdskl *l, stdsize ksize, stdsize vsize, stdcmp_fcn kcmp) +{ + stdcode ret = STDESUCCESS; + stdint8 lvl; + stdtime t; + + if (ksize == 0) { + ret = STDEINVAL; + goto stdskl_construct_fail; + } + + l->size = 0; + l->ksize = ksize; + l->vsize = vsize; + l->cmp_fcn = kcmp; + + /* initialize randomization using current system time w/ subsecond precision */ + + stdtime_now(&t); + stdrand32_dseed(l->seed, stdhcode_sfh(&t, sizeof(t))); + l->bits_left = 0; + + /* allocate and init end_node -- NOTE: rest of list must be initialized b4 calling this fcn */ + + if ((l->end_node = stdskl_low_create_node(l, 4, NULL, NULL)) == NULL) { + ret = STDENOMEM; + goto stdskl_construct_fail; + } + + /* make end_node reference itself */ + + lvl = l->end_node->height; + + do { + l->end_node->nexts[lvl] = l->end_node; + l->end_node->prevs[lvl] = l->end_node; + + } while (lvl-- != 0); + + goto stdskl_construct_end; + + /* error handling and return */ + + stdskl_construct_fail: + l->end_node = NULL; + l->ksize = 0; /* make STDSKL_IS_LEGAL(l) false */ + + stdskl_construct_end: + return ret; +} + +/************************************************************************************************ + * stdskl_copy_construct: Construct a copy of a list. + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_copy_construct(stdskl *dst, const stdskl *src) +{ + stdcode ret; + stdit it; + + STDSAFETY_CHECK(STDSKL_IS_LEGAL(src)); + + if ((ret = stdskl_construct(dst, src->ksize, src->vsize, src->cmp_fcn)) != STDESUCCESS) { + goto stdskl_copy_construct_fail; + } + + if ((ret = stdskl_insert_seq_n(dst, NULL, stdskl_begin(src, &it), src->size, STDFALSE)) != STDESUCCESS) { + goto stdskl_copy_construct_fail2; + } + + goto stdskl_copy_construct_end; + + /* error handling and return */ + + stdskl_copy_construct_fail2: + stdskl_destruct(dst); + + stdskl_copy_construct_fail: + dst->end_node = NULL; + dst->ksize = 0; /* make STDSKL_IS_LEGAL(dst) false */ + + stdskl_copy_construct_end: + return ret; +} + +/************************************************************************************************ + * stdskl_destruct: Reclaim a list's resources and invalidate it. + ***********************************************************************************************/ + +STDINLINE void stdskl_destruct(stdskl *l) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + stdskl_clear(l); + free(l->end_node); + + l->end_node = NULL; + l->ksize = 0; /* make STDSKL_IS_LEGAL(l) false */ +} + +/************************************************************************************************ + * stdskl_set_eq: Set a list to contain the same contents as another. + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_set_eq(stdskl *dst, const stdskl *src) +{ + stdcode ret = STDESUCCESS; + stdskl cpy; + + STDSAFETY_CHECK(STDSKL_IS_LEGAL(dst) && STDSKL_IS_LEGAL(src) && + dst->ksize == src->ksize && dst->vsize == src->vsize && + dst->cmp_fcn == src->cmp_fcn); + + /* TODO: an improvement would be to resize the number of nodes in + the table as needed: just slice off or splice on an appropriate + sequence of nodes to the begin or end of the list and overwrite + all nodes: this would cut down on "unnecessary" memory + allocs/frees + */ + + if (dst == src) { + goto stdskl_set_eq_end; + } + + if ((ret = stdskl_copy_construct(&cpy, src)) != STDESUCCESS) { + goto stdskl_set_eq_end; + } + + stdskl_swap(dst, &cpy); + stdskl_destruct(&cpy); + + stdskl_set_eq_end: + return ret; +} + +/************************************************************************************************ + * stdskl_swap: Set a l1 to reference l2's sequence and vice versa. + ***********************************************************************************************/ + +STDINLINE void stdskl_swap(stdskl *l1, stdskl *l2) +{ + stdskl cpy; + + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l1) && STDSKL_IS_LEGAL(l2)); + + STDSWAP(*l1, *l2, cpy); +} + +/************************************************************************************************ + * stdskl_begin: Get an iterator to the beginning of a list. + ***********************************************************************************************/ + +STDINLINE stdit *stdskl_begin(const stdskl *l, stdit *it) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + it->type_id = STDSKL_IT_ID; + it->impl.skl.node = l->end_node->nexts[0]; + it->impl.skl.ksize = l->ksize; + it->impl.skl.vsize = l->vsize; + + return it; +} + +/************************************************************************************************ + * stdskl_last: Get an iterator to the last element of a list. + ***********************************************************************************************/ + +STDINLINE stdit *stdskl_last(const stdskl *l, stdit *it) +{ + STDBOUNDS_CHECK(l->size != 0); + + return stdit_prev(stdskl_end(l, it)); +} + +/************************************************************************************************ + * stdskl_end: Get an iterator to the sentinel end of a list. + ***********************************************************************************************/ + +STDINLINE stdit *stdskl_end(const stdskl *l, stdit *it) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + it->type_id = STDSKL_IT_ID; + it->impl.skl.node = l->end_node; + it->impl.skl.ksize = l->ksize; + it->impl.skl.vsize = l->vsize; + + return it; +} + +/************************************************************************************************ + * stdskl_get: Get an iterator to an element of a list. + ***********************************************************************************************/ + +STDINLINE stdit *stdskl_get(const stdskl *l, stdit *it, stdsize elem_num) +{ + STDBOUNDS_CHECK(elem_num <= l->size); + + if (elem_num < (l->size >> 1)) { + stdskl_it_advance(stdskl_begin(l, it), elem_num); + + } else { + stdskl_it_retreat(stdskl_end(l, it), l->size - elem_num); + } + + return it; +} + +/************************************************************************************************ + * stdskl_is_begin: Return whether or not an iterator refers to the beginning of a list. + ***********************************************************************************************/ + +STDINLINE stdbool stdskl_is_begin(const stdskl *l, const stdit *it) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl)); + + return it->impl.skl.node == l->end_node->nexts[0]; +} + +/************************************************************************************************ + * stdskl_is_end: Return whether or not an iterator refers to the end of a list. + ***********************************************************************************************/ + +STDINLINE stdbool stdskl_is_end(const stdskl *l, const stdit *it) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl)); + + return it->impl.skl.node == l->end_node; +} + +/************************************************************************************************ + * stdskl_size: Return the number of key-value pairs a list contains. + ***********************************************************************************************/ + +STDINLINE stdsize stdskl_size(const stdskl *l) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + return l->size; +} + +/************************************************************************************************ + * stdskl_empty: Return whether or not a list's size is zero. + ***********************************************************************************************/ + +STDINLINE stdbool stdskl_empty(const stdskl *l) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + return l->size == 0; +} + +/************************************************************************************************ + * stdskl_clear: Set a lists size to zero. + ***********************************************************************************************/ + +STDINLINE void stdskl_clear(stdskl *l) +{ + stdskl_node * curr; + stdskl_node * prev; + stdint8 lvl; + + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + /* run through list destroying all nodes */ + + for (curr = l->end_node->nexts[0]; curr != l->end_node; ) { + prev = curr; + curr = curr->nexts[0]; + free(prev); + } + + /* fix list entries: end_node needs to self reference at all levels and size */ + + curr = l->end_node; + lvl = l->end_node->height; + + do { + curr->prevs[lvl] = curr; + curr->nexts[lvl] = curr; + + } while (lvl-- != 0); + + l->size = 0; +} + +/************************************************************************************************ + * stdskl_find: Find a key-value pair in a list. + ***********************************************************************************************/ + +STDINLINE stdit *stdskl_find(const stdskl *l, stdit *it, const void *key) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + if (!stdskl_low_find_right(l, key, STDTRUE, &it->impl.skl.node)) { + it->impl.skl.node = l->end_node; + } + + it->type_id = STDSKL_IT_ID; + it->impl.skl.ksize = l->ksize; + it->impl.skl.vsize = l->vsize; + + return it; +} + +/************************************************************************************************ + * stdskl_lowerb: Find the least element for which kcmp(key, elem) >= 0. + ***********************************************************************************************/ + +STDINLINE stdit *stdskl_lowerb(const stdskl *l, stdit *it, const void *key) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + stdskl_low_find_right(l, key, STDFALSE, &it->impl.skl.node); + + it->type_id = STDSKL_IT_ID; + it->impl.skl.ksize = l->ksize; + it->impl.skl.vsize = l->vsize; + + return it; +} + +/************************************************************************************************ + * stdskl_upperb: Find the least element for which kcmp(key, elem) > 0. + ***********************************************************************************************/ + +STDINLINE stdit *stdskl_upperb(const stdskl *l, stdit *it, const void *key) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + stdskl_low_find_left(l, key, STDFALSE, &it->impl.skl.node); + it->impl.skl.node = it->impl.skl.node->nexts[0]; /* found either the last entry for key or the prev entry if none: so get next */ + + it->type_id = STDSKL_IT_ID; + it->impl.skl.ksize = l->ksize; + it->impl.skl.vsize = l->vsize; + + return it; +} + +/************************************************************************************************ + * stdskl_contains: Return whether or not a list contains a certain key. + ***********************************************************************************************/ + +STDINLINE stdbool stdskl_contains(const stdskl *l, const void *key) +{ + stdskl_node * n; + + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + return stdskl_low_find_right(l, key, STDTRUE, &n); +} + +/************************************************************************************************ + * stdskl_put: If 'key' already exists in the list, overwrite such an + * entry with 'key' and 'value;' otherwise insert 'key' and 'value' + * into the list. + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_put(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint) +{ + return stdskl_put_n(l, it, key, val, 1, hint); +} + +/************************************************************************************************ + * stdskl_put_n: For each (key, val) in [(keys, vals), (keys+num_put, vals+num_put)) + * perform stdskl_put(l, it, key, val). + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_put_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_put, stdbool hint) +{ + stdit b; + + return stdskl_put_seq_n(l, it, stdit_pptr(&b, keys, vals, l->ksize, l->vsize), num_put, hint); +} + +/************************************************************************************************ + * stdskl_put_seq: For each (key, val) in [b, e) perform + * stdskl_put(l, it, key, val). + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_put_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && (stdit_eq(b, e) || STDTRUE) && + (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) && + (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) && + (stdit_val_size(b) == l->vsize || l->vsize == 0)); + + return stdskl_low_insert(l, it, b, e, (stdsize) -1, hint, STDTRUE, STDTRUE); +} + +/************************************************************************************************ + * stdskl_put_seq_n: For each (key, val) in [b, b+num_put) perform + * stdskl_put(l, it, key, val). + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_put_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_put, stdbool hint) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && + (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) && + (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) && + (stdit_val_size(b) == l->vsize || l->vsize == 0)); + + return stdskl_low_insert(l, it, b, NULL, num_put, hint, STDTRUE, STDTRUE); +} + +/************************************************************************************************ + * stdskl_insert: Insert a key and value into a list. + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_insert(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint) +{ + return stdskl_insert_n(l, it, key, val, 1, hint); +} + +/************************************************************************************************ + * stdskl_insert_n: Insert multiple keys and values into a list. + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_insert_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_insert, stdbool hint) +{ + stdit b; + + return stdskl_insert_seq_n(l, it, stdit_pptr(&b, keys, vals, l->ksize, l->vsize), num_insert, hint); +} + +/************************************************************************************************ + * stdskl_insert_seq: Insert a sequence of key-value pairs into a list. + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_insert_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && (stdit_eq(b, e) || STDTRUE) && + (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) && + (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) && + (stdit_val_size(b) == l->vsize || l->vsize == 0)); + + return stdskl_low_insert(l, it, b, e, (stdsize) -1, hint, STDFALSE, STDTRUE); +} + +/************************************************************************************************ + * stdskl_insert_seq_n: Insert a sequence of key-value pairs into a list. + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_insert_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_insert, stdbool hint) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && + (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl))) && + (stdit_key_size(b) == l->ksize || (stdit_key_size(b) == 0 && stdit_val_size(b) == l->ksize)) && + (stdit_val_size(b) == l->vsize || l->vsize == 0)); + + return stdskl_low_insert(l, it, b, NULL, num_insert, hint, STDFALSE, STDTRUE); +} + +/************************************************************************************************ + * stdskl_insert_rep: Repeatedly insert a key-value pair into a list. + ***********************************************************************************************/ + +STDINLINE stdcode stdskl_insert_rep(stdskl *l, stdit *it, const void *key, const void *val, stdsize num_times, stdbool hint) +{ + stdit b; + + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && + (!hint || (it != NULL && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl)))); + + return stdskl_low_insert(l, it, stdit_pptr(&b, key, val, l->ksize, l->vsize), NULL, num_times, hint, STDFALSE, STDFALSE); +} + +/************************************************************************************************ + * stdskl_erase: Erase a key-value pair from a list. + ***********************************************************************************************/ + +STDINLINE void stdskl_erase(stdskl *l, stdit *it) +{ + stdskl_erase_n(l, it, 1); +} + +/************************************************************************************************ + * stdskl_erase_n: Erase multiple key-value pairs from a list. + ***********************************************************************************************/ + +STDINLINE void stdskl_erase_n(stdskl *l, stdit *it, stdsize num_erase) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(it) && STDSKL_IT_IS_LEGAL(l, &it->impl.skl)); + + stdskl_low_erase(l, it, NULL, num_erase); +} + +/************************************************************************************************ + * stdskl_erase_seq: Erase a sequence from a list. + ***********************************************************************************************/ + +STDINLINE stdsize stdskl_erase_seq(stdskl *l, stdit *b, stdit *e) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l) && STDIT_SKL_IS_LEGAL(b) && STDSKL_IT_IS_LEGAL(l, &b->impl.skl) && (stdit_eq(b, e) || STDTRUE)); + + return stdskl_low_erase(l, b, e, (stdsize) -1); +} + +/************************************************************************************************ + * stdskl_erase_key: Erase all entries of a key from a list. + ***********************************************************************************************/ + +STDINLINE stdsize stdskl_erase_key(stdskl *l, const void *key) +{ + stdsize ret = 0; + stdit it; + + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + stdskl_lowerb(l, &it, key); + + for (; it.impl.skl.node != l->end_node && stdskl_low_key_cmp(l, key, STDSKL_NKEY(it.impl.skl.node)) == 0; ++ret) { + stdskl_erase(l, &it); /* advances 'it' */ + } + + return ret; +} + +/************************************************************************************************ + * stdskl_dseed: Set a skiplist's random number generator with a deterministic value. + ***********************************************************************************************/ + +STDINLINE void stdskl_dseed(stdskl *l, const void *seed, stdsize sizeof_seed) +{ + STDSAFETY_CHECK(STDSKL_IS_LEGAL(l)); + + stdrand32_dseed(l->seed, stdhcode_sfh(seed, sizeof_seed)); + l->bits_left = 0; +} + +/************************************************************************************************ + * stdskl_it_key: Get a key from an iterator. + ***********************************************************************************************/ + +STDINLINE const void *stdskl_it_key(const stdit *it) +{ + STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); + + return STDSKL_NKEY(it->impl.skl.node); +} + +/************************************************************************************************ + * stdskl_it_key_size: Get the size in bytes of the keys to which 'it' refers. + ***********************************************************************************************/ + +STDINLINE stdsize stdskl_it_key_size(const stdit *it) +{ + STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); + + return it->impl.skl.ksize; +} + +/************************************************************************************************ + * stdskl_it_val: Get a value from an iterator. + ***********************************************************************************************/ + +STDINLINE void *stdskl_it_val(const stdit *it) +{ + STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); + + return (void*) (it->type_id == STDSKL_IT_ID ? STDSKL_NVAL(it->impl.skl.node) : STDSKL_NKEY(it->impl.skl.node)); +} + +/************************************************************************************************ + * stdskl_it_val_size: Get the size in bytes of the values to which 'it' refers. + ***********************************************************************************************/ + +STDINLINE stdsize stdskl_it_val_size(const stdit *it) +{ + STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); + + return (it->type_id == STDSKL_IT_ID ? it->impl.skl.vsize : it->impl.skl.ksize); +} + +/************************************************************************************************ + * stdskl_it_eq: Compare two iterators for equality (refer to the same element). + ***********************************************************************************************/ + +STDINLINE stdbool stdskl_it_eq(const stdit *it1, const stdit *it2) +{ + STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it1) && STDIT_SKL_IS_LEGAL(it2) && + it1->impl.skl.ksize == it2->impl.skl.ksize && + it1->impl.skl.vsize == it2->impl.skl.vsize); + + return it1->impl.skl.node == it2->impl.skl.node; +} + +/************************************************************************************************ + * stdskl_it_next: Advance 'it' towards end by one position. + ***********************************************************************************************/ + +STDINLINE stdit *stdskl_it_next(stdit *it) +{ + STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); + + it->impl.skl.node = it->impl.skl.node->nexts[0]; + + return it; +} + +/************************************************************************************************ + * stdskl_it_advance: Advance 'it' towards end by 'num_advance' positions. + ***********************************************************************************************/ + +STDINLINE stdit *stdskl_it_advance(stdit *it, stdsize num_advance) +{ + STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); + + while (num_advance-- != 0) { + it->impl.skl.node = it->impl.skl.node->nexts[0]; + } + + return it; +} + +/************************************************************************************************ + * stdskl_it_prev: Advance 'it' towards begin by one position. + ***********************************************************************************************/ + +STDINLINE stdit *stdskl_it_prev(stdit *it) +{ + STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); + + it->impl.skl.node = it->impl.skl.node->prevs[0]; + + return it; +} + +/************************************************************************************************ + * stdskl_it_retreat: Advance 'it' towards end by 'num_retreat' positions. + ***********************************************************************************************/ + +STDINLINE stdit *stdskl_it_retreat(stdit *it, stdsize num_retreat) +{ + STDSAFETY_CHECK(STDIT_SKL_IS_LEGAL(it)); + + while (num_retreat-- != 0) { + it->impl.skl.node = it->impl.skl.node->prevs[0]; + } + + return it; +} + +#ifdef __cplusplus +} +#endif Modified: vendor/stdutil/current/src/stdthread.c =================================================================== --- vendor/stdutil/current/src/stdthread.c 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdthread.c 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). @@ -19,10 +19,115 @@ * (CNDS - http://www.cnds.jhu.edu) */ -#if defined(_REENTRANT) +#include <stdlib.h> +#include <stdutil/stderror.h> +#include <stdutil/stdthread.h> -# include <stdlib.h> +#ifdef __cplusplus +extern "C" { +#endif +/* TODO: Need to implement code for STDMUTEX_NULL for threaded versions */ +/* TODO: Need to implement code for STDCOND_NULL */ +/* TODO: Need to break out the different implementations into their + own sections of code (i.e. - multiple implementations of each + function) like we did for !defined(_REENTRANT) +*/ + +#if !defined(_REENTRANT) + +STDINLINE stdcode stdthread_spawn(stdthread * thr_ptr, stdthread_id * id, + stdthread_fcn thr_fcn, void * fcn_arg) +{ + return STDENOSYS; +} + +STDINLINE stdcode stdthread_detach(stdthread thr) +{ + return STDENOSYS; +} + +STDINLINE stdcode stdthread_join(stdthread thr, void ** exitval_ptr) +{ + return STDENOSYS; +} + +STDINLINE void stdthread_exit(void * exitval) +{ + exit(0); +} + +STDINLINE stdthread_id stdthread_self(void) +{ + return STDENOSYS; +} + +STDINLINE stdbool stdthread_eq(stdthread_id id1, stdthread_id id2) +{ + return STDENOSYS; +} + +STDINLINE stdcode stdmutex_construct(stdmutex *mut, stdmutex_type t) +{ + return (t == STDMUTEX_NULL ? STDESUCCESS : STDENOSYS); +} + +STDINLINE stdcode stdmutex_destruct(stdmutex *mut) +{ + return STDESUCCESS; +} + +STDINLINE stdcode stdmutex_grab(stdmutex *mut) +{ + return STDESUCCESS; +} + +STDINLINE stdcode stdmutex_trygrab(stdmutex *mut) +{ + return STDESUCCESS; +} + +STDINLINE stdcode stdmutex_drop(stdmutex *mut) +{ + return STDESUCCESS; +} + +STDINLINE stdcode stdmutex_is_owner(stdmutex *mut, unsigned * grab_cnt) +{ + *grab_cnt = (unsigned) -1; + + return STDESUCCESS; +} + +STDINLINE stdcode stdcond_construct(stdcond *cond) +{ + return STDENOSYS; +} + +STDINLINE stdcode stdcond_destruct(stdcond *cond) +{ + return STDENOSYS; +} + +STDINLINE stdcode stdcond_wake_one(stdcond *cond) +{ + return STDENOSYS; +} + +STDINLINE stdcode stdcond_wake_all(stdcond *cond) +{ + return STDENOSYS; +} + +STDINLINE stdcode stdcond_wait(stdcond *cond, stdmutex *mut) +{ + return STDENOSYS; +} + +/*STDINLINE stdcode stdcond_timedwait(stdcond *cond, stdmutex *mut, long ns);*/ + +#else + # if defined(_WIN32) # include <process.h> # define STDSLEEPERS_BEGIN(cond) ((cond)->sleepers_end.next) @@ -32,13 +137,6 @@ # include <sys/time.h> # endif -# include <stdutil/stderror.h> -# include <stdutil/stdthread.h> - -#ifdef __cplusplus -extern "C" { -#endif - /************************************************************************************************ * stdthread_spawn: Create a new thread and start its execution. ***********************************************************************************************/ @@ -439,7 +537,7 @@ * stdmutex_fast_cond_wait: Wait on a condition protected by a fast mutex. ***********************************************************************************************/ -STDINLINE stdcode stdmutex_fast_cond_wait(stdmutex *mut, stdcond *cond) +STDINLINE static stdcode stdmutex_fast_cond_wait(stdmutex *mut, stdcond *cond) # if defined(_WIN32) { /* NOTE: this WIN32 code works for both fast and recursive mutexes: @@ -799,8 +897,7 @@ * stdmutex_rcrsv_cond_wait: Atomically unlock a 'mut' and wait on 'cond.' ***********************************************************************************************/ -STDINLINE stdcode stdmutex_rcrsv_cond_wait(stdmutex *mut, stdcond *cond) - +STDINLINE static stdcode stdmutex_rcrsv_cond_wait(stdmutex *mut, stdcond *cond) # if defined(_WIN32) { /* NOTE: the WIN32 code works for both fast and recursive mutexes: @@ -863,6 +960,7 @@ stdcode ret = STDEINVAL; switch (t) { + case STDMUTEX_FAST: ret = stdmutex_fast_init(mut); break; @@ -870,6 +968,10 @@ case STDMUTEX_RCRSV: ret = stdmutex_rcrsv_init(mut); break; + + case STDMUTEX_NULL: + ret = STDESUCCESS; + break; } return ret; @@ -884,6 +986,7 @@ stdcode ret = STDEINVAL; switch (mut->mut_type) { + case STDMUTEX_FAST: ret = stdmutex_fast_fini(mut); break; @@ -891,6 +994,10 @@ case STDMUTEX_RCRSV: ret = stdmutex_rcrsv_fini(mut); break; + + case STDMUTEX_NULL: + ret = STDESUCCESS; + break; } return ret; @@ -905,6 +1012,7 @@ stdcode ret = STDEINVAL; switch (mut->mut_type) { + case STDMUTEX_FAST: ret = stdmutex_fast_grab(mut, STDTRUE); break; @@ -912,6 +1020,10 @@ case STDMUTEX_RCRSV: ret = stdmutex_rcrsv_grab(mut, STDTRUE); break; + + case STDMUTEX_NULL: + ret = STDESUCCESS; + break; } return ret; @@ -926,6 +1038,7 @@ stdcode ret = STDEINVAL; switch (mut->mut_type) { + case STDMUTEX_FAST: ret = stdmutex_fast_grab(mut, STDFALSE); break; @@ -933,6 +1046,10 @@ case STDMUTEX_RCRSV: ret = stdmutex_rcrsv_grab(mut, STDFALSE); break; + + case STDMUTEX_NULL: + ret = STDESUCCESS; + break; } return ret; @@ -947,6 +1064,7 @@ stdcode ret = STDEINVAL; switch (mut->mut_type) { + case STDMUTEX_FAST: ret = stdmutex_fast_drop(mut); break; @@ -954,6 +1072,10 @@ case STDMUTEX_RCRSV: ret = stdmutex_rcrsv_drop(mut); break; + + case STDMUTEX_NULL: + ret = STDESUCCESS; + break; } return ret; @@ -968,6 +1090,7 @@ stdcode ret = STDEINVAL; switch (mut->mut_type) { + case STDMUTEX_FAST: ret = STDENOSYS; break; @@ -975,6 +1098,11 @@ case STDMUTEX_RCRSV: ret = stdmutex_rcrsv_is_owner(mut, grab_cnt); break; + + case STDMUTEX_NULL: + *grab_cnt = (unsigned) -1; + ret = STDESUCCESS; + break; } return ret; @@ -1070,6 +1198,7 @@ stdcode ret = STDEINVAL; switch (mut->mut_type) { + case STDMUTEX_FAST: ret = stdmutex_fast_cond_wait(mut, cond); break; @@ -1077,6 +1206,10 @@ case STDMUTEX_RCRSV: ret = stdmutex_rcrsv_cond_wait(mut, cond); break; + + case STDMUTEX_NULL: + ret = STDESUCCESS; + break; } return ret; @@ -1094,6 +1227,7 @@ stdcode ret = STDEINVAL; switch (mut->mut_type) { + case STDMUTEX_FAST: ret = stdmutex_fast_cond_wait_timed(mut, cond); break; @@ -1101,6 +1235,10 @@ case STDMUTEX_RCRSV: ret = stdmutex_rcrsv_cond_wait_timed(mut, cond); break; + + case STDMUTEX_NULL: + ret = STDESUCCESS; + break; } return ret; @@ -1189,10 +1327,8 @@ # endif #endif +#endif + #ifdef __cplusplus } #endif - -#else -int stdthread_trnsl_dummy; /* avoids empty translation unit error #if !defined(_REENTRANT) */ -#endif Modified: vendor/stdutil/current/src/stdtime.c =================================================================== --- vendor/stdutil/current/src/stdtime.c 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdtime.c 2009-06-04 20:38:26 UTC (rev 421) @@ -1,334 +1,334 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University - * All rights reserved. - * - * The contents of this file are subject to a license (the ``License''). - * You may not use this file except in compliance with the License. The - * specific language governing the rights and limitations of the License - * can be found in the file ``STDUTIL_LICENSE'' found in this - * distribution. - * - * Software distributed under the License is distributed on an AS IS - * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. - * - * The Original Software is: - * The Stdutil Library - * - * Contributors: - * Creator - John Lane Schultz ([email protected]) - * The Center for Networking and Distributed Systems - * (CNDS - http://www.cnds.jhu.edu) - */ - -#if defined(_WIN32) -# include <windows.h> -# include <sys/types.h> -# include <sys/timeb.h> -#else -# include <time.h> -# include <sys/time.h> -#endif - -#include <stdutil/stderror.h> -#include <stdutil/stdtime.h> - -#ifdef __cplusplus -extern "C" { -#endif - -/* stdtime: sec == STDINT64_MIN -> nano == 0 - sec < 0 -> -STD1BILLION < nano <= 0 - sec == 0 -> -STD1BILLION < nano < STD1BILLION - sec > 0 -> 0 <= nano < STD1BILLION -*/ - -#define STDTIME_IS_LEGAL(t) ( ((t).sec != STDINT64_MIN || (t).nano == 0) && \ - (((t).sec >= 0 && (t).nano >= 0 && (t).nano < STD1BILLION) || \ - ((t).sec <= 0 && (t).nano <= 0 && (t).nano > -STD1BILLION)) ) - -/************************************************************************************************ - * stdtime: Get the current system time since UTC 00:00:00, Jan 1, 1970. - ***********************************************************************************************/ - -STDINLINE stdcode stdtime_now(stdtime *abs_time) -#if defined(_WIN32) -{ - struct _timeb t; - - _ftime(&t); - - abs_time->sec = t.time; - abs_time->nano = t.millitm * STD1MILLION; - - return STDESUCCESS; -} -#else -{ - stdcode ret = STDESUCCESS; - struct timeval t; - - if (gettimeofday(&t, NULL) != STDESUCCESS) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - goto stdtime_now_end; - } - - abs_time->sec = t.tv_sec; - abs_time->nano = t.tv_usec * STD1THOUSAND; - -stdtime_now_end: - return ret; -} -#endif - -/************************************************************************************************ - * stdtime_time64: Return a stdtime created from a stdtime_time64. - * - * NOTE: '/' and '%' aren't uniformly defined for negative operands so we negate as needed - ***********************************************************************************************/ - -STDINLINE stdtime stdtime_time64(stdtime64 src) -{ - stdtime64 cpy = (src >= 0 ? src : -src); - stdtime ret; - - ret.sec = cpy / STD1BILLION; - ret.nano = (stdint32) cpy % (stdint32) STD1BILLION; - - if (src < 0) { - ret.sec = -ret.sec; - ret.nano = -ret.nano; - } - - return ret; -} - -/************************************************************************************************ - * stdtime_cmp: Compare two stdtimes. - ***********************************************************************************************/ - -STDINLINE int stdtime_cmp(stdtime ls, stdtime rs) -{ - STDSAFETY_CHECK(STDTIME_IS_LEGAL(ls) && STDTIME_IS_LEGAL(rs)); - - if (ls.sec == rs.sec) { - - if (ls.nano == rs.nano) { - return 0; - } - - return (ls.nano < rs.nano ? -1 : 1); - } - - return (ls.sec < rs.sec ? -1 : 1); -} - -/************************************************************************************************ - * stdtime_sign: Get the sign (-1: negative, 0: none, 1: positive) of a stdtime. - ***********************************************************************************************/ - -STDINLINE int stdtime_sign(stdtime t) -{ - stdtime t2 = { 0, 0 }; - - return stdtime_cmp(t, t2); -} - -/************************************************************************************************ - * stdtime_neg: Return the negation of a stdtime. - ***********************************************************************************************/ - -STDINLINE stdtime stdtime_neg(stdtime t) -{ - STDSAFETY_CHECK(STDTIME_IS_LEGAL(t)); - - t.sec = -t.sec; - t.nano = -t.nano; - - return t; -} - -/************************************************************************************************ - * stdtime_add: Return the addition of two stdtimes. - ***********************************************************************************************/ - -STDINLINE stdtime stdtime_add(stdtime ls, stdtime rs) -{ - stdtime ret; - - STDSAFETY_CHECK(STDTIME_IS_LEGAL(ls) && STDTIME_IS_LEGAL(rs)); - - /* do the addition */ - - ret.sec = ls.sec + rs.sec; - ret.nano = ls.nano + rs.nano; - - /* ensure -STD1BILLION < nano < STD1BILLION */ - - if (ret.nano >= STD1BILLION) { - ++ret.sec; - ret.nano -= STD1BILLION; - - } else if (ret.nano <= -STD1BILLION) { - --ret.sec; - ret.nano += STD1BILLION; - } - - /* check for non-agreement in signs */ - - if (ret.sec > 0) { - - if (ret.nano < 0) { - --ret.sec; - ret.nano += STD1BILLION; - } - - } else if (ret.sec != 0) { - - if (ret.nano > 0) { - ++ret.sec; - ret.nano -= STD1BILLION; - } - } - - /* check for nasty edge case and wrap around if not exactly minimum representation */ - - if (ret.sec == STDINT64_MIN && ret.nano != 0) { - --ret.sec; - ret.nano += STD1BILLION; - } - - return ret; -} - -/************************************************************************************************ - * stdtime_sub: Return the difference of two stdtimes. - ***********************************************************************************************/ - -STDINLINE stdtime stdtime_sub(stdtime ls, stdtime rs) -{ - return stdtime_add(ls, stdtime_neg(rs)); -} - -/************************************************************************************************ - * stdtime64_now: Get the current system time since UTC 00:00:00, Jan 1, 1970. - ***********************************************************************************************/ - -STDINLINE stdcode stdtime64_now(stdtime64 *abs_time) -{ - stdtime t; - stdcode ret = stdtime_now(&t); - - if (ret == STDESUCCESS) { - *abs_time = stdtime64_time(t); - } - - return ret; -} - -/************************************************************************************************ - * stdtime64_time: Return a stdtime64 from a stdtime. - ***********************************************************************************************/ - -STDINLINE stdtime64 stdtime64_time(stdtime t) -{ - STDSAFETY_CHECK(STDTIME_IS_LEGAL(t)); - - return (stdtime64) t.sec * STD1BILLION + t.nano; -} - -/************************************************************************************************ - * stdsleep: Sleep for a period of time. On error, remndr will be - * filled if non-NULL. - ***********************************************************************************************/ - -STDINLINE stdcode stdsleep(stdtime delta, stdtime *remndr) -# if defined(_WIN32) -{ - stdcode ret = STDESUCCESS; - stdtime start_time = { 0, 0 }; - stdtime end_time = { 0, 0 }; - DWORD milli_sleep; - - if (delta.sec < 0 || delta.nano < 0 || delta.nano >= STD1BILLION) { - ret = STDEINVAL; - goto stdsleep_fail; - } - - /* conditional +1 for possible nanosecond division trunctation */ - - milli_sleep = (DWORD) (delta.sec * STD1THOUSAND + delta.nano / STD1MILLION) + (delta.nano != 0 ? 1 : 0); - - Sleep(milli_sleep); - - goto stdsleep_end; - - /* error handling and return */ - - stdsleep_fail: - if (remndr != NULL) { - *remndr = delta; - } - - stdsleep_end: - return ret; -} -#else -{ - stdcode ret; - struct timespec d; - struct timespec r; - - if (delta.sec < 0 || delta.nano < 0 || delta.nano >= STD1BILLION) { - ret = STDEINVAL; - goto stdsleep_fail; - } - - d.tv_sec = (time_t) delta.sec; - d.tv_nsec = delta.nano; - - if ((ret = nanosleep(&d, &r)) != STDESUCCESS) { - ret = errno; - STDSAFETY_CHECK(ret != STDESUCCESS); - - if (remndr != NULL) { - remndr->sec = r.tv_sec; - remndr->nano = r.tv_nsec; - } - } - - goto stdsleep_end; - - /* error handling and return */ - - stdsleep_fail: - if (remndr != NULL) { - *remndr = delta; - } - - stdsleep_end: - return ret; -} -#endif - -/************************************************************************************************ - * stdsleep64: Sleep for a number of nanoseconds. - ***********************************************************************************************/ - -STDINLINE stdcode stdsleep64(stdtime64 delta, stdtime64 *remndr) -{ - stdcode ret; - stdtime t_delta = stdtime_time64(delta); - stdtime t_remndr; - - ret = stdsleep(t_delta, (remndr != NULL ? &t_remndr : NULL)); - - if (ret != STDESUCCESS && remndr != NULL) { - *remndr = stdtime64_time(t_remndr); - } - - return ret; -} - -#ifdef __cplusplus -} -#endif +/* Copyright (c) 2000-2009, The Johns Hopkins University + * All rights reserved. + * + * The contents of this file are subject to a license (the ``License''). + * You may not use this file except in compliance with the License. The + * specific language governing the rights and limitations of the License + * can be found in the file ``STDUTIL_LICENSE'' found in this + * distribution. + * + * Software distributed under the License is distributed on an AS IS + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. + * + * The Original Software is: + * The Stdutil Library + * + * Contributors: + * Creator - John Lane Schultz ([email protected]) + * The Center for Networking and Distributed Systems + * (CNDS - http://www.cnds.jhu.edu) + */ + +#if defined(_WIN32) +# include <windows.h> +# include <sys/types.h> +# include <sys/timeb.h> +#else +# include <time.h> +# include <sys/time.h> +#endif + +#include <stdutil/stderror.h> +#include <stdutil/stdtime.h> + +#ifdef __cplusplus +extern "C" { +#endif + +/* stdtime: sec == STDINT64_MIN -> nano == 0 + sec < 0 -> -STD1BILLION < nano <= 0 + sec == 0 -> -STD1BILLION < nano < STD1BILLION + sec > 0 -> 0 <= nano < STD1BILLION +*/ + +#define STDTIME_IS_LEGAL(t) ( ((t).sec != STDINT64_MIN || (t).nano == 0) && \ + (((t).sec >= 0 && (t).nano >= 0 && (t).nano < STD1BILLION) || \ + ((t).sec <= 0 && (t).nano <= 0 && (t).nano > -STD1BILLION)) ) + +/************************************************************************************************ + * stdtime: Get the current system time since UTC 00:00:00, Jan 1, 1970. + ***********************************************************************************************/ + +STDINLINE stdcode stdtime_now(stdtime *abs_time) +#if defined(_WIN32) +{ + struct _timeb t; + + _ftime(&t); + + abs_time->sec = t.time; + abs_time->nano = t.millitm * STD1MILLION; + + return STDESUCCESS; +} +#else +{ + stdcode ret = STDESUCCESS; + struct timeval t; + + if (gettimeofday(&t, NULL) != STDESUCCESS) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + goto stdtime_now_end; + } + + abs_time->sec = t.tv_sec; + abs_time->nano = t.tv_usec * STD1THOUSAND; + +stdtime_now_end: + return ret; +} +#endif + +/************************************************************************************************ + * stdtime_time64: Return a stdtime created from a stdtime_time64. + * + * NOTE: '/' and '%' aren't uniformly defined for negative operands so we negate as needed + ***********************************************************************************************/ + +STDINLINE stdtime stdtime_time64(stdtime64 src) +{ + stdtime64 cpy = (src >= 0 ? src : -src); + stdtime ret; + + ret.sec = cpy / STD1BILLION; + ret.nano = (stdint32) (cpy % STD1BILLION); + + if (src < 0) { + ret.sec = -ret.sec; + ret.nano = -ret.nano; + } + + return ret; +} + +/************************************************************************************************ + * stdtime_cmp: Compare two stdtimes. + ***********************************************************************************************/ + +STDINLINE int stdtime_cmp(stdtime ls, stdtime rs) +{ + STDSAFETY_CHECK(STDTIME_IS_LEGAL(ls) && STDTIME_IS_LEGAL(rs)); + + if (ls.sec == rs.sec) { + + if (ls.nano == rs.nano) { + return 0; + } + + return (ls.nano < rs.nano ? -1 : 1); + } + + return (ls.sec < rs.sec ? -1 : 1); +} + +/************************************************************************************************ + * stdtime_sign: Get the sign (-1: negative, 0: none, 1: positive) of a stdtime. + ***********************************************************************************************/ + +STDINLINE int stdtime_sign(stdtime t) +{ + stdtime t2 = { 0, 0 }; + + return stdtime_cmp(t, t2); +} + +/************************************************************************************************ + * stdtime_neg: Return the negation of a stdtime. + ***********************************************************************************************/ + +STDINLINE stdtime stdtime_neg(stdtime t) +{ + STDSAFETY_CHECK(STDTIME_IS_LEGAL(t)); + + t.sec = -t.sec; + t.nano = -t.nano; + + return t; +} + +/************************************************************************************************ + * stdtime_add: Return the addition of two stdtimes. + ***********************************************************************************************/ + +STDINLINE stdtime stdtime_add(stdtime ls, stdtime rs) +{ + stdtime ret; + + STDSAFETY_CHECK(STDTIME_IS_LEGAL(ls) && STDTIME_IS_LEGAL(rs)); + + /* do the addition */ + + ret.sec = ls.sec + rs.sec; + ret.nano = ls.nano + rs.nano; + + /* ensure -STD1BILLION < nano < STD1BILLION */ + + if (ret.nano >= STD1BILLION) { + ++ret.sec; + ret.nano -= STD1BILLION; + + } else if (ret.nano <= -STD1BILLION) { + --ret.sec; + ret.nano += STD1BILLION; + } + + /* check for non-agreement in signs */ + + if (ret.sec > 0) { + + if (ret.nano < 0) { + --ret.sec; + ret.nano += STD1BILLION; + } + + } else if (ret.sec != 0) { + + if (ret.nano > 0) { + ++ret.sec; + ret.nano -= STD1BILLION; + } + } + + /* check for nasty edge case and wrap around if not exactly minimum representation */ + + if (ret.sec == STDINT64_MIN && ret.nano != 0) { + --ret.sec; + ret.nano += STD1BILLION; + } + + return ret; +} + +/************************************************************************************************ + * stdtime_sub: Return the difference of two stdtimes. + ***********************************************************************************************/ + +STDINLINE stdtime stdtime_sub(stdtime ls, stdtime rs) +{ + return stdtime_add(ls, stdtime_neg(rs)); +} + +/************************************************************************************************ + * stdtime64_now: Get the current system time since UTC 00:00:00, Jan 1, 1970. + ***********************************************************************************************/ + +STDINLINE stdcode stdtime64_now(stdtime64 *abs_time) +{ + stdtime t; + stdcode ret = stdtime_now(&t); + + if (ret == STDESUCCESS) { + *abs_time = stdtime64_time(t); + } + + return ret; +} + +/************************************************************************************************ + * stdtime64_time: Return a stdtime64 from a stdtime. + ***********************************************************************************************/ + +STDINLINE stdtime64 stdtime64_time(stdtime t) +{ + STDSAFETY_CHECK(STDTIME_IS_LEGAL(t)); + + return (stdtime64) t.sec * STD1BILLION + t.nano; +} + +/************************************************************************************************ + * stdsleep: Sleep for a period of time. On error, remndr will be + * filled if non-NULL. + ***********************************************************************************************/ + +STDINLINE stdcode stdsleep(stdtime delta, stdtime *remndr) +# if defined(_WIN32) +{ + stdcode ret = STDESUCCESS; + stdtime start_time = { 0, 0 }; + stdtime end_time = { 0, 0 }; + DWORD milli_sleep; + + if (delta.sec < 0 || delta.nano < 0 || delta.nano >= STD1BILLION) { + ret = STDEINVAL; + goto stdsleep_fail; + } + + /* conditional +1 for possible nanosecond division trunctation */ + + milli_sleep = (DWORD) (delta.sec * STD1THOUSAND + delta.nano / STD1MILLION) + (delta.nano != 0 ? 1 : 0); + + Sleep(milli_sleep); + + goto stdsleep_end; + + /* error handling and return */ + + stdsleep_fail: + if (remndr != NULL) { + *remndr = delta; + } + + stdsleep_end: + return ret; +} +#else +{ + stdcode ret; + struct timespec d; + struct timespec r; + + if (delta.sec < 0 || delta.nano < 0 || delta.nano >= STD1BILLION) { + ret = STDEINVAL; + goto stdsleep_fail; + } + + d.tv_sec = (time_t) delta.sec; + d.tv_nsec = delta.nano; + + if ((ret = nanosleep(&d, &r)) != STDESUCCESS) { + ret = errno; + STDSAFETY_CHECK(ret != STDESUCCESS); + + if (remndr != NULL) { + remndr->sec = r.tv_sec; + remndr->nano = r.tv_nsec; + } + } + + goto stdsleep_end; + + /* error handling and return */ + + stdsleep_fail: + if (remndr != NULL) { + *remndr = delta; + } + + stdsleep_end: + return ret; +} +#endif + +/************************************************************************************************ + * stdsleep64: Sleep for a number of nanoseconds. + ***********************************************************************************************/ + +STDINLINE stdcode stdsleep64(stdtime64 delta, stdtime64 *remndr) +{ + stdcode ret; + stdtime t_delta = stdtime_time64(delta); + stdtime t_remndr; + + ret = stdsleep(t_delta, (remndr != NULL ? &t_remndr : NULL)); + + if (ret != STDESUCCESS && remndr != NULL) { + *remndr = stdtime64_time(t_remndr); + } + + return ret; +} + +#ifdef __cplusplus +} +#endif Modified: vendor/stdutil/current/src/stdutil/private/stdarch.h =================================================================== --- vendor/stdutil/current/src/stdutil/private/stdarch.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/private/stdarch.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/private/stdarch_autoconf.h.in =================================================================== --- vendor/stdutil/current/src/stdutil/private/stdarch_autoconf.h.in 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/private/stdarch_autoconf.h.in 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/private/stdarch_wintel32.h =================================================================== --- vendor/stdutil/current/src/stdutil/private/stdarch_wintel32.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/private/stdarch_wintel32.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/private/stdarr_p.h =================================================================== --- vendor/stdutil/current/src/stdutil/private/stdarr_p.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/private/stdarr_p.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/private/stdcarr_p.h =================================================================== --- vendor/stdutil/current/src/stdutil/private/stdcarr_p.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/private/stdcarr_p.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/private/stddll_p.h =================================================================== --- vendor/stdutil/current/src/stdutil/private/stddll_p.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/private/stddll_p.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/private/stdhash_p.h =================================================================== --- vendor/stdutil/current/src/stdutil/private/stdhash_p.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/private/stdhash_p.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/private/stdit_p.h =================================================================== --- vendor/stdutil/current/src/stdutil/private/stdit_p.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/private/stdit_p.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/private/stdskl_p.h =================================================================== --- vendor/stdutil/current/src/stdutil/private/stdskl_p.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/private/stdskl_p.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,95 +1,95 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University - * All rights reserved. - * - * The contents of this file are subject to a license (the ``License''). - * You may not use this file except in compliance with the License. The - * specific language governing the rights and limitations of the License - * can be found in the file ``STDUTIL_LICENSE'' found in this - * distribution. - * - * Software distributed under the License is distributed on an AS IS - * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. - * - * The Original Software is: - * The Stdutil Library - * - * Contributors: - * Creator - John Lane Schultz ([email protected]) - * The Center for Networking and Distributed Systems - * (CNDS - http://www.cnds.jhu.edu) - */ - -#ifndef stdskl_p_h_2005_06_07_15_09_42_jschultz_at_cnds_jhu_edu -#define stdskl_p_h_2005_06_07_15_09_42_jschultz_at_cnds_jhu_edu - -/* stdskl_node: A type that contains a key-value pair and node linking information. - - height - 0 based height of this node; size of (prevs, nexts) arrays minus 1 - prevs - an array of pointers to previous elements in the list - nexts - an array of pointers to later elements in the list - key - pointer to the node's key - val - pointer to the node's val - - NOTE: The prevs and nexts arrays are appended onto the end of the - node in memory. - - NOTE: The key and value are then appended onto the end of this node in - memory after the prevs and nexts arrays (w/ padding as necessary). -*/ - -typedef struct stdskl_node -{ - stdint8 height; - struct stdskl_node ** prevs; - struct stdskl_node ** nexts; - - const void * key; - void * val; - -} stdskl_node; - -/* stdskl: A skiplist based dictionary that maps non-unique keys to values. - - end_node - pointer to sentinel end node of list - size - number of key-value pairs contained - ksize - size in bytes of key type contained - vsize - size in bytes of value type contained - cmp_fcn - user defined key comparison function - seed - state used to generate pseudo-random numbers - rand_bits - a random number that contains random bits - bits_left - how many unused bits remain in rand_bits -*/ - -typedef struct stdskl -{ - stdskl_node * end_node; - - stdsize size; - - stdsize ksize; - stdsize vsize; - - stdcmp_fcn cmp_fcn; - - stduint16 seed[3]; - stduint32 rand_bits; - stdint8 bits_left; - -} stdskl; - -/* stdskl_it: An iterator for a stdskl. - - node - pointer to the reference node in the list - ksize - size in bytes of referenced key type - vsize - size in bytes of referenced value type -*/ - -typedef struct -{ - stdskl_node * node; - stdsize ksize; - stdsize vsize; - -} stdskl_it; - -#endif +/* Copyright (c) 2000-2009, The Johns Hopkins University + * All rights reserved. + * + * The contents of this file are subject to a license (the ``License''). + * You may not use this file except in compliance with the License. The + * specific language governing the rights and limitations of the License + * can be found in the file ``STDUTIL_LICENSE'' found in this + * distribution. + * + * Software distributed under the License is distributed on an AS IS + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. + * + * The Original Software is: + * The Stdutil Library + * + * Contributors: + * Creator - John Lane Schultz ([email protected]) + * The Center for Networking and Distributed Systems + * (CNDS - http://www.cnds.jhu.edu) + */ + +#ifndef stdskl_p_h_2005_06_07_15_09_42_jschultz_at_cnds_jhu_edu +#define stdskl_p_h_2005_06_07_15_09_42_jschultz_at_cnds_jhu_edu + +/* stdskl_node: A type that contains a key-value pair and node linking information. + + height - 0 based height of this node; size of (prevs, nexts) arrays minus 1 + prevs - an array of pointers to previous elements in the list + nexts - an array of pointers to later elements in the list + key - pointer to the node's key + val - pointer to the node's val + + NOTE: The prevs and nexts arrays are appended onto the end of the + node in memory. + + NOTE: The key and value are then appended onto the end of this node in + memory after the prevs and nexts arrays (w/ padding as necessary). +*/ + +typedef struct stdskl_node +{ + stdint8 height; + struct stdskl_node ** prevs; + struct stdskl_node ** nexts; + + const void * key; + void * val; + +} stdskl_node; + +/* stdskl: A skiplist based dictionary that maps non-unique keys to values. + + end_node - pointer to sentinel end node of list + size - number of key-value pairs contained + ksize - size in bytes of key type contained + vsize - size in bytes of value type contained + cmp_fcn - user defined key comparison function + seed - state used to generate pseudo-random numbers + rand_bits - a random number that contains random bits + bits_left - how many unused bits remain in rand_bits +*/ + +typedef struct stdskl +{ + stdskl_node * end_node; + + stdsize size; + + stdsize ksize; + stdsize vsize; + + stdcmp_fcn cmp_fcn; + + stduint16 seed[3]; + stduint32 rand_bits; + stdint8 bits_left; + +} stdskl; + +/* stdskl_it: An iterator for a stdskl. + + node - pointer to the reference node in the list + ksize - size in bytes of referenced key type + vsize - size in bytes of referenced value type +*/ + +typedef struct +{ + stdskl_node * node; + stdsize ksize; + stdsize vsize; + +} stdskl_it; + +#endif Modified: vendor/stdutil/current/src/stdutil/private/stdthread_p.h =================================================================== --- vendor/stdutil/current/src/stdutil/private/stdthread_p.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/private/stdthread_p.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). @@ -22,7 +22,16 @@ #ifndef stdthread_p_h_2000_05_18_12_57_48_jschultz_at_cnds_jhu_edu #define stdthread_p_h_2000_05_18_12_57_48_jschultz_at_cnds_jhu_edu -#if defined(_WIN32) +#if !defined(_REENTRANT) + +# define STDTHREAD_FCN + +typedef int stdthread; +typedef int stdthread_id; +typedef int stdmutex_impl; +typedef int stdcond_impl; + +#elif defined(_WIN32) # include <windows.h> # define STDTHREAD_FCN __stdcall @@ -97,4 +106,4 @@ typedef stdcond_impl stdcond; -# endif +#endif Modified: vendor/stdutil/current/src/stdutil/stdarr.h =================================================================== --- vendor/stdutil/current/src/stdutil/stdarr.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stdarr.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/stdcarr.h =================================================================== --- vendor/stdutil/current/src/stdutil/stdcarr.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stdcarr.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/stddefines.h =================================================================== --- vendor/stdutil/current/src/stdutil/stddefines.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stddefines.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). @@ -69,21 +69,21 @@ typedef stdarch_int32 stdint32; typedef stdarch_uint32 stduint32; -#define STDINT32_MAX (STDINT32_MIN - 1) +#define STDINT32_MAX ((stdint32) ((stduint32) STDINT32_MIN - 1)) #define STDINT32_MIN ((stdint32) ((stduint32) 0x1 << 31)) #define STDUINT32_MAX ((stduint32) -1) typedef stdarch_int64 stdint64; typedef stdarch_uint64 stduint64; -#define STDINT64_MAX (STDINT64_MIN - 1) +#define STDINT64_MAX ((stdint64) ((stduint64) STDINT64_MIN - 1)) #define STDINT64_MIN ((stdint64) ((stduint64) 0x1 << 63)) #define STDUINT64_MAX ((stduint64) -1) typedef size_t stdsize; typedef stdarch_ssize stdssize; /* a signed version of size_t */ -#define STDSSIZE_MAX (STDSSIZE_MIN - 1) +#define STDSSIZE_MAX ((stdssize) ((stdsize) STDSSIZE_MIN - 1)) #define STDSSIZE_MIN ((stdssize) ((stdsize) 0x1 << (sizeof(stdssize) * 8 - 1)) #define STDSIZE_MAX ((stdsize) -1) Modified: vendor/stdutil/current/src/stdutil/stddll.h =================================================================== --- vendor/stdutil/current/src/stdutil/stddll.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stddll.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/stderror.h =================================================================== --- vendor/stdutil/current/src/stdutil/stderror.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stderror.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). @@ -124,6 +124,12 @@ # define STDEINTR 507 #endif +#if defined(ETIMEDOUT) +# define STDETIMEDOUT ETIMEDOUT +#else +# define STDETIMEDOUT 508 +#endif + #ifdef __cplusplus } #endif Modified: vendor/stdutil/current/src/stdutil/stdfd.h =================================================================== --- vendor/stdutil/current/src/stdutil/stdfd.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stdfd.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,89 +1,89 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University - * All rights reserved. - * - * The contents of this file are subject to a license (the ``License''). - * You may not use this file except in compliance with the License. The - * specific language governing the rights and limitations of the License - * can be found in the file ``STDUTIL_LICENSE'' found in this - * distribution. - * - * Software distributed under the License is distributed on an AS IS - * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. - * - * The Original Software is: - * The Stdutil Library - * - * Contributors: - * Creator - John Lane Schultz ([email protected]) - * The Center for Networking and Distributed Systems - * (CNDS - http://www.cnds.jhu.edu) - */ - -#ifndef stdfd_h_2003_10_20_13_49_08_jschultz_at_cnds_jhu_edu -#define stdfd_h_2003_10_20_13_49_08_jschultz_at_cnds_jhu_edu - -#include <stdio.h> -#include <stdutil/stddefines.h> - -#ifdef __cplusplus -extern "C" { -#endif - -typedef struct -{ - int fd; - FILE * stream; - -} stdfd; - -#define STDFD_INIT() { -1, NULL } - -typedef enum -{ - STDFD_READ_ONLY = 2000, /* rb */ - STDFD_READ_WRITE_EXISTING, /* rb+ */ - STDFD_WRITE_ONLY, /* wb */ - STDFD_READ_WRITE_NEW, /* wb+ */ - STDFD_APPEND_ONLY, /* ab */ - STDFD_READ_APPEND /* ab+ */ - -} stdfd_access_type; /* as per fopen(): redefined for static enum check warnings */ - -typedef enum -{ - STDSEEK_SET = SEEK_SET, - STDSEEK_CUR = SEEK_CUR, - STDSEEK_END = SEEK_END - -} stdfd_whence; /* as per fseek(): redefined for static enum check warnings */ - -/* File Descriptor Operations */ - -STDINLINE stdcode stdfd_open(stdfd *fd, const char *path, stdfd_access_type mode); -STDINLINE stdcode stdfd_close(stdfd *fd); - -STDINLINE stdcode stdfd_read(stdfd *fd, void *ptr, stdsize nsize, stdsize nmemb, stdsize *num); -STDINLINE stdcode stdfd_write(stdfd *fd, const void *ptr, stdsize nsize, stdsize nmemb, stdsize *num); - -STDINLINE stdcode stdfd_flush(stdfd *fd); -STDINLINE stdcode stdfd_sync(stdfd *fd); - -STDINLINE stdcode stdfd_seek(stdfd *fd, long offset, stdfd_whence whence); -STDINLINE stdcode stdfd_tell(stdfd *fd, long *pos); - -STDINLINE stdbool stdfd_eof(stdfd *fd); -STDINLINE stdbool stdfd_err(stdfd *fd); -STDINLINE void stdfd_clr_err(stdfd *fd); - -STDINLINE stdcode stdfd_trylock(stdfd *fd); -STDINLINE stdcode stdfd_unlock(stdfd *fd); - -/* File Operations */ - -STDINLINE stdcode stdfile_unlink(const char * path); - -#ifdef __cplusplus -} -#endif - -#endif +/* Copyright (c) 2000-2009, The Johns Hopkins University + * All rights reserved. + * + * The contents of this file are subject to a license (the ``License''). + * You may not use this file except in compliance with the License. The + * specific language governing the rights and limitations of the License + * can be found in the file ``STDUTIL_LICENSE'' found in this + * distribution. + * + * Software distributed under the License is distributed on an AS IS + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. + * + * The Original Software is: + * The Stdutil Library + * + * Contributors: + * Creator - John Lane Schultz ([email protected]) + * The Center for Networking and Distributed Systems + * (CNDS - http://www.cnds.jhu.edu) + */ + +#ifndef stdfd_h_2003_10_20_13_49_08_jschultz_at_cnds_jhu_edu +#define stdfd_h_2003_10_20_13_49_08_jschultz_at_cnds_jhu_edu + +#include <stdio.h> +#include <stdutil/stddefines.h> + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct +{ + int fd; + FILE * stream; + +} stdfd; + +#define STDFD_INIT() { -1, NULL } + +typedef enum +{ + STDFD_READ_ONLY = 2000, /* rb */ + STDFD_READ_WRITE_EXISTING, /* rb+ */ + STDFD_WRITE_ONLY, /* wb */ + STDFD_READ_WRITE_NEW, /* wb+ */ + STDFD_APPEND_ONLY, /* ab */ + STDFD_READ_APPEND /* ab+ */ + +} stdfd_access_type; /* as per fopen(): redefined for static enum check warnings */ + +typedef enum +{ + STDSEEK_SET = SEEK_SET, + STDSEEK_CUR = SEEK_CUR, + STDSEEK_END = SEEK_END + +} stdfd_whence; /* as per fseek(): redefined for static enum check warnings */ + +/* File Descriptor Operations */ + +STDINLINE stdcode stdfd_open(stdfd *fd, const char *path, stdfd_access_type mode); +STDINLINE stdcode stdfd_close(stdfd *fd); + +STDINLINE stdcode stdfd_read(stdfd *fd, void *ptr, stdsize nsize, stdsize nmemb, stdsize *num); +STDINLINE stdcode stdfd_write(stdfd *fd, const void *ptr, stdsize nsize, stdsize nmemb, stdsize *num); + +STDINLINE stdcode stdfd_flush(stdfd *fd); +STDINLINE stdcode stdfd_sync(stdfd *fd); + +STDINLINE stdcode stdfd_seek(stdfd *fd, long offset, stdfd_whence whence); +STDINLINE stdcode stdfd_tell(stdfd *fd, long *pos); + +STDINLINE stdbool stdfd_eof(stdfd *fd); +STDINLINE stdbool stdfd_err(stdfd *fd); +STDINLINE void stdfd_clr_err(stdfd *fd); + +STDINLINE stdcode stdfd_trylock(stdfd *fd); +STDINLINE stdcode stdfd_unlock(stdfd *fd); + +/* File Operations */ + +STDINLINE stdcode stdfile_unlink(const char * path); + +#ifdef __cplusplus +} +#endif + +#endif Modified: vendor/stdutil/current/src/stdutil/stdhash.h =================================================================== --- vendor/stdutil/current/src/stdutil/stdhash.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stdhash.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/stdit.h =================================================================== --- vendor/stdutil/current/src/stdutil/stdit.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stdit.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil/stdskl.h =================================================================== --- vendor/stdutil/current/src/stdutil/stdskl.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stdskl.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,105 +1,105 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University - * All rights reserved. - * - * The contents of this file are subject to a license (the ``License''). - * You may not use this file except in compliance with the License. The - * specific language governing the rights and limitations of the License - * can be found in the file ``STDUTIL_LICENSE'' found in this - * distribution. - * - * Software distributed under the License is distributed on an AS IS - * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. - * - * The Original Software is: - * The Stdutil Library - * - * Contributors: - * Creator - John Lane Schultz ([email protected]) - * The Center for Networking and Distributed Systems - * (CNDS - http://www.cnds.jhu.edu) - */ - -#ifndef stdskl_h_2004_07_24_13_13_49_jschultz_at_cnds_jhu_edu -#define stdskl_h_2004_07_24_13_13_49_jschultz_at_cnds_jhu_edu - -#include <stdutil/stdit.h> - -# ifdef __cplusplus -extern "C" { -# endif - -/* Structors */ - -STDINLINE stdcode stdskl_construct(stdskl *l, stdsize ksize, stdsize vsize, stdcmp_fcn kcmp); -STDINLINE stdcode stdskl_copy_construct(stdskl *dst, const stdskl *src); -STDINLINE void stdskl_destruct(stdskl *l); - -/* Assigners */ - -STDINLINE stdcode stdskl_set_eq(stdskl *dst, const stdskl *src); -STDINLINE void stdskl_swap(stdskl *l1, stdskl *l2); - -/* Iterators */ - -STDINLINE stdit * stdskl_begin(const stdskl *l, stdit *it); -STDINLINE stdit * stdskl_last(const stdskl *l, stdit *it); -STDINLINE stdit * stdskl_end(const stdskl *l, stdit *it); -STDINLINE stdit * stdskl_get(const stdskl *l, stdit *it, size_t elem_num); /* O(n) */ - -STDINLINE stdbool stdskl_is_begin(const stdskl *l, const stdit *it); -STDINLINE stdbool stdskl_is_end(const stdskl *l, const stdit *it); - -/* Size Information */ - -STDINLINE stdsize stdskl_size(const stdskl *l); -STDINLINE stdbool stdskl_empty(const stdskl *l); - -/* Size Operations */ - -STDINLINE void stdskl_clear(stdskl *l); - -/* Dictionary Operations: O(lg n) */ - -STDINLINE stdit * stdskl_find(const stdskl *l, stdit *it, const void *key); -STDINLINE stdit * stdskl_lowerb(const stdskl *l, stdit *it, const void *key); -STDINLINE stdit * stdskl_upperb(const stdskl *l, stdit *it, const void *key); -STDINLINE stdbool stdskl_contains(const stdskl *l, const void *key); - -STDINLINE stdcode stdskl_put(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint); -STDINLINE stdcode stdskl_put_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_put, stdbool hint); -STDINLINE stdcode stdskl_put_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint); -STDINLINE stdcode stdskl_put_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_put, stdbool hint); - -STDINLINE stdcode stdskl_insert(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint); -STDINLINE stdcode stdskl_insert_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_insert, stdbool hint); -STDINLINE stdcode stdskl_insert_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint); -STDINLINE stdcode stdskl_insert_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_insert, stdbool hint); -STDINLINE stdcode stdskl_insert_rep(stdskl *l, stdit *it, const void *key, const void *val, stdsize num_times, stdbool hint); - -STDINLINE void stdskl_erase(stdskl *l, stdit *it); -STDINLINE void stdskl_erase_n(stdskl *l, stdit *it, stdsize num_erase); -STDINLINE void stdskl_erase_seq(stdskl *l, stdit *b, stdit *e); -STDINLINE void stdskl_erase_key(stdskl *l, const void *key); - -/* Randomization */ - -STDINLINE void stdskl_dseed(stdskl *l, const void *seed, stdsize sizeof_seed); - -/* Iterator Fcns */ - -STDINLINE const void * stdskl_it_key(const stdit *it); -STDINLINE stdsize stdskl_it_key_size(const stdit *it); -STDINLINE void * stdskl_it_val(const stdit *it); -STDINLINE stdsize stdskl_it_val_size(const stdit *it); -STDINLINE stdbool stdskl_it_eq(const stdit *it1, const stdit *it2); - -STDINLINE stdit * stdskl_it_next(stdit *it); -STDINLINE stdit * stdskl_it_advance(stdit *it, stdsize num_advance); -STDINLINE stdit * stdskl_it_prev(stdit *it); -STDINLINE stdit * stdskl_it_retreat(stdit *it, stdsize num_retreat); - -# ifdef __cplusplus -} -# endif - -#endif +/* Copyright (c) 2000-2009, The Johns Hopkins University + * All rights reserved. + * + * The contents of this file are subject to a license (the ``License''). + * You may not use this file except in compliance with the License. The + * specific language governing the rights and limitations of the License + * can be found in the file ``STDUTIL_LICENSE'' found in this + * distribution. + * + * Software distributed under the License is distributed on an AS IS + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. + * + * The Original Software is: + * The Stdutil Library + * + * Contributors: + * Creator - John Lane Schultz ([email protected]) + * The Center for Networking and Distributed Systems + * (CNDS - http://www.cnds.jhu.edu) + */ + +#ifndef stdskl_h_2004_07_24_13_13_49_jschultz_at_cnds_jhu_edu +#define stdskl_h_2004_07_24_13_13_49_jschultz_at_cnds_jhu_edu + +#include <stdutil/stdit.h> + +# ifdef __cplusplus +extern "C" { +# endif + +/* Structors */ + +STDINLINE stdcode stdskl_construct(stdskl *l, stdsize ksize, stdsize vsize, stdcmp_fcn kcmp); +STDINLINE stdcode stdskl_copy_construct(stdskl *dst, const stdskl *src); +STDINLINE void stdskl_destruct(stdskl *l); + +/* Assigners */ + +STDINLINE stdcode stdskl_set_eq(stdskl *dst, const stdskl *src); +STDINLINE void stdskl_swap(stdskl *l1, stdskl *l2); + +/* Iterators */ + +STDINLINE stdit * stdskl_begin(const stdskl *l, stdit *it); +STDINLINE stdit * stdskl_last(const stdskl *l, stdit *it); +STDINLINE stdit * stdskl_end(const stdskl *l, stdit *it); +STDINLINE stdit * stdskl_get(const stdskl *l, stdit *it, size_t elem_num); /* O(n) */ + +STDINLINE stdbool stdskl_is_begin(const stdskl *l, const stdit *it); +STDINLINE stdbool stdskl_is_end(const stdskl *l, const stdit *it); + +/* Size Information */ + +STDINLINE stdsize stdskl_size(const stdskl *l); +STDINLINE stdbool stdskl_empty(const stdskl *l); + +/* Size Operations */ + +STDINLINE void stdskl_clear(stdskl *l); + +/* Dictionary Operations: O(lg n) */ + +STDINLINE stdit * stdskl_find(const stdskl *l, stdit *it, const void *key); +STDINLINE stdit * stdskl_lowerb(const stdskl *l, stdit *it, const void *key); +STDINLINE stdit * stdskl_upperb(const stdskl *l, stdit *it, const void *key); +STDINLINE stdbool stdskl_contains(const stdskl *l, const void *key); + +STDINLINE stdcode stdskl_put(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint); +STDINLINE stdcode stdskl_put_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_put, stdbool hint); +STDINLINE stdcode stdskl_put_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint); +STDINLINE stdcode stdskl_put_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_put, stdbool hint); + +STDINLINE stdcode stdskl_insert(stdskl *l, stdit *it, const void *key, const void *val, stdbool hint); +STDINLINE stdcode stdskl_insert_n(stdskl *l, stdit *it, const void *keys, const void *vals, stdsize num_insert, stdbool hint); +STDINLINE stdcode stdskl_insert_seq(stdskl *l, stdit *it, const stdit *b, const stdit *e, stdbool hint); +STDINLINE stdcode stdskl_insert_seq_n(stdskl *l, stdit *it, const stdit *b, stdsize num_insert, stdbool hint); +STDINLINE stdcode stdskl_insert_rep(stdskl *l, stdit *it, const void *key, const void *val, stdsize num_times, stdbool hint); + +STDINLINE void stdskl_erase(stdskl *l, stdit *it); +STDINLINE void stdskl_erase_n(stdskl *l, stdit *it, stdsize num_erase); +STDINLINE stdsize stdskl_erase_seq(stdskl *l, stdit *b, stdit *e); +STDINLINE stdsize stdskl_erase_key(stdskl *l, const void *key); + +/* Randomization */ + +STDINLINE void stdskl_dseed(stdskl *l, const void *seed, stdsize sizeof_seed); + +/* Iterator Fcns */ + +STDINLINE const void * stdskl_it_key(const stdit *it); +STDINLINE stdsize stdskl_it_key_size(const stdit *it); +STDINLINE void * stdskl_it_val(const stdit *it); +STDINLINE stdsize stdskl_it_val_size(const stdit *it); +STDINLINE stdbool stdskl_it_eq(const stdit *it1, const stdit *it2); + +STDINLINE stdit * stdskl_it_next(stdit *it); +STDINLINE stdit * stdskl_it_advance(stdit *it, stdsize num_advance); +STDINLINE stdit * stdskl_it_prev(stdit *it); +STDINLINE stdit * stdskl_it_retreat(stdit *it, stdsize num_retreat); + +# ifdef __cplusplus +} +# endif + +#endif Modified: vendor/stdutil/current/src/stdutil/stdthread.h =================================================================== --- vendor/stdutil/current/src/stdutil/stdthread.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stdthread.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). @@ -22,22 +22,21 @@ #ifndef stdthread_h_2000_03_14_12_28_17_jschultz_at_cnds_jhu_edu #define stdthread_h_2000_03_14_12_28_17_jschultz_at_cnds_jhu_edu -#if defined(_REENTRANT) /* NOTE: these types and functions are only declared+defined when _REENTRANT is defined */ +#include <stdutil/stddefines.h> -# include <stdutil/stddefines.h> - -# ifdef __cplusplus +#ifdef __cplusplus extern "C" { -# endif +#endif typedef enum { + STDMUTEX_NULL = (int) 0xe38a690cUL, STDMUTEX_FAST = (int) 0xa720c831UL, STDMUTEX_RCRSV = (int) 0x3f6c20deUL } stdmutex_type; -# include <stdutil/private/stdthread_p.h> +#include <stdutil/private/stdthread_p.h> /* Declare thread entry functions like this: void * STDTHREAD_FCN foo(void * arg); */ @@ -80,4 +79,3 @@ # endif #endif -#endif Modified: vendor/stdutil/current/src/stdutil/stdtime.h =================================================================== --- vendor/stdutil/current/src/stdutil/stdtime.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stdtime.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,62 +1,62 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University - * All rights reserved. - * - * The contents of this file are subject to a license (the ``License''). - * You may not use this file except in compliance with the License. The - * specific language governing the rights and limitations of the License - * can be found in the file ``STDUTIL_LICENSE'' found in this - * distribution. - * - * Software distributed under the License is distributed on an AS IS - * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. - * - * The Original Software is: - * The Stdutil Library - * - * Contributors: - * Creator - John Lane Schultz ([email protected]) - * The Center for Networking and Distributed Systems - * (CNDS - http://www.cnds.jhu.edu) - */ - -#ifndef stdtime_h_2003_12_18_18_09_56_jschultz_at_cnds_jhu_edu -#define stdtime_h_2003_12_18_18_09_56_jschultz_at_cnds_jhu_edu - -#include <stdutil/stddefines.h> - -#ifdef __cplusplus -extern "C" { -#endif - -typedef struct -{ - stdint64 sec; - stdint32 nano; - -} stdtime; - -typedef stdint64 stdtime64; /* time represented in nanoseconds */ - -STDINLINE stdcode stdtime_now(stdtime *abs_time); -STDINLINE stdtime stdtime_time64(stdtime64 src); - -STDINLINE int stdtime_cmp(stdtime ls, stdtime rs); -STDINLINE int stdtime_sign(stdtime t); - -STDINLINE stdtime stdtime_neg(stdtime t); -STDINLINE stdtime stdtime_add(stdtime ls, stdtime rs); -STDINLINE stdtime stdtime_sub(stdtime ls, stdtime rs); - -STDINLINE stdcode stdtime64_now(stdtime64 *abs_time); -STDINLINE stdtime64 stdtime64_time(stdtime t); /* conversion can silently over/under flow */ - -/* sleep fcns */ - -STDINLINE stdcode stdsleep(stdtime delta, stdtime * rem); -STDINLINE stdcode stdsleep64(stdtime64 delta, stdtime64 * rem); - -#ifdef __cplusplus -} -#endif - -#endif +/* Copyright (c) 2000-2009, The Johns Hopkins University + * All rights reserved. + * + * The contents of this file are subject to a license (the ``License''). + * You may not use this file except in compliance with the License. The + * specific language governing the rights and limitations of the License + * can be found in the file ``STDUTIL_LICENSE'' found in this + * distribution. + * + * Software distributed under the License is distributed on an AS IS + * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. + * + * The Original Software is: + * The Stdutil Library + * + * Contributors: + * Creator - John Lane Schultz ([email protected]) + * The Center for Networking and Distributed Systems + * (CNDS - http://www.cnds.jhu.edu) + */ + +#ifndef stdtime_h_2003_12_18_18_09_56_jschultz_at_cnds_jhu_edu +#define stdtime_h_2003_12_18_18_09_56_jschultz_at_cnds_jhu_edu + +#include <stdutil/stddefines.h> + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct +{ + stdint64 sec; + stdint32 nano; + +} stdtime; + +typedef stdint64 stdtime64; /* time represented in nanoseconds */ + +STDINLINE stdcode stdtime_now(stdtime *abs_time); +STDINLINE stdtime stdtime_time64(stdtime64 src); + +STDINLINE int stdtime_cmp(stdtime ls, stdtime rs); +STDINLINE int stdtime_sign(stdtime t); + +STDINLINE stdtime stdtime_neg(stdtime t); +STDINLINE stdtime stdtime_add(stdtime ls, stdtime rs); +STDINLINE stdtime stdtime_sub(stdtime ls, stdtime rs); + +STDINLINE stdcode stdtime64_now(stdtime64 *abs_time); +STDINLINE stdtime64 stdtime64_time(stdtime t); /* conversion can silently over/under flow */ + +/* sleep fcns */ + +STDINLINE stdcode stdsleep(stdtime delta, stdtime * rem); +STDINLINE stdcode stdsleep64(stdtime64 delta, stdtime64 * rem); + +#ifdef __cplusplus +} +#endif + +#endif Modified: vendor/stdutil/current/src/stdutil/stdutil.h =================================================================== --- vendor/stdutil/current/src/stdutil/stdutil.h 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil/stdutil.h 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). Modified: vendor/stdutil/current/src/stdutil.c =================================================================== --- vendor/stdutil/current/src/stdutil.c 2009-06-02 03:59:20 UTC (rev 420) +++ vendor/stdutil/current/src/stdutil.c 2009-06-04 20:38:26 UTC (rev 421) @@ -1,4 +1,4 @@ -/* Copyright (c) 2000-2006, The Johns Hopkins University +/* Copyright (c) 2000-2009, The Johns Hopkins University * All rights reserved. * * The contents of this file are subject to a license (the ``License''). @@ -219,7 +219,7 @@ defined (__BORLANDC__) || defined (__TURBOC__)) # define stdhcode_sfh_get16bits(d) ( *((const stduint16*)(d)) ) #else -# define stdhcode_sfh_get16bits(d) ( ((stduint32) *((const stduint8 *)(d) + 1) << 8) | *(const stduint32 *)(d) ) +# define stdhcode_sfh_get16bits(d) ( ((stduint32) *((const stduint8 *)(d) + 1) << 8) | (stduint32) *(const stduint8 *)(d) ) #endif STDINLINE stduint32 stdhcode_sfh(const void * buf, stdsize buf_len)