Mercurial > repos > clustalomega > clustalomega
annotate clustalomega/clustal-omega-0.2.0/src/squid/gki.c @ 0:ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
author | clustalomega |
---|---|
date | Tue, 07 Jun 2011 17:04:25 -0400 |
parents | |
children |
rev | line source |
---|---|
0
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
1 /***************************************************************** |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
2 * SQUID - a library of functions for biological sequence analysis |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
3 * Copyright (C) 1992-2002 Washington University School of Medicine |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
4 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
5 * This source code is freely distributed under the terms of the |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
6 * GNU General Public License. See the files COPYRIGHT and LICENSE |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
7 * for details. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
8 *****************************************************************/ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
9 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
10 /* gki.c |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
11 * SRE, Sat May 1 14:49:08 1999 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
12 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
13 * "generic key index" module: emulation of Perl hashes. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
14 * Maps keys (ASCII char strings) to array index. Dynamically |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
15 * resizes the hash table. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
16 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
17 * Limitations: |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
18 * - hash table can only grow; no provision for deleting keys |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
19 * or downsizing the hash table. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
20 * - Maximum hash table size set at 100003. Performance |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
21 * will degrade for key sets much larger than this. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
22 * - Assumes that integers are 32 bits (or greater). |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
23 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
24 * Defines a typedef'd structure: |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
25 * gki - a key index hash table. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
26 * Provides functions: |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
27 * GKIInit() - start a hash table. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
28 * GKIStoreKey() - store a new key, get a unique index. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
29 * GKIKeyIndex() - retrieve an existing key's index. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
30 * GKIFree() - free a hash table. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
31 * GKIStatus() - Debugging: prints internal status of a hash struct |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
32 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
33 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
34 * Note that there are no dependencies on squid; the gki.c/gki.h |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
35 * pair are base ANSI C and can be reused anywhere. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
36 ***************************************************************** |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
37 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
38 * API for storing/reading stuff: |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
39 * moral equivalent of Perl's $foo{$key} = whatever, $bar{$key} = whatever: |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
40 * #include "gki.h" |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
41 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
42 * gki *hash; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
43 * int idx; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
44 * char *key; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
45 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
46 * hash = GKIInit(); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
47 * (Storing:) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
48 * (foreach key) { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
49 * idx = GKIStoreKey(hash, key); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
50 * (reallocate foo, bar as needed) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
51 * foo[idx] = whatever; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
52 * bar[idx] = whatever; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
53 * } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
54 * (Reading:) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
55 * (foreach key) { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
56 * idx = GKIKeyIndex(hash, key); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
57 * if (idx == -1) {no_such_key; } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
58 * (do something with) foo[idx]; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
59 * (do something with) bar[idx]; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
60 * } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
61 * GKIFree(); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
62 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
63 ***************************************************************** |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
64 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
65 * Timings on wrasse for 45402 keys in /usr/dict/words using |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
66 * Tests/test_gki: |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
67 * 250 msec store (6 usec/store) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
68 * 140 msec retrieve (3 usec/retrieve) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
69 * and using the 13408 names of Pfam's GP120.full alignment: |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
70 * 70 msec store (5 usec/store) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
71 * 50 msec retrieve (4 usec/retrieve) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
72 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
73 * RCS $Id: gki.c 217 2011-03-19 10:27:10Z andreas $ (Original squid RCS Id: gki.c,v 1.3 2000/12/21 23:42:59 eddy Exp) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
74 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
75 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
76 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
77 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
78 #include <stdio.h> |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
79 #include <stdlib.h> |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
80 #include <string.h> |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
81 #include <limits.h> |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
82 #include "squid.h" |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
83 #include "gki.h" |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
84 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
85 /* |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
86 * Best hash table sizes are prime numbers (see Knuth vol 3, Sorting |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
87 * and Searching). |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
88 * gki_primes[] defines the ascending order of hash table sizes |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
89 * that we use in upsizing the hash table dynamically. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
90 * useful site for testing primes: |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
91 * http://www.idbsu.edu/people/jbrennan/algebra/numbers/sieve.html |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
92 * Because of the way gki_hashvalue works, the largest number |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
93 * must be < INT_MAX / 128 / 128 : 131072 on a 32 bit machine. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
94 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
95 static int gki_primes[] = { 101, 1009, 10007, 100003 }; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
96 #define GKI_NPRIMES 4 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
97 #define GKI_ALPHABETSIZE 128 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
98 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
99 static GKI *gki_alloc(int primelevel); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
100 static int gki_hashvalue(GKI *hash, char *key); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
101 static int gki_upsize(GKI *old); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
102 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
103 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
104 /* Function: GKIInit() |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
105 * Date: SRE, Sat May 1 11:12:24 1999 [May Day geek-out] |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
106 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
107 * Purpose: Initialize a hash table for key indexing. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
108 * Simply a wrapper around a level 0 gki_alloc(). |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
109 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
110 * Args: (void) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
111 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
112 * Returns: An allocated hash table structure. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
113 * Caller frees with GKIFree(). |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
114 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
115 GKI * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
116 GKIInit(void) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
117 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
118 GKI *hash; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
119 hash = gki_alloc(0); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
120 return hash; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
121 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
122 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
123 /* Function: GKIFree() |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
124 * Date: SRE, Sat May 1 11:13:26 1999 [May Day geek-out] |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
125 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
126 * Purpose: Free a key index hash table. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
127 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
128 * Args: hash - the gki structure |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
129 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
130 * Returns: (void). |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
131 * hash table is destroyed. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
132 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
133 void |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
134 GKIFree(GKI *hash) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
135 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
136 struct gki_elem *ptr; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
137 int i; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
138 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
139 if (hash == NULL) return; /* tolerate a NULL */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
140 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
141 for (i = 0; i < hash->nhash; i++) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
142 while (hash->table[i] != NULL) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
143 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
144 ptr = hash->table[i]->nxt; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
145 /* NULL keys can occur after we've gki_upsize'd */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
146 if (hash->table[i]->key != NULL) free(hash->table[i]->key); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
147 free(hash->table[i]); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
148 hash->table[i] = ptr; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
149 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
150 free(hash->table); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
151 free(hash); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
152 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
153 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
154 /* Function: GKIStoreKey() |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
155 * Date: SRE, Sat May 1 11:16:48 1999 [May Day geek-out] |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
156 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
157 * Purpose: Store a key in the key index hash table. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
158 * Associate it with a unique "key index", counting |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
159 * from 0. (It's this index that lets us map |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
160 * the hashed keys to indexed C arrays, (clumsily) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
161 * emulating Perl's hashes.) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
162 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
163 * Does *not* check to see if the key's already |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
164 * in the table, so it's possible to store multiple |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
165 * copies of a key with different indices; probably |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
166 * not what you want, so if you're not sure the |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
167 * key is unique, check the table first with |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
168 * GKIKeyIndex(). |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
169 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
170 * Args: hash - GKI structure to store the key in |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
171 * key - string to store |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
172 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
173 * Returns: the new key's index. Since it's always the |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
174 * last one in the current array, this index is |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
175 * just hash->nkeys-1. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
176 * On a malloc failure, returns -1. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
177 * hash table is modified. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
178 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
179 int |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
180 GKIStoreKey(GKI *hash, char *key) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
181 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
182 int val; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
183 struct gki_elem *ptr; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
184 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
185 val = gki_hashvalue(hash, key); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
186 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
187 ptr = hash->table[val]; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
188 hash->table[val] = MallocOrDie(sizeof(struct gki_elem)); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
189 hash->table[val]->key = MallocOrDie(sizeof(char) * (strlen(key)+1)); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
190 strcpy(hash->table[val]->key, key); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
191 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
192 hash->table[val]->idx = hash->nkeys; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
193 hash->table[val]->nxt = ptr; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
194 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
195 hash->nkeys++; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
196 /* time to upsize? */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
197 if (hash->nkeys > 3*hash->nhash && hash->primelevel < GKI_NPRIMES-1) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
198 gki_upsize(hash); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
199 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
200 return hash->nkeys-1; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
201 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
202 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
203 /* Function: GKIKeyIndex() |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
204 * Date: SRE, Sat May 1 11:20:42 1999 [May Day geek-out] |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
205 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
206 * Purpose: Look up a key in the hash table. Return |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
207 * its index (0..nkeys-1), else -1 if the key |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
208 * isn't in the hash (yet). |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
209 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
210 * Args: hash - the GKI hash table to search in |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
211 * key - the key to look up |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
212 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
213 * Returns: -1 if key is not found; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
214 * index of key if it is found (range 0..nkeys-1). |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
215 * hash table is unchanged. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
216 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
217 int |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
218 GKIKeyIndex(GKI *hash, char *key) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
219 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
220 struct gki_elem *ptr; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
221 int val; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
222 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
223 val = gki_hashvalue(hash, key); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
224 for (ptr = hash->table[val]; ptr != NULL; ptr = ptr->nxt) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
225 if (strcmp(key, ptr->key) == 0) return ptr->idx; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
226 return -1; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
227 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
228 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
229 /* Function: GKIStatus() |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
230 * Date: SRE, Sat May 1 11:11:13 1999 [St. Louis] |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
231 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
232 * Purpose: (DEBUGGING) How are we doing? Calculate some |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
233 * simple statistics for the hash table. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
234 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
235 * Args: hash - the GKI hash table to look at |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
236 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
237 * Returns: (void) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
238 * Prints diagnostics on stdout. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
239 * hash table is unchanged. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
240 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
241 void |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
242 GKIStatus(GKI *hash) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
243 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
244 struct gki_elem *ptr; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
245 int i; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
246 int nkeys; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
247 int nempty = 0; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
248 int maxkeys = -1; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
249 int minkeys = INT_MAX; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
250 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
251 for (i = 0; i < hash->nhash; i++) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
252 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
253 nkeys = 0; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
254 for (ptr = hash->table[i]; ptr != NULL; ptr = ptr->nxt) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
255 nkeys++; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
256 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
257 if (nkeys == 0) nempty++; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
258 if (nkeys > maxkeys) maxkeys = nkeys; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
259 if (nkeys < minkeys) minkeys = nkeys; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
260 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
261 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
262 printf("Total keys: %d\n", hash->nkeys); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
263 printf("Hash table size: %d\n", hash->nhash); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
264 printf("Average occupancy: %.1f\n", (float) hash->nkeys / (float) hash->nhash); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
265 printf("Unoccupied slots: %d\n", nempty); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
266 printf("Most in one slot: %d\n", maxkeys); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
267 printf("Least in one slot: %d\n", minkeys); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
268 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
269 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
270 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
271 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
272 /* Function: gki_alloc() |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
273 * Date: SRE, Sat May 1 11:55:47 1999 [May Day geek-out] |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
274 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
275 * Purpose: Allocate a hash table structure with the |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
276 * size given by primelevel. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
277 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
278 * Args: primelevel - level 0..GKI_NPRIMES-1, specifying |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
279 * the size of the table; see gki_primes[] |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
280 * array. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
281 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
282 * Returns: An allocated hash table structure. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
283 * Caller frees with GKIFree(). |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
284 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
285 static GKI * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
286 gki_alloc(int primelevel) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
287 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
288 GKI *hash; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
289 int i; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
290 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
291 if (primelevel < 0 || primelevel >= GKI_NPRIMES) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
292 Die("bad primelevel in gki_alloc()"); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
293 hash = MallocOrDie(sizeof(GKI)); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
294 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
295 hash->primelevel = primelevel; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
296 hash->nhash = gki_primes[hash->primelevel]; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
297 hash->table = MallocOrDie(sizeof(struct gki_elem) * hash->nhash); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
298 for (i = 0; i < hash->nhash; i++) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
299 hash->table[i] = NULL; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
300 hash->nkeys = 0; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
301 return hash; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
302 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
303 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
304 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
305 /* Function: gki_hashvalue() |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
306 * Date: SRE, Sat May 1 11:14:10 1999 [May Day geek-out] |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
307 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
308 * Purpose: Calculate the hash value for a key. Usually |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
309 * we expect a one-word key, but the function will |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
310 * hash any ASCII string effectively. The hash function |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
311 * is a simple one (see p. 233 of Sedgewick, |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
312 * Algorithms in C). |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
313 * Slightly optimized: does two characters at a time |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
314 * before doing the modulo; this gives us a significant |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
315 * speedup. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
316 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
317 * Args: hash - the gki structure (we need to know the hash table size) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
318 * key - a string to calculate the hash value for |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
319 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
320 * Returns: a hash value, in the range 0..hash->nhash-1. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
321 * hash table is unmodified. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
322 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
323 static int |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
324 gki_hashvalue(GKI *hash, char *key) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
325 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
326 int val = 0; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
327 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
328 for (; *key != '\0'; key++) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
329 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
330 val = GKI_ALPHABETSIZE*val + *key; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
331 if (*(++key) == '\0') { val = val % hash->nhash; break; } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
332 val = (GKI_ALPHABETSIZE*val + *key) % hash->nhash; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
333 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
334 return val; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
335 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
336 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
337 /* Function: gki_upsize() |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
338 * Date: SRE, Sat May 1 11:46:07 1999 [May Day geek-out] |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
339 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
340 * Purpose: Grow the hash table to the next available size. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
341 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
342 * Args: old - the GKI hash table to reallocate. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
343 * |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
344 * Returns: 1 on success (the hash table is changed); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
345 * 0 on failure; the table is already at its maximum size, |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
346 * and the hash table is returned unchanged. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
347 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
348 static int |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
349 gki_upsize(GKI *old) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
350 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
351 GKI *new; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
352 int i; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
353 struct gki_elem *optr; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
354 struct gki_elem *nptr; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
355 int val; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
356 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
357 if (old->primelevel >= GKI_NPRIMES-1) return 0; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
358 new = gki_alloc(old->primelevel+1); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
359 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
360 /* Read the old, store in the new, while *not changing* |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
361 * any key indices. Because of the way the lists are |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
362 * treated as LIFO stacks, all the lists are reversed |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
363 * in the new structure. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
364 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
365 for (i = 0; i < old->nhash; i++) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
366 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
367 optr = old->table[i]; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
368 while (optr != NULL) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
369 { |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
370 val = gki_hashvalue(new, optr->key); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
371 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
372 nptr = new->table[val]; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
373 new->table[val] = optr; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
374 optr = optr->nxt; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
375 new->table[val]->nxt = nptr; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
376 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
377 } |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
378 free(old->table); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
379 |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
380 /* Now swap within the interior of the structures, so the old |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
381 * structure is updated to the new structure. |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
382 * (nkeys is identical, so we don't need to swap that element.) |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
383 */ |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
384 old->primelevel = new->primelevel; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
385 old->nhash = new->nhash; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
386 old->table = new->table; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
387 free(new); |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
388 return 1; |
ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
clustalomega
parents:
diff
changeset
|
389 } |