1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
|
/* p 144 - 147 K&R */
/* C:\JPD\AStyle.exe --style=vtk --indent=spaces=2 --pad-oper --pad-comma --align-pointer=name --add-brackets --indent-switches --delete-empty-lines */
/* hash : form hash value from string s */
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#define HASHSIZE 201
static struct nlist *hashtab[HASHSIZE] ; /* pointer table */
struct nlist *lookup (char *s);
struct nlist *install (char *name, char *defn);
unsigned hash (char *s);
char *strduup(char *s);
int i = 0;
unsigned char stat[100];
struct nlist
{
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn; /* replacement text */
};
/* make a duplicate of s */
char *strduup(char *s)
{
char *p;
p = (char *) malloc ((strlen(s)+1)); /* + 1 for '\0' */
if (p != NULL)
strcpy(p, s);
return p;
}
/* install: put (name defn) in hashtab */
struct nlist *install (char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL)
{
np = (struct nlist *) malloc(sizeof(*np)); /* not found */
if (np == NULL || (np->name = strduup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
}else /* already there */
free ((void *) np->defn); /* free previous defn */
if ((np->defn = strduup(defn)) == NULL)
return NULL;
printf("defn= %p name = %p", np->defn, np->name);
return np;
}
/* lookup ; look for s in hashtab */
struct nlist *lookup (char *s)
{
struct nlist *np;
for (np =hashtab[hash(s)]; np != NULL ; np = np->next)
if (strcmp(s, np->name ) == 0)
return np; /* found */
return NULL; /* not found */
}
int main(void)
{
char unhello [] = "Hello, world.";
int j;
install (unhello, (char *)hash ("Hello, world."));
hash ("hello, world.");
hash ("Helo, world.");
hash ("Hella, world.");
hash ("Hello, World.");
hash ("Hello, WOrld.");
hash ("Hello, worldd.");
hash ("Hello, wfrld.");
hash ("Hello, worf.");
hash ("Hlo, world.");
hash ("Hello, world.");
printf("\n\nstat = ");
for (j =0;j<i ;j++ )
{
printf("\t%d", stat[j]);
}
return 0;
}
unsigned hash (char *s)
{
unsigned hashval;
/* printf("\nhashval = %u\n", hashval); */
for (hashval = 0; *s != '\0' ; s++ )
{
hashval += *s + (31 * hashval);
printf("\n*s=%u + 31 * hashval = %u\t\t\t s = %s\n", *s, hashval, s );
}
stat[i] = (hashval % HASHSIZE);
i++;
printf("\n\n\t\ti = %d\t\t\tmodulo = %d\n", i, stat[i-1]);
return hashval % HASHSIZE;
}
int undef(char * name) {
struct nlist * np1, * np2;
if ((np1 = lookup(name)) == NULL) /* name not found */
return 1;
for ( np1 = np2 = hashtab[hash(name)]; np1 != NULL;
np2 = np1, np1 = np1->next ) {
if ( strcmp(name, np1->name) == 0 ) { /* name found */
/* Remove node from list */
if ( np1 == np2 )
hashtab[hash(name)] = np1->next;
else
np2->next = np1->next;
/* Free memory */
free(np1->name);
free(np1->defn);
free(np1);
return 0;
}
}
return 1; /* name not found */
} |
Partager