c10-1.c

/* code: c10-1.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_TABLE_ERROR (-1)
#define DATA_SIZE 10
#define HASH_TABLE_SIZE 10

struct hash_node_type {
  int data;
  int key;
  struct hash_node_type *next;
};
typedef struct hash_node_type HASH_NODE;


struct hash_table_type {
  struct hash_node_type **bucket;
  int size;
  int num;
};
typedef struct hash_table_type HASH_TABLE;

/* ------------------------------------------- */
int hash_function (HASH_TABLE * table, int key) {
  return key % table->size;
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE * table, int table_size) {
  table->num = 0;
  table->size = table_size;
  table->bucket = calloc (table->size, sizeof (HASH_NODE *));
}

/* ------------------------------------------- */
int hash_table_search (HASH_TABLE * table, int key) {
  int h;
  HASH_NODE *node;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node != NULL; node = node->next) {
    if (node->key == key) {
      break;
    }
  }

  if (node) {
    return node->data;
  }
  else {
    return HASH_TABLE_ERROR;
  }
}

/* ------------------------------------------- */
int hash_table_insert (HASH_TABLE * table, int key, int data) {
  int tmp;
  HASH_NODE *node;
  int h;

  if ((tmp = hash_table_search (table, key)) != HASH_TABLE_ERROR) {
    return (tmp);
  }

  h = hash_function (table, key);
  node = malloc (sizeof (HASH_NODE));
  node->data = data;
  node->key = key;
  node->next = table->bucket[h];
  table->bucket[h] = node;
  table->num++;

  return HASH_TABLE_ERROR;
}

/* ------------------------------------------- */
int hash_table_delete (HASH_TABLE * table, int key) {
  HASH_NODE *node, *node_temp;
  int data;
  int h;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node; node = node->next) {
    if (node->key == key)
      break;
  }

  if (node == NULL)
    return HASH_TABLE_ERROR;

  if (node == table->bucket[h]) {
    table->bucket[h] = node->next;
  }
  else {
    for (node_temp = table->bucket[h]; node_temp && node_temp->next;
	 node_temp = node_temp->next) {
      if (node_temp->next == node)
	break;
    }
    node_temp->next = node->next;
  }
  data = node->data;
  free (node);
  return (data);
}

