Code:
// util.h //////////////////////////////////////////////
#ifndef UTIL_H__
#define UTIL_H__
#include <stddef.h> // size_t
void die(const char *msg);
void *xmalloc(size_t sz);
char *xstrdup(const char *s);
#endif
// util.c //////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#include "util.h"
void die(const char *msg) {
if (msg[0] == '!')
perror(msg + 1);
else
fprintf(stderr, "Error: %s\n", msg);
exit(EXIT_FAILURE);
}
void *xmalloc(size_t sz) {
void *p = malloc(sz);
if (!p) die("!xmalloc");
return p;
}
char *xstrdup(const char *s) {
return strcpy(xmalloc(strlen(s) + 1), s);
}
// hashtable.h //////////////////////////////////////////////
#ifndef HASHTABLE_H__
#define HASHTABLE_H__
#include <stddef.h> // size_t
typedef struct HTEntry HTEntry;
typedef struct HashTable HashTable;
HashTable *ht_create (size_t);
void ht_delete(HashTable*);
void ht_add(HashTable*, const char*, const char*,
const char*, unsigned int);
void ht_remove(HashTable*, const char*);
HTEntry *ht_get(HashTable*, const char*);
#endif
// hashtable.c //////////////////////////////////////////////
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
//#include "hashtable.h"
//#include "util.h"
struct HTEntry {
char *key, *type, *value;
unsigned int line;
struct HTEntry *next;
};
struct HashTable {
size_t size, num_items;
struct HTEntry **items;
struct HashTable *prev;
};
static unsigned long hash (const char* key) {
unsigned long sum = 0;
for ( ; *key; key++) {
if (!isalpha(*key)) die("bad key");
sum = (sum * 65599) ^ (toupper(*key) - 'A');
}
return sum;
}
static void grow(HashTable *ht) {
HashTable *temp, swap;
HTEntry *ent;
temp = ht_create(ht->size * 2);
for (size_t i = 0; i < ht->size; i++)
for (ent = ht->items[i]; ent; ent = ent->next)
ht_add(temp, ent->key, ent->type, ent->value,
ent->line);
swap = *ht;
*ht = *temp;
*temp = swap;
ht_delete(temp);
}
HashTable *ht_create(size_t size) {
HashTable *ht;
if (size < 1) return NULL;
ht = xmalloc(sizeof(HashTable));
ht->size = size;
ht->num_items = 0;
ht->items = xmalloc(size * sizeof(HTEntry*));
for (size_t i = 0; i < size; i++)
ht->items[i] = NULL;
ht->prev = NULL;
return ht;
}
void ht_delete(HashTable* ht) {
HTEntry *ent, *next;
for (size_t i = 0; i < ht->size; i++)
for (ent = ht->items[i]; ent; ent = next) {
next = ent->next;
free(ent->key);
free(ent->type);
free(ent->value);
free(ent);
}
free(ht->items);
free(ht);
}
void ht_add(HashTable *ht,
const char *key,
const char *type,
const char *value,
unsigned int line) {
assert(key);
assert(type);
assert(value);
HTEntry *ent = xmalloc(sizeof(HTEntry));
ent->key = xstrdup(key);
ent->type = xstrdup(type);
ent->value = xstrdup(value);
ent->line = line;
unsigned long elem = hash(key) % ht->size;
ent->next = ht->items[elem];
ht->items[elem] = ent;
ht->num_items++;
if (ht->num_items > ht->size * 2)
grow(ht);
}
void ht_remove(HashTable *ht, const char *key) {
HTEntry **prev, *ent;
unsigned long elem = hash(key) % ht->size;
for (prev = &ht->items[elem]; *prev; prev = &(*prev)->next) {
if (!strcmp((*prev)->key, key)) {
ent = *prev;
*prev = ent->next;
free(ent->key);
free(ent->type);
free(ent->value);
free(ent);
ht->num_items--;
return;
}
}
}
HTEntry *ht_get(HashTable *ht, const char *key) {
unsigned long elem = hash(key) % ht->size;
for (HTEntry *ent = ht->items[elem]; ent; ent = ent->next)
if (!strcmp(ent->key, key))
return ent;
return NULL;
}
void ht_stats(HashTable *ht, int show_detail) {
size_t used = 0, maxcnt = 0;
for (size_t i = 0; i < ht->size; i++) {
if (show_detail) printf("%4zu:\n", i);
HTEntry *e = ht->items[i];
if (!e) {
if (show_detail) printf(" null\n");
}
else {
size_t cnt = 0;
used++;
for ( ; e; e = e->next) {
cnt++;
if (show_detail)
printf(" key: %s\n", e->key);
}
if (cnt > maxcnt) maxcnt = cnt;
}
}
printf("size: %4zu\n", ht->size);
printf("num_items: %4zu\n", ht->num_items);
printf("Used buckets: %zu out of %zu\n", used, ht->size);
printf("Max bucket size: %zu\n", maxcnt);
printf("Avg per used bucket: %f\n",
(double)ht->num_items / used);
}
// main.c ///////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
//#include "hashtable.h"
#define HT_SIZE 10
int main() {
const char *s[] = {
"ALPHA", "BETA", "GAMMA", "DELTA",
"EPSILON", "ZETA", "ETA", "THETA",
"IOTA", "KAPPA", "LAMBDA", "MU",
"NU", "XI", "OMICRON", "PI",
"RHO", "SIGMA", "TAU", "UPSILON",
"PHI", "CHI", "PSI", "OMEGA",
#if 0
"HYDROGEN", "HELIUM", "LITHIUM", "BERYLLIUM",
"BORON", "CARBON", "NITROGEN", "OXYGEN",
"FLUORINE", "NEON", "SODIUM", "MAGNESIUM",
"ALUMINUM", "SILICON", "PHOSPHORUS", "SULFUR",
"CHLORINE", "ARGON",
#endif
};
size_t sz = sizeof s / sizeof s[0];
HashTable *ht = ht_create(HT_SIZE);
for (size_t i = 0; i < sz; i++)
ht_add(ht, s[i], "xxx", "yyy", 1);
// Delete every second string in s
#if 0
for (size_t i = 0; i < sz; i += 2)
ht_remove(ht, s[i]);
#endif
ht_stats(ht, 1);
ht_delete(ht);
return 0;
}
Originally Posted by algorism
