← Back to branch summary

~ubuntu-branches/ubuntu/natty/lua-gtk/natty

« back to all changes in this revision

Viewing changes to src/hash/hash-cmph-fch.c

  • Committer: Bazaar Package Importer
  • Author(s): Enrico Tassi
  • Date: 2009-05-17 18:16:21 UTC
  • mfrom: (1.2.1 upstream) (4.1.1 experimental)
  • Revision ID: james.westby@ubuntu.com-20090517181621-9kmdd82nxg54jsio
http://bugs.debian.org/507205
http://bugs.debian.org/522087
http://bugs.debian.org/498120
* new upstream snapshot comprising many more GNOME libraries:
    Gtk, GDK, GLib, Pango, Atk, Libxml2, Cairo, Clutter, Gtkhtml, 
    GtkSourceView, Gio, Gtkspell and GConf. 
* new upstream release includes a new configure script written in Lua,
  no more bashisms there (Closes: #507205)
* renamed binary packages to liblua5.1-gnome-*
* updated standards-version to 3.8.1, no changes needed
* patch to load .so.* version of libraries and not .so (that was requiring
  -dev packages) (Closes: #522087)
* removed redundant Architecture line from the source stanza of control
  (Closes: #498120)
* updated copyright file, Wolfgang Oertl holds it for 2009 too.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/hash/hash-cmph-fch.c
 
1
/** vim:sw=4:sts=4
 
2
 *
 
3
 * Support for the FCH algorithm of the cmph library, which is an older and
 
4
 * less powerful algorithm than BDZ, which is also supported.
 
5
 * by Wolfgang Oertl 2007
 
6
 *
 
7
 * This code is derived from the cmph library (http://cmph.sourceforge.net/)
 
8
 * version 0.6 by Davi de Castro Reis and Fabiano Cupertino Botelho.
 
9
 *
 
10
 * I could have linked lua-gtk with the cmph library, but that would have
 
11
 * resulted in an almost 50 kB larger lua-gtk.  This is so because the cmph
 
12
 * library supports more algorithms and includes the generation code too,
 
13
 * whereas I only need the very much simpler lookup code at runtime.
 
14
 */
 
15
 
 
16
#include "lg-hash.h"
 
17
 
 
18
 
 
19
/**
 
20
 * From fch.c.
 
21
 *
 
22
 * Note: the type of p1 and p2 was changed from float to unsigned int, because
 
23
 * they can only contain integers anyway.
 
24
 */
 
25
static int mixh10h1h12(unsigned int b, unsigned int p1, unsigned int p2,
 
26
    unsigned int i)
 
27
{
 
28
    if (i < p1) {
 
29
        i %= p2;
 
30
    } else {
 
31
        i %= b;
 
32
        if (i < p2)
 
33
            i += p2;
 
34
    }
 
35
 
 
36
    return i;
 
37
}
 
38
 
 
39
 
 
40
/**
 
41
 * Hash lookup function.  Returns a bucket number; any input string results
 
42
 * in a valid bucket.  Whether the key is in the hash table has to be
 
43
 * determined later from the contents of the bucket.
 
44
 */
 
45
const unsigned char *hash_search_fch(lua_State *L, const struct hash_info *hi2,
 
46
    const unsigned char *key, int keylen, int *datalen)
 
47
{
 
48
    const struct hash_info_fch *hi = (const struct hash_info_fch*) hi2;
 
49
    unsigned int h1, h2, g, hash_value;
 
50
 
 
51
    // Calculate a first hash value; it is also used for comparison with the
 
52
    // hash value stored in the bucket to identify hits and misses.
 
53
    hash_value = h1 = compute_hash(&hi->h1, key, keylen, (void*)0);
 
54
 
 
55
    // The first hash value is used to achieve the "minimal" and "perfect"
 
56
    // properties of the hash algorithm.  Using it an entry in the "g"
 
57
    // table is looked up, which is added to the second hash value and
 
58
    // mapping it to the interval [0, n-1] without holes or duplicates.
 
59
    h1 = mixh10h1h12(hi->b, hi->p1, hi->p2, h1 % hi->m);
 
60
 
 
61
    // The "g" table may contain 16 or 32 bit entries depending on the
 
62
    // number of buckets; up to 2 ^ 16 it is enough to store 16 bit.
 
63
    switch (hi->g_size) {
 
64
        case 16:
 
65
        g = hi->g[h1];
 
66
        break;
 
67
 
 
68
        case 32:
 
69
        g = hi->g[h1 * 2] + (hi->g[h1*2 + 1] << 16);
 
70
        break;
 
71
 
 
72
        default:
 
73
        return (void*) 0;
 
74
    }
 
75
 
 
76
    // Calculate the second hash value and the final bucket number.
 
77
    h2 = compute_hash(&hi->h2, key, keylen, (void*)0) % hi->m;
 
78
    return hash_search_cmph(L, hi2, datalen, hash_value, (h2 + g) % hi->m);
 
79
}
 
80
 
 
81