/* ------------------------------------------- */
void hash_table_free (HASH_TABLE * table) {
  HASH_NODE *node, *node_temp;
  int i;

  for (i = 0; i < table->size; i++) {
    node = table->bucket[i];
    while (node != NULL) {
      node_temp = node;
      node = node->next;
      free (node_temp);
    }
  }

  if (table->bucket != NULL) {
    free (table->bucket);
    memset (table, 0, sizeof (HASH_TABLE));
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE * table) {
  HASH_NODE *node;
  int i;
  printf ("------------------------\n");
  for (i = 0; i < table->size; i++) {
    printf ("%02d: ", i);
    node = table->bucket[i];
    while (node != NULL) {
      printf ("%2d ", node->data);
      node = node->next;
    }
    printf ("\n");
  }
  printf ("------------------------\n");
}

/* ------------------------------------------- */
void hash_table_info (HASH_TABLE * table) {
  printf ("--- hash table info ---\n");
  printf ("buckets: %d \n", table->size);
  printf ("num: %d \n", table->num);
  printf ("------------------------\n");
}

/* ------------------------------------------- */
int main () {
  int i, data;
  HASH_TABLE *table;
  int key[DATA_SIZE];

  table = malloc (sizeof (HASH_TABLE));
  hash_table_init (table, HASH_TABLE_SIZE);

  for (i = 0; i < DATA_SIZE; i++) {
    data = rand () % (DATA_SIZE * 100);
    key[i] = data;
    printf ("(insert) data:%d   key:%d\n", data, key[i]);
    hash_table_insert (table, key[i], data);
  }

  hash_table_info (table);
  hash_table_display (table);

  printf ("[search] key:%d -> data:%d\n", key[0],
	  hash_table_search (table, key[0]));
  printf ("[search] key:%d -> data:%d\n", key[1],
	  hash_table_search (table, key[1]));
  printf ("[search] key:%d -> data:%d\n", key[2],
	  hash_table_search (table, key[2]));

  hash_table_free (table);

  free (table);

  return 0;
}

c10-2.c

/* code: c10-2.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------ */
long int hash_kr (char *str) {
  long int hash;
  int c;

  hash = 0;
  while ((c = *str++)) {
    hash += c;
  }
  return hash;
}

/* ------------------------------------------ */
int main () {
  int i;
  char *key[] = {
    "alpha", "bravo", "charlie", "delta",
    "echo", "foxtrot", "golf", "hotel",
    "india", "juliet", "kilo", "lima",
    "mike", "november", "oscar", "papa",
    "quebec", "romeo", "sierra", "tango",
    "uniform", "victor", "whisky", "x-ray",
    "yankee", "zulu"
  };

  for (i = 0; i < 26; i++) {
    printf ("%8s: %ld\n", key[i], hash_kr (key[i]));
  }

  return 0;
}

q10-1.c

/* code: q10-1.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------ */
int is_prime (int number) {
  int i, prime;

  prime = 1;
  if (number < 2)
    return 0;
  for (i = 2; i < number; i++) {
    if ((number % i) == 0) {
      prime = 0;
    }
  }
  return prime;
}

/* ------------------------------------------ */
int main () {
  int i, prime;

  for (i = 0; i < 100; i++) {
    prime = is_prime (i);

    if (prime == 1) {
      printf ("%d ", i);
    }
  }

  return 0;
}

q10-2.c

/* code: q10-2.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_TABLE_ERROR (-1)
#define DATA_SIZE 10
#define HASH_TABLE_SIZE 13

struct hash_node_type {
  int data;
  int key;
  struct hash_node_type *next;
};
typedef struct hash_node_type HASH_NODE;


struct hash_table_type {
  struct hash_node_type **bucket;
  int size;
  int num;
};
typedef struct hash_table_type HASH_TABLE;

/* ------------------------------------------- */
int hash_function (HASH_TABLE * table, int key) {
  return key % table->size;
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE * table, int table_size) {
  table->num = 0;
  table->size = table_size;
  table->bucket = calloc (table->size, sizeof (HASH_NODE *));
}

/* ------------------------------------------- */
int hash_table_search (HASH_TABLE * table, int key) {
  int h;
  HASH_NODE *node;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node != NULL; node = node->next) {
    if (node->key == key) {
      break;
    }
  }

  if (node) {
    return node->data;
  }
  else {
    return HASH_TABLE_ERROR;
  }
}

/* ------------------------------------------- */
int hash_table_insert (HASH_TABLE * table, int key, int data) {
  int tmp;
  HASH_NODE *node;
  int h;

  if ((tmp = hash_table_search (table, key)) != HASH_TABLE_ERROR) {
    return (tmp);
  }

  h = hash_function (table, key);
  node = malloc (sizeof (HASH_NODE));
  node->data = data;
  node->key = key;
  node->next = table->bucket[h];
  table->bucket[h] = node;
  table->num++;

  return HASH_TABLE_ERROR;
}

/* ------------------------------------------- */
int hash_table_delete (HASH_TABLE * table, int key) {
  HASH_NODE *node, *node_temp;
  int data;
  int h;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node; node = node->next) {
    if (node->key == key)
      break;
  }

  if (node == NULL)
    return HASH_TABLE_ERROR;

  if (node == table->bucket[h]) {
    table->bucket[h] = node->next;
  }
  else {
    for (node_temp = table->bucket[h]; node_temp && node_temp->next;
	 node_temp = node_temp->next) {
      if (node_temp->next == node)
	break;
    }
    node_temp->next = node->next;
  }
  data = node->data;
  free (node);
  return (data);
}

