HTable

About

HTable is a lightweight implementation of hash tables in C

Homepage

http://culot.org/public/Code/htable.html

Installation

1. Install the header file into your normal place for header files. E.g. ~/include
2. Install the man page into your normal place for man pages: E.g. ~/man/man3

Test program: keyvalue.c

There is also a test program mentioned on the homepage. The following simple test program uses HTable to implement a simple command interpreter. Commands can be of the following two forms:

KEY = VALUE

Assign VALUE to the symbol KEY,  possibly overwriting the old VALUE of KEY.

KEY

Print the current value of KEY, or show an error message if KEY is not yet defined.


The command interpreter is very simplistic -- no whitespace is allowed in the KEY or VALUE, and all tokens must be separated by at least one whitespace character.

Code Listing: keyvalue.c

 // ---------------------------------------------------------------------------  
 // keyvalue.c: Simple program to test/demonstrate htable  
 // 2012-12-23  
 // ---------------------------------------------------------------------------  
 // COMPILATION  
 //           gcc -Wall -std=gnu99 -o keyvalue keyvalue.c  
 // USAGE QUICKSTART  
 //           Run the program and then type the following example commands:  
 //          a = 123  
 //           b = 456  
 //          a  
 //          b  
 //          c  
 // ---------------------------------------------------------------------------  
 // ---------------------------------------------------------------------------  
   
 #include <stdio.h>  
 #include <string.h>  
 #include <stdbool.h>  
 #include <stdlib.h>  
 #include <assert.h>  
 #include <htable/htable.h>  
   
 // ---------------------------------------------------------------------------  
 // Begin Utilities declarations  
 // ---------------------------------------------------------------------------  
 // nullterm (s, n): null-terminate string s  
 // n: number of elements allocated to s  
 void nullterm(char *s, int n) {  
      s[n-1] = '\0';  
 }  
 // ---------------------------------------------------------------------------  
 // ---------------------------------------------------------------------------  
   
 // ---------------------------------------------------------------------------  
 // Begin Command declarations  
 // ---------------------------------------------------------------------------  
 #define COMMAND_KEYMAX 1000  
 #define COMMAND_VALUEMAX 1000  
 struct command_s {  
      enum {COMMAND_UNKNOWN = 0, COMMAND_ASSIGNMENT, COMMAND_RECALL} type;  
      char key[COMMAND_KEYMAX];  
      char value[COMMAND_VALUEMAX];  
      HTABLE_ENTRY (command_s);  
 };  
 typedef struct command_s command;  
   
 // command_get(c, tempbuf): Tokenize tempbuf into command c  
 // Return value: NULL on error  
 // c->type tells the type of command:  
 //          COMMAND_UNKNOWN: An error occured  
 //           COMMAND_ASSIGNMENT: A command such as "abc = 123"  
 //          COMMAND_RECALL: A command such as "abc"  
 void *command_get(command *c, char *tempbuf);  
   
 // command_print(c): Print command c  
 void *command_print(command *c);  
   
 // command_dup(c): Duplicate command c - analogue to strdup  
 command *command_dup(command *c);  
   
 // command_extract: needed for HTABLE  
 void command_extract (command *c, char **key, int *len) {  
      *key = c->key;  
      *len = strlen(c->key);  
 }  
   
 // command_compare: needed for HTABLE  
 int command_compare (command *c1, command *c2) {  
      return strcmp(c1->key, c2->key);  
 }  
 // ---------------------------------------------------------------------------  
 // ---------------------------------------------------------------------------  
   
 // ---------------------------------------------------------------------------  
 // Begin Main  
 // ---------------------------------------------------------------------------  
 #define BUFSIZE 100000  
 char buf[BUFSIZE] = "";  
 char buf_t[BUFSIZE] = "";  
   
 // Define def_book and def_table for use with HTABLE  
 #define HSIZE 100  
 HTABLE_HEAD(def_book, HSIZE, command_s) def_table =  
      HTABLE_INITIALIZER(&def_table);  
 HTABLE_GENERATE(def_book, command_s, command_extract, command_compare);  
   
 int main()  
 {  
      command *c = malloc(sizeof(command));  
      assert(c);  
             
      while (fgets(buf, BUFSIZE, stdin) != NULL) {  
           strcpy(buf_t, buf);  
           command_get(c, buf_t);  
           switch(c->type) {  
                case COMMAND_ASSIGNMENT:  
                // remove old element from hashtable if it exists  
                {  
                     command *celm = HTABLE_LOOKUP(def_book, &def_table, c);  
                     if (celm) {       
                          HTABLE_REMOVE(def_book, &def_table, celm);  
                          free(celm);  
                     }  
                }  
                // insert new element into hashtable  
                {  
                     command *cdup = command_dup(c);  
                     assert(cdup);  
                     HTABLE_INSERT(def_book, &def_table, cdup);  
                }  
                break;  
                case COMMAND_RECALL:  
                {  
                     command *celm = HTABLE_LOOKUP(def_book, &def_table, c);  
                     if (celm)  
                          printf("%s: %s\n", c->key, celm->value);  
                     else  
                          printf("%s is not defined\n", c->key);  
                }  
                break;  
                default:  
                     ;  
           }  
      }  
      free(c);  
      return 0;  
 }  
 // ---------------------------------------------------------------------------  
 // ---------------------------------------------------------------------------  
   
 // ---------------------------------------------------------------------------  
 // Begin Command definitions  
 // ---------------------------------------------------------------------------  
 #define WORDS_MAX 3  
 const char DELIM[] = " \n";  
 char *words[WORDS_MAX] = {""};  
   
 void *command_get(command *c, char *tempbuf)  
 {  
      // initialize command  
      strncpy(c->key, "(unknown)", COMMAND_KEYMAX);  
      nullterm(c->key, COMMAND_KEYMAX);  
      strncpy(c->value, "(unknown)", COMMAND_VALUEMAX);  
      nullterm(c->value, COMMAND_VALUEMAX);  
      c->type = COMMAND_UNKNOWN;  
        
      // tokenize  
      char *str = buf_t;  
      int wordscount = 0;  
      while (true) {  
           char *tok;  
           if ((tok = strtok(str, DELIM)) == NULL)  
                break; // no more tokens  
           str = NULL;  
           // save tokens  
           if (wordscount == WORDS_MAX) {  
                printf("commandline: Syntax error (expected: KEY or KEY = VALUE)\n");  
                return NULL;  
           }  
           words[wordscount++] = tok;  
      }  
      // process tokens and assign to c  
      if (wordscount == 1) {  
           c->type = COMMAND_RECALL;  
           strncpy(c->key, words[0], COMMAND_KEYMAX);  
           nullterm(c->key, COMMAND_KEYMAX);            
           return command_get;  
      }  
      if (wordscount == 3) {  
           if (strcmp(words[1],"=") != 0) {  
                printf("commandline: Syntax error (expected: KEY = VALUE)\n");  
                return NULL;  
           }  
           c->type = COMMAND_ASSIGNMENT;  
           strncpy(c->key, words[0], COMMAND_KEYMAX);  
           nullterm(c->key, COMMAND_KEYMAX);  
           strncpy(c->value, words[2], COMMAND_VALUEMAX);  
           nullterm(c->value, COMMAND_VALUEMAX);  
           return command_get;       
      }  
      printf("commandline: Syntax error (expected: KEY or KEY = VALUE)\n");  
      return NULL;       
 }  
   
 void *command_print(command *c)  
 {  
      printf("KEY: %s\n", c->key);  
      printf("VALUE: %s\n", c->value);  
      return command_print;  
 }  
   
 command *command_dup(command *c)  
 {  
      command *ptr = malloc(sizeof(*c));  
      if (!ptr)  
           return NULL;  
      memcpy(ptr, c, sizeof(*c));  
      return ptr;  
 }  
 // ---------------------------------------------------------------------------  
 // ---------------------------------------------------------------------------  
   

