Eric Blake wrote:
Jim Meyering jim at meyering.net writes:
/* If the growth threshold of the buckets in use has been reached,
increase
the table size and rehash. There's no point in checking the number
of
entries: if the hashing function is ill-conditioned, rehashing
In strcasestr.m4, there is no need to do the linear time check if gnulib is
going to override the function anyway.
Also, I prefer not to rely on AC_REPLACE_FUNCS when it makes the code harder
to understand. AC_REPLACE_FUNCS is a nice shorthand for the simple cases, but
here its use leads to
In strstr.m4 as well, the linear time check can be skipped if the function
is going to be overridden anyway.
2009-06-18 Bruno Haible br...@clisp.org
* m4/strstr.m4 (gl_FUNC_STRSTR): Skip linear time test if strstr is
going to be replaced anyway.
--- m4/strstr.m4.orig
Sam Steingold wrote:
after:
$ grep -i sigsegv config.status
S[LIBSIGSEGV_PREFIX]=
S[LTLIBSIGSEGV]=
S[LIBSIGSEGV]=
S[HAVE_LIBSIGSEGV]=yes
D[HAVE_LIBSIGSEGV]= 1
D[HAVE_LIBSIGSEGV]= 1
...
$ ls -l /usr/include/sigsegv* /usr/lib*/libsigsegv*
8 -rw-r--r-- 1 root root 5802 Sep
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
According to Bruno Haible on 6/18/2009 2:19 AM:
In strstr.m4 as well, the linear time check can be skipped if the function
is going to be overridden anyway.
Thanks. I thought about that optimization, but didn't do it. But it does
shave off
-function
-I/usr/local/src/blackfin/toolchains/win32/20090618/libftdi/destdir/include
-MT gettime.o -MD -MP -MF .deps/gettime.Tpo -c -o gettime.o
/proj/gnulib/lib/gettime.c; \
then mv -f .deps/gettime.Tpo .deps/gettime.Po; else rm -f
.deps/gettime.Tpo; exit 1; fi
In file included from /proj
Eric Blake wrote:
According to Jim Meyering on 6/17/2009 1:21 PM:
is not quite right. A hashing function may be somewhat ill-conditioned for
one
bucket size, but much better conditioned for another size. At any rate, it
looks like the correct fix is to check for rehashing thresholds based
Eric Blake wrote:
...
+ hash: minor optimization
+ * lib/hash.c (hash_lookup, hash_find_entry): Avoid function call
+ when possible.
+ (hash_initialize): Document this promise.
+ (hash_do_for_each, hash_clear, hash_free): Use C89 syntax.
+ * tests/test-hash.c
On Thu, Jun 18, 2009 at 5:31 AM, Bruno Haiblebr...@clisp.org wrote:
Sam Steingold wrote:
after:
$ grep -i sigsegv config.status
S[LIBSIGSEGV_PREFIX]=
S[LTLIBSIGSEGV]=
S[LIBSIGSEGV]=
S[HAVE_LIBSIGSEGV]=yes
D[HAVE_LIBSIGSEGV]= 1
D[HAVE_LIBSIGSEGV]= 1
...
$ ls -l
Eric Blake wrote:
I haven't pushed the second one to savannah yet; what do you think of it?
Sometimes it is desirable to hash distinct pointers, in which case
allowing a NULL user function to request this seems to make sense. My
design choice was to provide trivial functions at
Date: Wed, 17 Jun 2009 19:58:58 -0600
From: e...@byu.net
With that in place, Jay, would you mind testing this latest snapshot?
http://home.comcast.net/~ericblake/m4-1.4.13.3-5f008.tar.gz [1.3M]
.gz.asc
.tar.bz2 [992K]
.bz2.asc
.xz [822K]
.xz.asc
Jim Meyering jim at meyering.net writes:
Unless I become exceptionally unresponsive,
please post before pushing changes to hash.c.
I would have requested that you not mix clean-up like this with
a semantics-changing change set:
Sorry for jumping the gun on that. I'll be a little more
Eric Blake wrote:
...
That discards bits, in the case where non-malloced values are being used. The
assertion is nice when you know that all values are malloc'd, but is harsh for
a default. So, how about I squash this slight modification into my patch
before pushing this commit?
diff --git
Eric Blake e...@byu.net writes:
static size_t
raw_hasher (const void *data, size_t n)
{
- return (size_t) data % n;
+ /* When hashing unique pointers, it is often the case that they were
+ generated by malloc and thus have the property that the low-order
+ bits are 0. As this
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
According to Jim Meyering on 6/18/2009 11:37 AM:
+ size_t val = data;
+ val = (val 3) | (val (CHAR_BIT * sizeof val - 3));
+ return val % n;
That looks fine.
Added as:
size_t val = (size_t) data;
val = ((val 3) | (val (CHAR_BIT * sizeof
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
According to Eric Blake on 6/18/2009 1:00 PM:
Then we can use this:
val = rotrsomething (val, 3);
For rotr64, it is probably superfluous; but for sizes smaller than int
smaller sizes it makes a difference. I think that warrants a
Eric Blake wrote:
According to Jim Meyering on 6/18/2009 11:37 AM:
+ size_t val = data;
+ val = (val 3) | (val (CHAR_BIT * sizeof val - 3));
+ return val % n;
That looks fine.
Added as:
size_t val = (size_t) data;
val = ((val 3) | (val (CHAR_BIT * sizeof val - 3))) SIZE_MAX;
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
According to Eric Blake on 6/18/2009 7:29 AM:
Here's two simple patches. I'm committing the first, as there should be
enough cases where you end up searching for an element already known to be
hashed, where making an indirect function call is
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
According to Eric Blake on 6/18/2009 1:06 PM:
According to Eric Blake on 6/18/2009 1:00 PM:
Then we can use this:
val = rotrsomething (val, 3);
For rotr64, it is probably superfluous; but for sizes smaller than int
smaller sizes it makes a
Eric Blake wrote:
...
From dd342c74a01a02cd35f53da621d6ac122fd606f5 Mon Sep 17 00:00:00 2001
From: Eric Blake e...@byu.net
Date: Thu, 18 Jun 2009 13:31:11 -0600
Subject: [PATCH] hash: make rotation more obvious
* modules/hash (Depends-on): Add bitrotate and stdint.
* lib/bitrotate.h
Jim Meyering jim at meyering.net writes:
if (new_table == NULL)
return false;
+ if (new_table-n_buckets == table-n_buckets)
+return true;
Aargh. Ten minutes after I push, I finally see my memory leak.
Obviously, new_table needs to be freed before returning true.
--
Eric
Eric Blake e...@byu.net writes:
Here's the patch. Simon, as bitrotate owner, do you also agree?
Looks fine, thanks.
/Simon
Eric Blake wrote:
Jim Meyering jim at meyering.net writes:
if (new_table == NULL)
return false;
+ if (new_table-n_buckets == table-n_buckets)
+return true;
Aargh. Ten minutes after I push, I finally see my memory leak.
Obviously, new_table needs to be freed before
Jim Meyering jim at meyering.net writes:
Aargh. Ten minutes after I push, I finally see my memory leak.
Obviously, new_table needs to be freed before returning true.
Hah! I should have looked at more than the patch.
Is that code path already exercised by test-hash.c?
If so, I would
Jim Meyering jim at meyering.net writes:
My first attempt used a full two-pass algorithm for the cleanup case. With
one
pass, the allocations and frees are intermingled, with two passes all frees
occur before any allocations. However, I have been unable (so far) to
contrive
any such
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
According to Eric Blake on 6/18/2009 5:22 PM:
This patch gets things to the state where I'm happy that the memory
allocation
failure recovery works correctly. But as-is, this patch uses a one-pass
algorithm, so my test case means the failure
26 matches
Mail list logo