/* ------------------------------------------- */
void hash_table_free (HASH_TABLE * table) {
  HASH_NODE *node, *node_temp;
  int i;

  for (i = 0; i < table->size; i++) {
    node = table->bucket[i];
    while (node != NULL) {
      node_temp = node;
      node = node->next;
      free (node_temp);
    }
  }

  if (table->bucket != NULL) {
    free (table->bucket);
    memset (table, 0, sizeof (HASH_TABLE));
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE * table) {
  HASH_NODE *node;
  int i;
  printf ("------------------------\n");
  for (i = 0; i < table->size; i++) {
    printf ("%02d: ", i);
    node = table->bucket[i];
    while (node != NULL) {
      printf ("%2d(%d) ", node->data, node->key);
      node = node->next;
    }
    printf ("\n");
  }
  printf ("------------------------\n");
}

/* ------------------------------------------- */
void hash_table_info (HASH_TABLE * table) {
  printf ("--- hash table info ---\n");
  printf ("buckets: %d \n", table->size);
  printf ("num: %d \n", table->num);
  printf ("------------------------\n");
}

/* ------------------------------------------- */
int main () {
  int i, data;
  HASH_TABLE *table;
  int key[DATA_SIZE];

  table = malloc (sizeof (HASH_TABLE));
  hash_table_init (table, HASH_TABLE_SIZE);

  for (i = 0; i < DATA_SIZE; i++) {
    key[i] = rand () % (DATA_SIZE * 100);
    data = i + 10;
    printf ("(insert) data:%d   key:%d\n", data, key[i]);
    hash_table_insert (table, key[i], data);
  }

  hash_table_info (table);
  hash_table_display (table);

  printf ("[search] key:%d -> data:%d\n", key[0],
	  hash_table_search (table, key[0]));
  printf ("[search] key:%d -> data:%d\n", key[1],
	  hash_table_search (table, key[1]));
  printf ("[search] key:%d -> data:%d\n", key[2],
	  hash_table_search (table, key[2]));

  for (i = 0; i < (DATA_SIZE / 2); i++) {
    hash_table_delete (table, key[i]);
  }

  hash_table_display (table);

  hash_table_free (table);

  free (table);

  return 0;
}

q10-3.c

/* code: q10-3.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_TABLE_ERROR (-1)
#define DATA_SIZE       1000000
#define HASH_TABLE_SIZE 1500000
// #define HASH_TABLE_SIZE 1000000
// #define HASH_TABLE_SIZE 10000

struct hash_node_type {
  int data;
  int key;
  struct hash_node_type *next;
};
typedef struct hash_node_type HASH_NODE;


struct hash_table_type {
  struct hash_node_type **bucket;
  int size;
  int num;
};
typedef struct hash_table_type HASH_TABLE;

/* ------------------------------------------- */
int hash_function (HASH_TABLE * table, int key) {
  return key % table->size;
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE * table, int table_size) {
  table->num = 0;
  table->size = table_size;
  table->bucket = calloc (table->size, sizeof (HASH_NODE *));
}

/* ------------------------------------------- */
int hash_table_search (HASH_TABLE * table, int key) {
  int h;
  HASH_NODE *node;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node != NULL; node = node->next) {
    if (node->key == key) {
      break;
    }
  }

  if (node) {
    return node->data;
  }
  else {
    return HASH_TABLE_ERROR;
  }
}

/* ------------------------------------------- */
int hash_table_insert (HASH_TABLE * table, int key, int data) {
  int tmp;
  HASH_NODE *node;
  int h;

  if ((tmp = hash_table_search (table, key)) != HASH_TABLE_ERROR) {
    return (tmp);
  }

  h = hash_function (table, key);
  node = malloc (sizeof (HASH_NODE));
  node->data = data;
  node->key = key;
  node->next = table->bucket[h];
  table->bucket[h] = node;
  table->num++;

  return HASH_TABLE_ERROR;
}