Explanations

struct mystruct_s {
   // ...
   HTABLE_ENTRY (mystruct_s);
};

the struct to be hashed

next

This word is reserved by HTABLE and cannot be used as a member of mystruct_s

void extract(struct mystruct_s *s, char **key, int *len);

user-defined function which returns key and len contained in s. *key should be a character string representing the key. *len should be equal to strlen(*key).

int compare(struct mystruct_s *s, struct mystruct_s *t):

user-defined comparison function: returns a value compatible with strcmp

NAME

a user-defined name which identifies the hash-table

var

a user-defined variable which stores the hash-table. Used together with NAME.

HTABLE_HEAD(NAME, SIZE, mystruct_s) var = HTABLE_INITIALIZER(&var);

macro to initialize the hashtable. For compatibility, do this outside of any function definition.

HTABLE_GENERATE(NAME, mystruct_s, extract, compare);

macro to initialize the hashtable. Use after HTABLE_HEAD. For compatibility, do this outside of any function definition.

objptr, elmptr

variables with type (struct mystruct_s *) which hold a pointer to a hashed object

elmptr = HTABLE_INSERT(NAME, &var, objptr);

insert objptr into the hashtable. On success, elmptr is a pointer to objptr. If the element was not inserted (e.g. because it was already in the hashtable), then elmptr is NULL.

elmptr = HTABLE_LOOKUP(NAME, &var, objptr);

lookup an object in the hashtable (NAME,var). The object to be found must have a key matching the object pointed to by objptr. If found, elmptr points to the found object. Otherwise, elmptr is NULL.

HTABLE_REMOVE(NAME, &var, objptr);

remove the object from hashtable (NAME,var) whose key matches the element pointed to by objptr.


End of post