clustalomega: clustalomega/clustal-omega-0.2.0/src/squid/gki.c annotate

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_ALPHABETSIZEval + 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_ALPHABETSIZEval + 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 }

Mercurial > repos > clustalomega > clustalomega

annotate clustalomega/clustal-omega-0.2.0/src/squid/gki.c @ 0:ff1768533a07