/* ------------------------------------------- */
int hash_table_delete (HASH_TABLE * table, int key) {
  HASH_NODE *node, *node_temp;
  int data;
  int h;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node; node = node->next) {
    if (node->key == key)
      break;
  }

  if (node == NULL)
    return HASH_TABLE_ERROR;

  if (node == table->bucket[h]) {
    table->bucket[h] = node->next;
  }
  else {
    for (node_temp = table->bucket[h]; node_temp && node_temp->next;
	 node_temp = node_temp->next) {
      if (node_temp->next == node)
	break;
    }
    node_temp->next = node->next;
  }
  data = node->data;
  free (node);
  return (data);
}

/* ------------------------------------------- */
void hash_table_free (HASH_TABLE * table) {
  HASH_NODE *node, *node_temp;
  int i;

  for (i = 0; i < table->size; i++) {
    node = table->bucket[i];
    while (node != NULL) {
      node_temp = node;
      node = node->next;
      free (node_temp);
    }
  }

  if (table->bucket != NULL) {
    free (table->bucket);
    memset (table, 0, sizeof (HASH_TABLE));
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE * table) {
  HASH_NODE *node;
  int i;
  printf ("------------------------\n");
  for (i = 0; i < table->size; i++) {
    printf ("%02d: ", i);
    node = table->bucket[i];
    while (node != NULL) {
      printf ("%2d(%d) ", node->data, node->key);
      node = node->next;
    }
    printf ("\n");
  }
  printf ("------------------------\n");
}

/* ------------------------------------------- */
void hash_table_info (HASH_TABLE * table) {
  printf ("--- hash table info ---\n");
  printf ("buckets: %d \n", table->size);
  printf ("num: %d \n", table->num);
  printf ("------------------------\n");
}

/* ------------------------------------------- */
int main () {
  int i, data;
  HASH_TABLE *table;
  int key[DATA_SIZE];

  table = malloc (sizeof (HASH_TABLE));
  hash_table_init (table, HASH_TABLE_SIZE);

  for (i = 0; i < DATA_SIZE; i++) {
    key[i] = rand () % (DATA_SIZE * 100);
    data = i + 10;
    hash_table_insert (table, key[i], data);
  }

  hash_table_info (table);
  // hash_table_display (table);

  hash_table_free (table);

  free (table);

  return 0;
}

q10-4.c

/* code: q10-4.c   (v1.18.00) */
#include <stdio.h>

/* ------------------------------------------ */
long int hash_djb (char *str) {
  long int hash;
  int c;
  hash = 5381;
  while ((c = *str++)) {
    hash = ((hash << 5) + hash) + c;
  }
  return hash;
}

/* ------------------------------------------ */
int main () {
  int i;
  char *key[] = {
    "alpha", "bravo", "charlie", "delta",
    "echo", "foxtrot", "golf", "hotel",
    "india", "juliet", "kilo", "lima",
    "mike", "november", "oscar", "papa",
    "quebec", "romeo", "sierra", "tango",
    "uniform", "victor", "whisky", "x-ray",
    "yankee", "zulu"
  };

  for (i = 0; i < 26; i++) {
    printf ("%8s: %ld\n", key[i], hash_djb (key[i]));
  }

  return 0;
}

q10-5.c

/* code: q10-5.c   (v1.18.00) */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_TABLE_ERROR (-1)
#define DATA_SIZE 26
#define HASH_TABLE_SIZE 29

struct hash_node_type {
  int data;
  char *key;
  struct hash_node_type *next;
};
typedef struct hash_node_type HASH_NODE;


struct hash_table_type {
  struct hash_node_type **bucket;
  int size;
  int num;
};
typedef struct hash_table_type HASH_TABLE;

/* ------------------------------------------- */
int hash_function (HASH_TABLE * table, char *key) {
  int hash;
  int c;

  hash = 0;
  while ((c = *key++)) {
    hash += c;
  }

  return hash % table->size;
}

/* ------------------------------------------- */
void hash_table_init (HASH_TABLE * table, int table_size) {
  table->num = 0;
  table->size = table_size;
  table->bucket = calloc (table->size, sizeof (HASH_NODE *));
}

/* ------------------------------------------- */
int hash_table_search (HASH_TABLE * table, char *key) {
  int h;
  HASH_NODE *node;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node != NULL; node = node->next) {
    if (!strcmp (node->key, key)) {
      break;
    }
  }

  if (node) {
    return node->data;
  }
  else {
    return HASH_TABLE_ERROR;
  }
}

