diff options
Diffstat (limited to 'gl/lib')
52 files changed, 7973 insertions, 128 deletions
diff --git a/gl/lib/Makefile.am b/gl/lib/Makefile.am index 6ae85232..2bb6646e 100644 --- a/gl/lib/Makefile.am +++ b/gl/lib/Makefile.am @@ -36,11 +36,13 @@ # --po-domain=man-db \ # --no-vc-files \ # argp \ +# array-list \ # canonicalize \ # closedir \ # dirent \ # dirname \ # error \ +# fcntl \ # flock \ # fnmatch-gnu \ # fstat \ @@ -51,9 +53,14 @@ # gitlog-to-changelog \ # glob \ # gnupload \ +# hash-map \ +# hash-pjw-bare \ +# hash-set \ # idpriv-drop \ # idpriv-droptemp \ +# lchown \ # lib-ignore \ +# linkedhash-list \ # localcharset \ # lock \ # memmem \ @@ -65,6 +72,7 @@ # openat \ # opendir \ # progname \ +# rbtree-list \ # regex \ # rename \ # setenv \ @@ -72,6 +80,8 @@ # signal \ # sigprocmask \ # stat-time \ +# stdbool \ +# strcase \ # strcasestr \ # strerror \ # strsep \ @@ -81,6 +91,10 @@ # warnings \ # xalloc \ # xgetcwd \ +# xlist \ +# xmap \ +# xset \ +# xstdopen \ # xstrndup \ # xvasprintf @@ -178,6 +192,12 @@ libgnu_la_SOURCES += argp.h argp-ba.c argp-eexst.c argp-fmtstream.c ## end gnulib module argp +## begin gnulib module array-list + +libgnu_la_SOURCES += gl_array_list.h gl_array_list.c + +## end gnulib module array-list + ## begin gnulib module assure @@ -235,6 +255,15 @@ EXTRA_libgnu_la_SOURCES += chdir-long.c ## end gnulib module chdir-long +## begin gnulib module chown + + +EXTRA_DIST += chown.c fchown-stub.c + +EXTRA_libgnu_la_SOURCES += chown.c fchown-stub.c + +## end gnulib module chown + ## begin gnulib module cloexec libgnu_la_SOURCES += cloexec.c @@ -820,12 +849,30 @@ EXTRA_DIST += hash.h ## end gnulib module hash +## begin gnulib module hash-map + +libgnu_la_SOURCES += gl_hash_map.h gl_hash_map.c gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h + +## end gnulib module hash-map + ## begin gnulib module hash-pjw libgnu_la_SOURCES += hash-pjw.h hash-pjw.c ## end gnulib module hash-pjw +## begin gnulib module hash-pjw-bare + +libgnu_la_SOURCES += hash-pjw-bare.h hash-pjw-bare.c + +## end gnulib module hash-pjw-bare + +## begin gnulib module hash-set + +libgnu_la_SOURCES += gl_hash_set.h gl_hash_set.c gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h + +## end gnulib module hash-set + ## begin gnulib module hash-triple libgnu_la_SOURCES += hash-triple.c @@ -907,6 +954,15 @@ EXTRA_DIST += langinfo.in.h ## end gnulib module langinfo +## begin gnulib module lchown + + +EXTRA_DIST += lchown.c + +EXTRA_libgnu_la_SOURCES += lchown.c + +## end gnulib module lchown + ## begin gnulib module libc-config @@ -942,6 +998,18 @@ EXTRA_DIST += limits.in.h ## end gnulib module limits-h +## begin gnulib module linkedhash-list + +libgnu_la_SOURCES += gl_linkedhash_list.h gl_linkedhash_list.c gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h gl_anylinked_list1.h gl_anylinked_list2.h + +## end gnulib module linkedhash-list + +## begin gnulib module list + +libgnu_la_SOURCES += gl_list.h gl_list.c + +## end gnulib module list + ## begin gnulib module localcharset libgnu_la_SOURCES += localcharset.c @@ -1049,6 +1117,12 @@ EXTRA_DIST += malloca.h ## end gnulib module malloca +## begin gnulib module map + +libgnu_la_SOURCES += gl_map.h gl_map.c + +## end gnulib module map + ## begin gnulib module mbrtowc @@ -1271,6 +1345,12 @@ EXTRA_libgnu_la_SOURCES += rawmemchr.c ## end gnulib module rawmemchr +## begin gnulib module rbtree-list + +libgnu_la_SOURCES += gl_rbtree_list.h gl_rbtree_list.c gl_anyrbtree_list1.h gl_anyrbtree_list2.h gl_anytree_list1.h gl_anytree_list2.h + +## end gnulib module rbtree-list + ## begin gnulib module readdir @@ -1374,6 +1454,12 @@ EXTRA_libgnu_la_SOURCES += select.c ## end gnulib module select +## begin gnulib module set + +libgnu_la_SOURCES += gl_set.h gl_set.c + +## end gnulib module set + ## begin gnulib module setenv @@ -1927,6 +2013,14 @@ EXTRA_DIST += stdlib.in.h ## end gnulib module stdlib +## begin gnulib module stdopen + +libgnu_la_SOURCES += stdopen.c + +EXTRA_DIST += stdopen.h + +## end gnulib module stdopen + ## begin gnulib module strcase @@ -3029,12 +3123,38 @@ EXTRA_DIST += xgetcwd.h ## end gnulib module xgetcwd +## begin gnulib module xlist + +libgnu_la_SOURCES += gl_xlist.h gl_xlist.c + +## end gnulib module xlist + +## begin gnulib module xmap + +libgnu_la_SOURCES += gl_xmap.h gl_xmap.c + +## end gnulib module xmap + +## begin gnulib module xset + +libgnu_la_SOURCES += gl_xset.h gl_xset.c + +## end gnulib module xset + ## begin gnulib module xsize libgnu_la_SOURCES += xsize.h xsize.c ## end gnulib module xsize +## begin gnulib module xstdopen + +libgnu_la_SOURCES += xstdopen.c + +EXTRA_DIST += xstdopen.h + +## end gnulib module xstdopen + ## begin gnulib module xstrndup libgnu_la_SOURCES += xstrndup.h xstrndup.c diff --git a/gl/lib/Makefile.in b/gl/lib/Makefile.in index f95eca35..3433fb81 100644 --- a/gl/lib/Makefile.in +++ b/gl/lib/Makefile.in @@ -50,11 +50,13 @@ # --po-domain=man-db \ # --no-vc-files \ # argp \ +# array-list \ # canonicalize \ # closedir \ # dirent \ # dirname \ # error \ +# fcntl \ # flock \ # fnmatch-gnu \ # fstat \ @@ -65,9 +67,14 @@ # gitlog-to-changelog \ # glob \ # gnupload \ +# hash-map \ +# hash-pjw-bare \ +# hash-set \ # idpriv-drop \ # idpriv-droptemp \ +# lchown \ # lib-ignore \ +# linkedhash-list \ # localcharset \ # lock \ # memmem \ @@ -79,6 +86,7 @@ # openat \ # opendir \ # progname \ +# rbtree-list \ # regex \ # rename \ # setenv \ @@ -86,6 +94,8 @@ # signal \ # sigprocmask \ # stat-time \ +# stdbool \ +# strcase \ # strcasestr \ # strerror \ # strsep \ @@ -95,6 +105,10 @@ # warnings \ # xalloc \ # xgetcwd \ +# xlist \ +# xmap \ +# xset \ +# xstdopen \ # xstrndup \ # xvasprintf @@ -184,6 +198,7 @@ am__aclocal_m4_deps = $(top_srcdir)/m4/man-arg-automatic-create.m4 \ $(top_srcdir)/m4/man-arg-db.m4 \ $(top_srcdir)/m4/man-arg-device.m4 \ $(top_srcdir)/m4/man-arg-mandirs.m4 \ + $(top_srcdir)/m4/man-arg-manual.m4 \ $(top_srcdir)/m4/man-arg-override-dir.m4 \ $(top_srcdir)/m4/man-arg-sections.m4 \ $(top_srcdir)/m4/man-arg-setuid.m4 \ @@ -206,7 +221,7 @@ am__aclocal_m4_deps = $(top_srcdir)/m4/man-arg-automatic-create.m4 \ $(top_srcdir)/gl/m4/btowc.m4 \ $(top_srcdir)/gl/m4/builtin-expect.m4 \ $(top_srcdir)/gl/m4/canonicalize.m4 \ - $(top_srcdir)/gl/m4/chdir-long.m4 \ + $(top_srcdir)/gl/m4/chdir-long.m4 $(top_srcdir)/gl/m4/chown.m4 \ $(top_srcdir)/gl/m4/clock_time.m4 $(top_srcdir)/gl/m4/close.m4 \ $(top_srcdir)/gl/m4/closedir.m4 $(top_srcdir)/gl/m4/codeset.m4 \ $(top_srcdir)/gl/m4/d-ino.m4 $(top_srcdir)/gl/m4/d-type.m4 \ @@ -250,7 +265,7 @@ am__aclocal_m4_deps = $(top_srcdir)/m4/man-arg-automatic-create.m4 \ $(top_srcdir)/gl/m4/intmax_t.m4 \ $(top_srcdir)/gl/m4/inttypes_h.m4 $(top_srcdir)/gl/m4/ioctl.m4 \ $(top_srcdir)/gl/m4/langinfo_h.m4 \ - $(top_srcdir)/gl/m4/largefile.m4 \ + $(top_srcdir)/gl/m4/largefile.m4 $(top_srcdir)/gl/m4/lchown.m4 \ $(top_srcdir)/gl/m4/lib-ignore.m4 \ $(top_srcdir)/gl/m4/lib-ld.m4 $(top_srcdir)/gl/m4/lib-link.m4 \ $(top_srcdir)/gl/m4/lib-prefix.m4 \ @@ -357,22 +372,26 @@ am__DEPENDENCIES_1 = am__dirstamp = $(am__leading_dot)dirstamp am_libgnu_la_OBJECTS = areadlink-with-size.lo argp-ba.lo argp-eexst.lo \ argp-fmtstream.lo argp-fs-xinl.lo argp-help.lo argp-parse.lo \ - argp-pin.lo argp-pv.lo argp-pvh.lo argp-xinl.lo bitrotate.lo \ - canonicalize.lo cloexec.lo dirname.lo basename.lo \ - dirname-lgpl.lo basename-lgpl.lo stripslash.lo exitfail.lo \ - fd-hook.lo fd-safer-flag.lo dup-safer-flag.lo file-set.lo \ - filenamecat-lgpl.lo getprogname.lo gettime.lo hard-locale.lo \ - hash.lo hash-pjw.lo hash-triple.lo idpriv-drop.lo \ - idpriv-droptemp.lo localcharset.lo glthread/lock.lo malloca.lo \ - nonblocking.lo openat-die.lo progname.lo same.lo save-cwd.lo \ - malloc/scratch_buffer_grow.lo \ + argp-pin.lo argp-pv.lo argp-pvh.lo argp-xinl.lo \ + gl_array_list.lo bitrotate.lo canonicalize.lo cloexec.lo \ + dirname.lo basename.lo dirname-lgpl.lo basename-lgpl.lo \ + stripslash.lo exitfail.lo fd-hook.lo fd-safer-flag.lo \ + dup-safer-flag.lo file-set.lo filenamecat-lgpl.lo \ + getprogname.lo gettime.lo hard-locale.lo hash.lo \ + gl_hash_map.lo hash-pjw.lo hash-pjw-bare.lo gl_hash_set.lo \ + hash-triple.lo idpriv-drop.lo idpriv-droptemp.lo \ + gl_linkedhash_list.lo gl_list.lo localcharset.lo \ + glthread/lock.lo malloca.lo gl_map.lo nonblocking.lo \ + openat-die.lo progname.lo gl_rbtree_list.lo same.lo \ + save-cwd.lo malloc/scratch_buffer_grow.lo \ malloc/scratch_buffer_grow_preserve.lo \ - malloc/scratch_buffer_set_array_size.lo sig-handler.lo \ - sockets.lo stat-time.lo strnlen1.lo sys_socket.lo tempname.lo \ - glthread/threadlib.lo timespec.lo unistd.lo dup-safer.lo \ - fd-safer.lo pipe-safer.lo utimens.lo wctype-h.lo xmalloc.lo \ - xalloc-die.lo xgetcwd.lo xsize.lo xstrndup.lo xvasprintf.lo \ - xasprintf.lo + malloc/scratch_buffer_set_array_size.lo gl_set.lo \ + sig-handler.lo sockets.lo stat-time.lo stdopen.lo strnlen1.lo \ + sys_socket.lo tempname.lo glthread/threadlib.lo timespec.lo \ + unistd.lo dup-safer.lo fd-safer.lo pipe-safer.lo utimens.lo \ + wctype-h.lo xmalloc.lo xalloc-die.lo xgetcwd.lo gl_xlist.lo \ + gl_xmap.lo gl_xset.lo xsize.lo xstdopen.lo xstrndup.lo \ + xvasprintf.lo xasprintf.lo libgnu_la_OBJECTS = $(am_libgnu_la_OBJECTS) AM_V_lt = $(am__v_lt_@AM_V@) am__v_lt_ = $(am__v_lt_@AM_DEFAULT_V@) @@ -407,31 +426,38 @@ am__depfiles_remade = ./$(DEPDIR)/alloca.Plo \ ./$(DEPDIR)/basename-lgpl.Plo ./$(DEPDIR)/basename.Plo \ ./$(DEPDIR)/bitrotate.Plo ./$(DEPDIR)/btowc.Plo \ ./$(DEPDIR)/canonicalize-lgpl.Plo ./$(DEPDIR)/canonicalize.Plo \ - ./$(DEPDIR)/chdir-long.Plo ./$(DEPDIR)/cloexec.Plo \ - ./$(DEPDIR)/close.Plo ./$(DEPDIR)/closedir.Plo \ - ./$(DEPDIR)/dirfd.Plo ./$(DEPDIR)/dirname-lgpl.Plo \ - ./$(DEPDIR)/dirname.Plo ./$(DEPDIR)/dup-safer-flag.Plo \ - ./$(DEPDIR)/dup-safer.Plo ./$(DEPDIR)/dup.Plo \ - ./$(DEPDIR)/dup2.Plo ./$(DEPDIR)/error.Plo \ + ./$(DEPDIR)/chdir-long.Plo ./$(DEPDIR)/chown.Plo \ + ./$(DEPDIR)/cloexec.Plo ./$(DEPDIR)/close.Plo \ + ./$(DEPDIR)/closedir.Plo ./$(DEPDIR)/dirfd.Plo \ + ./$(DEPDIR)/dirname-lgpl.Plo ./$(DEPDIR)/dirname.Plo \ + ./$(DEPDIR)/dup-safer-flag.Plo ./$(DEPDIR)/dup-safer.Plo \ + ./$(DEPDIR)/dup.Plo ./$(DEPDIR)/dup2.Plo ./$(DEPDIR)/error.Plo \ ./$(DEPDIR)/exitfail.Plo ./$(DEPDIR)/fchdir.Plo \ - ./$(DEPDIR)/fcntl.Plo ./$(DEPDIR)/fd-hook.Plo \ - ./$(DEPDIR)/fd-safer-flag.Plo ./$(DEPDIR)/fd-safer.Plo \ - ./$(DEPDIR)/fdopendir.Plo ./$(DEPDIR)/file-set.Plo \ - ./$(DEPDIR)/filenamecat-lgpl.Plo ./$(DEPDIR)/float.Plo \ - ./$(DEPDIR)/flock.Plo ./$(DEPDIR)/fnmatch.Plo \ - ./$(DEPDIR)/fnmatch_loop.Plo ./$(DEPDIR)/fstat.Plo \ - ./$(DEPDIR)/fstatat.Plo ./$(DEPDIR)/futimens.Plo \ - ./$(DEPDIR)/getcwd-lgpl.Plo ./$(DEPDIR)/getcwd.Plo \ - ./$(DEPDIR)/getdelim.Plo ./$(DEPDIR)/getdtablesize.Plo \ - ./$(DEPDIR)/getline.Plo ./$(DEPDIR)/getlogin_r.Plo \ - ./$(DEPDIR)/getopt.Plo ./$(DEPDIR)/getopt1.Plo \ - ./$(DEPDIR)/getprogname.Plo ./$(DEPDIR)/gettime.Plo \ - ./$(DEPDIR)/gettimeofday.Plo ./$(DEPDIR)/glob.Plo \ + ./$(DEPDIR)/fchown-stub.Plo ./$(DEPDIR)/fcntl.Plo \ + ./$(DEPDIR)/fd-hook.Plo ./$(DEPDIR)/fd-safer-flag.Plo \ + ./$(DEPDIR)/fd-safer.Plo ./$(DEPDIR)/fdopendir.Plo \ + ./$(DEPDIR)/file-set.Plo ./$(DEPDIR)/filenamecat-lgpl.Plo \ + ./$(DEPDIR)/float.Plo ./$(DEPDIR)/flock.Plo \ + ./$(DEPDIR)/fnmatch.Plo ./$(DEPDIR)/fnmatch_loop.Plo \ + ./$(DEPDIR)/fstat.Plo ./$(DEPDIR)/fstatat.Plo \ + ./$(DEPDIR)/futimens.Plo ./$(DEPDIR)/getcwd-lgpl.Plo \ + ./$(DEPDIR)/getcwd.Plo ./$(DEPDIR)/getdelim.Plo \ + ./$(DEPDIR)/getdtablesize.Plo ./$(DEPDIR)/getline.Plo \ + ./$(DEPDIR)/getlogin_r.Plo ./$(DEPDIR)/getopt.Plo \ + ./$(DEPDIR)/getopt1.Plo ./$(DEPDIR)/getprogname.Plo \ + ./$(DEPDIR)/gettime.Plo ./$(DEPDIR)/gettimeofday.Plo \ + ./$(DEPDIR)/gl_array_list.Plo ./$(DEPDIR)/gl_hash_map.Plo \ + ./$(DEPDIR)/gl_hash_set.Plo ./$(DEPDIR)/gl_linkedhash_list.Plo \ + ./$(DEPDIR)/gl_list.Plo ./$(DEPDIR)/gl_map.Plo \ + ./$(DEPDIR)/gl_rbtree_list.Plo ./$(DEPDIR)/gl_set.Plo \ + ./$(DEPDIR)/gl_xlist.Plo ./$(DEPDIR)/gl_xmap.Plo \ + ./$(DEPDIR)/gl_xset.Plo ./$(DEPDIR)/glob.Plo \ ./$(DEPDIR)/glob_pattern_p.Plo ./$(DEPDIR)/globfree.Plo \ - ./$(DEPDIR)/hard-locale.Plo ./$(DEPDIR)/hash-pjw.Plo \ - ./$(DEPDIR)/hash-triple.Plo ./$(DEPDIR)/hash.Plo \ - ./$(DEPDIR)/idpriv-drop.Plo ./$(DEPDIR)/idpriv-droptemp.Plo \ - ./$(DEPDIR)/ioctl.Plo ./$(DEPDIR)/itold.Plo \ + ./$(DEPDIR)/hard-locale.Plo ./$(DEPDIR)/hash-pjw-bare.Plo \ + ./$(DEPDIR)/hash-pjw.Plo ./$(DEPDIR)/hash-triple.Plo \ + ./$(DEPDIR)/hash.Plo ./$(DEPDIR)/idpriv-drop.Plo \ + ./$(DEPDIR)/idpriv-droptemp.Plo ./$(DEPDIR)/ioctl.Plo \ + ./$(DEPDIR)/itold.Plo ./$(DEPDIR)/lchown.Plo \ ./$(DEPDIR)/localcharset.Plo ./$(DEPDIR)/localeconv.Plo \ ./$(DEPDIR)/localtime-buffer.Plo ./$(DEPDIR)/lstat.Plo \ ./$(DEPDIR)/malloc.Plo ./$(DEPDIR)/malloca.Plo \ @@ -461,21 +487,22 @@ am__depfiles_remade = ./$(DEPDIR)/alloca.Plo \ ./$(DEPDIR)/sockets.Plo ./$(DEPDIR)/stat-time.Plo \ ./$(DEPDIR)/stat-w32.Plo ./$(DEPDIR)/stat.Plo \ ./$(DEPDIR)/stdio-read.Plo ./$(DEPDIR)/stdio-write.Plo \ - ./$(DEPDIR)/strcasecmp.Plo ./$(DEPDIR)/strcasestr.Plo \ - ./$(DEPDIR)/strchrnul.Plo ./$(DEPDIR)/strdup.Plo \ - ./$(DEPDIR)/strerror-override.Plo ./$(DEPDIR)/strerror.Plo \ - ./$(DEPDIR)/stripslash.Plo ./$(DEPDIR)/strncasecmp.Plo \ - ./$(DEPDIR)/strndup.Plo ./$(DEPDIR)/strnlen.Plo \ - ./$(DEPDIR)/strnlen1.Plo ./$(DEPDIR)/strsep.Plo \ - ./$(DEPDIR)/sys_socket.Plo ./$(DEPDIR)/tempname.Plo \ - ./$(DEPDIR)/timespec.Plo ./$(DEPDIR)/unistd.Plo \ - ./$(DEPDIR)/unsetenv.Plo ./$(DEPDIR)/utime.Plo \ - ./$(DEPDIR)/utimens.Plo ./$(DEPDIR)/vasnprintf.Plo \ - ./$(DEPDIR)/vasprintf.Plo ./$(DEPDIR)/vsnprintf.Plo \ - ./$(DEPDIR)/wcrtomb.Plo ./$(DEPDIR)/wctype-h.Plo \ - ./$(DEPDIR)/xalloc-die.Plo ./$(DEPDIR)/xasprintf.Plo \ - ./$(DEPDIR)/xgetcwd.Plo ./$(DEPDIR)/xmalloc.Plo \ - ./$(DEPDIR)/xsize.Plo ./$(DEPDIR)/xstrndup.Plo \ + ./$(DEPDIR)/stdopen.Plo ./$(DEPDIR)/strcasecmp.Plo \ + ./$(DEPDIR)/strcasestr.Plo ./$(DEPDIR)/strchrnul.Plo \ + ./$(DEPDIR)/strdup.Plo ./$(DEPDIR)/strerror-override.Plo \ + ./$(DEPDIR)/strerror.Plo ./$(DEPDIR)/stripslash.Plo \ + ./$(DEPDIR)/strncasecmp.Plo ./$(DEPDIR)/strndup.Plo \ + ./$(DEPDIR)/strnlen.Plo ./$(DEPDIR)/strnlen1.Plo \ + ./$(DEPDIR)/strsep.Plo ./$(DEPDIR)/sys_socket.Plo \ + ./$(DEPDIR)/tempname.Plo ./$(DEPDIR)/timespec.Plo \ + ./$(DEPDIR)/unistd.Plo ./$(DEPDIR)/unsetenv.Plo \ + ./$(DEPDIR)/utime.Plo ./$(DEPDIR)/utimens.Plo \ + ./$(DEPDIR)/vasnprintf.Plo ./$(DEPDIR)/vasprintf.Plo \ + ./$(DEPDIR)/vsnprintf.Plo ./$(DEPDIR)/wcrtomb.Plo \ + ./$(DEPDIR)/wctype-h.Plo ./$(DEPDIR)/xalloc-die.Plo \ + ./$(DEPDIR)/xasprintf.Plo ./$(DEPDIR)/xgetcwd.Plo \ + ./$(DEPDIR)/xmalloc.Plo ./$(DEPDIR)/xsize.Plo \ + ./$(DEPDIR)/xstdopen.Plo ./$(DEPDIR)/xstrndup.Plo \ ./$(DEPDIR)/xvasprintf.Plo glthread/$(DEPDIR)/lock.Plo \ glthread/$(DEPDIR)/threadlib.Plo \ malloc/$(DEPDIR)/scratch_buffer_grow.Plo \ @@ -1644,25 +1671,25 @@ noinst_LIBRARIES = noinst_LTLIBRARIES = libgnu.la EXTRA_DIST = alloca.c alloca.in.h areadlink.h assure.h openat-priv.h \ openat-proc.c btowc.c canonicalize.h canonicalize-lgpl.c \ - chdir-long.c chdir-long.h cloexec.h close.c closedir.c \ - dirent-private.h dirent.in.h dirfd.c stripslash.c dirname.h \ - dosname.h dup.c dup2.c errno.in.h error.c error.h exitfail.h \ - fchdir.c fcntl.c fcntl.in.h fd-hook.h fdopendir.c file-set.h \ - filename.h filenamecat.h flexmember.h float.c float.in.h \ - itold.c flock.c fnmatch.c fnmatch_loop.c fnmatch.in.h fstat.c \ - stat-w32.c stat-w32.h at-func.c fstatat.c futimens.c getcwd.c \ - getcwd-lgpl.c getdelim.c getdtablesize.c getline.c \ - getlogin_r.c getopt-cdefs.in.h getopt-core.h getopt-ext.h \ - getopt-pfx-core.h getopt-pfx-ext.h getopt.c getopt.in.h \ - getopt1.c getopt_int.h gettimeofday.c \ - $(top_srcdir)/build-aux/gitlog-to-changelog glob.c \ - glob_internal.h glob_pattern_p.c globfree.c glob-libc.h \ + chdir-long.c chdir-long.h chown.c fchown-stub.c cloexec.h \ + close.c closedir.c dirent-private.h dirent.in.h dirfd.c \ + stripslash.c dirname.h dosname.h dup.c dup2.c errno.in.h \ + error.c error.h exitfail.h fchdir.c fcntl.c fcntl.in.h \ + fd-hook.h fdopendir.c file-set.h filename.h filenamecat.h \ + flexmember.h float.c float.in.h itold.c flock.c fnmatch.c \ + fnmatch_loop.c fnmatch.in.h fstat.c stat-w32.c stat-w32.h \ + at-func.c fstatat.c futimens.c getcwd.c getcwd-lgpl.c \ + getdelim.c getdtablesize.c getline.c getlogin_r.c \ + getopt-cdefs.in.h getopt-core.h getopt-ext.h getopt-pfx-core.h \ + getopt-pfx-ext.h getopt.c getopt.in.h getopt1.c getopt_int.h \ + gettimeofday.c $(top_srcdir)/build-aux/gitlog-to-changelog \ + glob.c glob_internal.h glob_pattern_p.c globfree.c glob-libc.h \ glob.in.h $(top_srcdir)/build-aux/gnupload hard-locale.h \ hash.h hash-triple.h $(top_srcdir)/build-aux/config.rpath \ idpriv.h idpriv.h intprops.h ioctl.c w32sock.h langinfo.in.h \ - cdefs.h libc-config.h limits.in.h localcharset.h locale.in.h \ - localeconv.c localtime-buffer.c localtime-buffer.h lstat.c \ - malloc.c malloc.c malloca.h mbrtowc.c mbsinit.c \ + lchown.c cdefs.h libc-config.h limits.in.h localcharset.h \ + locale.in.h localeconv.c localtime-buffer.c localtime-buffer.h \ + lstat.c malloc.c malloc.c malloca.h mbrtowc.c mbsinit.c \ mbsrtowcs-impl.h mbsrtowcs-state.c mbsrtowcs.c mbtowc-impl.h \ mbtowc.c memchr.c memchr.valgrind memmem.c str-two-way.h \ mempcpy.c memrchr.c mkdir.c mkdtemp.c mkstemp.c msvc-inval.c \ @@ -1678,7 +1705,7 @@ EXTRA_DIST = alloca.c alloca.in.h areadlink.h assure.h openat-priv.h \ sleep.c _Noreturn.h arg-nonnull.h c++defs.h warn-on-use.h \ w32sock.h stat-w32.c stat-w32.h stat.c stat-time.h \ stdalign.in.h stdarg.in.h stdbool.in.h stddef.in.h stdint.in.h \ - stdio.in.h stdlib.in.h strcasecmp.c strncasecmp.c \ + stdio.in.h stdlib.in.h stdopen.h strcasecmp.c strncasecmp.c \ str-two-way.h strcasestr.c strchrnul.c strchrnul.valgrind \ strdup.c streq.h strerror.c strerror-override.c \ strerror-override.h string.in.h strings.in.h strndup.c \ @@ -1691,7 +1718,7 @@ EXTRA_DIST = alloca.c alloca.in.h areadlink.h assure.h openat-priv.h \ printf-args.h printf-parse.c printf-parse.h vasnprintf.c \ vasnprintf.h asprintf.c vasprintf.c verify.h vsnprintf.c \ wchar.in.h wcrtomb.c wctype.in.h xalloc.h xalloc-oversized.h \ - xgetcwd.h xalloc.h + xgetcwd.h xstdopen.h xalloc.h BUILT_SOURCES = $(ALLOCA_H) dirent.h $(ERRNO_H) fcntl.h $(FLOAT_H) \ $(FNMATCH_H) $(GETOPT_H) $(GETOPT_CDEFS_H) $(GLOB_H) \ langinfo.h $(LIMITS_H) locale.h signal.h $(STDALIGN_H) \ @@ -1725,47 +1752,57 @@ AM_CFLAGS = libgnu_la_SOURCES = areadlink-with-size.c argp.h argp-ba.c \ argp-eexst.c argp-fmtstream.c argp-fmtstream.h argp-fs-xinl.c \ argp-help.c argp-namefrob.h argp-parse.c argp-pin.c argp-pv.c \ - argp-pvh.c argp-xinl.c bitrotate.h bitrotate.c canonicalize.c \ - cloexec.c dirname.c basename.c dirname-lgpl.c basename-lgpl.c \ - stripslash.c exitfail.c fd-hook.c fd-safer-flag.c \ - dup-safer-flag.c file-set.c filenamecat-lgpl.c getprogname.h \ - getprogname.c gettext.h gettime.c hard-locale.c hash.c \ - hash-pjw.h hash-pjw.c hash-triple.c idpriv-drop.c \ - idpriv-droptemp.c localcharset.c glthread/lock.h \ - glthread/lock.c malloca.c minmax.h nonblocking.c openat-die.c \ - progname.h progname.c same.c save-cwd.c \ + argp-pvh.c argp-xinl.c gl_array_list.h gl_array_list.c \ + bitrotate.h bitrotate.c canonicalize.c cloexec.c dirname.c \ + basename.c dirname-lgpl.c basename-lgpl.c stripslash.c \ + exitfail.c fd-hook.c fd-safer-flag.c dup-safer-flag.c \ + file-set.c filenamecat-lgpl.c getprogname.h getprogname.c \ + gettext.h gettime.c hard-locale.c hash.c gl_hash_map.h \ + gl_hash_map.c gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h \ + hash-pjw.h hash-pjw.c hash-pjw-bare.h hash-pjw-bare.c \ + gl_hash_set.h gl_hash_set.c gl_anyhash1.h gl_anyhash2.h \ + gl_anyhash_primes.h hash-triple.c idpriv-drop.c \ + idpriv-droptemp.c gl_linkedhash_list.h gl_linkedhash_list.c \ + gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h \ + gl_anylinked_list1.h gl_anylinked_list2.h gl_list.h gl_list.c \ + localcharset.c glthread/lock.h glthread/lock.c malloca.c \ + gl_map.h gl_map.c minmax.h nonblocking.c openat-die.c \ + progname.h progname.c gl_rbtree_list.h gl_rbtree_list.c \ + gl_anyrbtree_list1.h gl_anyrbtree_list2.h gl_anytree_list1.h \ + gl_anytree_list2.h same.c save-cwd.c \ malloc/scratch_buffer_grow.c \ malloc/scratch_buffer_grow_preserve.c \ - malloc/scratch_buffer_set_array_size.c sig-handler.c \ - size_max.h sockets.h sockets.c stat-time.c strnlen1.h \ - strnlen1.c sys_socket.c tempname.c glthread/threadlib.c \ - timespec.c unistd.c dup-safer.c fd-safer.c pipe-safer.c \ - utimens.c wctype-h.c xmalloc.c xalloc-die.c xgetcwd.c xsize.h \ - xsize.c xstrndup.h xstrndup.c xvasprintf.h xvasprintf.c \ - xasprintf.c + malloc/scratch_buffer_set_array_size.c gl_set.h gl_set.c \ + sig-handler.c size_max.h sockets.h sockets.c stat-time.c \ + stdopen.c strnlen1.h strnlen1.c sys_socket.c tempname.c \ + glthread/threadlib.c timespec.c unistd.c dup-safer.c \ + fd-safer.c pipe-safer.c utimens.c wctype-h.c xmalloc.c \ + xalloc-die.c xgetcwd.c gl_xlist.h gl_xlist.c gl_xmap.h \ + gl_xmap.c gl_xset.h gl_xset.c xsize.h xsize.c xstdopen.c \ + xstrndup.h xstrndup.c xvasprintf.h xvasprintf.c xasprintf.c libgnu_la_LIBADD = $(gl_LTLIBOBJS) @LTALLOCA@ libgnu_la_DEPENDENCIES = $(gl_LTLIBOBJS) @LTALLOCA@ EXTRA_libgnu_la_SOURCES = alloca.c openat-proc.c btowc.c \ - canonicalize-lgpl.c chdir-long.c close.c closedir.c dirfd.c \ - stripslash.c dup.c dup2.c error.c fchdir.c fcntl.c fdopendir.c \ - float.c itold.c flock.c fnmatch.c fnmatch_loop.c fstat.c \ - stat-w32.c at-func.c fstatat.c futimens.c getcwd.c \ - getcwd-lgpl.c getdelim.c getdtablesize.c getline.c \ - getlogin_r.c getopt.c getopt1.c gettimeofday.c glob.c \ - glob_pattern_p.c globfree.c ioctl.c localeconv.c \ - localtime-buffer.c lstat.c malloc.c malloc.c mbrtowc.c \ - mbsinit.c mbsrtowcs-state.c mbsrtowcs.c mbtowc.c memchr.c \ - memmem.c mempcpy.c memrchr.c mkdir.c mkdtemp.c mkstemp.c \ - msvc-inval.c msvc-nothrow.c nanosleep.c nl_langinfo.c \ - stdio-read.c stdio-write.c open.c openat.c opendir.c raise.c \ - rawmemchr.c readdir.c readlink.c realloc.c regcomp.c regex.c \ - regex_internal.c regexec.c rename.c rewinddir.c rmdir.c \ - select.c setenv.c sigaction.c sigprocmask.c sleep.c stat-w32.c \ - stat.c strcasecmp.c strncasecmp.c strcasestr.c strchrnul.c \ - strdup.c strerror.c strerror-override.c strndup.c strnlen.c \ - strsep.c unsetenv.c utime.c asnprintf.c printf-args.c \ - printf-parse.c vasnprintf.c asprintf.c vasprintf.c vsnprintf.c \ - wcrtomb.c + canonicalize-lgpl.c chdir-long.c chown.c fchown-stub.c close.c \ + closedir.c dirfd.c stripslash.c dup.c dup2.c error.c fchdir.c \ + fcntl.c fdopendir.c float.c itold.c flock.c fnmatch.c \ + fnmatch_loop.c fstat.c stat-w32.c at-func.c fstatat.c \ + futimens.c getcwd.c getcwd-lgpl.c getdelim.c getdtablesize.c \ + getline.c getlogin_r.c getopt.c getopt1.c gettimeofday.c \ + glob.c glob_pattern_p.c globfree.c ioctl.c lchown.c \ + localeconv.c localtime-buffer.c lstat.c malloc.c malloc.c \ + mbrtowc.c mbsinit.c mbsrtowcs-state.c mbsrtowcs.c mbtowc.c \ + memchr.c memmem.c mempcpy.c memrchr.c mkdir.c mkdtemp.c \ + mkstemp.c msvc-inval.c msvc-nothrow.c nanosleep.c \ + nl_langinfo.c stdio-read.c stdio-write.c open.c openat.c \ + opendir.c raise.c rawmemchr.c readdir.c readlink.c realloc.c \ + regcomp.c regex.c regex_internal.c regexec.c rename.c \ + rewinddir.c rmdir.c select.c setenv.c sigaction.c \ + sigprocmask.c sleep.c stat-w32.c stat.c strcasecmp.c \ + strncasecmp.c strcasestr.c strchrnul.c strdup.c strerror.c \ + strerror-override.c strndup.c strnlen.c strsep.c unsetenv.c \ + utime.c asnprintf.c printf-args.c printf-parse.c vasnprintf.c \ + asprintf.c vasprintf.c vsnprintf.c wcrtomb.c libgnu_la_LDFLAGS = $(AM_LDFLAGS) -no-undefined $(LIBSOCKET) \ $(LIB_CLOCK_GETTIME) $(LIB_GETLOGIN) $(LIB_NANOSLEEP) \ $(LIB_SELECT) $(LTLIBINTL) $(LTLIBTHREAD) @@ -1900,6 +1937,7 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/canonicalize-lgpl.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/canonicalize.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/chdir-long.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/chown.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/cloexec.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/close.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/closedir.Plo@am__quote@ # am--include-marker @@ -1913,6 +1951,7 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/error.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/exitfail.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fchdir.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fchown-stub.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fcntl.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fd-hook.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/fd-safer-flag.Plo@am__quote@ # am--include-marker @@ -1938,10 +1977,22 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/getprogname.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gettime.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gettimeofday.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gl_array_list.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gl_hash_map.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gl_hash_set.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gl_linkedhash_list.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gl_list.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gl_map.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gl_rbtree_list.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gl_set.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gl_xlist.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gl_xmap.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/gl_xset.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/glob.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/glob_pattern_p.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/globfree.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/hard-locale.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/hash-pjw-bare.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/hash-pjw.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/hash-triple.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/hash.Plo@am__quote@ # am--include-marker @@ -1949,6 +2000,7 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/idpriv-droptemp.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/ioctl.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/itold.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/lchown.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/localcharset.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/localeconv.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/localtime-buffer.Plo@am__quote@ # am--include-marker @@ -2007,6 +2059,7 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/stat.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/stdio-read.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/stdio-write.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/stdopen.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/strcasecmp.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/strcasestr.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/strchrnul.Plo@am__quote@ # am--include-marker @@ -2036,6 +2089,7 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/xgetcwd.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/xmalloc.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/xsize.Plo@am__quote@ # am--include-marker +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/xstdopen.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/xstrndup.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/xvasprintf.Plo@am__quote@ # am--include-marker @AMDEP_TRUE@@am__include@ @am__quote@glthread/$(DEPDIR)/lock.Plo@am__quote@ # am--include-marker @@ -2313,6 +2367,7 @@ distclean: distclean-recursive -rm -f ./$(DEPDIR)/canonicalize-lgpl.Plo -rm -f ./$(DEPDIR)/canonicalize.Plo -rm -f ./$(DEPDIR)/chdir-long.Plo + -rm -f ./$(DEPDIR)/chown.Plo -rm -f ./$(DEPDIR)/cloexec.Plo -rm -f ./$(DEPDIR)/close.Plo -rm -f ./$(DEPDIR)/closedir.Plo @@ -2326,6 +2381,7 @@ distclean: distclean-recursive -rm -f ./$(DEPDIR)/error.Plo -rm -f ./$(DEPDIR)/exitfail.Plo -rm -f ./$(DEPDIR)/fchdir.Plo + -rm -f ./$(DEPDIR)/fchown-stub.Plo -rm -f ./$(DEPDIR)/fcntl.Plo -rm -f ./$(DEPDIR)/fd-hook.Plo -rm -f ./$(DEPDIR)/fd-safer-flag.Plo @@ -2351,10 +2407,22 @@ distclean: distclean-recursive -rm -f ./$(DEPDIR)/getprogname.Plo -rm -f ./$(DEPDIR)/gettime.Plo -rm -f ./$(DEPDIR)/gettimeofday.Plo + -rm -f ./$(DEPDIR)/gl_array_list.Plo + -rm -f ./$(DEPDIR)/gl_hash_map.Plo + -rm -f ./$(DEPDIR)/gl_hash_set.Plo + -rm -f ./$(DEPDIR)/gl_linkedhash_list.Plo + -rm -f ./$(DEPDIR)/gl_list.Plo + -rm -f ./$(DEPDIR)/gl_map.Plo + -rm -f ./$(DEPDIR)/gl_rbtree_list.Plo + -rm -f ./$(DEPDIR)/gl_set.Plo + -rm -f ./$(DEPDIR)/gl_xlist.Plo + -rm -f ./$(DEPDIR)/gl_xmap.Plo + -rm -f ./$(DEPDIR)/gl_xset.Plo -rm -f ./$(DEPDIR)/glob.Plo -rm -f ./$(DEPDIR)/glob_pattern_p.Plo -rm -f ./$(DEPDIR)/globfree.Plo -rm -f ./$(DEPDIR)/hard-locale.Plo + -rm -f ./$(DEPDIR)/hash-pjw-bare.Plo -rm -f ./$(DEPDIR)/hash-pjw.Plo -rm -f ./$(DEPDIR)/hash-triple.Plo -rm -f ./$(DEPDIR)/hash.Plo @@ -2362,6 +2430,7 @@ distclean: distclean-recursive -rm -f ./$(DEPDIR)/idpriv-droptemp.Plo -rm -f ./$(DEPDIR)/ioctl.Plo -rm -f ./$(DEPDIR)/itold.Plo + -rm -f ./$(DEPDIR)/lchown.Plo -rm -f ./$(DEPDIR)/localcharset.Plo -rm -f ./$(DEPDIR)/localeconv.Plo -rm -f ./$(DEPDIR)/localtime-buffer.Plo @@ -2420,6 +2489,7 @@ distclean: distclean-recursive -rm -f ./$(DEPDIR)/stat.Plo -rm -f ./$(DEPDIR)/stdio-read.Plo -rm -f ./$(DEPDIR)/stdio-write.Plo + -rm -f ./$(DEPDIR)/stdopen.Plo -rm -f ./$(DEPDIR)/strcasecmp.Plo -rm -f ./$(DEPDIR)/strcasestr.Plo -rm -f ./$(DEPDIR)/strchrnul.Plo @@ -2449,6 +2519,7 @@ distclean: distclean-recursive -rm -f ./$(DEPDIR)/xgetcwd.Plo -rm -f ./$(DEPDIR)/xmalloc.Plo -rm -f ./$(DEPDIR)/xsize.Plo + -rm -f ./$(DEPDIR)/xstdopen.Plo -rm -f ./$(DEPDIR)/xstrndup.Plo -rm -f ./$(DEPDIR)/xvasprintf.Plo -rm -f glthread/$(DEPDIR)/lock.Plo @@ -2523,6 +2594,7 @@ maintainer-clean: maintainer-clean-recursive -rm -f ./$(DEPDIR)/canonicalize-lgpl.Plo -rm -f ./$(DEPDIR)/canonicalize.Plo -rm -f ./$(DEPDIR)/chdir-long.Plo + -rm -f ./$(DEPDIR)/chown.Plo -rm -f ./$(DEPDIR)/cloexec.Plo -rm -f ./$(DEPDIR)/close.Plo -rm -f ./$(DEPDIR)/closedir.Plo @@ -2536,6 +2608,7 @@ maintainer-clean: maintainer-clean-recursive -rm -f ./$(DEPDIR)/error.Plo -rm -f ./$(DEPDIR)/exitfail.Plo -rm -f ./$(DEPDIR)/fchdir.Plo + -rm -f ./$(DEPDIR)/fchown-stub.Plo -rm -f ./$(DEPDIR)/fcntl.Plo -rm -f ./$(DEPDIR)/fd-hook.Plo -rm -f ./$(DEPDIR)/fd-safer-flag.Plo @@ -2561,10 +2634,22 @@ maintainer-clean: maintainer-clean-recursive -rm -f ./$(DEPDIR)/getprogname.Plo -rm -f ./$(DEPDIR)/gettime.Plo -rm -f ./$(DEPDIR)/gettimeofday.Plo + -rm -f ./$(DEPDIR)/gl_array_list.Plo + -rm -f ./$(DEPDIR)/gl_hash_map.Plo + -rm -f ./$(DEPDIR)/gl_hash_set.Plo + -rm -f ./$(DEPDIR)/gl_linkedhash_list.Plo + -rm -f ./$(DEPDIR)/gl_list.Plo + -rm -f ./$(DEPDIR)/gl_map.Plo + -rm -f ./$(DEPDIR)/gl_rbtree_list.Plo + -rm -f ./$(DEPDIR)/gl_set.Plo + -rm -f ./$(DEPDIR)/gl_xlist.Plo + -rm -f ./$(DEPDIR)/gl_xmap.Plo + -rm -f ./$(DEPDIR)/gl_xset.Plo -rm -f ./$(DEPDIR)/glob.Plo -rm -f ./$(DEPDIR)/glob_pattern_p.Plo -rm -f ./$(DEPDIR)/globfree.Plo -rm -f ./$(DEPDIR)/hard-locale.Plo + -rm -f ./$(DEPDIR)/hash-pjw-bare.Plo -rm -f ./$(DEPDIR)/hash-pjw.Plo -rm -f ./$(DEPDIR)/hash-triple.Plo -rm -f ./$(DEPDIR)/hash.Plo @@ -2572,6 +2657,7 @@ maintainer-clean: maintainer-clean-recursive -rm -f ./$(DEPDIR)/idpriv-droptemp.Plo -rm -f ./$(DEPDIR)/ioctl.Plo -rm -f ./$(DEPDIR)/itold.Plo + -rm -f ./$(DEPDIR)/lchown.Plo -rm -f ./$(DEPDIR)/localcharset.Plo -rm -f ./$(DEPDIR)/localeconv.Plo -rm -f ./$(DEPDIR)/localtime-buffer.Plo @@ -2630,6 +2716,7 @@ maintainer-clean: maintainer-clean-recursive -rm -f ./$(DEPDIR)/stat.Plo -rm -f ./$(DEPDIR)/stdio-read.Plo -rm -f ./$(DEPDIR)/stdio-write.Plo + -rm -f ./$(DEPDIR)/stdopen.Plo -rm -f ./$(DEPDIR)/strcasecmp.Plo -rm -f ./$(DEPDIR)/strcasestr.Plo -rm -f ./$(DEPDIR)/strchrnul.Plo @@ -2659,6 +2746,7 @@ maintainer-clean: maintainer-clean-recursive -rm -f ./$(DEPDIR)/xgetcwd.Plo -rm -f ./$(DEPDIR)/xmalloc.Plo -rm -f ./$(DEPDIR)/xsize.Plo + -rm -f ./$(DEPDIR)/xstdopen.Plo -rm -f ./$(DEPDIR)/xstrndup.Plo -rm -f ./$(DEPDIR)/xvasprintf.Plo -rm -f glthread/$(DEPDIR)/lock.Plo diff --git a/gl/lib/argp-help.c b/gl/lib/argp-help.c index febd5477..f4e2e048 100644 --- a/gl/lib/argp-help.c +++ b/gl/lib/argp-help.c @@ -1031,7 +1031,7 @@ static void print_header (const char *str, const struct argp *argp, struct pentry_state *pest) { - const char *tstr = dgettext (argp->argp_domain, str); + const char *tstr = str ? dgettext (argp->argp_domain, str) : NULL; const char *fstr = filter_doc (tstr, ARGP_KEY_HELP_HEADER, argp, pest->state); if (fstr) @@ -1422,8 +1422,10 @@ argp_args_usage (const struct argp *argp, const struct argp_state *state, char *our_level = *levels; int multiple = 0; const struct argp_child *child = argp->children; - const char *tdoc = dgettext (argp->argp_domain, argp->args_doc), *nl = 0; + const char *tdoc = + argp->args_doc ? dgettext (argp->argp_domain, argp->args_doc) : NULL; const char *fdoc = filter_doc (tdoc, ARGP_KEY_HELP_ARGS_DOC, argp, state); + const char *nl = NULL; if (fdoc) { @@ -1487,7 +1489,7 @@ argp_doc (const struct argp *argp, const struct argp_state *state, void *input = 0; int anything = 0; size_t inp_text_limit = 0; - const char *doc = dgettext (argp->argp_domain, argp->doc); + const char *doc = argp->doc ? dgettext (argp->argp_domain, argp->doc) : NULL; const struct argp_child *child = argp->children; if (doc) @@ -1564,7 +1566,7 @@ argp_doc (const struct argp *argp, const struct argp_state *state, } /* Output a usage message for ARGP to STREAM. If called from - argp_state_help, STATE is the relevent parsing state. FLAGS are from the + argp_state_help, STATE is the relevant parsing state. FLAGS are from the set ARGP_HELP_*. NAME is what to use wherever a 'program name' is needed. */ static void diff --git a/gl/lib/argp.h b/gl/lib/argp.h index 317ac034..7aba8877 100644 --- a/gl/lib/argp.h +++ b/gl/lib/argp.h @@ -69,6 +69,9 @@ typedef int error_t; extern "C" { #endif +/* Glibc documentation: + https://www.gnu.org/software/libc/manual/html_node/Argp.html */ + /* A description of a particular option. A pointer to an array of these is passed in the OPTIONS field of an argp structure. Each option entry can correspond to one long option and/or one short option; more @@ -236,9 +239,9 @@ struct argp ARGP_KEY_ definitions below. */ argp_parser_t parser; - /* A string describing what other arguments are wanted by this program. It - is only used by argp_usage to print the "Usage:" message. If it - contains newlines, the strings separated by them are considered + /* If non-NULL, a string describing what other arguments are wanted by this + program. It is only used by argp_usage to print the "Usage:" message. + If it contains newlines, the strings separated by them are considered alternative usage patterns, and printed on separate lines (lines after the first are prefix by " or: " instead of "Usage:"). */ const char *args_doc; diff --git a/gl/lib/cdefs.h b/gl/lib/cdefs.h index f7a10644..96d26164 100644 --- a/gl/lib/cdefs.h +++ b/gl/lib/cdefs.h @@ -340,7 +340,7 @@ semantics. clang++ identifies itself as gcc-4.2, but has support for GNU inlining - semantics, that can be checked fot by using the __GNUC_STDC_INLINE_ and + semantics, that can be checked for by using the __GNUC_STDC_INLINE_ and __GNUC_GNU_INLINE__ macro definitions. */ #if (!defined __cplusplus || __GNUC_PREREQ (4,3) \ || (defined __clang__ && (defined __GNUC_STDC_INLINE__ \ diff --git a/gl/lib/chown.c b/gl/lib/chown.c new file mode 100644 index 00000000..fc73e778 --- /dev/null +++ b/gl/lib/chown.c @@ -0,0 +1,151 @@ +/* provide consistent interface to chown for systems that don't interpret + an ID of -1 as meaning "don't change the corresponding ID". + + Copyright (C) 1997, 2004-2007, 2009-2019 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* written by Jim Meyering */ + +#include <config.h> + +/* Specification. */ +#include <unistd.h> + +#include <errno.h> +#include <fcntl.h> +#include <stdbool.h> +#include <string.h> +#include <sys/stat.h> + +#if !HAVE_CHOWN + +/* Simple stub that always fails with ENOSYS, for mingw. */ +int +chown (const char *file _GL_UNUSED, uid_t uid _GL_UNUSED, + gid_t gid _GL_UNUSED) +{ + errno = ENOSYS; + return -1; +} + +#else /* HAVE_CHOWN */ + +/* Below we refer to the system's chown(). */ +# undef chown + +/* Provide a more-closely POSIX-conforming version of chown on + systems with one or both of the following problems: + - chown doesn't treat an ID of -1 as meaning + "don't change the corresponding ID". + - chown doesn't dereference symlinks. */ + +int +rpl_chown (const char *file, uid_t uid, gid_t gid) +{ + struct stat st; + bool stat_valid = false; + int result; + +# if CHOWN_CHANGE_TIME_BUG + if (gid != (gid_t) -1 || uid != (uid_t) -1) + { + if (stat (file, &st)) + return -1; + stat_valid = true; + } +# endif + +# if CHOWN_FAILS_TO_HONOR_ID_OF_NEGATIVE_ONE + if (gid == (gid_t) -1 || uid == (uid_t) -1) + { + /* Stat file to get id(s) that should remain unchanged. */ + if (!stat_valid && stat (file, &st)) + return -1; + if (gid == (gid_t) -1) + gid = st.st_gid; + if (uid == (uid_t) -1) + uid = st.st_uid; + } +# endif + +# if CHOWN_MODIFIES_SYMLINK + { + /* Handle the case in which the system-supplied chown function + does *not* follow symlinks. Instead, it changes permissions + on the symlink itself. To work around that, we open the + file (but this can fail due to lack of read or write permission) and + use fchown on the resulting descriptor. */ + int open_flags = O_NONBLOCK | O_NOCTTY; + int fd = open (file, O_RDONLY | open_flags); + if (0 <= fd + || (errno == EACCES + && 0 <= (fd = open (file, O_WRONLY | open_flags)))) + { + int saved_errno; + bool fchown_socket_failure; + + result = fchown (fd, uid, gid); + saved_errno = errno; + + /* POSIX says fchown can fail with errno == EINVAL on sockets + and pipes, so fall back on chown in that case. */ + fchown_socket_failure = + (result != 0 && saved_errno == EINVAL + && fstat (fd, &st) == 0 + && (S_ISFIFO (st.st_mode) || S_ISSOCK (st.st_mode))); + + close (fd); + + if (! fchown_socket_failure) + { + errno = saved_errno; + return result; + } + } + else if (errno != EACCES) + return -1; + } +# endif + +# if CHOWN_TRAILING_SLASH_BUG + if (!stat_valid) + { + size_t len = strlen (file); + if (len && file[len - 1] == '/' && stat (file, &st)) + return -1; + } +# endif + + result = chown (file, uid, gid); + +# if CHOWN_CHANGE_TIME_BUG + if (result == 0 && stat_valid + && (uid == st.st_uid || uid == (uid_t) -1) + && (gid == st.st_gid || gid == (gid_t) -1)) + { + /* No change in ownership, but at least one argument was not -1, + so we are required to update ctime. Since chown succeeded, + we assume that chmod will do likewise. Fortunately, on all + known systems where a 'no-op' chown skips the ctime update, a + 'no-op' chmod still does the trick. */ + result = chmod (file, st.st_mode & (S_IRWXU | S_IRWXG | S_IRWXO + | S_ISUID | S_ISGID | S_ISVTX)); + } +# endif + + return result; +} + +#endif /* HAVE_CHOWN */ diff --git a/gl/lib/fchown-stub.c b/gl/lib/fchown-stub.c new file mode 100644 index 00000000..62b69690 --- /dev/null +++ b/gl/lib/fchown-stub.c @@ -0,0 +1,16 @@ +#include <config.h> + +#include <sys/types.h> +#include <errno.h> + +/* A trivial substitute for 'fchown'. + + DJGPP 2.03 and earlier (and perhaps later) don't have 'fchown', + so we pretend no-one has permission for this operation. */ + +int +fchown (int fd, uid_t uid, gid_t gid) +{ + errno = EPERM; + return -1; +} diff --git a/gl/lib/fcntl.c b/gl/lib/fcntl.c index f602fad6..51f62ef7 100644 --- a/gl/lib/fcntl.c +++ b/gl/lib/fcntl.c @@ -545,7 +545,7 @@ rpl_fcntl_DUPFD_CLOEXEC (int fd, int target) #ifdef __KLIBC__ static int -klibc_fcntl (int fd, int action, /* arg */...); +klibc_fcntl (int fd, int action, /* arg */...) { va_list arg_ptr; int arg; diff --git a/gl/lib/file-set.c b/gl/lib/file-set.c index 5916a178..5eb9fae3 100644 --- a/gl/lib/file-set.c +++ b/gl/lib/file-set.c @@ -48,7 +48,7 @@ record_file (Hash_table *ht, char const *file, struct stat const *stats) if (ent_from_table != ent) { - /* There was alread a matching entry in the table, so ENT was + /* There was already a matching entry in the table, so ENT was not inserted. Free it. */ triple_free (ent); } diff --git a/gl/lib/gettext.h b/gl/lib/gettext.h index 89f53d91..c7c0fdb5 100644 --- a/gl/lib/gettext.h +++ b/gl/lib/gettext.h @@ -184,9 +184,16 @@ npgettext_aux (const char *domain, #include <string.h> -#if (((__GNUC__ >= 3 || __GNUG__ >= 2) && !defined __STRICT_ANSI__) \ - /* || (__STDC_VERSION__ == 199901L && !defined __HP_cc) - || (__STDC_VERSION__ >= 201112L && !defined __STDC_NO_VLA__) */ ) +/* GNULIB_NO_VLA can be defined to disable use of VLAs even if supported. + This relates to the -Wvla and -Wvla-larger-than warnings, enabled in + the default GCC many warnings set. This allows programs to disable use + of VLAs, which may be unintended, or may be awkward to support portably, + or may have security implications due to non-deterministic stack usage. */ + +#if (!defined GNULIB_NO_VLA \ + && (((__GNUC__ >= 3 || __GNUG__ >= 2) && !defined __STRICT_ANSI__) \ + /* || (__STDC_VERSION__ == 199901L && !defined __HP_cc) + || (__STDC_VERSION__ >= 201112L && !defined __STDC_NO_VLA__) */ )) # define _LIBGETTEXT_HAVE_VARIABLE_SIZE_ARRAYS 1 #else # define _LIBGETTEXT_HAVE_VARIABLE_SIZE_ARRAYS 0 diff --git a/gl/lib/gl_anyhash1.h b/gl/lib/gl_anyhash1.h new file mode 100644 index 00000000..e9644546 --- /dev/null +++ b/gl/lib/gl_anyhash1.h @@ -0,0 +1,31 @@ +/* Hash table for sequential list, set, and map data type. + Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* Common code of + gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c, + gl_linkedhash_set.c, gl_hash_set.c, + gl_linkedhash_map.c, gl_hash_map.c. */ + +/* Hash table entry. */ +struct gl_hash_entry +{ + struct gl_hash_entry *hash_next; /* chain of entries in same bucket */ + size_t hashcode; /* cache of the hash code of + - the key (for map data type) or + - the value (for list, set data types) */ +}; +typedef struct gl_hash_entry * gl_hash_entry_t; diff --git a/gl/lib/gl_anyhash2.h b/gl/lib/gl_anyhash2.h new file mode 100644 index 00000000..e9ccf84d --- /dev/null +++ b/gl/lib/gl_anyhash2.h @@ -0,0 +1,82 @@ +/* Hash table for sequential list, set, and map data type. + Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* Common code of + gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c, + gl_linkedhash_set.c, gl_hash_set.c, + gl_linkedhash_map.c, gl_hash_map.c. */ + +#include "gl_anyhash_primes.h" + +/* Resize the hash table with a new estimated size. */ +static void +hash_resize (CONTAINER_T container, size_t estimate) +{ + size_t new_size = next_prime (estimate); + + if (new_size > container->table_size) + { + gl_hash_entry_t *old_table = container->table; + /* Allocate the new table. */ + gl_hash_entry_t *new_table; + size_t i; + + if (size_overflow_p (xtimes (new_size, sizeof (gl_hash_entry_t)))) + goto fail; + new_table = + (gl_hash_entry_t *) calloc (new_size, sizeof (gl_hash_entry_t)); + if (new_table == NULL) + goto fail; + + /* Iterate through the entries of the old table. */ + for (i = container->table_size; i > 0; ) + { + gl_hash_entry_t node = old_table[--i]; + + while (node != NULL) + { + gl_hash_entry_t next = node->hash_next; + /* Add the entry to the new table. */ + size_t bucket = node->hashcode % new_size; + node->hash_next = new_table[bucket]; + new_table[bucket] = node; + + node = next; + } + } + + container->table = new_table; + container->table_size = new_size; + free (old_table); + } + return; + + fail: + /* Just continue without resizing the table. */ + return; +} + +/* Resize the hash table if needed, after CONTAINER_COUNT (container) was + incremented. */ +static void +hash_resize_after_add (CONTAINER_T container) +{ + size_t count = CONTAINER_COUNT (container); + size_t estimate = xsum (count, count / 2); /* 1.5 * count */ + if (estimate > container->table_size) + hash_resize (container, estimate); +} diff --git a/gl/lib/gl_anyhash_primes.h b/gl/lib/gl_anyhash_primes.h new file mode 100644 index 00000000..4f80b97f --- /dev/null +++ b/gl/lib/gl_anyhash_primes.h @@ -0,0 +1,87 @@ +/* Table of primes, for use by hash tables. + Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* Array of primes, approximately in steps of factor 1.2. + This table was computed by executing the Common Lisp expression + (dotimes (i 244) (format t "nextprime(~D)~%" (ceiling (expt 1.2d0 i)))) + and feeding the result to PARI/gp. */ +static const size_t primes[] = + { + 11, 13, 17, 19, 23, 29, 37, 41, 47, 59, 67, 83, 97, 127, 139, 167, 199, + 239, 293, 347, 419, 499, 593, 709, 853, 1021, 1229, 1471, 1777, 2129, 2543, + 3049, 3659, 4391, 5273, 6323, 7589, 9103, 10937, 13109, 15727, 18899, + 22651, 27179, 32609, 39133, 46957, 56359, 67619, 81157, 97369, 116849, + 140221, 168253, 201907, 242309, 290761, 348889, 418667, 502409, 602887, + 723467, 868151, 1041779, 1250141, 1500181, 1800191, 2160233, 2592277, + 3110741, 3732887, 4479463, 5375371, 6450413, 7740517, 9288589, 11146307, + 13375573, 16050689, 19260817, 23112977, 27735583, 33282701, 39939233, + 47927081, 57512503, 69014987, 82818011, 99381577, 119257891, 143109469, + 171731387, 206077643, 247293161, 296751781, 356102141, 427322587, + 512787097, 615344489, 738413383, 886096061, 1063315271, 1275978331, + 1531174013, 1837408799, 2204890543UL, 2645868653UL, 3175042391UL, + 3810050851UL, +#if SIZE_MAX > 4294967295UL + 4572061027UL, 5486473229UL, 6583767889UL, 7900521449UL, 9480625733UL, + 11376750877UL, 13652101063UL, 16382521261UL, 19659025513UL, 23590830631UL, + 28308996763UL, 33970796089UL, 40764955463UL, 48917946377UL, 58701535657UL, + 70441842749UL, 84530211301UL, 101436253561UL, 121723504277UL, + 146068205131UL, 175281846149UL, 210338215379UL, 252405858521UL, + 302887030151UL, 363464436191UL, 436157323417UL, 523388788231UL, + 628066545713UL, 753679854847UL, 904415825857UL, 1085298991109UL, + 1302358789181UL, 1562830547009UL, 1875396656429UL, 2250475987709UL, + 2700571185239UL, 3240685422287UL, 3888822506759UL, 4666587008147UL, + 5599904409713UL, 6719885291641UL, 8063862349969UL, 9676634819959UL, + 11611961783951UL, 13934354140769UL, 16721224968907UL, 20065469962669UL, + 24078563955191UL, 28894276746229UL, 34673132095507UL, 41607758514593UL, + 49929310217531UL, 59915172260971UL, 71898206713183UL, 86277848055823UL, + 103533417666967UL, 124240101200359UL, 149088121440451UL, 178905745728529UL, + 214686894874223UL, 257624273849081UL, 309149128618903UL, 370978954342639UL, + 445174745211143UL, 534209694253381UL, 641051633104063UL, 769261959724877UL, + 923114351670013UL, 1107737222003791UL, 1329284666404567UL, + 1595141599685509UL, 1914169919622551UL, 2297003903547091UL, + 2756404684256459UL, 3307685621107757UL, 3969222745329323UL, + 4763067294395177UL, 5715680753274209UL, 6858816903929113UL, + 8230580284714831UL, 9876696341657791UL, 11852035609989371UL, + 14222442731987227UL, 17066931278384657UL, 20480317534061597UL, + 24576381040873903UL, 29491657249048679UL, 35389988698858471UL, + 42467986438630267UL, 50961583726356109UL, 61153900471627387UL, + 73384680565952851UL, 88061616679143347UL, 105673940014972061UL, + 126808728017966413UL, 152170473621559703UL, 182604568345871671UL, + 219125482015045997UL, 262950578418055169UL, 315540694101666193UL, + 378648832921999397UL, 454378599506399233UL, 545254319407679131UL, + 654305183289214771UL, 785166219947057701UL, 942199463936469157UL, + 1130639356723763129UL, 1356767228068515623UL, 1628120673682218619UL, + 1953744808418662409UL, 2344493770102394881UL, 2813392524122873857UL, + 3376071028947448339UL, 4051285234736937517UL, 4861542281684325481UL, + 5833850738021191727UL, 7000620885625427969UL, 8400745062750513217UL, + 10080894075300616261UL, 12097072890360739951UL, 14516487468432885797UL, + 17419784962119465179UL, +#endif + SIZE_MAX /* sentinel, to ensure the search terminates */ + }; + +/* Return a suitable prime >= ESTIMATE. */ +static size_t +next_prime (size_t estimate) +{ + size_t i; + + for (i = 0; i < sizeof (primes) / sizeof (primes[0]); i++) + if (primes[i] >= estimate) + return primes[i]; + return SIZE_MAX; /* not a prime, but better than nothing */ +} diff --git a/gl/lib/gl_anylinked_list1.h b/gl/lib/gl_anylinked_list1.h new file mode 100644 index 00000000..a12b1adc --- /dev/null +++ b/gl/lib/gl_anylinked_list1.h @@ -0,0 +1,48 @@ +/* Sequential list data type implemented by a linked list. + Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* Common code of gl_linked_list.c and gl_linkedhash_list.c. */ + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Concrete list node implementation, valid for this file only. */ +struct gl_list_node_impl +{ +#if WITH_HASHTABLE + struct gl_hash_entry h; /* hash table entry fields; must be first */ +#endif + struct gl_list_node_impl *next; + struct gl_list_node_impl *prev; + const void *value; +}; + +/* Concrete gl_list_impl type, valid for this file only. */ +struct gl_list_impl +{ + struct gl_list_impl_base base; +#if WITH_HASHTABLE + /* A hash table: managed as an array of collision lists. */ + struct gl_hash_entry **table; + size_t table_size; +#endif + /* A circular list anchored at root. + The first node is = root.next, the last node is = root.prev. + The root's value is unused. */ + struct gl_list_node_impl root; + /* Number of list nodes, excluding the root. */ + size_t count; +}; diff --git a/gl/lib/gl_anylinked_list2.h b/gl/lib/gl_anylinked_list2.h new file mode 100644 index 00000000..dc7f2cd5 --- /dev/null +++ b/gl/lib/gl_anylinked_list2.h @@ -0,0 +1,1195 @@ +/* Sequential list data type implemented by a linked list. + Copyright (C) 2006-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* Common code of gl_linked_list.c and gl_linkedhash_list.c. */ + +/* If the symbol SIGNAL_SAFE_LIST is defined, the code is compiled in such + a way that a gl_list_t data structure may be used from within a signal + handler. The operations allowed in the signal handler are: + gl_list_iterator, gl_list_iterator_next, gl_list_iterator_free. + The list and node fields that are therefore accessed from the signal handler + are: + list->root, node->next, node->value. + We are careful to make modifications to these fields only in an order + that maintains the consistency of the list data structure at any moment, + and we use 'volatile' assignments to prevent the compiler from reordering + such assignments. */ +#ifdef SIGNAL_SAFE_LIST +# define ASYNCSAFE(type) *(type volatile *)& +#else +# define ASYNCSAFE(type) +#endif + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +static gl_list_t +gl_linked_nx_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates) +{ + struct gl_list_impl *list = + (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); + + if (list == NULL) + return NULL; + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; + list->base.allow_duplicates = allow_duplicates; +#if WITH_HASHTABLE + list->table_size = 11; + list->table = + (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); + if (list->table == NULL) + goto fail; +#endif + list->root.next = &list->root; + list->root.prev = &list->root; + list->count = 0; + + return list; + +#if WITH_HASHTABLE + fail: + free (list); + return NULL; +#endif +} + +static gl_list_t +gl_linked_nx_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents) +{ + struct gl_list_impl *list = + (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); + gl_list_node_t tail; + + if (list == NULL) + return NULL; + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; + list->base.allow_duplicates = allow_duplicates; +#if WITH_HASHTABLE + { + size_t estimate = xsum (count, count / 2); /* 1.5 * count */ + if (estimate < 10) + estimate = 10; + list->table_size = next_prime (estimate); + if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t)))) + goto fail1; + list->table = + (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); + if (list->table == NULL) + goto fail1; + } +#endif + list->count = count; + tail = &list->root; + for (; count > 0; contents++, count--) + { + gl_list_node_t node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (node == NULL) + goto fail2; + + node->value = *contents; +#if WITH_HASHTABLE + node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (node->value) + : (size_t)(uintptr_t) node->value); + + /* Add node to the hash table. */ + if (add_to_bucket (list, node) < 0) + { + free (node); + goto fail2; + } +#endif + + /* Add node to the list. */ + node->prev = tail; + tail->next = node; + tail = node; + } + tail->next = &list->root; + list->root.prev = tail; + + return list; + + fail2: + { + gl_list_node_t node; + + for (node = tail; node != &list->root; ) + { + gl_list_node_t prev = node->prev; + + free (node); + node = prev; + } + } +#if WITH_HASHTABLE + free (list->table); + fail1: +#endif + free (list); + return NULL; +} + +static size_t _GL_ATTRIBUTE_PURE +gl_linked_size (gl_list_t list) +{ + return list->count; +} + +static const void * _GL_ATTRIBUTE_PURE +gl_linked_node_value (gl_list_t list, gl_list_node_t node) +{ + return node->value; +} + +static int +gl_linked_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) +{ +#if WITH_HASHTABLE + if (elt != node->value) + { + size_t new_hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + + if (new_hashcode != node->h.hashcode) + { + remove_from_bucket (list, node); + node->value = elt; + node->h.hashcode = new_hashcode; + if (add_to_bucket (list, node) < 0) + { + /* Out of memory. We removed node from a bucket but cannot add + it to another bucket. In order to avoid inconsistencies, we + must remove node entirely from the list. */ + gl_list_node_t before_removed = node->prev; + gl_list_node_t after_removed = node->next; + ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed; + after_removed->prev = before_removed; + list->count--; + free (node); + return -1; + } + } + else + node->value = elt; + } +#else + node->value = elt; +#endif + return 0; +} + +static gl_list_node_t _GL_ATTRIBUTE_PURE +gl_linked_next_node (gl_list_t list, gl_list_node_t node) +{ + return (node->next != &list->root ? node->next : NULL); +} + +static gl_list_node_t _GL_ATTRIBUTE_PURE +gl_linked_previous_node (gl_list_t list, gl_list_node_t node) +{ + return (node->prev != &list->root ? node->prev : NULL); +} + +static const void * _GL_ATTRIBUTE_PURE +gl_linked_get_at (gl_list_t list, size_t position) +{ + size_t count = list->count; + gl_list_node_t node; + + if (!(position < count)) + /* Invalid argument. */ + abort (); + /* Here we know count > 0. */ + if (position <= ((count - 1) / 2)) + { + node = list->root.next; + for (; position > 0; position--) + node = node->next; + } + else + { + position = count - 1 - position; + node = list->root.prev; + for (; position > 0; position--) + node = node->prev; + } + return node->value; +} + +static gl_list_node_t +gl_linked_nx_set_at (gl_list_t list, size_t position, const void *elt) +{ + size_t count = list->count; + gl_list_node_t node; + + if (!(position < count)) + /* Invalid argument. */ + abort (); + /* Here we know count > 0. */ + if (position <= ((count - 1) / 2)) + { + node = list->root.next; + for (; position > 0; position--) + node = node->next; + } + else + { + position = count - 1 - position; + node = list->root.prev; + for (; position > 0; position--) + node = node->prev; + } +#if WITH_HASHTABLE + if (elt != node->value) + { + size_t new_hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + + if (new_hashcode != node->h.hashcode) + { + remove_from_bucket (list, node); + node->value = elt; + node->h.hashcode = new_hashcode; + if (add_to_bucket (list, node) < 0) + { + /* Out of memory. We removed node from a bucket but cannot add + it to another bucket. In order to avoid inconsistencies, we + must remove node entirely from the list. */ + gl_list_node_t before_removed = node->prev; + gl_list_node_t after_removed = node->next; + ASYNCSAFE(gl_list_node_t) before_removed->next = after_removed; + after_removed->prev = before_removed; + list->count--; + free (node); + return NULL; + } + } + else + node->value = elt; + } +#else + node->value = elt; +#endif + return node; +} + +static gl_list_node_t _GL_ATTRIBUTE_PURE +gl_linked_search_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + size_t count = list->count; + + if (!(start_index <= end_index && end_index <= count)) + /* Invalid arguments. */ + abort (); + { +#if WITH_HASHTABLE + size_t hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t bucket = hashcode % list->table_size; + gl_listelement_equals_fn equals = list->base.equals_fn; + + if (!list->base.allow_duplicates) + { + /* Look for the first match in the hash bucket. */ + gl_list_node_t found = NULL; + gl_list_node_t node; + + for (node = (gl_list_node_t) list->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + { + found = node; + break; + } + if (start_index > 0) + /* Look whether found's index is < start_index. */ + for (node = list->root.next; ; node = node->next) + { + if (node == found) + return NULL; + if (--start_index == 0) + break; + } + if (end_index < count) + /* Look whether found's index is >= end_index. */ + { + end_index = count - end_index; + for (node = list->root.prev; ; node = node->prev) + { + if (node == found) + return NULL; + if (--end_index == 0) + break; + } + } + return found; + } + else + { + /* Look whether there is more than one match in the hash bucket. */ + bool multiple_matches = false; + gl_list_node_t first_match = NULL; + gl_list_node_t node; + + for (node = (gl_list_node_t) list->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + { + if (first_match == NULL) + first_match = node; + else + { + multiple_matches = true; + break; + } + } + if (multiple_matches) + { + /* We need the match with the smallest index. But we don't have + a fast mapping node -> index. So we have to walk the list. */ + end_index -= start_index; + node = list->root.next; + for (; start_index > 0; start_index--) + node = node->next; + + for (; + end_index > 0; + node = node->next, end_index--) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + return node; + /* The matches must have all been at indices < start_index or + >= end_index. */ + return NULL; + } + else + { + if (start_index > 0) + /* Look whether first_match's index is < start_index. */ + for (node = list->root.next; node != &list->root; node = node->next) + { + if (node == first_match) + return NULL; + if (--start_index == 0) + break; + } + if (end_index < list->count) + /* Look whether first_match's index is >= end_index. */ + { + end_index = list->count - end_index; + for (node = list->root.prev; ; node = node->prev) + { + if (node == first_match) + return NULL; + if (--end_index == 0) + break; + } + } + return first_match; + } + } +#else + gl_listelement_equals_fn equals = list->base.equals_fn; + gl_list_node_t node = list->root.next; + + end_index -= start_index; + for (; start_index > 0; start_index--) + node = node->next; + + if (equals != NULL) + { + for (; end_index > 0; node = node->next, end_index--) + if (equals (elt, node->value)) + return node; + } + else + { + for (; end_index > 0; node = node->next, end_index--) + if (elt == node->value) + return node; + } + return NULL; +#endif + } +} + +static size_t _GL_ATTRIBUTE_PURE +gl_linked_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + size_t count = list->count; + + if (!(start_index <= end_index && end_index <= count)) + /* Invalid arguments. */ + abort (); + { +#if WITH_HASHTABLE + /* Here the hash table doesn't help much. It only allows us to minimize + the number of equals() calls, by looking up first the node and then + its index. */ + size_t hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t bucket = hashcode % list->table_size; + gl_listelement_equals_fn equals = list->base.equals_fn; + gl_list_node_t node; + + /* First step: Look up the node. */ + if (!list->base.allow_duplicates) + { + /* Look for the first match in the hash bucket. */ + for (node = (gl_list_node_t) list->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + break; + } + else + { + /* Look whether there is more than one match in the hash bucket. */ + bool multiple_matches = false; + gl_list_node_t first_match = NULL; + + for (node = (gl_list_node_t) list->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + { + if (first_match == NULL) + first_match = node; + else + { + multiple_matches = true; + break; + } + } + if (multiple_matches) + { + /* We need the match with the smallest index. But we don't have + a fast mapping node -> index. So we have to walk the list. */ + size_t index; + + index = start_index; + node = list->root.next; + for (; start_index > 0; start_index--) + node = node->next; + + for (; + index < end_index; + node = node->next, index++) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + return index; + /* The matches must have all been at indices < start_index or + >= end_index. */ + return (size_t)(-1); + } + node = first_match; + } + + /* Second step: Look up the index of the node. */ + if (node == NULL) + return (size_t)(-1); + else + { + size_t index = 0; + + for (; node->prev != &list->root; node = node->prev) + index++; + + if (index >= start_index && index < end_index) + return index; + else + return (size_t)(-1); + } +#else + gl_listelement_equals_fn equals = list->base.equals_fn; + size_t index = start_index; + gl_list_node_t node = list->root.next; + + for (; start_index > 0; start_index--) + node = node->next; + + if (equals != NULL) + { + for (; + index < end_index; + node = node->next, index++) + if (equals (elt, node->value)) + return index; + } + else + { + for (; + index < end_index; + node = node->next, index++) + if (elt == node->value) + return index; + } + return (size_t)(-1); +#endif + } +} + +static gl_list_node_t +gl_linked_nx_add_first (gl_list_t list, const void *elt) +{ + gl_list_node_t node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (node == NULL) + return NULL; + + ASYNCSAFE(const void *) node->value = elt; +#if WITH_HASHTABLE + node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (node->value) + : (size_t)(uintptr_t) node->value); + + /* Add node to the hash table. */ + if (add_to_bucket (list, node) < 0) + { + free (node); + return NULL; + } +#endif + + /* Add node to the list. */ + node->prev = &list->root; + ASYNCSAFE(gl_list_node_t) node->next = list->root.next; + node->next->prev = node; + ASYNCSAFE(gl_list_node_t) list->root.next = node; + list->count++; + +#if WITH_HASHTABLE + hash_resize_after_add (list); +#endif + + return node; +} + +static gl_list_node_t +gl_linked_nx_add_last (gl_list_t list, const void *elt) +{ + gl_list_node_t node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (node == NULL) + return NULL; + + ASYNCSAFE(const void *) node->value = elt; +#if WITH_HASHTABLE + node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (node->value) + : (size_t)(uintptr_t) node->value); + + /* Add node to the hash table. */ + if (add_to_bucket (list, node) < 0) + { + free (node); + return NULL; + } +#endif + + /* Add node to the list. */ + ASYNCSAFE(gl_list_node_t) node->next = &list->root; + node->prev = list->root.prev; + ASYNCSAFE(gl_list_node_t) node->prev->next = node; + list->root.prev = node; + list->count++; + +#if WITH_HASHTABLE + hash_resize_after_add (list); +#endif + + return node; +} + +static gl_list_node_t +gl_linked_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; + + ASYNCSAFE(const void *) new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); + + /* Add new_node to the hash table. */ + if (add_to_bucket (list, new_node) < 0) + { + free (new_node); + return NULL; + } +#endif + + /* Add new_node to the list. */ + ASYNCSAFE(gl_list_node_t) new_node->next = node; + new_node->prev = node->prev; + ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node; + node->prev = new_node; + list->count++; + +#if WITH_HASHTABLE + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_linked_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; + + ASYNCSAFE(const void *) new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); + + /* Add new_node to the hash table. */ + if (add_to_bucket (list, new_node) < 0) + { + free (new_node); + return NULL; + } +#endif + + /* Add new_node to the list. */ + new_node->prev = node; + ASYNCSAFE(gl_list_node_t) new_node->next = node->next; + new_node->next->prev = new_node; + ASYNCSAFE(gl_list_node_t) node->next = new_node; + list->count++; + +#if WITH_HASHTABLE + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_linked_nx_add_at (gl_list_t list, size_t position, const void *elt) +{ + size_t count = list->count; + gl_list_node_t new_node; + + if (!(position <= count)) + /* Invalid argument. */ + abort (); + + new_node = (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + if (new_node == NULL) + return NULL; + + ASYNCSAFE(const void *) new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); + + /* Add new_node to the hash table. */ + if (add_to_bucket (list, new_node) < 0) + { + free (new_node); + return NULL; + } +#endif + + /* Add new_node to the list. */ + if (position <= (count / 2)) + { + gl_list_node_t node; + + node = &list->root; + for (; position > 0; position--) + node = node->next; + new_node->prev = node; + ASYNCSAFE(gl_list_node_t) new_node->next = node->next; + new_node->next->prev = new_node; + ASYNCSAFE(gl_list_node_t) node->next = new_node; + } + else + { + gl_list_node_t node; + + position = count - position; + node = &list->root; + for (; position > 0; position--) + node = node->prev; + ASYNCSAFE(gl_list_node_t) new_node->next = node; + new_node->prev = node->prev; + ASYNCSAFE(gl_list_node_t) new_node->prev->next = new_node; + node->prev = new_node; + } + list->count++; + +#if WITH_HASHTABLE + hash_resize_after_add (list); +#endif + + return new_node; +} + +static bool +gl_linked_remove_node (gl_list_t list, gl_list_node_t node) +{ + gl_list_node_t prev; + gl_list_node_t next; + +#if WITH_HASHTABLE + /* Remove node from the hash table. */ + remove_from_bucket (list, node); +#endif + + /* Remove node from the list. */ + prev = node->prev; + next = node->next; + + ASYNCSAFE(gl_list_node_t) prev->next = next; + next->prev = prev; + list->count--; + + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (node->value); + free (node); + return true; +} + +static bool +gl_linked_remove_at (gl_list_t list, size_t position) +{ + size_t count = list->count; + gl_list_node_t removed_node; + + if (!(position < count)) + /* Invalid argument. */ + abort (); + /* Here we know count > 0. */ + if (position <= ((count - 1) / 2)) + { + gl_list_node_t node; + gl_list_node_t after_removed; + + node = &list->root; + for (; position > 0; position--) + node = node->next; + removed_node = node->next; + after_removed = node->next->next; + ASYNCSAFE(gl_list_node_t) node->next = after_removed; + after_removed->prev = node; + } + else + { + gl_list_node_t node; + gl_list_node_t before_removed; + + position = count - 1 - position; + node = &list->root; + for (; position > 0; position--) + node = node->prev; + removed_node = node->prev; + before_removed = node->prev->prev; + node->prev = before_removed; + ASYNCSAFE(gl_list_node_t) before_removed->next = node; + } +#if WITH_HASHTABLE + remove_from_bucket (list, removed_node); +#endif + list->count--; + + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (removed_node->value); + free (removed_node); + return true; +} + +static bool +gl_linked_remove (gl_list_t list, const void *elt) +{ + gl_list_node_t node = gl_linked_search_from_to (list, 0, list->count, elt); + + if (node != NULL) + return gl_linked_remove_node (list, node); + else + return false; +} + +static void +gl_linked_list_free (gl_list_t list) +{ + gl_listelement_dispose_fn dispose = list->base.dispose_fn; + gl_list_node_t node; + + for (node = list->root.next; node != &list->root; ) + { + gl_list_node_t next = node->next; + if (dispose != NULL) + dispose (node->value); + free (node); + node = next; + } +#if WITH_HASHTABLE + free (list->table); +#endif + free (list); +} + +/* --------------------- gl_list_iterator_t Data Type --------------------- */ + +static gl_list_iterator_t +gl_linked_iterator (gl_list_t list) +{ + gl_list_iterator_t result; + + result.vtable = list->base.vtable; + result.list = list; + result.p = list->root.next; + result.q = &list->root; +#if defined GCC_LINT || defined lint + result.i = 0; + result.j = 0; + result.count = 0; +#endif + + return result; +} + +static gl_list_iterator_t +gl_linked_iterator_from_to (gl_list_t list, + size_t start_index, size_t end_index) +{ + gl_list_iterator_t result; + size_t n1, n2, n3; + + if (!(start_index <= end_index && end_index <= list->count)) + /* Invalid arguments. */ + abort (); + result.vtable = list->base.vtable; + result.list = list; + n1 = start_index; + n2 = end_index - start_index; + n3 = list->count - end_index; + /* Find the maximum among n1, n2, n3, so as to reduce the number of + loop iterations to n1 + n2 + n3 - max(n1,n2,n3). */ + if (n1 > n2 && n1 > n3) + { + /* n1 is the maximum, use n2 and n3. */ + gl_list_node_t node; + size_t i; + + node = &list->root; + for (i = n3; i > 0; i--) + node = node->prev; + result.q = node; + for (i = n2; i > 0; i--) + node = node->prev; + result.p = node; + } + else if (n2 > n3) + { + /* n2 is the maximum, use n1 and n3. */ + gl_list_node_t node; + size_t i; + + node = list->root.next; + for (i = n1; i > 0; i--) + node = node->next; + result.p = node; + + node = &list->root; + for (i = n3; i > 0; i--) + node = node->prev; + result.q = node; + } + else + { + /* n3 is the maximum, use n1 and n2. */ + gl_list_node_t node; + size_t i; + + node = list->root.next; + for (i = n1; i > 0; i--) + node = node->next; + result.p = node; + for (i = n2; i > 0; i--) + node = node->next; + result.q = node; + } + +#if defined GCC_LINT || defined lint + result.i = 0; + result.j = 0; + result.count = 0; +#endif + + return result; +} + +static bool +gl_linked_iterator_next (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep) +{ + if (iterator->p != iterator->q) + { + gl_list_node_t node = (gl_list_node_t) iterator->p; + *eltp = node->value; + if (nodep != NULL) + *nodep = node; + iterator->p = node->next; + return true; + } + else + return false; +} + +static void +gl_linked_iterator_free (gl_list_iterator_t *iterator) +{ +} + +/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ + +static gl_list_node_t _GL_ATTRIBUTE_PURE +gl_linked_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + + for (node = list->root.next; node != &list->root; node = node->next) + { + int cmp = compar (node->value, elt); + + if (cmp > 0) + break; + if (cmp == 0) + return node; + } + return NULL; +} + +static gl_list_node_t _GL_ATTRIBUTE_PURE +gl_linked_sortedlist_search_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t low, size_t high, + const void *elt) +{ + size_t count = list->count; + + if (!(low <= high && high <= list->count)) + /* Invalid arguments. */ + abort (); + + high -= low; + if (high > 0) + { + /* Here we know low < count. */ + size_t position = low; + gl_list_node_t node; + + if (position <= ((count - 1) / 2)) + { + node = list->root.next; + for (; position > 0; position--) + node = node->next; + } + else + { + position = count - 1 - position; + node = list->root.prev; + for (; position > 0; position--) + node = node->prev; + } + + do + { + int cmp = compar (node->value, elt); + + if (cmp > 0) + break; + if (cmp == 0) + return node; + node = node->next; + } + while (--high > 0); + } + return NULL; +} + +static size_t _GL_ATTRIBUTE_PURE +gl_linked_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + size_t index; + + for (node = list->root.next, index = 0; + node != &list->root; + node = node->next, index++) + { + int cmp = compar (node->value, elt); + + if (cmp > 0) + break; + if (cmp == 0) + return index; + } + return (size_t)(-1); +} + +static size_t _GL_ATTRIBUTE_PURE +gl_linked_sortedlist_indexof_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t low, size_t high, + const void *elt) +{ + size_t count = list->count; + + if (!(low <= high && high <= list->count)) + /* Invalid arguments. */ + abort (); + + high -= low; + if (high > 0) + { + /* Here we know low < count. */ + size_t index = low; + size_t position = low; + gl_list_node_t node; + + if (position <= ((count - 1) / 2)) + { + node = list->root.next; + for (; position > 0; position--) + node = node->next; + } + else + { + position = count - 1 - position; + node = list->root.prev; + for (; position > 0; position--) + node = node->prev; + } + + do + { + int cmp = compar (node->value, elt); + + if (cmp > 0) + break; + if (cmp == 0) + return index; + node = node->next; + index++; + } + while (--high > 0); + } + return (size_t)(-1); +} + +static gl_list_node_t +gl_linked_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + + for (node = list->root.next; node != &list->root; node = node->next) + if (compar (node->value, elt) >= 0) + return gl_linked_nx_add_before (list, node, elt); + return gl_linked_nx_add_last (list, elt); +} + +static bool +gl_linked_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + + for (node = list->root.next; node != &list->root; node = node->next) + { + int cmp = compar (node->value, elt); + + if (cmp > 0) + break; + if (cmp == 0) + return gl_linked_remove_node (list, node); + } + return false; +} diff --git a/gl/lib/gl_anyrbtree_list1.h b/gl/lib/gl_anyrbtree_list1.h new file mode 100644 index 00000000..29ea451e --- /dev/null +++ b/gl/lib/gl_anyrbtree_list1.h @@ -0,0 +1,76 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ + +/* A red-black tree is a binary tree where every node is colored black or + red such that + 1. The root is black. + 2. No red node has a red parent. + Or equivalently: No red node has a red child. + 3. All paths from the root down to any NULL endpoint contain the same + number of black nodes. + Let's call this the "black-height" bh of the tree. It follows that every + such path contains exactly bh black and between 0 and bh red nodes. (The + extreme cases are a path containing only black nodes, and a path colored + alternately black-red-black-red-...-black-red.) The height of the tree + therefore is >= bh, <= 2*bh. + */ + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Color of a node. */ +typedef enum color { BLACK, RED } color_t; + +/* Concrete list node implementation, valid for this file only. */ +struct gl_list_node_impl +{ +#if WITH_HASHTABLE + struct gl_hash_entry h; /* hash table entry fields; must be first */ +#endif + struct gl_list_node_impl *left; /* left branch, or NULL */ + struct gl_list_node_impl *right; /* right branch, or NULL */ + /* Parent pointer, or NULL. The parent pointer is not needed for most + operations. It is needed so that a gl_list_node_t can be returned + without memory allocation, on which the functions gl_list_remove_node, + gl_list_add_before, gl_list_add_after can be implemented. */ + struct gl_list_node_impl *parent; + color_t color; /* node's color */ + size_t branch_size; /* number of nodes in this branch, + = branchsize(left)+branchsize(right)+1 */ + const void *value; +}; + +/* Concrete gl_list_impl type, valid for this file only. */ +struct gl_list_impl +{ + struct gl_list_impl_base base; +#if WITH_HASHTABLE + /* A hash table: managed as an array of collision lists. */ + struct gl_hash_entry **table; + size_t table_size; +#endif + struct gl_list_node_impl *root; /* root node or NULL */ +}; + +/* A red-black tree of height h has a black-height bh >= ceil(h/2) and + therefore at least 2^ceil(h/2) - 1 elements. So, h <= 116 (because a tree + of height h >= 117 would have at least 2^59 - 1 elements, and because even + on 64-bit machines, + sizeof (gl_list_node_impl) * (2^59 - 1) > 2^64 + this would exceed the address space of the machine. */ +#define MAXHEIGHT 116 diff --git a/gl/lib/gl_anyrbtree_list2.h b/gl/lib/gl_anyrbtree_list2.h new file mode 100644 index 00000000..102d71a5 --- /dev/null +++ b/gl/lib/gl_anyrbtree_list2.h @@ -0,0 +1,1028 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006-2007, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* Common code of gl_rbtree_list.c and gl_rbtreehash_list.c. */ + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Create a subtree for count >= 1 elements. + Its black-height bh is passed as argument, with + 2^bh - 1 <= count <= 2^(bh+1) - 1. bh == 0 implies count == 1. + Its height is h where 2^(h-1) <= count <= 2^h - 1. + Return NULL upon out-of-memory. */ +static gl_list_node_t +create_subtree_with_contents (unsigned int bh, + size_t count, const void **contents) +{ + size_t half1 = (count - 1) / 2; + size_t half2 = count / 2; + /* Note: half1 + half2 = count - 1. */ + gl_list_node_t node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + if (node == NULL) + return NULL; + + if (half1 > 0) + { + /* half1 > 0 implies count > 1, implies bh >= 1, implies + 2^(bh-1) - 1 <= half1 <= 2^bh - 1. */ + node->left = + create_subtree_with_contents (bh - 1, half1, contents); + if (node->left == NULL) + goto fail1; + node->left->parent = node; + } + else + node->left = NULL; + + node->value = contents[half1]; + + if (half2 > 0) + { + /* half2 > 0 implies count > 1, implies bh >= 1, implies + 2^(bh-1) - 1 <= half2 <= 2^bh - 1. */ + node->right = + create_subtree_with_contents (bh - 1, half2, contents + half1 + 1); + if (node->right == NULL) + goto fail2; + node->right->parent = node; + } + else + node->right = NULL; + + node->color = (bh == 0 ? RED : BLACK); + + node->branch_size = count; + + return node; + + fail2: + if (node->left != NULL) + free_subtree (node->left); + fail1: + free (node); + return NULL; +} + +static gl_list_t +gl_tree_nx_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents) +{ + struct gl_list_impl *list = + (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); + + if (list == NULL) + return NULL; + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; + list->base.allow_duplicates = allow_duplicates; +#if WITH_HASHTABLE + { + size_t estimate = xsum (count, count / 2); /* 1.5 * count */ + if (estimate < 10) + estimate = 10; + list->table_size = next_prime (estimate); + if (size_overflow_p (xtimes (list->table_size, sizeof (gl_hash_entry_t)))) + goto fail1; + list->table = + (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); + if (list->table == NULL) + goto fail1; + } +#endif + if (count > 0) + { + /* Assuming 2^bh - 1 <= count <= 2^(bh+1) - 2, we create a tree whose + upper bh levels are black, and only the partially present lowest + level is red. */ + unsigned int bh; + { + size_t n; + for (n = count + 1, bh = 0; n > 1; n = n >> 1) + bh++; + } + + list->root = create_subtree_with_contents (bh, count, contents); + if (list->root == NULL) + goto fail2; + list->root->parent = NULL; + +#if WITH_HASHTABLE + /* Now that the tree is built, node_position() works. Now we can + add the nodes to the hash table. */ + if (add_nodes_to_buckets (list) < 0) + goto fail3; +#endif + } + else + list->root = NULL; + + return list; + +#if WITH_HASHTABLE + fail3: + free_subtree (list->root); +#endif + fail2: +#if WITH_HASHTABLE + free (list->table); + fail1: +#endif + free (list); + return NULL; +} + +/* Rotate left a subtree. + + B D + / \ / \ + A D --> B E + / \ / \ + C E A C + + Change the tree structure, update the branch sizes. + The caller must update the colors and register D as child of its parent. */ +static gl_list_node_t +rotate_left (gl_list_node_t b_node, gl_list_node_t d_node) +{ + gl_list_node_t a_node = b_node->left; + gl_list_node_t c_node = d_node->left; + gl_list_node_t e_node = d_node->right; + + b_node->right = c_node; + d_node->left = b_node; + + d_node->parent = b_node->parent; + b_node->parent = d_node; + if (c_node != NULL) + c_node->parent = b_node; + + b_node->branch_size = + (a_node != NULL ? a_node->branch_size : 0) + + 1 + (c_node != NULL ? c_node->branch_size : 0); + d_node->branch_size = + b_node->branch_size + 1 + (e_node != NULL ? e_node->branch_size : 0); + + return d_node; +} + +/* Rotate right a subtree. + + D B + / \ / \ + B E --> A D + / \ / \ + A C C E + + Change the tree structure, update the branch sizes. + The caller must update the colors and register B as child of its parent. */ +static gl_list_node_t +rotate_right (gl_list_node_t b_node, gl_list_node_t d_node) +{ + gl_list_node_t a_node = b_node->left; + gl_list_node_t c_node = b_node->right; + gl_list_node_t e_node = d_node->right; + + d_node->left = c_node; + b_node->right = d_node; + + b_node->parent = d_node->parent; + d_node->parent = b_node; + if (c_node != NULL) + c_node->parent = d_node; + + d_node->branch_size = + (c_node != NULL ? c_node->branch_size : 0) + + 1 + (e_node != NULL ? e_node->branch_size : 0); + b_node->branch_size = + (a_node != NULL ? a_node->branch_size : 0) + 1 + d_node->branch_size; + + return b_node; +} + +/* Ensure the tree is balanced, after an insertion operation. + Also assigns node->color. + parent is the given node's parent, known to be non-NULL. */ +static void +rebalance_after_add (gl_list_t list, gl_list_node_t node, gl_list_node_t parent) +{ + for (;;) + { + /* At this point, parent = node->parent != NULL. + Think of node->color being RED (although node->color is not yet + assigned.) */ + gl_list_node_t grandparent; + gl_list_node_t uncle; + + if (parent->color == BLACK) + { + /* A RED color for node is acceptable. */ + node->color = RED; + return; + } + + grandparent = parent->parent; + /* Since parent is RED, we know that + grandparent is != NULL and colored BLACK. */ + + if (grandparent->left == parent) + uncle = grandparent->right; + else if (grandparent->right == parent) + uncle = grandparent->left; + else + abort (); + + if (uncle != NULL && uncle->color == RED) + { + /* Change grandparent from BLACK to RED, and + change parent and uncle from RED to BLACK. + This makes it acceptable for node to be RED. */ + node->color = RED; + parent->color = uncle->color = BLACK; + node = grandparent; + } + else + { + /* grandparent and uncle are BLACK. parent is RED. node wants + to be RED too. + In this case, recoloring is not sufficient. Need to perform + one or two rotations. */ + gl_list_node_t *grandparentp; + + if (grandparent->parent == NULL) + grandparentp = &list->root; + else if (grandparent->parent->left == grandparent) + grandparentp = &grandparent->parent->left; + else if (grandparent->parent->right == grandparent) + grandparentp = &grandparent->parent->right; + else + abort (); + + if (grandparent->left == parent) + { + if (parent->right == node) + { + /* Rotation between node and parent. */ + grandparent->left = rotate_left (parent, node); + node = parent; + parent = grandparent->left; + } + /* grandparent and uncle are BLACK. parent and node want to be + RED. parent = grandparent->left. node = parent->left. + + grandparent parent + bh+1 bh+1 + / \ / \ + parent uncle --> node grandparent + bh bh bh bh + / \ / \ + node C C uncle + bh bh bh bh + */ + *grandparentp = rotate_right (parent, grandparent); + parent->color = BLACK; + node->color = grandparent->color = RED; + } + else /* grandparent->right == parent */ + { + if (parent->left == node) + { + /* Rotation between node and parent. */ + grandparent->right = rotate_right (node, parent); + node = parent; + parent = grandparent->right; + } + /* grandparent and uncle are BLACK. parent and node want to be + RED. parent = grandparent->right. node = parent->right. + + grandparent parent + bh+1 bh+1 + / \ / \ + uncle parent --> grandparent node + bh bh bh bh + / \ / \ + C node uncle C + bh bh bh bh + */ + *grandparentp = rotate_left (grandparent, parent); + parent->color = BLACK; + node->color = grandparent->color = RED; + } + return; + } + + /* Start again with a new (node, parent) pair. */ + parent = node->parent; + + if (parent == NULL) + { + /* Change node's color from RED to BLACK. This increases the + tree's black-height. */ + node->color = BLACK; + return; + } + } +} + +/* Ensure the tree is balanced, after a deletion operation. + CHILD was a grandchild of PARENT and is now its child. Between them, + a black node was removed. CHILD is also black, or NULL. + (CHILD can also be NULL. But PARENT is non-NULL.) */ +static void +rebalance_after_remove (gl_list_t list, gl_list_node_t child, gl_list_node_t parent) +{ + for (;;) + { + /* At this point, we reduced the black-height of the CHILD subtree by 1. + To make up, either look for a possibility to turn a RED to a BLACK + node, or try to reduce the black-height tree of CHILD's sibling + subtree as well. */ + gl_list_node_t *parentp; + + if (parent->parent == NULL) + parentp = &list->root; + else if (parent->parent->left == parent) + parentp = &parent->parent->left; + else if (parent->parent->right == parent) + parentp = &parent->parent->right; + else + abort (); + + if (parent->left == child) + { + gl_list_node_t sibling = parent->right; + /* sibling's black-height is >= 1. In particular, + sibling != NULL. + + parent + / \ + child sibling + bh bh+1 + */ + + if (sibling->color == RED) + { + /* sibling is RED, hence parent is BLACK and sibling's children + are non-NULL and BLACK. + + parent sibling + bh+2 bh+2 + / \ / \ + child sibling --> parent SR + bh bh+1 bh+1 bh+1 + / \ / \ + SL SR child SL + bh+1 bh+1 bh bh+1 + */ + *parentp = rotate_left (parent, sibling); + parent->color = RED; + sibling->color = BLACK; + + /* Concentrate on the subtree of parent. The new sibling is + one of the old sibling's children, and known to be BLACK. */ + parentp = &sibling->left; + sibling = parent->right; + } + /* Now we know that sibling is BLACK. + + parent + / \ + child sibling + bh bh+1 + */ + if (sibling->right != NULL && sibling->right->color == RED) + { + /* + parent sibling + bh+1|bh+2 bh+1|bh+2 + / \ / \ + child sibling --> parent SR + bh bh+1 bh+1 bh+1 + / \ / \ + SL SR child SL + bh bh bh bh + */ + *parentp = rotate_left (parent, sibling); + sibling->color = parent->color; + parent->color = BLACK; + sibling->right->color = BLACK; + return; + } + else if (sibling->left != NULL && sibling->left->color == RED) + { + /* + parent parent + bh+1|bh+2 bh+1|bh+2 + / \ / \ + child sibling --> child SL + bh bh+1 bh bh+1 + / \ / \ + SL SR SLL sibling + bh bh bh bh + / \ / \ + SLL SLR SLR SR + bh bh bh bh + + where SLL, SLR, SR are all black. + */ + parent->right = rotate_right (sibling->left, sibling); + /* Change sibling from BLACK to RED and SL from RED to BLACK. */ + sibling->color = RED; + sibling = parent->right; + sibling->color = BLACK; + + /* Now do as in the previous case. */ + *parentp = rotate_left (parent, sibling); + sibling->color = parent->color; + parent->color = BLACK; + sibling->right->color = BLACK; + return; + } + else + { + if (parent->color == BLACK) + { + /* Change sibling from BLACK to RED. Then the entire + subtree at parent has decreased its black-height. + parent parent + bh+2 bh+1 + / \ / \ + child sibling --> child sibling + bh bh+1 bh bh + */ + sibling->color = RED; + + child = parent; + } + else + { + /* Change parent from RED to BLACK, but compensate by + changing sibling from BLACK to RED. + parent parent + bh+1 bh+1 + / \ / \ + child sibling --> child sibling + bh bh+1 bh bh + */ + parent->color = BLACK; + sibling->color = RED; + return; + } + } + } + else if (parent->right == child) + { + gl_list_node_t sibling = parent->left; + /* sibling's black-height is >= 1. In particular, + sibling != NULL. + + parent + / \ + sibling child + bh+1 bh + */ + + if (sibling->color == RED) + { + /* sibling is RED, hence parent is BLACK and sibling's children + are non-NULL and BLACK. + + parent sibling + bh+2 bh+2 + / \ / \ + sibling child --> SR parent + bh+1 ch bh+1 bh+1 + / \ / \ + SL SR SL child + bh+1 bh+1 bh+1 bh + */ + *parentp = rotate_right (sibling, parent); + parent->color = RED; + sibling->color = BLACK; + + /* Concentrate on the subtree of parent. The new sibling is + one of the old sibling's children, and known to be BLACK. */ + parentp = &sibling->right; + sibling = parent->left; + } + /* Now we know that sibling is BLACK. + + parent + / \ + sibling child + bh+1 bh + */ + if (sibling->left != NULL && sibling->left->color == RED) + { + /* + parent sibling + bh+1|bh+2 bh+1|bh+2 + / \ / \ + sibling child --> SL parent + bh+1 bh bh+1 bh+1 + / \ / \ + SL SR SR child + bh bh bh bh + */ + *parentp = rotate_right (sibling, parent); + sibling->color = parent->color; + parent->color = BLACK; + sibling->left->color = BLACK; + return; + } + else if (sibling->right != NULL && sibling->right->color == RED) + { + /* + parent parent + bh+1|bh+2 bh+1|bh+2 + / \ / \ + sibling child --> SR child + bh+1 bh bh+1 bh + / \ / \ + SL SR sibling SRR + bh bh bh bh + / \ / \ + SRL SRR SL SRL + bh bh bh bh + + where SL, SRL, SRR are all black. + */ + parent->left = rotate_left (sibling, sibling->right); + /* Change sibling from BLACK to RED and SL from RED to BLACK. */ + sibling->color = RED; + sibling = parent->left; + sibling->color = BLACK; + + /* Now do as in the previous case. */ + *parentp = rotate_right (sibling, parent); + sibling->color = parent->color; + parent->color = BLACK; + sibling->left->color = BLACK; + return; + } + else + { + if (parent->color == BLACK) + { + /* Change sibling from BLACK to RED. Then the entire + subtree at parent has decreased its black-height. + parent parent + bh+2 bh+1 + / \ / \ + sibling child --> sibling child + bh+1 bh bh bh + */ + sibling->color = RED; + + child = parent; + } + else + { + /* Change parent from RED to BLACK, but compensate by + changing sibling from BLACK to RED. + parent parent + bh+1 bh+1 + / \ / \ + sibling child --> sibling child + bh+1 bh bh bh + */ + parent->color = BLACK; + sibling->color = RED; + return; + } + } + } + else + abort (); + + /* Start again with a new (child, parent) pair. */ + parent = child->parent; + +#if 0 /* Already handled. */ + if (child != NULL && child->color == RED) + { + child->color = BLACK; + return; + } +#endif + + if (parent == NULL) + return; + } +} + +static void +gl_tree_remove_node_from_tree (gl_list_t list, gl_list_node_t node) +{ + gl_list_node_t parent = node->parent; + + if (node->left == NULL) + { + /* Replace node with node->right. */ + gl_list_node_t child = node->right; + + if (child != NULL) + { + child->parent = parent; + /* Since node->left == NULL, child must be RED and of height 1, + hence node must have been BLACK. Recolor the child. */ + child->color = BLACK; + } + if (parent == NULL) + list->root = child; + else + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = parent; p != NULL; p = p->parent) + p->branch_size--; + } + + if (child == NULL && node->color == BLACK) + rebalance_after_remove (list, child, parent); + } + } + else if (node->right == NULL) + { + /* It is not absolutely necessary to treat this case. But the more + general case below is more complicated, hence slower. */ + /* Replace node with node->left. */ + gl_list_node_t child = node->left; + + child->parent = parent; + /* Since node->right == NULL, child must be RED and of height 1, + hence node must have been BLACK. Recolor the child. */ + child->color = BLACK; + if (parent == NULL) + list->root = child; + else + { + if (parent->left == node) + parent->left = child; + else /* parent->right == node */ + parent->right = child; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = parent; p != NULL; p = p->parent) + p->branch_size--; + } + } + } + else + { + /* Replace node with the rightmost element of the node->left subtree. */ + gl_list_node_t subst; + gl_list_node_t subst_parent; + gl_list_node_t child; + color_t removed_color; + + for (subst = node->left; subst->right != NULL; ) + subst = subst->right; + + subst_parent = subst->parent; + + child = subst->left; + + removed_color = subst->color; + + /* The case subst_parent == node is special: If we do nothing special, + we get confusion about node->left, subst->left and child->parent. + subst_parent == node + <==> The 'for' loop above terminated immediately. + <==> subst == subst_parent->left + [otherwise subst == subst_parent->right] + In this case, we would need to first set + child->parent = node; node->left = child; + and later - when we copy subst into node's position - again + child->parent = subst; subst->left = child; + Altogether a no-op. */ + if (subst_parent != node) + { + if (child != NULL) + child->parent = subst_parent; + subst_parent->right = child; + } + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = subst_parent; p != NULL; p = p->parent) + p->branch_size--; + } + + /* Copy subst into node's position. + (This is safer than to copy subst's value into node, keep node in + place, and free subst.) */ + if (subst_parent != node) + { + subst->left = node->left; + subst->left->parent = subst; + } + subst->right = node->right; + subst->right->parent = subst; + subst->color = node->color; + subst->branch_size = node->branch_size; + subst->parent = parent; + if (parent == NULL) + list->root = subst; + else if (parent->left == node) + parent->left = subst; + else /* parent->right == node */ + parent->right = subst; + + if (removed_color == BLACK) + { + if (child != NULL && child->color == RED) + /* Recolor the child. */ + child->color = BLACK; + else + /* Rebalancing starts at child's parent, that is subst_parent - + except when subst_parent == node. In this case, we need to use + its replacement, subst. */ + rebalance_after_remove (list, child, + subst_parent != node ? subst_parent : subst); + } + } +} + +static gl_list_node_t +gl_tree_nx_add_first (gl_list_t list, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* Add it to the tree. */ + if (list->root == NULL) + { + new_node->color = BLACK; + list->root = new_node; + new_node->parent = NULL; + } + else + { + gl_list_node_t node; + + for (node = list->root; node->left != NULL; ) + node = node->left; + + node->left = new_node; + new_node->parent = node; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + } + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_nx_add_last (gl_list_t list, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* Add it to the tree. */ + if (list->root == NULL) + { + new_node->color = BLACK; + list->root = new_node; + new_node->parent = NULL; + } + else + { + gl_list_node_t node; + + for (node = list->root; node->right != NULL; ) + node = node->right; + + node->right = new_node; + new_node->parent = node; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + } + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* Add it to the tree. */ + if (node->left == NULL) + node->left = new_node; + else + { + for (node = node->left; node->right != NULL; ) + node = node->right; + node->right = new_node; + } + new_node->parent = node; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; +} + +static gl_list_node_t +gl_tree_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + /* Create new node. */ + gl_list_node_t new_node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (new_node == NULL) + return NULL; + + new_node->left = NULL; + new_node->right = NULL; + new_node->branch_size = 1; + new_node->value = elt; +#if WITH_HASHTABLE + new_node->h.hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (new_node->value) + : (size_t)(uintptr_t) new_node->value); +#endif + + /* Add it to the tree. */ + if (node->right == NULL) + node->right = new_node; + else + { + for (node = node->right; node->left != NULL; ) + node = node->left; + node->left = new_node; + } + new_node->parent = node; + + /* Update branch_size fields of the parent nodes. */ + { + gl_list_node_t p; + + for (p = node; p != NULL; p = p->parent) + p->branch_size++; + } + + /* Color and rebalance. */ + rebalance_after_add (list, new_node, node); + +#if WITH_HASHTABLE + /* Add node to the hash table. + Note that this is only possible _after_ the node has been added to the + tree structure, because add_to_bucket() uses node_position(). */ + if (add_to_bucket (list, new_node) < 0) + { + gl_tree_remove_node_from_tree (list, new_node); + free (new_node); + return NULL; + } + hash_resize_after_add (list); +#endif + + return new_node; +} diff --git a/gl/lib/gl_anytree_list1.h b/gl/lib/gl_anytree_list1.h new file mode 100644 index 00000000..c0ef5677 --- /dev/null +++ b/gl/lib/gl_anytree_list1.h @@ -0,0 +1,41 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* Common code of gl_avltree_list.c, gl_rbtree_list.c, + gl_avltreehash_list.c, gl_rbtreehash_list.c. */ + +/* An item on the stack used for iterating across the elements. */ +typedef struct +{ + gl_list_node_t node; + size_t rightp; +} iterstack_item_t; + +/* A stack used for iterating across the elements. */ +typedef iterstack_item_t iterstack_t[MAXHEIGHT]; + +/* Free a non-empty subtree recursively. + This function is recursive and therefore not very fast. */ +static void +free_subtree (gl_list_node_t node) +{ + if (node->left != NULL) + free_subtree (node->left); + if (node->right != NULL) + free_subtree (node->right); + free (node); +} diff --git a/gl/lib/gl_anytree_list2.h b/gl/lib/gl_anytree_list2.h new file mode 100644 index 00000000..6ce41bf7 --- /dev/null +++ b/gl/lib/gl_anytree_list2.h @@ -0,0 +1,940 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* Common code of gl_avltree_list.c, gl_rbtree_list.c, + gl_avltreehash_list.c, gl_rbtreehash_list.c. */ + +static gl_list_t +gl_tree_nx_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates) +{ + struct gl_list_impl *list = (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); + + if (list == NULL) + return NULL; + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; + list->base.allow_duplicates = allow_duplicates; +#if WITH_HASHTABLE + list->table_size = 11; + list->table = + (gl_hash_entry_t *) calloc (list->table_size, sizeof (gl_hash_entry_t)); + if (list->table == NULL) + goto fail; +#endif + list->root = NULL; + + return list; + +#if WITH_HASHTABLE + fail: + free (list); + return NULL; +#endif +} + +static size_t +gl_tree_size (gl_list_t list) +{ + return (list->root != NULL ? list->root->branch_size : 0); +} + +static const void * +gl_tree_node_value (gl_list_t list, gl_list_node_t node) +{ + return node->value; +} + +static int +gl_tree_node_nx_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +{ +#if WITH_HASHTABLE + if (elt != node->value) + { + size_t new_hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + + if (new_hashcode != node->h.hashcode) + { + remove_from_bucket (list, node); + node->value = elt; + node->h.hashcode = new_hashcode; + if (add_to_bucket (list, node) < 0) + { + /* Out of memory. We removed node from a bucket but cannot add + it to another bucket. In order to avoid inconsistencies, we + must remove node entirely from the list. */ + gl_tree_remove_node_from_tree (list, node); + free (node); + return -1; + } + } + else + node->value = elt; + } +#else + node->value = elt; +#endif + return 0; +} + +static gl_list_node_t _GL_ATTRIBUTE_PURE +gl_tree_next_node (gl_list_t list, gl_list_node_t node) +{ + if (node->right != NULL) + { + node = node->right; + while (node->left != NULL) + node = node->left; + } + else + { + while (node->parent != NULL && node->parent->right == node) + node = node->parent; + node = node->parent; + } + return node; +} + +static gl_list_node_t _GL_ATTRIBUTE_PURE +gl_tree_previous_node (gl_list_t list, gl_list_node_t node) +{ + if (node->left != NULL) + { + node = node->left; + while (node->right != NULL) + node = node->right; + } + else + { + while (node->parent != NULL && node->parent->left == node) + node = node->parent; + node = node->parent; + } + return node; +} + +/* Return the node at the given position < gl_tree_size (list). */ +static gl_list_node_t _GL_ATTRIBUTE_PURE +node_at (gl_list_node_t root, size_t position) +{ + /* Here we know that root != NULL. */ + gl_list_node_t node = root; + + for (;;) + { + if (node->left != NULL) + { + if (position < node->left->branch_size) + { + node = node->left; + continue; + } + position -= node->left->branch_size; + } + if (position == 0) + break; + position--; + node = node->right; + } + return node; +} + +static const void * _GL_ATTRIBUTE_PURE +gl_tree_get_at (gl_list_t list, size_t position) +{ + gl_list_node_t node = list->root; + + if (!(node != NULL && position < node->branch_size)) + /* Invalid argument. */ + abort (); + node = node_at (node, position); + return node->value; +} + +static gl_list_node_t +gl_tree_nx_set_at (gl_list_t list, size_t position, const void *elt) +{ + gl_list_node_t node = list->root; + + if (!(node != NULL && position < node->branch_size)) + /* Invalid argument. */ + abort (); + node = node_at (node, position); +#if WITH_HASHTABLE + if (elt != node->value) + { + size_t new_hashcode = + (list->base.hashcode_fn != NULL + ? list->base.hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + + if (new_hashcode != node->h.hashcode) + { + remove_from_bucket (list, node); + node->value = elt; + node->h.hashcode = new_hashcode; + if (add_to_bucket (list, node) < 0) + { + /* Out of memory. We removed node from a bucket but cannot add + it to another bucket. In order to avoid inconsistencies, we + must remove node entirely from the list. */ + gl_tree_remove_node_from_tree (list, node); + free (node); + return NULL; + } + } + else + node->value = elt; + } +#else + node->value = elt; +#endif + return node; +} + +#if !WITH_HASHTABLE + +static gl_list_node_t +gl_tree_search_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + if (!(start_index <= end_index + && end_index <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + { + gl_listelement_equals_fn equals = list->base.equals_fn; + /* Iterate across all elements. */ + gl_list_node_t node = list->root; + iterstack_t stack; + iterstack_item_t *stack_ptr = &stack[0]; + size_t index = 0; + + if (start_index == 0) + { + /* Consider all elements. */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + return NULL; + stack_ptr--; + if (!stack_ptr->rightp) + break; + } + node = stack_ptr->node; + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return node; + index++; + if (index >= end_index) + return NULL; + /* Descend on right branch. */ + stack_ptr->rightp = 1; + node = node->right; + stack_ptr++; + } + } + else + { + /* Consider only elements at indices >= start_index. + In this case, rightp contains the difference between the start_index + for the parent node and the one for the child node (0 when the child + node is the parent's left child, > 0 when the child is the parent's + right child). */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + if (node->branch_size <= start_index) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + return NULL; + stack_ptr--; + if (!stack_ptr->rightp) + break; + start_index += stack_ptr->rightp; + } + node = stack_ptr->node; + { + size_t left_branch_size1 = + (node->left != NULL ? node->left->branch_size : 0) + 1; + if (start_index < left_branch_size1) + { + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return node; + /* Now that we have considered all indices < left_branch_size1, + we can increment start_index. */ + start_index = left_branch_size1; + } + index++; + if (index >= end_index) + return NULL; + /* Descend on right branch. */ + start_index -= left_branch_size1; + stack_ptr->rightp = left_branch_size1; + } + node = node->right; + stack_ptr++; + } + } + } +} + +static size_t +gl_tree_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + if (!(start_index <= end_index + && end_index <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + { + gl_listelement_equals_fn equals = list->base.equals_fn; + /* Iterate across all elements. */ + gl_list_node_t node = list->root; + iterstack_t stack; + iterstack_item_t *stack_ptr = &stack[0]; + size_t index = 0; + + if (start_index == 0) + { + /* Consider all elements. */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + return (size_t)(-1); + stack_ptr--; + if (!stack_ptr->rightp) + break; + } + node = stack_ptr->node; + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return index; + index++; + if (index >= end_index) + return (size_t)(-1); + /* Descend on right branch. */ + stack_ptr->rightp = 1; + node = node->right; + stack_ptr++; + } + } + else + { + /* Consider only elements at indices >= start_index. + In this case, rightp contains the difference between the start_index + for the parent node and the one for the child node (0 when the child + node is the parent's left child, > 0 when the child is the parent's + right child). */ + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + if (node->branch_size <= start_index) + break; + stack_ptr->node = node; + stack_ptr->rightp = 0; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + return (size_t)(-1); + stack_ptr--; + if (!stack_ptr->rightp) + break; + start_index += stack_ptr->rightp; + } + node = stack_ptr->node; + { + size_t left_branch_size1 = + (node->left != NULL ? node->left->branch_size : 0) + 1; + if (start_index < left_branch_size1) + { + /* Test against current element. */ + if (equals != NULL ? equals (elt, node->value) : elt == node->value) + return index; + /* Now that we have considered all indices < left_branch_size1, + we can increment start_index. */ + start_index = left_branch_size1; + } + index++; + if (index >= end_index) + return (size_t)(-1); + /* Descend on right branch. */ + start_index -= left_branch_size1; + stack_ptr->rightp = left_branch_size1; + } + node = node->right; + stack_ptr++; + } + } + } +} + +#endif + +static gl_list_node_t +gl_tree_nx_add_at (gl_list_t list, size_t position, const void *elt) +{ + size_t count = (list->root != NULL ? list->root->branch_size : 0); + + if (!(position <= count)) + /* Invalid argument. */ + abort (); + if (position == count) + return gl_tree_nx_add_last (list, elt); + else + return gl_tree_nx_add_before (list, node_at (list->root, position), elt); +} + +static bool +gl_tree_remove_node (gl_list_t list, gl_list_node_t node) +{ +#if WITH_HASHTABLE + /* Remove node from the hash table. + Note that this is only possible _before_ the node is removed from the + tree structure, because remove_from_bucket() uses node_position(). */ + remove_from_bucket (list, node); +#endif + + gl_tree_remove_node_from_tree (list, node); + + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (node->value); + free (node); + return true; +} + +static bool +gl_tree_remove_at (gl_list_t list, size_t position) +{ + gl_list_node_t node = list->root; + + if (!(node != NULL && position < node->branch_size)) + /* Invalid argument. */ + abort (); + node = node_at (node, position); + return gl_tree_remove_node (list, node); +} + +static bool +gl_tree_remove (gl_list_t list, const void *elt) +{ + if (list->root != NULL) + { + gl_list_node_t node = + gl_tree_search_from_to (list, 0, list->root->branch_size, elt); + + if (node != NULL) + return gl_tree_remove_node (list, node); + } + return false; +} + +#if !WITH_HASHTABLE + +static void +gl_tree_list_free (gl_list_t list) +{ + /* Iterate across all elements in post-order. */ + gl_list_node_t node = list->root; + iterstack_t stack; + iterstack_item_t *stack_ptr = &stack[0]; + + for (;;) + { + /* Descend on left branch. */ + for (;;) + { + if (node == NULL) + break; + stack_ptr->node = node; + stack_ptr->rightp = false; + node = node->left; + stack_ptr++; + } + /* Climb up again. */ + for (;;) + { + if (stack_ptr == &stack[0]) + goto done_iterate; + stack_ptr--; + node = stack_ptr->node; + if (!stack_ptr->rightp) + break; + /* Free the current node. */ + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (node->value); + free (node); + } + /* Descend on right branch. */ + stack_ptr->rightp = true; + node = node->right; + stack_ptr++; + } + done_iterate: + free (list); +} + +#endif + +/* --------------------- gl_list_iterator_t Data Type --------------------- */ + +static gl_list_iterator_t +gl_tree_iterator (gl_list_t list) +{ + gl_list_iterator_t result; + gl_list_node_t node; + + result.vtable = list->base.vtable; + result.list = list; + /* Start node is the leftmost node. */ + node = list->root; + if (node != NULL) + while (node->left != NULL) + node = node->left; + result.p = node; + /* End point is past the rightmost node. */ + result.q = NULL; +#if defined GCC_LINT || defined lint + result.i = 0; + result.j = 0; + result.count = 0; +#endif + + return result; +} + +static gl_list_iterator_t +gl_tree_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index) +{ + size_t count = (list->root != NULL ? list->root->branch_size : 0); + gl_list_iterator_t result; + + if (!(start_index <= end_index && end_index <= count)) + /* Invalid arguments. */ + abort (); + result.vtable = list->base.vtable; + result.list = list; + /* Start node is the node at position start_index. */ + result.p = (start_index < count ? node_at (list->root, start_index) : NULL); + /* End point is the node at position end_index. */ + result.q = (end_index < count ? node_at (list->root, end_index) : NULL); +#if defined GCC_LINT || defined lint + result.i = 0; + result.j = 0; + result.count = 0; +#endif + + return result; +} + +static bool +gl_tree_iterator_next (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep) +{ + if (iterator->p != iterator->q) + { + gl_list_node_t node = (gl_list_node_t) iterator->p; + *eltp = node->value; + if (nodep != NULL) + *nodep = node; + /* Advance to the next node. */ + if (node->right != NULL) + { + node = node->right; + while (node->left != NULL) + node = node->left; + } + else + { + while (node->parent != NULL && node->parent->right == node) + node = node->parent; + node = node->parent; + } + iterator->p = node; + return true; + } + else + return false; +} + +static void +gl_tree_iterator_free (gl_list_iterator_t *iterator) +{ +} + +/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ + +static gl_list_node_t +gl_tree_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + + for (node = list->root; node != NULL; ) + { + int cmp = compar (node->value, elt); + + if (cmp < 0) + node = node->right; + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have an element equal to ELT. But we need the leftmost such + element. */ + gl_list_node_t found = node; + node = node->left; + for (; node != NULL; ) + { + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + node = node->right; + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + found = node; + node = node->left; + } + } + return found; + } + } + return NULL; +} + +static gl_list_node_t +gl_tree_sortedlist_search_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t low, size_t high, + const void *elt) +{ + gl_list_node_t node; + + if (!(low <= high + && high <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + + for (node = list->root; node != NULL; ) + { + size_t left_branch_size = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size) + { + low -= left_branch_size + 1; + high -= left_branch_size + 1; + node = node->right; + } + else if (high <= left_branch_size) + node = node->left; + else + { + /* Here low <= left_branch_size < high. */ + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + low = 0; + high -= left_branch_size + 1; + node = node->right; + } + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have an element equal to ELT. But we need the leftmost + such element. */ + gl_list_node_t found = node; + node = node->left; + for (; node != NULL; ) + { + size_t left_branch_size2 = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size2) + { + low -= left_branch_size2 + 1; + node = node->right; + } + else + { + /* Here low <= left_branch_size2. */ + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + { + low = 0; + node = node->right; + } + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + found = node; + node = node->left; + } + } + } + return found; + } + } + } + return NULL; +} + +static size_t +gl_tree_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node; + size_t position; + + for (node = list->root, position = 0; node != NULL; ) + { + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + if (node->left != NULL) + position += node->left->branch_size; + position++; + node = node->right; + } + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have an element equal to ELT. But we need the leftmost such + element. */ + size_t found_position = + position + (node->left != NULL ? node->left->branch_size : 0); + node = node->left; + for (; node != NULL; ) + { + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + { + if (node->left != NULL) + position += node->left->branch_size; + position++; + node = node->right; + } + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + found_position = + position + + (node->left != NULL ? node->left->branch_size : 0); + node = node->left; + } + } + return found_position; + } + } + return (size_t)(-1); +} + +static size_t +gl_tree_sortedlist_indexof_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t low, size_t high, + const void *elt) +{ + gl_list_node_t node; + size_t position; + + if (!(low <= high + && high <= (list->root != NULL ? list->root->branch_size : 0))) + /* Invalid arguments. */ + abort (); + + for (node = list->root, position = 0; node != NULL; ) + { + size_t left_branch_size = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size) + { + low -= left_branch_size + 1; + high -= left_branch_size + 1; + position += left_branch_size + 1; + node = node->right; + } + else if (high <= left_branch_size) + node = node->left; + else + { + /* Here low <= left_branch_size < high. */ + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + low = 0; + high -= left_branch_size + 1; + position += left_branch_size + 1; + node = node->right; + } + else if (cmp > 0) + node = node->left; + else /* cmp == 0 */ + { + /* We have an element equal to ELT. But we need the leftmost + such element. */ + size_t found_position = + position + (node->left != NULL ? node->left->branch_size : 0); + node = node->left; + for (; node != NULL; ) + { + size_t left_branch_size2 = + (node->left != NULL ? node->left->branch_size : 0); + + if (low > left_branch_size2) + { + low -= left_branch_size2 + 1; + node = node->right; + } + else + { + /* Here low <= left_branch_size2. */ + int cmp2 = compar (node->value, elt); + + if (cmp2 < 0) + { + position += left_branch_size2 + 1; + node = node->right; + } + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + found_position = position + left_branch_size2; + node = node->left; + } + } + } + return found_position; + } + } + } + return (size_t)(-1); +} + +static gl_list_node_t +gl_tree_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node = list->root; + + if (node == NULL) + return gl_tree_nx_add_first (list, elt); + + for (;;) + { + int cmp = compar (node->value, elt); + + if (cmp < 0) + { + if (node->right == NULL) + return gl_tree_nx_add_after (list, node, elt); + node = node->right; + } + else if (cmp > 0) + { + if (node->left == NULL) + return gl_tree_nx_add_before (list, node, elt); + node = node->left; + } + else /* cmp == 0 */ + return gl_tree_nx_add_before (list, node, elt); + } +} + +static bool +gl_tree_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t node = gl_tree_sortedlist_search (list, compar, elt); + if (node != NULL) + return gl_tree_remove_node (list, node); + else + return false; +} diff --git a/gl/lib/gl_array_list.c b/gl/lib/gl_array_list.c new file mode 100644 index 00000000..4ac743fd --- /dev/null +++ b/gl/lib/gl_array_list.c @@ -0,0 +1,680 @@ +/* Sequential list data type implemented by an array. + Copyright (C) 2006-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "gl_array_list.h" + +#include <stdlib.h> +/* Get memcpy. */ +#include <string.h> + +/* Checked size_t computations. */ +#include "xsize.h" + +#ifndef uintptr_t +# define uintptr_t unsigned long +#endif + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Concrete gl_list_impl type, valid for this file only. */ +struct gl_list_impl +{ + struct gl_list_impl_base base; + /* An array of ALLOCATED elements, of which the first COUNT are used. + 0 <= COUNT <= ALLOCATED. */ + const void **elements; + size_t count; + size_t allocated; +}; + +/* struct gl_list_node_impl doesn't exist here. The pointers are actually + indices + 1. */ +#define INDEX_TO_NODE(index) (gl_list_node_t)(uintptr_t)(size_t)((index) + 1) +#define NODE_TO_INDEX(node) ((uintptr_t)(node) - 1) + +static gl_list_t +gl_array_nx_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates) +{ + struct gl_list_impl *list = + (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); + + if (list == NULL) + return NULL; + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; + list->base.allow_duplicates = allow_duplicates; + list->elements = NULL; + list->count = 0; + list->allocated = 0; + + return list; +} + +static gl_list_t +gl_array_nx_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents) +{ + struct gl_list_impl *list = + (struct gl_list_impl *) malloc (sizeof (struct gl_list_impl)); + + if (list == NULL) + return NULL; + + list->base.vtable = implementation; + list->base.equals_fn = equals_fn; + list->base.hashcode_fn = hashcode_fn; + list->base.dispose_fn = dispose_fn; + list->base.allow_duplicates = allow_duplicates; + if (count > 0) + { + if (size_overflow_p (xtimes (count, sizeof (const void *)))) + goto fail; + list->elements = (const void **) malloc (count * sizeof (const void *)); + if (list->elements == NULL) + goto fail; + memcpy (list->elements, contents, count * sizeof (const void *)); + } + else + list->elements = NULL; + list->count = count; + list->allocated = count; + + return list; + + fail: + free (list); + return NULL; +} + +static size_t +gl_array_size (gl_list_t list) +{ + return list->count; +} + +static const void * _GL_ATTRIBUTE_PURE +gl_array_node_value (gl_list_t list, gl_list_node_t node) +{ + uintptr_t index = NODE_TO_INDEX (node); + if (!(index < list->count)) + /* Invalid argument. */ + abort (); + return list->elements[index]; +} + +static int +gl_array_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) +{ + uintptr_t index = NODE_TO_INDEX (node); + if (!(index < list->count)) + /* Invalid argument. */ + abort (); + list->elements[index] = elt; + return 0; +} + +static gl_list_node_t _GL_ATTRIBUTE_PURE +gl_array_next_node (gl_list_t list, gl_list_node_t node) +{ + uintptr_t index = NODE_TO_INDEX (node); + if (!(index < list->count)) + /* Invalid argument. */ + abort (); + index++; + if (index < list->count) + return INDEX_TO_NODE (index); + else + return NULL; +} + +static gl_list_node_t _GL_ATTRIBUTE_PURE +gl_array_previous_node (gl_list_t list, gl_list_node_t node) +{ + uintptr_t index = NODE_TO_INDEX (node); + if (!(index < list->count)) + /* Invalid argument. */ + abort (); + if (index > 0) + return INDEX_TO_NODE (index - 1); + else + return NULL; +} + +static const void * _GL_ATTRIBUTE_PURE +gl_array_get_at (gl_list_t list, size_t position) +{ + size_t count = list->count; + + if (!(position < count)) + /* Invalid argument. */ + abort (); + return list->elements[position]; +} + +static gl_list_node_t +gl_array_nx_set_at (gl_list_t list, size_t position, const void *elt) +{ + size_t count = list->count; + + if (!(position < count)) + /* Invalid argument. */ + abort (); + list->elements[position] = elt; + return INDEX_TO_NODE (position); +} + +static size_t +gl_array_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + size_t count = list->count; + + if (!(start_index <= end_index && end_index <= count)) + /* Invalid arguments. */ + abort (); + + if (start_index < end_index) + { + gl_listelement_equals_fn equals = list->base.equals_fn; + if (equals != NULL) + { + size_t i; + + for (i = start_index;;) + { + if (equals (elt, list->elements[i])) + return i; + i++; + if (i == end_index) + break; + } + } + else + { + size_t i; + + for (i = start_index;;) + { + if (elt == list->elements[i]) + return i; + i++; + if (i == end_index) + break; + } + } + } + return (size_t)(-1); +} + +static gl_list_node_t +gl_array_search_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + size_t index = gl_array_indexof_from_to (list, start_index, end_index, elt); + return INDEX_TO_NODE (index); +} + +/* Ensure that list->allocated > list->count. + Return 0 upon success, -1 upon out-of-memory. */ +static int +grow (gl_list_t list) +{ + size_t new_allocated; + size_t memory_size; + const void **memory; + + new_allocated = xtimes (list->allocated, 2); + new_allocated = xsum (new_allocated, 1); + memory_size = xtimes (new_allocated, sizeof (const void *)); + if (size_overflow_p (memory_size)) + /* Overflow, would lead to out of memory. */ + return -1; + memory = (const void **) realloc (list->elements, memory_size); + if (memory == NULL) + /* Out of memory. */ + return -1; + list->elements = memory; + list->allocated = new_allocated; + return 0; +} + +static gl_list_node_t +gl_array_nx_add_first (gl_list_t list, const void *elt) +{ + size_t count = list->count; + const void **elements; + size_t i; + + if (count == list->allocated) + if (grow (list) < 0) + return NULL; + elements = list->elements; + for (i = count; i > 0; i--) + elements[i] = elements[i - 1]; + elements[0] = elt; + list->count = count + 1; + return INDEX_TO_NODE (0); +} + +static gl_list_node_t +gl_array_nx_add_last (gl_list_t list, const void *elt) +{ + size_t count = list->count; + + if (count == list->allocated) + if (grow (list) < 0) + return NULL; + list->elements[count] = elt; + list->count = count + 1; + return INDEX_TO_NODE (count); +} + +static gl_list_node_t +gl_array_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + size_t count = list->count; + uintptr_t index = NODE_TO_INDEX (node); + size_t position; + const void **elements; + size_t i; + + if (!(index < count)) + /* Invalid argument. */ + abort (); + position = index; + if (count == list->allocated) + if (grow (list) < 0) + return NULL; + elements = list->elements; + for (i = count; i > position; i--) + elements[i] = elements[i - 1]; + elements[position] = elt; + list->count = count + 1; + return INDEX_TO_NODE (position); +} + +static gl_list_node_t +gl_array_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + size_t count = list->count; + uintptr_t index = NODE_TO_INDEX (node); + size_t position; + const void **elements; + size_t i; + + if (!(index < count)) + /* Invalid argument. */ + abort (); + position = index + 1; + if (count == list->allocated) + if (grow (list) < 0) + return NULL; + elements = list->elements; + for (i = count; i > position; i--) + elements[i] = elements[i - 1]; + elements[position] = elt; + list->count = count + 1; + return INDEX_TO_NODE (position); +} + +static gl_list_node_t +gl_array_nx_add_at (gl_list_t list, size_t position, const void *elt) +{ + size_t count = list->count; + const void **elements; + size_t i; + + if (!(position <= count)) + /* Invalid argument. */ + abort (); + if (count == list->allocated) + if (grow (list) < 0) + return NULL; + elements = list->elements; + for (i = count; i > position; i--) + elements[i] = elements[i - 1]; + elements[position] = elt; + list->count = count + 1; + return INDEX_TO_NODE (position); +} + +static bool +gl_array_remove_node (gl_list_t list, gl_list_node_t node) +{ + size_t count = list->count; + uintptr_t index = NODE_TO_INDEX (node); + size_t position; + const void **elements; + size_t i; + + if (!(index < count)) + /* Invalid argument. */ + abort (); + position = index; + elements = list->elements; + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[position]); + for (i = position + 1; i < count; i++) + elements[i - 1] = elements[i]; + list->count = count - 1; + return true; +} + +static bool +gl_array_remove_at (gl_list_t list, size_t position) +{ + size_t count = list->count; + const void **elements; + size_t i; + + if (!(position < count)) + /* Invalid argument. */ + abort (); + elements = list->elements; + if (list->base.dispose_fn != NULL) + list->base.dispose_fn (elements[position]); + for (i = position + 1; i < count; i++) + elements[i - 1] = elements[i]; + list->count = count - 1; + return true; +} + +static bool +gl_array_remove (gl_list_t list, const void *elt) +{ + size_t position = gl_array_indexof_from_to (list, 0, list->count, elt); + if (position == (size_t)(-1)) + return false; + else + return gl_array_remove_at (list, position); +} + +static void +gl_array_list_free (gl_list_t list) +{ + if (list->elements != NULL) + { + if (list->base.dispose_fn != NULL) + { + size_t count = list->count; + + if (count > 0) + { + gl_listelement_dispose_fn dispose = list->base.dispose_fn; + const void **elements = list->elements; + + do + dispose (*elements++); + while (--count > 0); + } + } + free (list->elements); + } + free (list); +} + +/* --------------------- gl_list_iterator_t Data Type --------------------- */ + +static gl_list_iterator_t +gl_array_iterator (gl_list_t list) +{ + gl_list_iterator_t result; + + result.vtable = list->base.vtable; + result.list = list; + result.count = list->count; + result.p = list->elements + 0; + result.q = list->elements + list->count; +#if defined GCC_LINT || defined lint + result.i = 0; + result.j = 0; +#endif + + return result; +} + +static gl_list_iterator_t +gl_array_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index) +{ + gl_list_iterator_t result; + + if (!(start_index <= end_index && end_index <= list->count)) + /* Invalid arguments. */ + abort (); + result.vtable = list->base.vtable; + result.list = list; + result.count = list->count; + result.p = list->elements + start_index; + result.q = list->elements + end_index; +#if defined GCC_LINT || defined lint + result.i = 0; + result.j = 0; +#endif + + return result; +} + +static bool +gl_array_iterator_next (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep) +{ + gl_list_t list = iterator->list; + if (iterator->count != list->count) + { + if (iterator->count != list->count + 1) + /* Concurrent modifications were done on the list. */ + abort (); + /* The last returned element was removed. */ + iterator->count--; + iterator->p = (const void **) iterator->p - 1; + iterator->q = (const void **) iterator->q - 1; + } + if (iterator->p < iterator->q) + { + const void **p = (const void **) iterator->p; + *eltp = *p; + if (nodep != NULL) + *nodep = INDEX_TO_NODE (p - list->elements); + iterator->p = p + 1; + return true; + } + else + return false; +} + +static void +gl_array_iterator_free (gl_list_iterator_t *iterator _GL_UNUSED) +{ +} + +/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ + +static size_t +gl_array_sortedlist_indexof_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t low, size_t high, + const void *elt) +{ + if (!(low <= high && high <= list->count)) + /* Invalid arguments. */ + abort (); + if (low < high) + { + /* At each loop iteration, low < high; for indices < low the values + are smaller than ELT; for indices >= high the values are greater + than ELT. So, if the element occurs in the list, it is at + low <= position < high. */ + do + { + size_t mid = low + (high - low) / 2; /* low <= mid < high */ + int cmp = compar (list->elements[mid], elt); + + if (cmp < 0) + low = mid + 1; + else if (cmp > 0) + high = mid; + else /* cmp == 0 */ + { + /* We have an element equal to ELT at index MID. But we need + the minimal such index. */ + high = mid; + /* At each loop iteration, low <= high and + compar (list->elements[high], elt) == 0, + and we know that the first occurrence of the element is at + low <= position <= high. */ + while (low < high) + { + size_t mid2 = low + (high - low) / 2; /* low <= mid2 < high */ + int cmp2 = compar (list->elements[mid2], elt); + + if (cmp2 < 0) + low = mid2 + 1; + else if (cmp2 > 0) + /* The list was not sorted. */ + abort (); + else /* cmp2 == 0 */ + { + if (mid2 == low) + break; + high = mid2 - 1; + } + } + return low; + } + } + while (low < high); + /* Here low == high. */ + } + return (size_t)(-1); +} + +static size_t +gl_array_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + return gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, + elt); +} + +static gl_list_node_t +gl_array_sortedlist_search_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t low, size_t high, + const void *elt) +{ + size_t index = + gl_array_sortedlist_indexof_from_to (list, compar, low, high, elt); + return INDEX_TO_NODE (index); +} + +static gl_list_node_t +gl_array_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + size_t index = + gl_array_sortedlist_indexof_from_to (list, compar, 0, list->count, elt); + return INDEX_TO_NODE (index); +} + +static gl_list_node_t +gl_array_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + size_t count = list->count; + size_t low = 0; + size_t high = count; + + /* At each loop iteration, low <= high; for indices < low the values are + smaller than ELT; for indices >= high the values are greater than ELT. */ + while (low < high) + { + size_t mid = low + (high - low) / 2; /* low <= mid < high */ + int cmp = compar (list->elements[mid], elt); + + if (cmp < 0) + low = mid + 1; + else if (cmp > 0) + high = mid; + else /* cmp == 0 */ + { + low = mid; + break; + } + } + return gl_array_nx_add_at (list, low, elt); +} + +static bool +gl_array_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + size_t index = gl_array_sortedlist_indexof (list, compar, elt); + if (index == (size_t)(-1)) + return false; + else + return gl_array_remove_at (list, index); +} + + +const struct gl_list_implementation gl_array_list_implementation = + { + gl_array_nx_create_empty, + gl_array_nx_create, + gl_array_size, + gl_array_node_value, + gl_array_node_nx_set_value, + gl_array_next_node, + gl_array_previous_node, + gl_array_get_at, + gl_array_nx_set_at, + gl_array_search_from_to, + gl_array_indexof_from_to, + gl_array_nx_add_first, + gl_array_nx_add_last, + gl_array_nx_add_before, + gl_array_nx_add_after, + gl_array_nx_add_at, + gl_array_remove_node, + gl_array_remove_at, + gl_array_remove, + gl_array_list_free, + gl_array_iterator, + gl_array_iterator_from_to, + gl_array_iterator_next, + gl_array_iterator_free, + gl_array_sortedlist_search, + gl_array_sortedlist_search_from_to, + gl_array_sortedlist_indexof, + gl_array_sortedlist_indexof_from_to, + gl_array_sortedlist_nx_add, + gl_array_sortedlist_remove + }; diff --git a/gl/lib/gl_array_list.h b/gl/lib/gl_array_list.h new file mode 100644 index 00000000..98158feb --- /dev/null +++ b/gl/lib/gl_array_list.h @@ -0,0 +1,34 @@ +/* Sequential list data type implemented by an array. + Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_ARRAY_LIST_H +#define _GL_ARRAY_LIST_H + +#include "gl_list.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_list_implementation gl_array_list_implementation; +#define GL_ARRAY_LIST &gl_array_list_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_ARRAY_LIST_H */ diff --git a/gl/lib/gl_hash_map.c b/gl/lib/gl_hash_map.c new file mode 100644 index 00000000..534b472f --- /dev/null +++ b/gl/lib/gl_hash_map.c @@ -0,0 +1,337 @@ +/* Map data type implemented by a hash table. + Copyright (C) 2006, 2008-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2018. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "gl_hash_map.h" + +#include <stdint.h> /* for SIZE_MAX */ +#include <stdlib.h> + +#include "xsize.h" + +#ifndef uintptr_t +# define uintptr_t unsigned long +#endif + +/* --------------------------- gl_map_t Data Type --------------------------- */ + +#include "gl_anyhash1.h" + +/* Concrete list node implementation, valid for this file only. */ +struct gl_list_node_impl +{ + struct gl_hash_entry h; /* hash table entry fields; must be first */ + const void *key; + const void *value; +}; +typedef struct gl_list_node_impl * gl_list_node_t; + +/* Concrete gl_map_impl type, valid for this file only. */ +struct gl_map_impl +{ + struct gl_map_impl_base base; + gl_mapkey_hashcode_fn hashcode_fn; + /* A hash table: managed as an array of collision lists. */ + struct gl_hash_entry **table; + size_t table_size; + /* Number of hash table entries. */ + size_t count; +}; + +#define CONTAINER_T gl_map_t +#define CONTAINER_COUNT(map) (map)->count +#include "gl_anyhash2.h" + +/* --------------------------- gl_map_t Data Type --------------------------- */ + +static gl_map_t +gl_hash_nx_create_empty (gl_map_implementation_t implementation, + gl_mapkey_equals_fn equals_fn, + gl_mapkey_hashcode_fn hashcode_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn) +{ + struct gl_map_impl *map = + (struct gl_map_impl *) malloc (sizeof (struct gl_map_impl)); + + if (map == NULL) + return NULL; + + map->base.vtable = implementation; + map->base.equals_fn = equals_fn; + map->base.kdispose_fn = kdispose_fn; + map->base.vdispose_fn = vdispose_fn; + map->hashcode_fn = hashcode_fn; + map->table_size = 11; + map->table = + (gl_hash_entry_t *) calloc (map->table_size, sizeof (gl_hash_entry_t)); + if (map->table == NULL) + goto fail; + map->count = 0; + + return map; + + fail: + free (map); + return NULL; +} + +static size_t _GL_ATTRIBUTE_PURE +gl_hash_size (gl_map_t map) +{ + return map->count; +} + +static bool _GL_ATTRIBUTE_PURE +gl_hash_search (gl_map_t map, const void *key, const void **valuep) +{ + size_t hashcode = + (map->hashcode_fn != NULL + ? map->hashcode_fn (key) + : (size_t)(uintptr_t) key); + size_t bucket = hashcode % map->table_size; + gl_mapkey_equals_fn equals = map->base.equals_fn; + + /* Look for a match in the hash bucket. */ + gl_list_node_t node; + + for (node = (gl_list_node_t) map->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (key, node->key) + : key == node->key)) + { + *valuep = node->value; + return true; + } + return false; +} + +static int +gl_hash_nx_getput (gl_map_t map, const void *key, const void *value, + const void **oldvaluep) +{ + size_t hashcode = + (map->hashcode_fn != NULL + ? map->hashcode_fn (key) + : (size_t)(uintptr_t) key); + size_t bucket = hashcode % map->table_size; + gl_mapkey_equals_fn equals = map->base.equals_fn; + + /* Look for a match in the hash bucket. */ + { + gl_list_node_t node; + + for (node = (gl_list_node_t) map->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (key, node->key) + : key == node->key)) + { + *oldvaluep = node->value; + node->value = value; + return 0; + } + } + + /* Allocate a new node. */ + gl_list_node_t node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (node == NULL) + return -1; + + node->key = key; + node->value = value; + node->h.hashcode = hashcode; + + /* Add node to the hash table. */ + node->h.hash_next = map->table[bucket]; + map->table[bucket] = &node->h; + + /* Add node to the map. */ + map->count++; + + hash_resize_after_add (map); + + return 1; +} + +static bool +gl_hash_getremove (gl_map_t map, const void *key, const void **oldvaluep) +{ + size_t hashcode = + (map->hashcode_fn != NULL + ? map->hashcode_fn (key) + : (size_t)(uintptr_t) key); + size_t bucket = hashcode % map->table_size; + gl_mapkey_equals_fn equals = map->base.equals_fn; + + /* Look for the first match in the hash bucket. */ + gl_list_node_t *nodep; + + for (nodep = (gl_list_node_t *) &map->table[bucket]; + *nodep != NULL; + nodep = (gl_list_node_t *) &(*nodep)->h.hash_next) + { + gl_list_node_t node = *nodep; + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (key, node->key) + : key == node->key)) + { + *oldvaluep = node->value; + + /* Remove node from the hash table. */ + *nodep = (gl_list_node_t) node->h.hash_next; + + /* Remove node from the map. */ + map->count--; + + if (map->base.kdispose_fn != NULL) + map->base.kdispose_fn (node->key); + free (node); + return true; + } + } + + return false; +} + +static void +gl_hash_free (gl_map_t map) +{ + if (map->count > 0) + { + gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn; + gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn; + struct gl_hash_entry **table = map->table; + size_t i; + + for (i = map->table_size; i > 0; ) + { + gl_hash_entry_t node = table[--i]; + + while (node != NULL) + { + gl_hash_entry_t next = node->hash_next; + + /* Free the entry. */ + if (vdispose != NULL) + vdispose (((gl_list_node_t) node)->value); + if (kdispose != NULL) + kdispose (((gl_list_node_t) node)->key); + free (node); + + node = next; + } + } + } + + free (map->table); + free (map); +} + +/* ---------------------- gl_map_iterator_t Data Type ---------------------- */ + +/* Here we iterate through the hash buckets. Therefore the order in which the + pairs are returned is unpredictable. */ + +static gl_map_iterator_t +gl_hash_iterator (gl_map_t map) +{ + gl_map_iterator_t result; + + result.vtable = map->base.vtable; + result.map = map; + result.p = NULL; /* runs through the nodes of a bucket */ + result.i = 0; /* index of the bucket that p points into + 1 */ + result.j = map->table_size; +#if defined GCC_LINT || defined lint + result.q = NULL; + result.count = 0; +#endif + + return result; +} + +static bool +gl_hash_iterator_next (gl_map_iterator_t *iterator, + const void **keyp, const void **valuep) +{ + if (iterator->p != NULL) + { + /* We're traversing a bucket. */ + gl_list_node_t node = (gl_list_node_t) iterator->p; + *keyp = node->key; + *valuep = node->value; + iterator->p = (gl_list_node_t) node->h.hash_next; + return true; + } + else + { + /* Find the next bucket that is not empty. */ + size_t j = iterator->j; + size_t i = iterator->i; + + if (i < j) + { + gl_hash_entry_t *table = iterator->map->table; + do + { + gl_list_node_t node = (gl_list_node_t) table[i++]; + if (node != NULL) + { + *keyp = node->key; + *valuep = node->value; + iterator->p = (gl_list_node_t) node->h.hash_next; + iterator->i = i; + return true; + } + } + while (i < j); + } + /* Here iterator->p is still NULL, and i == j. */ + iterator->i = j; + return false; + } +} + +static void +gl_hash_iterator_free (gl_map_iterator_t *iterator) +{ +} + + +const struct gl_map_implementation gl_hash_map_implementation = + { + gl_hash_nx_create_empty, + gl_hash_size, + gl_hash_search, + gl_hash_nx_getput, + gl_hash_getremove, + gl_hash_free, + gl_hash_iterator, + gl_hash_iterator_next, + gl_hash_iterator_free + }; diff --git a/gl/lib/gl_hash_map.h b/gl/lib/gl_hash_map.h new file mode 100644 index 00000000..9f539f93 --- /dev/null +++ b/gl/lib/gl_hash_map.h @@ -0,0 +1,34 @@ +/* Map data type implemented by a hash table. + Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2018. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_HASH_MAP_H +#define _GL_HASH_MAP_H + +#include "gl_map.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_map_implementation gl_hash_map_implementation; +#define GL_HASH_MAP &gl_hash_map_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_HASH_MAP_H */ diff --git a/gl/lib/gl_hash_set.c b/gl/lib/gl_hash_set.c new file mode 100644 index 00000000..303d1375 --- /dev/null +++ b/gl/lib/gl_hash_set.c @@ -0,0 +1,317 @@ +/* Set data type implemented by a hash table. + Copyright (C) 2006, 2008-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2018. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "gl_hash_set.h" + +#include <stdint.h> /* for SIZE_MAX */ +#include <stdlib.h> + +#include "xsize.h" + +#ifndef uintptr_t +# define uintptr_t unsigned long +#endif + +/* --------------------------- gl_set_t Data Type --------------------------- */ + +#include "gl_anyhash1.h" + +/* Concrete list node implementation, valid for this file only. */ +struct gl_list_node_impl +{ + struct gl_hash_entry h; /* hash table entry fields; must be first */ + const void *value; +}; +typedef struct gl_list_node_impl * gl_list_node_t; + +/* Concrete gl_set_impl type, valid for this file only. */ +struct gl_set_impl +{ + struct gl_set_impl_base base; + gl_setelement_hashcode_fn hashcode_fn; + /* A hash table: managed as an array of collision lists. */ + struct gl_hash_entry **table; + size_t table_size; + /* Number of hash table entries. */ + size_t count; +}; + +#define CONTAINER_T gl_set_t +#define CONTAINER_COUNT(set) (set)->count +#include "gl_anyhash2.h" + +/* --------------------------- gl_set_t Data Type --------------------------- */ + +static gl_set_t +gl_hash_nx_create_empty (gl_set_implementation_t implementation, + gl_setelement_equals_fn equals_fn, + gl_setelement_hashcode_fn hashcode_fn, + gl_setelement_dispose_fn dispose_fn) +{ + struct gl_set_impl *set = + (struct gl_set_impl *) malloc (sizeof (struct gl_set_impl)); + + if (set == NULL) + return NULL; + + set->base.vtable = implementation; + set->base.equals_fn = equals_fn; + set->base.dispose_fn = dispose_fn; + set->hashcode_fn = hashcode_fn; + set->table_size = 11; + set->table = + (gl_hash_entry_t *) calloc (set->table_size, sizeof (gl_hash_entry_t)); + if (set->table == NULL) + goto fail; + set->count = 0; + + return set; + + fail: + free (set); + return NULL; +} + +static size_t _GL_ATTRIBUTE_PURE +gl_hash_size (gl_set_t set) +{ + return set->count; +} + +static bool _GL_ATTRIBUTE_PURE +gl_hash_search (gl_set_t set, const void *elt) +{ + size_t hashcode = + (set->hashcode_fn != NULL + ? set->hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t bucket = hashcode % set->table_size; + gl_setelement_equals_fn equals = set->base.equals_fn; + + /* Look for a match in the hash bucket. */ + gl_list_node_t node; + + for (node = (gl_list_node_t) set->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + return true; + return false; +} + +static int +gl_hash_nx_add (gl_set_t set, const void *elt) +{ + size_t hashcode = + (set->hashcode_fn != NULL + ? set->hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t bucket = hashcode % set->table_size; + gl_setelement_equals_fn equals = set->base.equals_fn; + + /* Look for a match in the hash bucket. */ + { + gl_list_node_t node; + + for (node = (gl_list_node_t) set->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + return 0; + } + + /* Allocate a new node. */ + gl_list_node_t node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (node == NULL) + return -1; + + node->value = elt; + node->h.hashcode = hashcode; + + /* Add node to the hash table. */ + node->h.hash_next = set->table[bucket]; + set->table[bucket] = &node->h; + + /* Add node to the set. */ + set->count++; + + hash_resize_after_add (set); + + return 1; +} + +static bool +gl_hash_remove (gl_set_t set, const void *elt) +{ + size_t hashcode = + (set->hashcode_fn != NULL + ? set->hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t bucket = hashcode % set->table_size; + gl_setelement_equals_fn equals = set->base.equals_fn; + + /* Look for the first match in the hash bucket. */ + gl_list_node_t *nodep; + + for (nodep = (gl_list_node_t *) &set->table[bucket]; + *nodep != NULL; + nodep = (gl_list_node_t *) &(*nodep)->h.hash_next) + { + gl_list_node_t node = *nodep; + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + { + /* Remove node from the hash table. */ + *nodep = (gl_list_node_t) node->h.hash_next; + + /* Remove node from the set. */ + set->count--; + + if (set->base.dispose_fn != NULL) + set->base.dispose_fn (node->value); + free (node); + return true; + } + } + + return false; +} + +static void +gl_hash_free (gl_set_t set) +{ + if (set->count > 0) + { + gl_setelement_dispose_fn dispose = set->base.dispose_fn; + struct gl_hash_entry **table = set->table; + size_t i; + + for (i = set->table_size; i > 0; ) + { + gl_hash_entry_t node = table[--i]; + + while (node != NULL) + { + gl_hash_entry_t next = node->hash_next; + + /* Free the entry. */ + if (dispose != NULL) + dispose (((gl_list_node_t) node)->value); + free (node); + + node = next; + } + } + } + + free (set->table); + free (set); +} + +/* ---------------------- gl_set_iterator_t Data Type ---------------------- */ + +/* Here we iterate through the hash buckets. Therefore the order in which the + elements are returned is unpredictable. */ + +static gl_set_iterator_t +gl_hash_iterator (gl_set_t set) +{ + gl_set_iterator_t result; + + result.vtable = set->base.vtable; + result.set = set; + result.p = NULL; /* runs through the nodes of a bucket */ + result.i = 0; /* index of the bucket that p points into + 1 */ + result.j = set->table_size; +#if defined GCC_LINT || defined lint + result.q = NULL; + result.count = 0; +#endif + + return result; +} + +static bool +gl_hash_iterator_next (gl_set_iterator_t *iterator, const void **eltp) +{ + if (iterator->p != NULL) + { + /* We're traversing a bucket. */ + gl_list_node_t node = (gl_list_node_t) iterator->p; + *eltp = node->value; + iterator->p = (gl_list_node_t) node->h.hash_next; + return true; + } + else + { + /* Find the next bucket that is not empty. */ + size_t j = iterator->j; + size_t i = iterator->i; + + if (i < j) + { + gl_hash_entry_t *table = iterator->set->table; + do + { + gl_list_node_t node = (gl_list_node_t) table[i++]; + if (node != NULL) + { + *eltp = node->value; + iterator->p = (gl_list_node_t) node->h.hash_next; + iterator->i = i; + return true; + } + } + while (i < j); + } + /* Here iterator->p is still NULL, and i == j. */ + iterator->i = j; + return false; + } +} + +static void +gl_hash_iterator_free (gl_set_iterator_t *iterator) +{ +} + + +const struct gl_set_implementation gl_hash_set_implementation = + { + gl_hash_nx_create_empty, + gl_hash_size, + gl_hash_search, + gl_hash_nx_add, + gl_hash_remove, + gl_hash_free, + gl_hash_iterator, + gl_hash_iterator_next, + gl_hash_iterator_free + }; diff --git a/gl/lib/gl_hash_set.h b/gl/lib/gl_hash_set.h new file mode 100644 index 00000000..b59aaa58 --- /dev/null +++ b/gl/lib/gl_hash_set.h @@ -0,0 +1,34 @@ +/* Set data type implemented by a hash table. + Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2018. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_HASH_SET_H +#define _GL_HASH_SET_H + +#include "gl_set.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_set_implementation gl_hash_set_implementation; +#define GL_HASH_SET &gl_hash_set_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_HASH_SET_H */ diff --git a/gl/lib/gl_linkedhash_list.c b/gl/lib/gl_linkedhash_list.c new file mode 100644 index 00000000..efe4996b --- /dev/null +++ b/gl/lib/gl_linkedhash_list.c @@ -0,0 +1,116 @@ +/* Sequential list data type implemented by a hash table with a linked list. + Copyright (C) 2006, 2008-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "gl_linkedhash_list.h" + +#include <stdint.h> /* for SIZE_MAX */ +#include <stdlib.h> + +#include "xsize.h" + +#ifndef uintptr_t +# define uintptr_t unsigned long +#endif + +#define WITH_HASHTABLE 1 + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Generic hash-table code. */ +#include "gl_anyhash1.h" + +/* Generic linked list code. */ +#include "gl_anylinked_list1.h" + +/* Generic hash-table code. */ +#define CONTAINER_T gl_list_t +#define CONTAINER_COUNT(list) (list)->count +#include "gl_anyhash2.h" + +/* Add a node to the hash table structure. */ +static void +add_to_bucket (gl_list_t list, gl_list_node_t node) +{ + size_t bucket = node->h.hashcode % list->table_size; + + node->h.hash_next = list->table[bucket]; + list->table[bucket] = &node->h; +} +/* Tell all compilers that the return value is 0. */ +#define add_to_bucket(list,node) ((add_to_bucket) (list, node), 0) + +/* Remove a node from the hash table structure. */ +static void +remove_from_bucket (gl_list_t list, gl_list_node_t node) +{ + size_t bucket = node->h.hashcode % list->table_size; + gl_hash_entry_t *p; + + for (p = &list->table[bucket]; ; p = &(*p)->hash_next) + { + if (*p == &node->h) + { + *p = node->h.hash_next; + break; + } + if (*p == NULL) + /* node is not in the right bucket. Did the hash codes + change inadvertently? */ + abort (); + } +} + +/* Generic linked list code. */ +#include "gl_anylinked_list2.h" + + +const struct gl_list_implementation gl_linkedhash_list_implementation = + { + gl_linked_nx_create_empty, + gl_linked_nx_create, + gl_linked_size, + gl_linked_node_value, + gl_linked_node_nx_set_value, + gl_linked_next_node, + gl_linked_previous_node, + gl_linked_get_at, + gl_linked_nx_set_at, + gl_linked_search_from_to, + gl_linked_indexof_from_to, + gl_linked_nx_add_first, + gl_linked_nx_add_last, + gl_linked_nx_add_before, + gl_linked_nx_add_after, + gl_linked_nx_add_at, + gl_linked_remove_node, + gl_linked_remove_at, + gl_linked_remove, + gl_linked_list_free, + gl_linked_iterator, + gl_linked_iterator_from_to, + gl_linked_iterator_next, + gl_linked_iterator_free, + gl_linked_sortedlist_search, + gl_linked_sortedlist_search_from_to, + gl_linked_sortedlist_indexof, + gl_linked_sortedlist_indexof_from_to, + gl_linked_sortedlist_nx_add, + gl_linked_sortedlist_remove + }; diff --git a/gl/lib/gl_linkedhash_list.h b/gl/lib/gl_linkedhash_list.h new file mode 100644 index 00000000..3477f32b --- /dev/null +++ b/gl/lib/gl_linkedhash_list.h @@ -0,0 +1,34 @@ +/* Sequential list data type implemented by a hash table with a linked list. + Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_LINKEDHASH_LIST_H +#define _GL_LINKEDHASH_LIST_H + +#include "gl_list.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_list_implementation gl_linkedhash_list_implementation; +#define GL_LINKEDHASH_LIST &gl_linkedhash_list_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_LINKEDHASH_LIST_H */ diff --git a/gl/lib/gl_list.c b/gl/lib/gl_list.c new file mode 100644 index 00000000..87932980 --- /dev/null +++ b/gl/lib/gl_list.c @@ -0,0 +1,3 @@ +#include <config.h> +#define GL_LIST_INLINE _GL_EXTERN_INLINE +#include "gl_list.h" diff --git a/gl/lib/gl_list.h b/gl/lib/gl_list.h new file mode 100644 index 00000000..5f2cade2 --- /dev/null +++ b/gl/lib/gl_list.h @@ -0,0 +1,843 @@ +/* Abstract sequential list data type. -*- coding: utf-8 -*- + Copyright (C) 2006-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_LIST_H +#define _GL_LIST_H + +#include <stdbool.h> +#include <stddef.h> + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef GL_LIST_INLINE +# define GL_LIST_INLINE _GL_INLINE +#endif + +#ifdef __cplusplus +extern "C" { +#endif + + +/* gl_list is an abstract list data type. It can contain any number of + objects ('void *' or 'const void *' pointers) in any given order. + Duplicates are allowed, but can optionally be forbidden. + + There are several implementations of this list datatype, optimized for + different operations or for memory. You can start using the simplest list + implementation, GL_ARRAY_LIST, and switch to a different implementation + later, when you realize which operations are performed the most frequently. + The API of the different implementations is exactly the same; when + switching to a different implementation, you only have to change the + gl_list_create call. + + The implementations are: + GL_ARRAY_LIST a growable array + GL_CARRAY_LIST a growable circular array + GL_LINKED_LIST a linked list + GL_AVLTREE_LIST a binary tree (AVL tree) + GL_RBTREE_LIST a binary tree (red-black tree) + GL_LINKEDHASH_LIST a hash table with a linked list + GL_AVLTREEHASH_LIST a hash table with a binary tree (AVL tree) + GL_RBTREEHASH_LIST a hash table with a binary tree (red-black tree) + + The memory consumption is asymptotically the same: O(1) for every object + in the list. When looking more closely at the average memory consumed + for an object, GL_ARRAY_LIST is the most compact representation, and + GL_LINKEDHASH_LIST and GL_TREEHASH_LIST need more memory. + + The guaranteed average performance of the operations is, for a list of + n elements: + + Operation ARRAY LINKED TREE LINKEDHASH TREEHASH + CARRAY with|without with|without + duplicates duplicates + + gl_list_size O(1) O(1) O(1) O(1) O(1) + gl_list_node_value O(1) O(1) O(1) O(1) O(1) + gl_list_node_set_value O(1) O(1) O(1) O(1) O((log n)²)/O(1) + gl_list_next_node O(1) O(1) O(log n) O(1) O(log n) + gl_list_previous_node O(1) O(1) O(log n) O(1) O(log n) + gl_list_get_at O(1) O(n) O(log n) O(n) O(log n) + gl_list_set_at O(1) O(n) O(log n) O(n) O((log n)²)/O(log n) + gl_list_search O(n) O(n) O(n) O(n)/O(1) O(log n)/O(1) + gl_list_search_from O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) + gl_list_search_from_to O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) + gl_list_indexof O(n) O(n) O(n) O(n) O(log n) + gl_list_indexof_from O(n) O(n) O(n) O(n) O((log n)²)/O(log n) + gl_list_indexof_from_to O(n) O(n) O(n) O(n) O((log n)²)/O(log n) + gl_list_add_first O(n)/O(1) O(1) O(log n) O(1) O((log n)²)/O(log n) + gl_list_add_last O(1) O(1) O(log n) O(1) O((log n)²)/O(log n) + gl_list_add_before O(n) O(1) O(log n) O(1) O((log n)²)/O(log n) + gl_list_add_after O(n) O(1) O(log n) O(1) O((log n)²)/O(log n) + gl_list_add_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) + gl_list_remove_node O(n) O(1) O(log n) O(n)/O(1) O((log n)²)/O(log n) + gl_list_remove_at O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) + gl_list_remove O(n) O(n) O(n) O(n)/O(1) O((log n)²)/O(log n) + gl_list_iterator O(1) O(1) O(log n) O(1) O(log n) + gl_list_iterator_from_to O(1) O(n) O(log n) O(n) O(log n) + gl_list_iterator_next O(1) O(1) O(log n) O(1) O(log n) + gl_sortedlist_search O(log n) O(n) O(log n) O(n) O(log n) + gl_sortedlist_search_from O(log n) O(n) O(log n) O(n) O(log n) + gl_sortedlist_indexof O(log n) O(n) O(log n) O(n) O(log n) + gl_sortedlist_indexof_fro O(log n) O(n) O(log n) O(n) O(log n) + gl_sortedlist_add O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) + gl_sortedlist_remove O(n) O(n) O(log n) O(n) O((log n)²)/O(log n) + */ + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Type of function used to compare two elements. + NULL denotes pointer comparison. */ +typedef bool (*gl_listelement_equals_fn) (const void *elt1, const void *elt2); + +/* Type of function used to compute a hash code. + NULL denotes a function that depends only on the pointer itself. */ +typedef size_t (*gl_listelement_hashcode_fn) (const void *elt); + +/* Type of function used to dispose an element once it's removed from a list. + NULL denotes a no-op. */ +typedef void (*gl_listelement_dispose_fn) (const void *elt); + +struct gl_list_impl; +/* Type representing an entire list. */ +typedef struct gl_list_impl * gl_list_t; + +struct gl_list_node_impl; +/* Type representing the position of an element in the list, in a way that + is more adapted to the list implementation than a plain index. + Note: It is invalidated by insertions and removals! */ +typedef struct gl_list_node_impl * gl_list_node_t; + +struct gl_list_implementation; +/* Type representing a list datatype implementation. */ +typedef const struct gl_list_implementation * gl_list_implementation_t; + +#if 0 /* Unless otherwise specified, these are defined inline below. */ + +/* Create an empty list. + IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST, + GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST, + GL_RBTREEHASH_LIST. + EQUALS_FN is an element comparison function or NULL. + HASHCODE_FN is an element hash code function or NULL. + DISPOSE_FN is an element disposal function or NULL. + ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in + the list. The implementation may verify this at runtime. */ +/* declared in gl_xlist.h */ +extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_t gl_list_nx_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates); + +/* Create a list with given contents. + IMPLEMENTATION is one of GL_ARRAY_LIST, GL_CARRAY_LIST, GL_LINKED_LIST, + GL_AVLTREE_LIST, GL_RBTREE_LIST, GL_LINKEDHASH_LIST, GL_AVLTREEHASH_LIST, + GL_RBTREEHASH_LIST. + EQUALS_FN is an element comparison function or NULL. + HASHCODE_FN is an element hash code function or NULL. + DISPOSE_FN is an element disposal function or NULL. + ALLOW_DUPLICATES is false if duplicate elements shall not be allowed in + the list. The implementation may verify this at runtime. + COUNT is the number of initial elements. + CONTENTS[0..COUNT-1] is the initial contents. */ +/* declared in gl_xlist.h */ +extern gl_list_t gl_list_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_t gl_list_nx_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents); + +/* Return the current number of elements in a list. */ +extern size_t gl_list_size (gl_list_t list); + +/* Return the element value represented by a list node. */ +extern const void * gl_list_node_value (gl_list_t list, gl_list_node_t node); + +/* Replace the element value represented by a list node. */ +/* declared in gl_xlist.h */ +extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node, + const void *elt); +/* Likewise. Return 0 upon success, -1 upon out-of-memory. */ +extern int gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Return the node immediately after the given node in the list, or NULL + if the given node is the last (rightmost) one in the list. */ +extern gl_list_node_t gl_list_next_node (gl_list_t list, gl_list_node_t node); + +/* Return the node immediately before the given node in the list, or NULL + if the given node is the first (leftmost) one in the list. */ +extern gl_list_node_t gl_list_previous_node (gl_list_t list, gl_list_node_t node); + +/* Return the element at a given position in the list. + POSITION must be >= 0 and < gl_list_size (list). */ +extern const void * gl_list_get_at (gl_list_t list, size_t position); + +/* Replace the element at a given position in the list. + POSITION must be >= 0 and < gl_list_size (list). + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position, + const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_set_at (gl_list_t list, size_t position, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Search whether an element is already in the list. + Return its node if found, or NULL if not present in the list. */ +extern gl_list_node_t gl_list_search (gl_list_t list, const void *elt); + +/* Search whether an element is already in the list, + at a position >= START_INDEX. + Return its node if found, or NULL if not present in the list. */ +extern gl_list_node_t gl_list_search_from (gl_list_t list, size_t start_index, + const void *elt); + +/* Search whether an element is already in the list, + at a position >= START_INDEX and < END_INDEX. + Return its node if found, or NULL if not present in the list. */ +extern gl_list_node_t gl_list_search_from_to (gl_list_t list, + size_t start_index, + size_t end_index, + const void *elt); + +/* Search whether an element is already in the list. + Return its position if found, or (size_t)(-1) if not present in the list. */ +extern size_t gl_list_indexof (gl_list_t list, const void *elt); + +/* Search whether an element is already in the list, + at a position >= START_INDEX. + Return its position if found, or (size_t)(-1) if not present in the list. */ +extern size_t gl_list_indexof_from (gl_list_t list, size_t start_index, + const void *elt); + +/* Search whether an element is already in the list, + at a position >= START_INDEX and < END_INDEX. + Return its position if found, or (size_t)(-1) if not present in the list. */ +extern size_t gl_list_indexof_from_to (gl_list_t list, + size_t start_index, size_t end_index, + const void *elt); + +/* Add an element as the first element of the list. + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_first (gl_list_t list, const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Add an element as the last element of the list. + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_last (gl_list_t list, const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Add an element before a given element node of the list. + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node, + const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_before (gl_list_t list, + gl_list_node_t node, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Add an element after a given element node of the list. + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node, + const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Add an element at a given position in the list. + POSITION must be >= 0 and <= gl_list_size (list). */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position, + const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_list_nx_add_at (gl_list_t list, size_t position, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Remove an element from the list. + Return true. */ +extern bool gl_list_remove_node (gl_list_t list, gl_list_node_t node); + +/* Remove an element at a given position from the list. + POSITION must be >= 0 and < gl_list_size (list). + Return true. */ +extern bool gl_list_remove_at (gl_list_t list, size_t position); + +/* Search and remove an element from the list. + Return true if it was found and removed. */ +extern bool gl_list_remove (gl_list_t list, const void *elt); + +/* Free an entire list. + (But this call does not free the elements of the list. It only invokes + the DISPOSE_FN on each of the elements of the list, and only if the list + is not a sublist.) */ +extern void gl_list_free (gl_list_t list); + +#endif /* End of inline and gl_xlist.h-defined functions. */ + +/* --------------------- gl_list_iterator_t Data Type --------------------- */ + +/* Functions for iterating through a list. */ + +/* Type of an iterator that traverses a list. + This is a fixed-size struct, so that creation of an iterator doesn't need + memory allocation on the heap. */ +typedef struct +{ + /* For fast dispatch of gl_list_iterator_next. */ + const struct gl_list_implementation *vtable; + /* For detecting whether the last returned element was removed. */ + gl_list_t list; + size_t count; + /* Other, implementation-private fields. */ + void *p; void *q; + size_t i; size_t j; +} gl_list_iterator_t; + +#if 0 /* These are defined inline below. */ + +/* Create an iterator traversing a list. + The list contents must not be modified while the iterator is in use, + except for replacing or removing the last returned element. */ +extern gl_list_iterator_t gl_list_iterator (gl_list_t list); + +/* Create an iterator traversing the element with indices i, + start_index <= i < end_index, of a list. + The list contents must not be modified while the iterator is in use, + except for replacing or removing the last returned element. */ +extern gl_list_iterator_t gl_list_iterator_from_to (gl_list_t list, + size_t start_index, + size_t end_index); + +/* If there is a next element, store the next element in *ELTP, store its + node in *NODEP if NODEP is non-NULL, advance the iterator and return true. + Otherwise, return false. */ +extern bool gl_list_iterator_next (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep); + +/* Free an iterator. */ +extern void gl_list_iterator_free (gl_list_iterator_t *iterator); + +#endif /* End of inline functions. */ + +/* ---------------------- Sorted gl_list_t Data Type ---------------------- */ + +/* The following functions are for lists without duplicates where the + order is given by a sort criterion. */ + +/* Type of function used to compare two elements. Same as for qsort(). + NULL denotes pointer comparison. */ +typedef int (*gl_listelement_compar_fn) (const void *elt1, const void *elt2); + +#if 0 /* Unless otherwise specified, these are defined inline below. */ + +/* Search whether an element is already in the list. + The list is assumed to be sorted with COMPAR. + Return its node if found, or NULL if not present in the list. + If the list contains several copies of ELT, the node of the leftmost one is + returned. */ +extern gl_list_node_t gl_sortedlist_search (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + +/* Search whether an element is already in the list. + The list is assumed to be sorted with COMPAR. + Only list elements with indices >= START_INDEX and < END_INDEX are + considered; the implementation uses these bounds to minimize the number + of COMPAR invocations. + Return its node if found, or NULL if not present in the list. + If the list contains several copies of ELT, the node of the leftmost one is + returned. */ +extern gl_list_node_t gl_sortedlist_search_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t start_index, + size_t end_index, + const void *elt); + +/* Search whether an element is already in the list. + The list is assumed to be sorted with COMPAR. + Return its position if found, or (size_t)(-1) if not present in the list. + If the list contains several copies of ELT, the position of the leftmost one + is returned. */ +extern size_t gl_sortedlist_indexof (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + +/* Search whether an element is already in the list. + The list is assumed to be sorted with COMPAR. + Only list elements with indices >= START_INDEX and < END_INDEX are + considered; the implementation uses these bounds to minimize the number + of COMPAR invocations. + Return its position if found, or (size_t)(-1) if not present in the list. + If the list contains several copies of ELT, the position of the leftmost one + is returned. */ +extern size_t gl_sortedlist_indexof_from_to (gl_list_t list, + gl_listelement_compar_fn compar, + size_t start_index, + size_t end_index, + const void *elt); + +/* Add an element at the appropriate position in the list. + The list is assumed to be sorted with COMPAR. + Return its node. */ +/* declared in gl_xlist.h */ +extern gl_list_node_t gl_sortedlist_add (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_list_node_t gl_sortedlist_nx_add (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Search and remove an element from the list. + The list is assumed to be sorted with COMPAR. + Return true if it was found and removed. + If the list contains several copies of ELT, only the leftmost one is + removed. */ +extern bool gl_sortedlist_remove (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + +#endif /* End of inline and gl_xlist.h-defined functions. */ + +/* ------------------------ Implementation Details ------------------------ */ + +struct gl_list_implementation +{ + /* gl_list_t functions. */ + gl_list_t (*nx_create_empty) (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates); + gl_list_t (*nx_create) (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents); + size_t (*size) (gl_list_t list); + const void * (*node_value) (gl_list_t list, gl_list_node_t node); + int (*node_nx_set_value) (gl_list_t list, gl_list_node_t node, + const void *elt); + gl_list_node_t (*next_node) (gl_list_t list, gl_list_node_t node); + gl_list_node_t (*previous_node) (gl_list_t list, gl_list_node_t node); + const void * (*get_at) (gl_list_t list, size_t position); + gl_list_node_t (*nx_set_at) (gl_list_t list, size_t position, + const void *elt); + gl_list_node_t (*search_from_to) (gl_list_t list, size_t start_index, + size_t end_index, const void *elt); + size_t (*indexof_from_to) (gl_list_t list, size_t start_index, + size_t end_index, const void *elt); + gl_list_node_t (*nx_add_first) (gl_list_t list, const void *elt); + gl_list_node_t (*nx_add_last) (gl_list_t list, const void *elt); + gl_list_node_t (*nx_add_before) (gl_list_t list, gl_list_node_t node, + const void *elt); + gl_list_node_t (*nx_add_after) (gl_list_t list, gl_list_node_t node, + const void *elt); + gl_list_node_t (*nx_add_at) (gl_list_t list, size_t position, + const void *elt); + bool (*remove_node) (gl_list_t list, gl_list_node_t node); + bool (*remove_at) (gl_list_t list, size_t position); + bool (*remove_elt) (gl_list_t list, const void *elt); + void (*list_free) (gl_list_t list); + /* gl_list_iterator_t functions. */ + gl_list_iterator_t (*iterator) (gl_list_t list); + gl_list_iterator_t (*iterator_from_to) (gl_list_t list, + size_t start_index, + size_t end_index); + bool (*iterator_next) (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep); + void (*iterator_free) (gl_list_iterator_t *iterator); + /* Sorted gl_list_t functions. */ + gl_list_node_t (*sortedlist_search) (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + gl_list_node_t (*sortedlist_search_from_to) (gl_list_t list, + gl_listelement_compar_fn compar, + size_t start_index, + size_t end_index, + const void *elt); + size_t (*sortedlist_indexof) (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + size_t (*sortedlist_indexof_from_to) (gl_list_t list, + gl_listelement_compar_fn compar, + size_t start_index, size_t end_index, + const void *elt); + gl_list_node_t (*sortedlist_nx_add) (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); + bool (*sortedlist_remove) (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); +}; + +struct gl_list_impl_base +{ + const struct gl_list_implementation *vtable; + gl_listelement_equals_fn equals_fn; + gl_listelement_hashcode_fn hashcode_fn; + gl_listelement_dispose_fn dispose_fn; + bool allow_duplicates; +}; + +/* Define all functions of this file as accesses to the + struct gl_list_implementation. */ + +GL_LIST_INLINE gl_list_t +gl_list_nx_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates) +{ + return implementation->nx_create_empty (implementation, equals_fn, + hashcode_fn, dispose_fn, + allow_duplicates); +} + +GL_LIST_INLINE gl_list_t +gl_list_nx_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents) +{ + return implementation->nx_create (implementation, equals_fn, hashcode_fn, + dispose_fn, allow_duplicates, count, + contents); +} + +GL_LIST_INLINE size_t +gl_list_size (gl_list_t list) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->size (list); +} + +GL_LIST_INLINE const void * +gl_list_node_value (gl_list_t list, gl_list_node_t node) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->node_value (list, node); +} + +GL_LIST_INLINE int +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_node_nx_set_value (gl_list_t list, gl_list_node_t node, + const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->node_nx_set_value (list, node, elt); +} + +GL_LIST_INLINE gl_list_node_t +gl_list_next_node (gl_list_t list, gl_list_node_t node) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->next_node (list, node); +} + +GL_LIST_INLINE gl_list_node_t +gl_list_previous_node (gl_list_t list, gl_list_node_t node) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->previous_node (list, node); +} + +GL_LIST_INLINE const void * +gl_list_get_at (gl_list_t list, size_t position) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->get_at (list, position); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_set_at (gl_list_t list, size_t position, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_set_at (list, position, elt); +} + +GL_LIST_INLINE gl_list_node_t +gl_list_search (gl_list_t list, const void *elt) +{ + size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); + return ((const struct gl_list_impl_base *) list)->vtable + ->search_from_to (list, 0, size, elt); +} + +GL_LIST_INLINE gl_list_node_t +gl_list_search_from (gl_list_t list, size_t start_index, const void *elt) +{ + size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); + return ((const struct gl_list_impl_base *) list)->vtable + ->search_from_to (list, start_index, size, elt); +} + +GL_LIST_INLINE gl_list_node_t +gl_list_search_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->search_from_to (list, start_index, end_index, elt); +} + +GL_LIST_INLINE size_t +gl_list_indexof (gl_list_t list, const void *elt) +{ + size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); + return ((const struct gl_list_impl_base *) list)->vtable + ->indexof_from_to (list, 0, size, elt); +} + +GL_LIST_INLINE size_t +gl_list_indexof_from (gl_list_t list, size_t start_index, const void *elt) +{ + size_t size = ((const struct gl_list_impl_base *) list)->vtable->size (list); + return ((const struct gl_list_impl_base *) list)->vtable + ->indexof_from_to (list, start_index, size, elt); +} + +GL_LIST_INLINE size_t +gl_list_indexof_from_to (gl_list_t list, size_t start_index, size_t end_index, + const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->indexof_from_to (list, start_index, end_index, elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_add_first (gl_list_t list, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_add_first (list, elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_add_last (gl_list_t list, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_add_last (list, elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_add_before (list, node, elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_add_after (list, node, elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_list_nx_add_at (gl_list_t list, size_t position, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->nx_add_at (list, position, elt); +} + +GL_LIST_INLINE bool +gl_list_remove_node (gl_list_t list, gl_list_node_t node) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->remove_node (list, node); +} + +GL_LIST_INLINE bool +gl_list_remove_at (gl_list_t list, size_t position) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->remove_at (list, position); +} + +GL_LIST_INLINE bool +gl_list_remove (gl_list_t list, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->remove_elt (list, elt); +} + +GL_LIST_INLINE void +gl_list_free (gl_list_t list) +{ + ((const struct gl_list_impl_base *) list)->vtable->list_free (list); +} + +GL_LIST_INLINE gl_list_iterator_t +gl_list_iterator (gl_list_t list) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->iterator (list); +} + +GL_LIST_INLINE gl_list_iterator_t +gl_list_iterator_from_to (gl_list_t list, size_t start_index, size_t end_index) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->iterator_from_to (list, start_index, end_index); +} + +GL_LIST_INLINE bool +gl_list_iterator_next (gl_list_iterator_t *iterator, + const void **eltp, gl_list_node_t *nodep) +{ + return iterator->vtable->iterator_next (iterator, eltp, nodep); +} + +GL_LIST_INLINE void +gl_list_iterator_free (gl_list_iterator_t *iterator) +{ + iterator->vtable->iterator_free (iterator); +} + +GL_LIST_INLINE gl_list_node_t +gl_sortedlist_search (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_search (list, compar, elt); +} + +GL_LIST_INLINE gl_list_node_t +gl_sortedlist_search_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_search_from_to (list, compar, start_index, end_index, + elt); +} + +GL_LIST_INLINE size_t +gl_sortedlist_indexof (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_indexof (list, compar, elt); +} + +GL_LIST_INLINE size_t +gl_sortedlist_indexof_from_to (gl_list_t list, gl_listelement_compar_fn compar, size_t start_index, size_t end_index, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_indexof_from_to (list, compar, start_index, end_index, + elt); +} + +GL_LIST_INLINE gl_list_node_t +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_sortedlist_nx_add (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_nx_add (list, compar, elt); +} + +GL_LIST_INLINE bool +gl_sortedlist_remove (gl_list_t list, gl_listelement_compar_fn compar, const void *elt) +{ + return ((const struct gl_list_impl_base *) list)->vtable + ->sortedlist_remove (list, compar, elt); +} + +#ifdef __cplusplus +} +#endif + +_GL_INLINE_HEADER_END + +#endif /* _GL_LIST_H */ diff --git a/gl/lib/gl_map.c b/gl/lib/gl_map.c new file mode 100644 index 00000000..758a65f3 --- /dev/null +++ b/gl/lib/gl_map.c @@ -0,0 +1,3 @@ +#include <config.h> +#define GL_MAP_INLINE _GL_EXTERN_INLINE +#include "gl_map.h" diff --git a/gl/lib/gl_map.h b/gl/lib/gl_map.h new file mode 100644 index 00000000..02a3ac37 --- /dev/null +++ b/gl/lib/gl_map.h @@ -0,0 +1,382 @@ +/* Abstract map data type. + Copyright (C) 2006-2007, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2018. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_MAP_H +#define _GL_MAP_H + +#include <stdbool.h> +#include <stddef.h> + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef GL_MAP_INLINE +# define GL_MAP_INLINE _GL_INLINE +#endif + +#ifdef __cplusplus +extern "C" { +#endif + + +/* gl_map is an abstract map data type. It can contain any number of + (key, value) pairs, where + - keys and values are objects ('void *' or 'const void *' pointers), + - There are no (key, value1) and (key, value2) pairs with the same key + (in the sense of a given comparator function). + + There are several implementations of this map datatype, optimized for + different operations or for memory. You can start using the simplest map + implementation, GL_ARRAY_MAP, and switch to a different implementation + later, when you realize which operations are performed the most frequently. + The API of the different implementations is exactly the same; when switching + to a different implementation, you only have to change the gl_map_create + call. + + The implementations are: + GL_ARRAY_MAP a growable array + GL_LINKEDHASH_MAP a hash table with a linked list + GL_HASH_MAP a hash table + + The memory consumption is asymptotically the same: O(1) for every pair + in the map. When looking more closely at the average memory consumed + for an object, GL_ARRAY_MAP is the most compact representation, then comes + GL_HASH_MAP, and GL_LINKEDHASH_MAP needs the most memory. + + The guaranteed average performance of the operations is, for a map of + n pairs: + + Operation ARRAY LINKEDHASH + HASH + + gl_map_size O(1) O(1) + gl_map_get O(n) O(1) + gl_map_put O(n) O(1) + gl_map_remove O(n) O(1) + gl_map_search O(n) O(1) + gl_map_iterator O(1) O(1) + gl_map_iterator_next O(1) O(1) + */ + +/* --------------------------- gl_map_t Data Type --------------------------- */ + +/* Type of function used to compare two keys. + NULL denotes pointer comparison. */ +typedef bool (*gl_mapkey_equals_fn) (const void *key1, const void *key2); + +/* Type of function used to compute a hash code. + NULL denotes a function that depends only on the pointer itself. */ +typedef size_t (*gl_mapkey_hashcode_fn) (const void *key); + +#ifndef _GL_MAP_DISPOSE_FNS_DEFINED + +/* Type of function used to dispose a key once a (key, value) pair is removed + from a map. NULL denotes a no-op. */ +typedef void (*gl_mapkey_dispose_fn) (const void *key); + +/* Type of function used to dispose a value once a (key, value) pair is removed + from a map. NULL denotes a no-op. */ +typedef void (*gl_mapvalue_dispose_fn) (const void *value); + +# define _GL_MAP_DISPOSE_FNS_DEFINED 1 +#endif + +struct gl_map_impl; +/* Type representing an entire map. */ +typedef struct gl_map_impl * gl_map_t; + +struct gl_map_implementation; +/* Type representing a map datatype implementation. */ +typedef const struct gl_map_implementation * gl_map_implementation_t; + +#if 0 /* Unless otherwise specified, these are defined inline below. */ + +/* Create an empty map. + IMPLEMENTATION is one of GL_ARRAY_MAP, GL_LINKEDHASH_MAP, GL_HASH_MAP. + EQUALS_FN is a key comparison function or NULL. + HASHCODE_FN is a key hash code function or NULL. + KDISPOSE_FN is a key disposal function or NULL. + VDISPOSE_FN is a value disposal function or NULL. */ +/* declared in gl_xmap.h */ +extern gl_map_t gl_map_create_empty (gl_map_implementation_t implementation, + gl_mapkey_equals_fn equals_fn, + gl_mapkey_hashcode_fn hashcode_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_map_t gl_map_nx_create_empty (gl_map_implementation_t implementation, + gl_mapkey_equals_fn equals_fn, + gl_mapkey_hashcode_fn hashcode_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn); + +/* Return the current number of pairs in a map. */ +extern size_t gl_map_size (gl_map_t map); + +/* Search whether a pair with the given key is already in the map. + Return the value if found, or NULL if not present in the map. */ +extern const void * gl_map_get (gl_map_t map, const void *key); + +/* Search whether a pair with the given key is already in the map. + Return true and set *VALUEP to the value if found. + Return false if not present in the map. */ +extern bool gl_map_search (gl_map_t map, const void *key, const void **valuep); + +/* Add a pair to a map. + Return true if a pair with the given key was not already in the map and so + this pair was added. + Return false if a pair with the given key was already in the map and only + its value was replaced. */ +/* declared in gl_xmap.h */ +extern bool gl_map_put (gl_map_t map, const void *key, const void *value); +/* Likewise. Return -1 upon out-of-memory. */ +extern int gl_map_nx_put (gl_map_t map, const void *key, const void *value) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Add a pair to a map and retrieve the previous value. + Return true if a pair with the given key was not already in the map and so + this pair was added. + Return false and set *OLDVALUEP to the previous value, if a pair with the + given key was already in the map and only its value was replaced. */ +/* declared in gl_xmap.h */ +extern bool gl_map_getput (gl_map_t map, const void *key, const void *value, + const void **oldvaluep); +/* Likewise. Return -1 upon out-of-memory. */ +extern int gl_map_nx_getput (gl_map_t map, const void *key, const void *value, + const void **oldvaluep) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Remove a pair from a map. + Return true if the key was found and its pair removed. + Return false otherwise. */ +extern bool gl_map_remove (gl_map_t map, const void *key); + +/* Remove a pair from a map and retrieve the previous value. + Return true and set *OLDVALUEP to the previous value, if the key was found + and its pair removed. + Return false otherwise. */ +extern bool gl_map_getremove (gl_map_t map, const void *key, + const void **oldvaluep); + +/* Free an entire map. + (But this call does not free the keys and values of the pairs in the map. + It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value + of the pairs in the map.) */ +extern void gl_map_free (gl_map_t map); + +#endif /* End of inline and gl_xmap.h-defined functions. */ + +/* ---------------------- gl_map_iterator_t Data Type ---------------------- */ + +/* Functions for iterating through a map. + Note: Iterating through a map of type GL_HASH_MAP returns the pairs in an + unpredictable order. If you need a predictable order, use GL_LINKEDHASH_MAP + instead of GL_HASH_MAP. */ + +/* Type of an iterator that traverses a map. + This is a fixed-size struct, so that creation of an iterator doesn't need + memory allocation on the heap. */ +typedef struct +{ + /* For fast dispatch of gl_map_iterator_next. */ + const struct gl_map_implementation *vtable; + /* For detecting whether the last returned pair was removed. */ + gl_map_t map; + size_t count; + /* Other, implementation-private fields. */ + void *p; void *q; + size_t i; size_t j; +} gl_map_iterator_t; + +#if 0 /* These are defined inline below. */ + +/* Create an iterator traversing a map. + The map's contents must not be modified while the iterator is in use, + except for modifying the value of the last returned key or removing the + last returned pair. */ +extern gl_map_iterator_t gl_map_iterator (gl_map_t map); + +/* If there is a next pair, store the next pair in *KEYP and *VALUEP, advance + the iterator, and return true. Otherwise, return false. */ +extern bool gl_map_iterator_next (gl_map_iterator_t *iterator, + const void **keyp, const void **valuep); + +/* Free an iterator. */ +extern void gl_map_iterator_free (gl_map_iterator_t *iterator); + +#endif /* End of inline functions. */ + +/* ------------------------- Implementation Details ------------------------- */ + +struct gl_map_implementation +{ + /* gl_map_t functions. */ + gl_map_t (*nx_create_empty) (gl_map_implementation_t implementation, + gl_mapkey_equals_fn equals_fn, + gl_mapkey_hashcode_fn hashcode_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn); + size_t (*size) (gl_map_t map); + bool (*search) (gl_map_t map, const void *key, const void **valuep); + int (*nx_getput) (gl_map_t map, const void *key, const void *value, + const void **oldvaluep); + bool (*getremove) (gl_map_t map, const void *key, const void **oldvaluep); + void (*map_free) (gl_map_t map); + /* gl_map_iterator_t functions. */ + gl_map_iterator_t (*iterator) (gl_map_t map); + bool (*iterator_next) (gl_map_iterator_t *iterator, + const void **keyp, const void **valuep); + void (*iterator_free) (gl_map_iterator_t *iterator); +}; + +struct gl_map_impl_base +{ + const struct gl_map_implementation *vtable; + gl_mapkey_equals_fn equals_fn; + gl_mapkey_dispose_fn kdispose_fn; + gl_mapvalue_dispose_fn vdispose_fn; +}; + +/* Define most functions of this file as accesses to the + struct gl_map_implementation. */ + +GL_MAP_INLINE gl_map_t +gl_map_nx_create_empty (gl_map_implementation_t implementation, + gl_mapkey_equals_fn equals_fn, + gl_mapkey_hashcode_fn hashcode_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn) +{ + return implementation->nx_create_empty (implementation, + equals_fn, hashcode_fn, + kdispose_fn, vdispose_fn); +} + +GL_MAP_INLINE size_t +gl_map_size (gl_map_t map) +{ + return ((const struct gl_map_impl_base *) map)->vtable->size (map); +} + +GL_MAP_INLINE bool +gl_map_search (gl_map_t map, const void *key, const void **valuep) +{ + return ((const struct gl_map_impl_base *) map)->vtable + ->search (map, key, valuep); +} + +GL_MAP_INLINE int +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_map_nx_getput (gl_map_t map, const void *key, const void *value, + const void **oldvaluep) +{ + return ((const struct gl_map_impl_base *) map)->vtable + ->nx_getput (map, key, value, oldvaluep); +} + +GL_MAP_INLINE bool +gl_map_getremove (gl_map_t map, const void *key, const void **oldvaluep) +{ + return ((const struct gl_map_impl_base *) map)->vtable + ->getremove (map, key, oldvaluep); +} + +GL_MAP_INLINE void +gl_map_free (gl_map_t map) +{ + ((const struct gl_map_impl_base *) map)->vtable->map_free (map); +} + +GL_MAP_INLINE gl_map_iterator_t +gl_map_iterator (gl_map_t map) +{ + return ((const struct gl_map_impl_base *) map)->vtable->iterator (map); +} + +GL_MAP_INLINE bool +gl_map_iterator_next (gl_map_iterator_t *iterator, + const void **keyp, const void **valuep) +{ + return iterator->vtable->iterator_next (iterator, keyp, valuep); +} + +GL_MAP_INLINE void +gl_map_iterator_free (gl_map_iterator_t *iterator) +{ + iterator->vtable->iterator_free (iterator); +} + +/* Define the convenience functions, that is, the functions that are independent + of the implementation. */ + +GL_MAP_INLINE const void * +gl_map_get (gl_map_t map, const void *key) +{ + const void *value = NULL; + gl_map_search (map, key, &value); + return value; +} + +GL_MAP_INLINE int +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_map_nx_put (gl_map_t map, const void *key, const void *value) +{ + const void *oldvalue; + int result = gl_map_nx_getput (map, key, value, &oldvalue); + if (result == 0) + { + gl_mapvalue_dispose_fn vdispose_fn = + ((const struct gl_map_impl_base *) map)->vdispose_fn; + if (vdispose_fn != NULL) + vdispose_fn (oldvalue); + } + return result; +} + +GL_MAP_INLINE bool +gl_map_remove (gl_map_t map, const void *key) +{ + const void *oldvalue; + bool result = gl_map_getremove (map, key, &oldvalue); + if (result) + { + gl_mapvalue_dispose_fn vdispose_fn = + ((const struct gl_map_impl_base *) map)->vdispose_fn; + if (vdispose_fn != NULL) + vdispose_fn (oldvalue); + } + return result; +} + +#ifdef __cplusplus +} +#endif + +_GL_INLINE_HEADER_END + +#endif /* _GL_MAP_H */ diff --git a/gl/lib/gl_rbtree_list.c b/gl/lib/gl_rbtree_list.c new file mode 100644 index 00000000..25d7c791 --- /dev/null +++ b/gl/lib/gl_rbtree_list.c @@ -0,0 +1,102 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006, 2008-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "gl_rbtree_list.h" + +#include <stdlib.h> + +/* -------------------------- gl_list_t Data Type -------------------------- */ + +/* Generic red-black tree code. */ +#include "gl_anyrbtree_list1.h" + +/* Generic binary tree code. */ +#include "gl_anytree_list1.h" + +/* Generic red-black tree code. */ +#include "gl_anyrbtree_list2.h" + +/* Generic binary tree code. */ +#include "gl_anytree_list2.h" + +/* For debugging. */ +static unsigned int +check_invariants (gl_list_node_t node, gl_list_node_t parent) +{ + unsigned int left_blackheight = + (node->left != NULL ? check_invariants (node->left, node) : 0); + unsigned int right_blackheight = + (node->right != NULL ? check_invariants (node->right, node) : 0); + + if (!(node->parent == parent)) + abort (); + if (!(node->branch_size + == (node->left != NULL ? node->left->branch_size : 0) + + 1 + (node->right != NULL ? node->right->branch_size : 0))) + abort (); + if (!(node->color == BLACK || node->color == RED)) + abort (); + if (parent == NULL && !(node->color == BLACK)) + abort (); + if (!(left_blackheight == right_blackheight)) + abort (); + + return left_blackheight + (node->color == BLACK ? 1 : 0); +} +void +gl_rbtree_list_check_invariants (gl_list_t list) +{ + if (list->root != NULL) + check_invariants (list->root, NULL); +} + +const struct gl_list_implementation gl_rbtree_list_implementation = + { + gl_tree_nx_create_empty, + gl_tree_nx_create, + gl_tree_size, + gl_tree_node_value, + gl_tree_node_nx_set_value, + gl_tree_next_node, + gl_tree_previous_node, + gl_tree_get_at, + gl_tree_nx_set_at, + gl_tree_search_from_to, + gl_tree_indexof_from_to, + gl_tree_nx_add_first, + gl_tree_nx_add_last, + gl_tree_nx_add_before, + gl_tree_nx_add_after, + gl_tree_nx_add_at, + gl_tree_remove_node, + gl_tree_remove_at, + gl_tree_remove, + gl_tree_list_free, + gl_tree_iterator, + gl_tree_iterator_from_to, + gl_tree_iterator_next, + gl_tree_iterator_free, + gl_tree_sortedlist_search, + gl_tree_sortedlist_search_from_to, + gl_tree_sortedlist_indexof, + gl_tree_sortedlist_indexof_from_to, + gl_tree_sortedlist_nx_add, + gl_tree_sortedlist_remove + }; diff --git a/gl/lib/gl_rbtree_list.h b/gl/lib/gl_rbtree_list.h new file mode 100644 index 00000000..a1d7d880 --- /dev/null +++ b/gl/lib/gl_rbtree_list.h @@ -0,0 +1,34 @@ +/* Sequential list data type implemented by a binary tree. + Copyright (C) 2006, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2006. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_RBTREE_LIST_H +#define _GL_RBTREE_LIST_H + +#include "gl_list.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_list_implementation gl_rbtree_list_implementation; +#define GL_RBTREE_LIST &gl_rbtree_list_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_RBTREE_LIST_H */ diff --git a/gl/lib/gl_set.c b/gl/lib/gl_set.c new file mode 100644 index 00000000..e00d2026 --- /dev/null +++ b/gl/lib/gl_set.c @@ -0,0 +1,3 @@ +#include <config.h> +#define GL_SET_INLINE _GL_EXTERN_INLINE +#include "gl_set.h" diff --git a/gl/lib/gl_set.h b/gl/lib/gl_set.h new file mode 100644 index 00000000..52a6cf2d --- /dev/null +++ b/gl/lib/gl_set.h @@ -0,0 +1,281 @@ +/* Abstract set data type. + Copyright (C) 2006-2007, 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2018. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_SET_H +#define _GL_SET_H + +#include <stdbool.h> +#include <stddef.h> + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef GL_SET_INLINE +# define GL_SET_INLINE _GL_INLINE +#endif + +#ifdef __cplusplus +extern "C" { +#endif + + +/* gl_set is an abstract set data type. It can contain any number of objects + ('void *' or 'const void *' pointers); the order does not matter. + Duplicates (in the sense of the comparator) are forbidden. + + There are several implementations of this set datatype, optimized for + different operations or for memory. You can start using the simplest set + implementation, GL_ARRAY_SET, and switch to a different implementation + later, when you realize which operations are performed the most frequently. + The API of the different implementations is exactly the same; when switching + to a different implementation, you only have to change the gl_set_create + call. + + The implementations are: + GL_ARRAY_SET a growable array + GL_LINKEDHASH_SET a hash table with a linked list + GL_HASH_SET a hash table + + The memory consumption is asymptotically the same: O(1) for every object + in the set. When looking more closely at the average memory consumed + for an object, GL_ARRAY_SET is the most compact representation, then comes + GL_HASH_SET, and GL_LINKEDHASH_SET needs the most memory. + + The guaranteed average performance of the operations is, for a set of + n elements: + + Operation ARRAY LINKEDHASH + HASH + + gl_set_size O(1) O(1) + gl_set_add O(n) O(1) + gl_set_remove O(n) O(1) + gl_set_search O(n) O(1) + gl_set_iterator O(1) O(1) + gl_set_iterator_next O(1) O(1) + */ + +/* --------------------------- gl_set_t Data Type --------------------------- */ + +/* Type of function used to compare two elements. + NULL denotes pointer comparison. */ +typedef bool (*gl_setelement_equals_fn) (const void *elt1, const void *elt2); + +/* Type of function used to compute a hash code. + NULL denotes a function that depends only on the pointer itself. */ +typedef size_t (*gl_setelement_hashcode_fn) (const void *elt); + +#ifndef _GL_SETELEMENT_DISPOSE_FN_DEFINED +/* Type of function used to dispose an element once it's removed from a set. + NULL denotes a no-op. */ +typedef void (*gl_setelement_dispose_fn) (const void *elt); +# define _GL_SETELEMENT_DISPOSE_FN_DEFINED 1 +#endif + +struct gl_set_impl; +/* Type representing an entire set. */ +typedef struct gl_set_impl * gl_set_t; + +struct gl_set_implementation; +/* Type representing a set datatype implementation. */ +typedef const struct gl_set_implementation * gl_set_implementation_t; + +#if 0 /* Unless otherwise specified, these are defined inline below. */ + +/* Create an empty set. + IMPLEMENTATION is one of GL_ARRAY_SET, GL_LINKEDHASH_SET, GL_HASH_SET. + EQUALS_FN is an element comparison function or NULL. + HASHCODE_FN is an element hash code function or NULL. + DISPOSE_FN is an element disposal function or NULL. */ +/* declared in gl_xset.h */ +extern gl_set_t gl_set_create_empty (gl_set_implementation_t implementation, + gl_setelement_equals_fn equals_fn, + gl_setelement_hashcode_fn hashcode_fn, + gl_setelement_dispose_fn dispose_fn); +/* Likewise. Return NULL upon out-of-memory. */ +extern gl_set_t gl_set_nx_create_empty (gl_set_implementation_t implementation, + gl_setelement_equals_fn equals_fn, + gl_setelement_hashcode_fn hashcode_fn, + gl_setelement_dispose_fn dispose_fn); + +/* Return the current number of elements in a set. */ +extern size_t gl_set_size (gl_set_t set); + +/* Search whether an element is already in the set. + Return true if found, or false if not present in the set. */ +extern bool gl_set_search (gl_set_t set, const void *elt); + +/* Add an element to a set. + Return true if it was not already in the set and added, false otherwise. */ +/* declared in gl_xset.h */ +extern bool gl_set_add (gl_set_t set, const void *elt); +/* Likewise. Return -1 upon out-of-memory. */ +extern int gl_set_nx_add (gl_set_t set, const void *elt) +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif + ; + +/* Remove an element from a set. + Return true if it was found and removed. */ +extern bool gl_set_remove (gl_set_t set, const void *elt); + +/* Free an entire set. + (But this call does not free the elements of the set. It only invokes + the DISPOSE_FN on each of the elements of the set.) */ +extern void gl_set_free (gl_set_t set); + +#endif /* End of inline and gl_xset.h-defined functions. */ + +/* ---------------------- gl_set_iterator_t Data Type ---------------------- */ + +/* Functions for iterating through a set. + Note: Iterating through a set of type GL_HASH_SET returns the elements in an + unpredictable order. If you need a predictable order, use GL_LINKEDHASH_SET + instead of GL_HASH_SET. */ + +/* Type of an iterator that traverses a set. + This is a fixed-size struct, so that creation of an iterator doesn't need + memory allocation on the heap. */ +typedef struct +{ + /* For fast dispatch of gl_set_iterator_next. */ + const struct gl_set_implementation *vtable; + /* For detecting whether the last returned element was removed. */ + gl_set_t set; + size_t count; + /* Other, implementation-private fields. */ + void *p; void *q; + size_t i; size_t j; +} gl_set_iterator_t; + +#if 0 /* These are defined inline below. */ + +/* Create an iterator traversing a set. + The set's contents must not be modified while the iterator is in use, + except for removing the last returned element. */ +extern gl_set_iterator_t gl_set_iterator (gl_set_t set); + +/* If there is a next element, store the next element in *ELTP, advance the + iterator and return true. Otherwise, return false. */ +extern bool gl_set_iterator_next (gl_set_iterator_t *iterator, + const void **eltp); + +/* Free an iterator. */ +extern void gl_set_iterator_free (gl_set_iterator_t *iterator); + +#endif /* End of inline functions. */ + +/* ------------------------ Implementation Details ------------------------ */ + +struct gl_set_implementation +{ + /* gl_set_t functions. */ + gl_set_t (*nx_create_empty) (gl_set_implementation_t implementation, + gl_setelement_equals_fn equals_fn, + gl_setelement_hashcode_fn hashcode_fn, + gl_setelement_dispose_fn dispose_fn); + size_t (*size) (gl_set_t set); + bool (*search) (gl_set_t set, const void *elt); + int (*nx_add) (gl_set_t set, const void *elt); + bool (*remove_elt) (gl_set_t set, const void *elt); + void (*set_free) (gl_set_t set); + /* gl_set_iterator_t functions. */ + gl_set_iterator_t (*iterator) (gl_set_t set); + bool (*iterator_next) (gl_set_iterator_t *iterator, const void **eltp); + void (*iterator_free) (gl_set_iterator_t *iterator); +}; + +struct gl_set_impl_base +{ + const struct gl_set_implementation *vtable; + gl_setelement_equals_fn equals_fn; + gl_setelement_dispose_fn dispose_fn; +}; + +/* Define all functions of this file as accesses to the + struct gl_set_implementation. */ + +GL_SET_INLINE gl_set_t +gl_set_nx_create_empty (gl_set_implementation_t implementation, + gl_setelement_equals_fn equals_fn, + gl_setelement_hashcode_fn hashcode_fn, + gl_setelement_dispose_fn dispose_fn) +{ + return implementation->nx_create_empty (implementation, equals_fn, + hashcode_fn, dispose_fn); +} + +GL_SET_INLINE size_t +gl_set_size (gl_set_t set) +{ + return ((const struct gl_set_impl_base *) set)->vtable->size (set); +} + +GL_SET_INLINE bool +gl_set_search (gl_set_t set, const void *elt) +{ + return ((const struct gl_set_impl_base *) set)->vtable->search (set, elt); +} + +GL_SET_INLINE int +#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) + __attribute__ ((__warn_unused_result__)) +#endif +gl_set_nx_add (gl_set_t set, const void *elt) +{ + return ((const struct gl_set_impl_base *) set)->vtable->nx_add (set, elt); +} + +GL_SET_INLINE bool +gl_set_remove (gl_set_t set, const void *elt) +{ + return ((const struct gl_set_impl_base *) set)->vtable->remove_elt (set, elt); +} + +GL_SET_INLINE void +gl_set_free (gl_set_t set) +{ + ((const struct gl_set_impl_base *) set)->vtable->set_free (set); +} + +GL_SET_INLINE gl_set_iterator_t +gl_set_iterator (gl_set_t set) +{ + return ((const struct gl_set_impl_base *) set)->vtable->iterator (set); +} + +GL_SET_INLINE bool +gl_set_iterator_next (gl_set_iterator_t *iterator, const void **eltp) +{ + return iterator->vtable->iterator_next (iterator, eltp); +} + +GL_SET_INLINE void +gl_set_iterator_free (gl_set_iterator_t *iterator) +{ + iterator->vtable->iterator_free (iterator); +} + +#ifdef __cplusplus +} +#endif + +_GL_INLINE_HEADER_END + +#endif /* _GL_SET_H */ diff --git a/gl/lib/gl_xlist.c b/gl/lib/gl_xlist.c new file mode 100644 index 00000000..fe3c8933 --- /dev/null +++ b/gl/lib/gl_xlist.c @@ -0,0 +1,3 @@ +#include <config.h> +#define GL_XLIST_INLINE _GL_EXTERN_INLINE +#include "gl_xlist.h" diff --git a/gl/lib/gl_xlist.h b/gl/lib/gl_xlist.h new file mode 100644 index 00000000..87885c33 --- /dev/null +++ b/gl/lib/gl_xlist.h @@ -0,0 +1,177 @@ +/* Abstract sequential list data type, with out-of-memory checking. + Copyright (C) 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2009. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_XLIST_H +#define _GL_XLIST_H + +#include "gl_list.h" +#include "xalloc.h" + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef GL_XLIST_INLINE +# define GL_XLIST_INLINE _GL_INLINE +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +/* These functions are thin wrappers around the corresponding functions with + _nx_ infix from gl_list.h. Upon out-of-memory, they invoke xalloc_die (), + instead of returning an error indicator. */ +#if 0 /* These are defined inline below. */ +extern gl_list_t gl_list_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates); +extern gl_list_t gl_list_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents); +extern void gl_list_node_set_value (gl_list_t list, gl_list_node_t node, + const void *elt); +extern gl_list_node_t gl_list_set_at (gl_list_t list, size_t position, + const void *elt); +extern gl_list_node_t gl_list_add_first (gl_list_t list, const void *elt); +extern gl_list_node_t gl_list_add_last (gl_list_t list, const void *elt); +extern gl_list_node_t gl_list_add_before (gl_list_t list, gl_list_node_t node, + const void *elt); +extern gl_list_node_t gl_list_add_after (gl_list_t list, gl_list_node_t node, + const void *elt); +extern gl_list_node_t gl_list_add_at (gl_list_t list, size_t position, + const void *elt); +extern gl_list_node_t gl_sortedlist_add (gl_list_t list, + gl_listelement_compar_fn compar, + const void *elt); +#endif + +GL_XLIST_INLINE gl_list_t +gl_list_create_empty (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates) +{ + gl_list_t result = + gl_list_nx_create_empty (implementation, equals_fn, hashcode_fn, dispose_fn, + allow_duplicates); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XLIST_INLINE gl_list_t +gl_list_create (gl_list_implementation_t implementation, + gl_listelement_equals_fn equals_fn, + gl_listelement_hashcode_fn hashcode_fn, + gl_listelement_dispose_fn dispose_fn, + bool allow_duplicates, + size_t count, const void **contents) +{ + gl_list_t result = + gl_list_nx_create (implementation, equals_fn, hashcode_fn, dispose_fn, + allow_duplicates, count, contents); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XLIST_INLINE void +gl_list_node_set_value (gl_list_t list, gl_list_node_t node, const void *elt) +{ + int result = gl_list_node_nx_set_value (list, node, elt); + if (result < 0) + xalloc_die (); +} + +GL_XLIST_INLINE gl_list_node_t +gl_list_set_at (gl_list_t list, size_t position, const void *elt) +{ + gl_list_node_t result = gl_list_nx_set_at (list, position, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XLIST_INLINE gl_list_node_t +gl_list_add_first (gl_list_t list, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_first (list, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XLIST_INLINE gl_list_node_t +gl_list_add_last (gl_list_t list, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_last (list, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XLIST_INLINE gl_list_node_t +gl_list_add_before (gl_list_t list, gl_list_node_t node, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_before (list, node, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XLIST_INLINE gl_list_node_t +gl_list_add_after (gl_list_t list, gl_list_node_t node, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_after (list, node, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XLIST_INLINE gl_list_node_t +gl_list_add_at (gl_list_t list, size_t position, const void *elt) +{ + gl_list_node_t result = gl_list_nx_add_at (list, position, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XLIST_INLINE gl_list_node_t +gl_sortedlist_add (gl_list_t list, gl_listelement_compar_fn compar, + const void *elt) +{ + gl_list_node_t result = gl_sortedlist_nx_add (list, compar, elt); + if (result == NULL) + xalloc_die (); + return result; +} + +#ifdef __cplusplus +} +#endif + +_GL_INLINE_HEADER_END + +#endif /* _GL_XLIST_H */ diff --git a/gl/lib/gl_xmap.c b/gl/lib/gl_xmap.c new file mode 100644 index 00000000..3d39fdba --- /dev/null +++ b/gl/lib/gl_xmap.c @@ -0,0 +1,3 @@ +#include <config.h> +#define GL_XMAP_INLINE _GL_EXTERN_INLINE +#include "gl_xmap.h" diff --git a/gl/lib/gl_xmap.h b/gl/lib/gl_xmap.h new file mode 100644 index 00000000..fb97bc3c --- /dev/null +++ b/gl/lib/gl_xmap.h @@ -0,0 +1,91 @@ +/* Abstract map data type, with out-of-memory checking. + Copyright (C) 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2018. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_XMAP_H +#define _GL_XMAP_H + +#include "gl_map.h" +#include "xalloc.h" + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef GL_XMAP_INLINE +# define GL_XMAP_INLINE _GL_INLINE +#endif + + +#ifdef __cplusplus +extern "C" { +#endif + +/* These functions are thin wrappers around the corresponding functions with + _nx_ infix from gl_map.h. Upon out-of-memory, they invoke xalloc_die (), + instead of returning an error indicator. */ +#if 0 /* These are defined inline below. */ +extern gl_map_t gl_map_create_empty (gl_map_implementation_t implementation, + gl_mapkey_equals_fn equals_fn, + gl_mapkey_hashcode_fn hashcode_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn); +extern bool gl_map_put (gl_map_t map, const void *key, const void *value); +extern bool gl_map_getput (gl_map_t map, const void *key, const void *value, + const void **oldvaluep); +#endif + +GL_XMAP_INLINE gl_map_t +gl_map_create_empty (gl_map_implementation_t implementation, + gl_mapkey_equals_fn equals_fn, + gl_mapkey_hashcode_fn hashcode_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn) +{ + gl_map_t result = + gl_map_nx_create_empty (implementation, equals_fn, hashcode_fn, + kdispose_fn, vdispose_fn); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XMAP_INLINE bool +gl_map_put (gl_map_t map, const void *key, const void *value) +{ + int result = gl_map_nx_put (map, key, value); + if (result < 0) + xalloc_die (); + return result; +} + +GL_XMAP_INLINE bool +gl_map_getput (gl_map_t map, const void *key, const void *value, + const void **oldvaluep) +{ + int result = gl_map_nx_getput (map, key, value, oldvaluep); + if (result < 0) + xalloc_die (); + return result; +} + +#ifdef __cplusplus +} +#endif + +_GL_INLINE_HEADER_END + +#endif /* _GL_XMAP_H */ diff --git a/gl/lib/gl_xset.c b/gl/lib/gl_xset.c new file mode 100644 index 00000000..83557c04 --- /dev/null +++ b/gl/lib/gl_xset.c @@ -0,0 +1,3 @@ +#include <config.h> +#define GL_XSET_INLINE _GL_EXTERN_INLINE +#include "gl_xset.h" diff --git a/gl/lib/gl_xset.h b/gl/lib/gl_xset.h new file mode 100644 index 00000000..23496dc4 --- /dev/null +++ b/gl/lib/gl_xset.h @@ -0,0 +1,76 @@ +/* Abstract set data type, with out-of-memory checking. + Copyright (C) 2009-2019 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 2009. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_XSET_H +#define _GL_XSET_H + +#include "gl_set.h" +#include "xalloc.h" + +#ifndef _GL_INLINE_HEADER_BEGIN + #error "Please include config.h first." +#endif +_GL_INLINE_HEADER_BEGIN +#ifndef GL_XSET_INLINE +# define GL_XSET_INLINE _GL_INLINE +#endif + + +#ifdef __cplusplus +extern "C" { +#endif + +/* These functions are thin wrappers around the corresponding functions with + _nx_ infix from gl_set.h. Upon out-of-memory, they invoke xalloc_die (), + instead of returning an error indicator. */ +#if 0 /* These are defined inline below. */ +extern gl_set_t gl_set_create_empty (gl_set_implementation_t implementation, + gl_setelement_equals_fn equals_fn, + gl_setelement_hashcode_fn hashcode_fn, + gl_setelement_dispose_fn dispose_fn); +extern bool gl_set_add (gl_set_t set, const void *elt); +#endif + +GL_XSET_INLINE gl_set_t +gl_set_create_empty (gl_set_implementation_t implementation, + gl_setelement_equals_fn equals_fn, + gl_setelement_hashcode_fn hashcode_fn, + gl_setelement_dispose_fn dispose_fn) +{ + gl_set_t result = + gl_set_nx_create_empty (implementation, equals_fn, hashcode_fn, dispose_fn); + if (result == NULL) + xalloc_die (); + return result; +} + +GL_XSET_INLINE bool +gl_set_add (gl_set_t set, const void *elt) +{ + int result = gl_set_nx_add (set, elt); + if (result < 0) + xalloc_die (); + return result; +} + +#ifdef __cplusplus +} +#endif + +_GL_INLINE_HEADER_END + +#endif /* _GL_XSET_H */ diff --git a/gl/lib/hash-pjw-bare.c b/gl/lib/hash-pjw-bare.c new file mode 100644 index 00000000..1b6f26bf --- /dev/null +++ b/gl/lib/hash-pjw-bare.c @@ -0,0 +1,42 @@ +/* hash-pjw-bare.c -- compute a hash value from a provided buffer. + + Copyright (C) 2012-2019 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify it + under the terms of the GNU General Public License as published + by the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#include <config.h> + +#include "hash-pjw-bare.h" + +#include <limits.h> + +#define SIZE_BITS (sizeof (size_t) * CHAR_BIT) + +/* Return a hash of the N bytes of X using the method described by + Bruno Haible in https://www.haible.de/bruno/hashfunc.html. + Note that while many hash functions reduce their result via modulo + to a 0..table_size-1 range, this function does not do that. */ + +size_t +hash_pjw_bare (const void *x, size_t n) +{ + const unsigned char *s = x; + size_t h = 0; + unsigned i; + + for (i = 0; i < n; i++) + h = s[i] + ((h << 9) | (h >> (SIZE_BITS - 9))); + + return h; +} diff --git a/gl/lib/hash-pjw-bare.h b/gl/lib/hash-pjw-bare.h new file mode 100644 index 00000000..8fd8d9fb --- /dev/null +++ b/gl/lib/hash-pjw-bare.h @@ -0,0 +1,24 @@ +/* hash-pjw-bare.h -- declaration for a simple hash function + Copyright (C) 2012-2019 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify it + under the terms of the GNU General Public License as published + by the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#include <stddef.h> + +/* Compute a hash code for a buffer starting at X and of size N, + and return the hash code. Note that unlike hash_pjw(), it does not + return it modulo a table size. + The result is platform dependent: it depends on the size of the 'size_t' + type. */ +extern size_t hash_pjw_bare (const void *x, size_t n) _GL_ATTRIBUTE_PURE; diff --git a/gl/lib/lchown.c b/gl/lib/lchown.c new file mode 100644 index 00000000..03138c29 --- /dev/null +++ b/gl/lib/lchown.c @@ -0,0 +1,117 @@ +/* Provide a stub lchown function for systems that lack it. + + Copyright (C) 1998-1999, 2002, 2004, 2006-2007, 2009-2019 Free Software + Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +/* written by Jim Meyering */ + +#include <config.h> + +#include <unistd.h> + +#include <errno.h> +#include <stdbool.h> +#include <string.h> +#include <sys/stat.h> + +#if !HAVE_LCHOWN + +/* If the system chown does not follow symlinks, we don't want it + replaced by gnulib's chown, which does follow symlinks. */ +# if CHOWN_MODIFIES_SYMLINK +# undef chown +# endif + +/* Work just like chown, except when FILE is a symbolic link. + In that case, set errno to EOPNOTSUPP and return -1. + But if autoconf tests determined that chown modifies + symlinks, then just call chown. */ + +int +lchown (const char *file, uid_t uid, gid_t gid) +{ +# if HAVE_CHOWN +# if ! CHOWN_MODIFIES_SYMLINK + struct stat stats; + + if (lstat (file, &stats) == 0 && S_ISLNK (stats.st_mode)) + { + errno = EOPNOTSUPP; + return -1; + } +# endif + + return chown (file, uid, gid); + +# else /* !HAVE_CHOWN */ + errno = ENOSYS; + return -1; +# endif +} + +#else /* HAVE_LCHOWN */ + +# undef lchown + +/* Work around trailing slash bugs in lchown. */ +int +rpl_lchown (const char *file, uid_t uid, gid_t gid) +{ + bool stat_valid = false; + int result; + +# if CHOWN_CHANGE_TIME_BUG + struct stat st; + + if (gid != (gid_t) -1 || uid != (uid_t) -1) + { + if (lstat (file, &st)) + return -1; + stat_valid = true; + if (!S_ISLNK (st.st_mode)) + return chown (file, uid, gid); + } +# endif + +# if CHOWN_TRAILING_SLASH_BUG + if (!stat_valid) + { + size_t len = strlen (file); + if (len && file[len - 1] == '/') + return chown (file, uid, gid); + } +# endif + + result = lchown (file, uid, gid); + +# if CHOWN_CHANGE_TIME_BUG && HAVE_LCHMOD + if (result == 0 && stat_valid + && (uid == st.st_uid || uid == (uid_t) -1) + && (gid == st.st_gid || gid == (gid_t) -1)) + { + /* No change in ownership, but at least one argument was not -1, + so we are required to update ctime. Since lchown succeeded, + we assume that lchmod will do likewise. But if the system + lacks lchmod and lutimes, we are out of luck. Oh well. */ + result = lchmod (file, st.st_mode & (S_IRWXU | S_IRWXG | S_IRWXO + | S_ISUID | S_ISGID | S_ISVTX)); + } +# endif + + return result; +} + +#endif /* HAVE_LCHOWN */ diff --git a/gl/lib/regexec.c b/gl/lib/regexec.c index 21cf7915..2f7cb5dc 100644 --- a/gl/lib/regexec.c +++ b/gl/lib/regexec.c @@ -2207,7 +2207,7 @@ sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx, dfa->nexts[node_idx])) /* The node can't accept the "multi byte", or the destination was already thrown away, then the node - could't accept the current input "multi byte". */ + couldn't accept the current input "multi byte". */ naccepted = 0; /* Otherwise, it is sure that the node could accept 'naccepted' bytes input. */ diff --git a/gl/lib/stdopen.c b/gl/lib/stdopen.c new file mode 100644 index 00000000..29350d1b --- /dev/null +++ b/gl/lib/stdopen.c @@ -0,0 +1,66 @@ +/* stdopen.c - ensure that the three standard file descriptors are in use + + Copyright (C) 2005-2006, 2019 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. */ + +/* Written by Paul Eggert and Jim Meyering. */ + +#include <config.h> + +#include "stdopen.h" + +#include <sys/stat.h> +#include <fcntl.h> +#include <unistd.h> +#include <errno.h> + +/* Try to ensure that all of the standard file numbers (0, 1, 2) + are in use. Without this, each application would have to guard + every call to open, dup, fopen, etc. with tests to ensure they + don't use one of the special file numbers when opening a file. + Return zero if successful, an errno value if at least one of + the file descriptors is initially closed and could not be opened. */ + +int +stdopen (void) +{ + int fd; + for (fd = STDIN_FILENO; fd <= STDERR_FILENO; fd++) + { + if (fcntl (fd, F_GETFD) < 0) + { + /* Open /dev/null with the contrary mode so that the typical + read (stdin) or write (stdout, stderr) operation will fail. + With descriptor 0, we can do even better on systems that + have /dev/full, by opening that write-only instead of + /dev/null. The only drawback is that a write-provoked + failure comes with a misleading errno value, ENOSPC. */ + int mode = fd == STDIN_FILENO ? O_WRONLY : O_RDONLY; + int full_fd = fd == STDIN_FILENO ? open ("/dev/full", mode) : -1; + int new_fd = full_fd < 0 ? open ("/dev/null", mode) : full_fd; + if (new_fd < 0) + return errno; + if (STDERR_FILENO < new_fd) + { + /* 0, 1, and 2 are already open somehow. + Our is not to reason why. */ + close (new_fd); + return 0; + } + } + } + + return 0; +} diff --git a/gl/lib/stdopen.h b/gl/lib/stdopen.h new file mode 100644 index 00000000..27901d39 --- /dev/null +++ b/gl/lib/stdopen.h @@ -0,0 +1,14 @@ +#ifndef STDOPEN_H +# define STDOPEN_H 1 + +# ifdef __cplusplus +extern "C" { +# endif + +int stdopen (void); + +# ifdef __cplusplus +} +# endif + +#endif diff --git a/gl/lib/sys_stat.in.h b/gl/lib/sys_stat.in.h index 58fa93fd..9ddd1a8d 100644 --- a/gl/lib/sys_stat.in.h +++ b/gl/lib/sys_stat.in.h @@ -54,9 +54,16 @@ /* The definition of _GL_WARN_ON_USE is copied here. */ +/* Before doing "#define mknod rpl_mknod" below, we need to include all + headers that may declare mknod(). OS/2 kLIBC declares mknod() in + <unistd.h>, not in <sys/stat.h>. */ +#ifdef __KLIBC__ +# include <unistd.h> +#endif + /* Before doing "#define mkdir rpl_mkdir" below, we need to include all headers that may declare mkdir(). Native Windows platforms declare mkdir - in <io.h> and/or <direct.h>, not in <unistd.h>. */ + in <io.h> and/or <direct.h>, not in <sys/stat.h>. */ #if defined _WIN32 && ! defined __CYGWIN__ # include <io.h> /* mingw32, mingw64 */ # include <direct.h> /* mingw64, MSVC 9 */ diff --git a/gl/lib/vasnprintf.c b/gl/lib/vasnprintf.c index c4759037..f1f47f0d 100644 --- a/gl/lib/vasnprintf.c +++ b/gl/lib/vasnprintf.c @@ -4874,6 +4874,7 @@ VASNPRINTF (DCHAR_T *resultbuf, size_t *lengthp, # if ! (((__GLIBC__ > 2 || (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 3)) \ && !defined __UCLIBC__) \ || (defined __APPLE__ && defined __MACH__) \ + || defined __ANDROID__ \ || (defined _WIN32 && ! defined __CYGWIN__)) fbp[1] = '%'; fbp[2] = 'n'; @@ -4895,6 +4896,14 @@ VASNPRINTF (DCHAR_T *resultbuf, size_t *lengthp, On Mac OS X 10.13 or newer, the use of %n in format strings in writable memory by default crashes the program, so we should avoid it in this situation. */ + /* On Android, we know that snprintf's return value conforms to + ISO C 99: the tests gl_SNPRINTF_RETVAL_C99 and + gl_SNPRINTF_TRUNCATION_C99 pass. + Therefore we can avoid using %n in this situation. + Starting on 2018-03-07, the use of %n in format strings + produces a fatal error (see + <https://android.googlesource.com/platform/bionic/+/41398d03b7e8e0dfb951660ae713e682e9fc0336>), + so we should avoid it. */ /* On native Windows systems (such as mingw), we can avoid using %n because: - Although the gl_SNPRINTF_TRUNCATION_C99 test fails, diff --git a/gl/lib/verify.h b/gl/lib/verify.h index b2e5f644..6930645a 100644 --- a/gl/lib/verify.h +++ b/gl/lib/verify.h @@ -26,7 +26,7 @@ here generates easier-to-read diagnostics when verify (R) fails. Define _GL_HAVE_STATIC_ASSERT to 1 if static_assert works as per C++11. - This will likely be supported by future GCC versions, in C++ mode. + This is supported by GCC 6.1.0 and later, in C++ mode. Use this only with GCC. If we were willing to slow 'configure' down we could also use it with other compilers, but since this @@ -36,9 +36,7 @@ && !defined __cplusplus) # define _GL_HAVE__STATIC_ASSERT 1 #endif -/* The condition (99 < __GNUC__) is temporary, until we know about the - first G++ release that supports static_assert. */ -#if (99 < __GNUC__) && defined __cplusplus +#if (6 <= __GNUC__) && defined __cplusplus # define _GL_HAVE_STATIC_ASSERT 1 #endif diff --git a/gl/lib/xstdopen.c b/gl/lib/xstdopen.c new file mode 100644 index 00000000..677a2801 --- /dev/null +++ b/gl/lib/xstdopen.c @@ -0,0 +1,35 @@ +/* Ensure that stdin, stdout, stderr are open. + Copyright (C) 2019 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "xstdopen.h" + +#include "stdopen.h" +#include "error.h" +#include "exitfail.h" + +#include "gettext.h" +#define _(msgid) gettext (msgid) + +void +xstdopen (void) +{ + int stdopen_errno = stdopen (); + if (stdopen_errno != 0) + error (exit_failure, stdopen_errno, _("standard file descriptors")); +} diff --git a/gl/lib/xstdopen.h b/gl/lib/xstdopen.h new file mode 100644 index 00000000..08a8a042 --- /dev/null +++ b/gl/lib/xstdopen.h @@ -0,0 +1,28 @@ +/* Ensure that stdin, stdout, stderr are open. + Copyright (C) 2019 Free Software Foundation, Inc. + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <https://www.gnu.org/licenses/>. */ + +#ifdef __cplusplus +extern "C" { +#endif + +/* Ensures that the file descriptors of stdin, stdout, stderr (0, 1, 2) are + open. Exits the program with an error message upon failure; the error + message may not appear if stderr is closed. */ +extern void xstdopen (void); + +#ifdef __cplusplus +} +#endif |