[Python-checkins] CVS: python/dist/src/Tools/perfecthash GenUCNHash.py,1.4,1.5 perfect_hash.py,1.2,1.3 perfhash.c,1.2,1.3
Jeremy Hylton
python-dev@python.org
2000年7月25日 20:56:09 -0700
Update of /cvsroot/python/python/dist/src/Tools/perfecthash
In directory slayer.i.sourceforge.net:/tmp/cvs-serv19915/Tools/perfecthash
Modified Files:
GenUCNHash.py perfect_hash.py perfhash.c
Log Message:
Fix UCNs machine with >= 32bit longs
originally submitted by Bill Tutt
Note: This code is actually going to be replaced in 2.0 by /F's new
database. Until then, this patch keeps the test suite working.
Index: GenUCNHash.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Tools/perfecthash/GenUCNHash.py,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -r1.4 -r1.5
*** GenUCNHash.py 2000年07月07日 17:53:54 1.4
--- GenUCNHash.py 2000年07月26日 03:56:06 1.5
***************
*** 13,18 ****
# These variables determine which hash function is tried first.
# Yields a multiple of 1.7875 for UnicodeData.txt on 2000/06/24/
! f1Seed = 1694245428
! f2Seed = -1917331657
# Maximum allowed multipler, if this isn't None then instead of continually
--- 13,18 ----
# These variables determine which hash function is tried first.
# Yields a multiple of 1.7875 for UnicodeData.txt on 2000/06/24/
! f1Seed = 0x64fc2234
! f2Seed = 0x8db7d737
# Maximum allowed multipler, if this isn't None then instead of continually
Index: perfect_hash.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Tools/perfecthash/perfect_hash.py,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -r1.2 -r1.3
*** perfect_hash.py 2000年06月30日 09:56:00 1.2
--- perfect_hash.py 2000年07月26日 03:56:06 1.3
***************
*** 74,80 ****
if self.caseInsensitive:
key = string.upper(key)
! x = perfhash.hash(self.seed, len(self.junk), key) % self.N
! #h = hash(self.junk + key) % self.N
! #assert x == h
return x
--- 74,78 ----
if self.caseInsensitive:
key = string.upper(key)
! x = perfhash.hash(self.seed, len(self.junk), key, self.N)
return x
***************
*** 83,96 ****
register int len;
register unsigned char *p;
! register long x;
len = cch;
p = (unsigned char *) key;
! x = %(junkSeed)d;
while (--len >= 0)
! x = (1000003*x) ^ """ % \
{
"lenJunk" : len(self.junk),
! "junkSeed" : self.seed,
}
--- 81,100 ----
register int len;
register unsigned char *p;
! register unsigned long x;
len = cch;
p = (unsigned char *) key;
! x = %(junkSeed)s;
while (--len >= 0)
! {
! /* (1000003 * x) ^ toupper(*(p++))
! * translated to handle > 32 bit longs
! */
! x = (0xf4243 * x);
! x = x & 0xFFFFFFFF;
! x = x ^ """ % \
{
"lenJunk" : len(self.junk),
! "junkSeed" : hex(self.seed),
}
***************
*** 100,117 ****
s = s + "*(p++);"
s = s + """
x ^= cch + %(lenJunk)d;
! if (x == -1)
! x = -2;
! x %%= k_cHashElements;
! /* ensure the returned value is positive so we mimic Python's %% operator */
! if (x < 0)
! x += k_cHashElements;
return x;
}
""" % { "lenJunk" : len(self.junk),
! "junkSeed" : self.seed, }
return s
-
WHITE, GREY, BLACK = 0,1,2
class Graph:
--- 104,130 ----
s = s + "*(p++);"
s = s + """
+ }
x ^= cch + %(lenJunk)d;
! if (x == 0xFFFFFFFF)
! x = 0xfffffffe;
! if (x & 0x80000000)
! {
! /* Emulate 32-bit signed (2's complement) modulo operation */
! x = (~x & 0xFFFFFFFF) + 1;
! x %%= k_cHashElements;
! if (x != 0)
! {
! x = x + (~k_cHashElements & 0xFFFFFFFF) + 1;
! x = (~x & 0xFFFFFFFF) + 1;
! }
! }
! else
! x %%= k_cHashElements;
return x;
}
""" % { "lenJunk" : len(self.junk),
! "junkSeed" : hex(self.seed), }
return s
WHITE, GREY, BLACK = 0,1,2
class Graph:
***************
*** 140,145 ****
if vertex1 > vertex2: vertex1, vertex2 = vertex2, vertex1
! # if self.edges.has_key( (vertex1, vertex2) ):
! # raise ValueError, 'Collision: vertices already connected'
self.edges[ (vertex1, vertex2) ] = value
--- 153,158 ----
if vertex1 > vertex2: vertex1, vertex2 = vertex2, vertex1
! if self.edges.has_key( (vertex1, vertex2) ):
! raise ValueError, 'Collision: vertices already connected'
self.edges[ (vertex1, vertex2) ] = value
***************
*** 342,347 ****
code = code + """
! static const %s G[k_cHashElements];
! static const %s %s[k_cKeys];
""" % (self.type, dataArrayType, dataArrayName)
--- 355,360 ----
code = code + """
! staticforward const %s G[k_cHashElements];
! staticforward const %s %s[k_cKeys];
""" % (self.type, dataArrayType, dataArrayName)
***************
*** 554,558 ****
for k, v in keys:
h1 = f1(k) ; h2 = f2(k)
! G.connect( h1,h2, v)
# Check if the resulting graph is acyclic; if it is,
--- 567,571 ----
for k, v in keys:
h1 = f1(k) ; h2 = f2(k)
! G.connect( h1, h2, v)
# Check if the resulting graph is acyclic; if it is,
***************
*** 599,605 ****
sys.stderr.write('\nIn order to regenerate this hash function, \n')
sys.stderr.write('you need to pass these following values back in:\n')
! sys.stderr.write('f1 seed: %s\n' % repr(f1.seed))
! sys.stderr.write('f2 seed: %s\n' % repr(f2.seed))
sys.stderr.write('initial multipler: %s\n' % c)
return PerfectHash(cchMaxKey, f1, f2, G, N, len(keys), maxHashValue)
--- 612,619 ----
sys.stderr.write('\nIn order to regenerate this hash function, \n')
sys.stderr.write('you need to pass these following values back in:\n')
! sys.stderr.write('f1 seed: %s\n' % hex(f1.seed))
! sys.stderr.write('f2 seed: %s\n' % hex(f2.seed))
sys.stderr.write('initial multipler: %s\n' % c)
return PerfectHash(cchMaxKey, f1, f2, G, N, len(keys), maxHashValue)
+
Index: perfhash.c
===================================================================
RCS file: /cvsroot/python/python/dist/src/Tools/perfecthash/perfhash.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -r1.2 -r1.3
*** perfhash.c 2000年07月22日 19:25:51 1.2
--- perfhash.c 2000年07月26日 03:56:06 1.3
***************
*** 6,14 ****
register int len;
register unsigned char *p;
! register long x;
! long lSeed;
unsigned long cchSeed;
! if (!PyArg_ParseTuple(args, "iiO:hash", &lSeed, &cchSeed, &a))
return NULL;
if (!PyString_Check(a))
--- 6,16 ----
register int len;
register unsigned char *p;
! register unsigned long x;
! unsigned long ulSeed;
unsigned long cchSeed;
+ unsigned long cHashElements;
! if (!PyArg_ParseTuple(args, "llOl:hash",
! &ulSeed, &cchSeed, &a, &cHashElements))
return NULL;
if (!PyString_Check(a))
***************
*** 20,30 ****
len = a->ob_size;
p = (unsigned char *) a->ob_sval;
! x = lSeed;
while (--len >= 0)
! x = (1000003*x) ^ *p++;
x ^= a->ob_size + cchSeed;
! if (x == -1)
! x = -2;
! return PyInt_FromLong(x);
}
--- 22,54 ----
len = a->ob_size;
p = (unsigned char *) a->ob_sval;
! x = ulSeed;
while (--len >= 0)
! {
! /* (1000003 * x) ^ *p++
! * translated to handle > 32 bit longs
! */
! x = (0xf4243 * x);
! x = x & 0xFFFFFFFF;
! x = x ^ *p++;
! }
x ^= a->ob_size + cchSeed;
! if (x == 0xFFFFFFFF)
! x = 0xfffffffe;
! if (x & 0x80000000)
! {
! /* Emulate Python 32-bit signed (2's complement)
! * modulo operation
! */
! x = (~x & 0xFFFFFFFF) + 1;
! x %= cHashElements;
! if (x != 0)
! {
! x = x + (~cHashElements & 0xFFFFFFFF) + 1;
! x = (~x & 0xFFFFFFFF) + 1;
! }
! }
! else
! x %= cHashElements;
! return PyInt_FromLong((long)x);
}
***************
*** 34,38 ****
register int len;
register unsigned char *p;
! register long x;
if (!PyString_Check(args))
--- 58,62 ----
register int len;
register unsigned char *p;
! register unsigned long x;
if (!PyString_Check(args))
***************
*** 46,53 ****
len = a->ob_size;
p = (unsigned char *) a->ob_sval;
! x = *p << 7;
while (--len >= 0)
! x = (1000003*x) ^ *p++;
! return PyInt_FromLong(x);
}
--- 70,84 ----
len = a->ob_size;
p = (unsigned char *) a->ob_sval;
! x = (*p << 7) & 0xFFFFFFFF;
while (--len >= 0)
! {
! /* (1000003 * x) ^ *p++
! * translated to handle > 32 bit longs
! */
! x = (0xf4243 * x);
! x = x & 0xFFFFFFFF;
! x = x ^ *p++;
! }
! return PyInt_FromLong((long)x);
}
***************
*** 69,72 ****
NULL, NULL, PYTHON_API_VERSION);
if ( m == NULL )
! Py_FatalError("can't initialize module hashModule");
}
--- 100,114 ----
NULL, NULL, PYTHON_API_VERSION);
if ( m == NULL )
! Py_FatalError("can't initialize module perfhash");
}
+
+
+
+
+
+
+
+
+
+
+