/* ------------------------------------------- */
int hash_table_insert (HASH_TABLE * table, char *key, int data) {
  int tmp;
  HASH_NODE *node;
  int h;

  if ((tmp = hash_table_search (table, key)) != HASH_TABLE_ERROR) {
    return (tmp);
  }

  h = hash_function (table, key);
  node = malloc (sizeof (HASH_NODE));
  node->data = data;
  node->key = key;
  node->next = table->bucket[h];
  table->bucket[h] = node;
  table->num++;

  return HASH_TABLE_ERROR;
}

/* ------------------------------------------- */
int hash_table_delete (HASH_TABLE * table, char *key) {
  HASH_NODE *node, *node_temp;
  int data;
  int h;

  h = hash_function (table, key);
  for (node = table->bucket[h]; node; node = node->next) {
    if (!strcmp (node->key, key))
      break;
  }

  if (node == NULL)
    return HASH_TABLE_ERROR;

  if (node == table->bucket[h]) {
    table->bucket[h] = node->next;
  }
  else {
    for (node_temp = table->bucket[h]; node_temp && node_temp->next;
	 node_temp = node_temp->next) {
      if (node_temp->next == node)
	break;
    }
    node_temp->next = node->next;
  }
  data = node->data;
  free (node);
  return (data);
}

/* ------------------------------------------- */
void hash_table_free (HASH_TABLE * table) {
  HASH_NODE *node, *node_temp;
  int i;

  for (i = 0; i < table->size; i++) {
    node = table->bucket[i];
    while (node != NULL) {
      node_temp = node;
      node = node->next;
      free (node_temp);
    }
  }

  if (table->bucket != NULL) {
    free (table->bucket);
    memset (table, 0, sizeof (HASH_TABLE));
  }
}

/* ------------------------------------------- */
void hash_table_display (HASH_TABLE * table) {
  HASH_NODE *node;
  int i;
  printf ("------------------------\n");
  for (i = 0; i < table->size; i++) {
    printf ("%02d: ", i);
    node = table->bucket[i];
    while (node != NULL) {
      printf ("%2d(%s) ", node->data, node->key);
      node = node->next;
    }
    printf ("\n");
  }
  printf ("------------------------\n");
}

/* ------------------------------------------- */
void hash_table_info (HASH_TABLE * table) {
  printf ("--- hash table stats ---\n");
  printf ("buckets: %d \n", table->size);
  printf ("num: %d \n", table->num);
  printf ("------------------------\n");
}

/* ------------------------------------------- */
int main () {
  int i;
  HASH_TABLE *table;
  static char *key[DATA_SIZE] = {
    "alpha", "bravo", "charlie", "delta",
    "echo", "foxtrot", "golf", "hotel",
    "india", "juliet", "kilo", "lima",
    "mike", "november", "oscar", "papa",
    "quebec", "romeo", "sierra", "tango",
    "uniform", "victor", "whisky", "x-ray",
    "yankee", "zulu"
  };

  table = malloc (sizeof (HASH_TABLE));
  hash_table_init (table, HASH_TABLE_SIZE);

  for (i = 0; i < DATA_SIZE; i++) {
    hash_table_insert (table, key[i], i);
  }

  hash_table_info (table);
  hash_table_display (table);

  printf ("search 'sierra' -> %d\n", hash_table_search (table, "sierra"));
  printf ("search 'kilo' -> %d\n", hash_table_search (table, "kilo"));
  printf ("search 'ouj' -> %d\n", hash_table_search (table, "ouj"));

  for (i = 0; i < (DATA_SIZE / 2); i++) {
    hash_table_delete (table, key[i]);
  }

  hash_table_display (table);

  hash_table_free (table);

  free (table);

  return 0;
}