example_hash.c File Reference

Example of using a librnr hash table. More...

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdarg.h>
#include "rnr/rnrconfig.h"
#include "rnr/new.h"
#include "rnr/log.h"
#include "rnr/hash.h"

Go to the source code of this file.

Typedefs
typedef char	input_t[256]
	Working input buffer.

Functions
static int	tokenize (char *string,...)
	Tokenize input. More...
static void	del_node_data (void *key, void *val)
	Delete node data - both key and value are dynamically allocated. More...
static void	force_grow (hash_t *h)
	Force table to grow by feeding the table random entries. More...
static void	force_shrink (hash_t *h)
	Force table to shink by deleting table random entries. More...
int	main (int argc, char *argv[])
	Example main. More...

Variables
static char *	Colorado14ers [][2]
	Colorado's 14,000+ foot mountains. More...
static int	MtnCounter = 0
	Make random keys unique.

Detailed Description

Example of using a librnr hash table.

LastChangedDate

2011-11-18 13:30:34 -0700 (Fri, 18 Nov 2011)

Rev

1577

Author

Robin Knight (robin.nosp@m..kni.nosp@m.ght@r.nosp@m.oadn.nosp@m.arrow.nosp@m.s.co.nosp@m.m)

Copyright

© 2007-2018. RoadNarrows LLC..
http://www.roadnarrows.com
All Rights Reserved

Definition in file example_hash.c.

Function Documentation

static void del_node_data ( void *  key, void *  val  )

static

Delete node data - both key and value are dynamically allocated.

Parameters

key	Data key.
val	Data value.

Definition at line 110 of file example_hash.c.

Referenced by force_grow(), and main().

{
  delete(key);
  delete(val);
}

static void force_grow ( hash_t *  h )

static

Force table to grow by feeding the table random entries.

Parameters

h	Pointer to hash table.

Definition at line 151 of file example_hash.c.

References arraysize, Colorado14ers, del_node_data(), hash_count, hash_insert(), hash_size, hash_t::highmark, MtnCounter, and new_strdup().

Referenced by main().

{
  hashcount_t   count, size;
  size_t        num_mtns = arraysize(Colorado14ers);
  int           mtn;
  char          buf[64];
  char         *key, *val;

  count = hash_count(h);
  size  = hash_size(h);

  printf(" starting count=%lu, table size=%lu\n", count, size); 

  // tables grows at highwater mark
  size = h->highmark;

  while( count++ < size )
  {
    mtn = (int)(random() % (long int)num_mtns);
    sprintf(buf, "%s(%d)", Colorado14ers[mtn][0], MtnCounter++);
    key = new_strdup(buf);
    val = new_strdup(Colorado14ers[mtn][1]);

    if( !hash_insert(h, key, val) )
    {
      puts("hash_insert failed");
      del_node_data(key, val);
      return;
    }
    else
    {
      printf(" added %s -> %s\n", key, val);
    }
  }

  count = hash_count(h);
  size  = hash_size(h);

  printf(" ending count=%lu, table size=%lu\n", count, size); 
}

static void force_shrink ( hash_t *  h )

static

Force table to shink by deleting table random entries.

Parameters

h	Pointer to hash table.

Definition at line 197 of file example_hash.c.

References hash_count, hash_node_delete(), hash_scan_begin(), hash_scan_next(), hash_size, hnode_get, hnode_getkey, hash_t::lowmark, and NULL.

Referenced by main().

{
  hashcount_t   count, size;
  hscan_t       hs;
  hnode_t      *hn;
  char         *key, *val;

  count = hash_count(h);
  size  = hash_size(h);

  printf(" starting count=%lu, table size=%lu\n", count, size); 

  // tables shrinks at lowwater mark
  size = h->lowmark;

  hash_scan_begin(&hs, h);

  // delete first count nodes
  while( ((hn = hash_scan_next(&hs)) != NULL) && (count-- > size) )
  {
    key = (char *)hnode_getkey(hn);
    val = (char *)hnode_get(hn);
    printf(" deleted %s -> %s\n", key, val); 
    hash_node_delete(h, hn);
  }

  count = hash_count(h);
  size  = hash_size(h);

  printf(" ending count=%lu, table size=%lu\n", count, size); 
}

int main	(	int	argc,
		char *	argv[]
	)

Example main.

Parameters

argc	Command-line argument count.
argv	Command-line argument list.

Exit Status:

Program exits with 0 success, > 0 on failure.

Definition at line 238 of file example_hash.c.

References del_node_data(), force_grow(), force_shrink(), hash_count, hash_insert(), hash_lookup(), hash_node_delete(), hash_scan_begin(), hash_scan_next(), hash_set_self_verify(), hash_size, hash_table_create(), hash_table_destroy(), HASHCOUNT_T_MAX, hnode_get, hnode_getkey, LOG_SET_THRESHOLD(), new_strdup(), NULL, and tokenize().

{
  input_t   in;
  hash_t   *h = NULL;
  hnode_t  *hn;
  hscan_t   hs;
  char     *tok1, *tok2;
  char     *key, *val;
  int       n;

  char *help =
  "n                      create new empty hash table\n"
  "x                      delete entire hash table\n"
  "a <key> <val>          add value to hash table\n"
  "d <key>                delete value from hash table\n"
  "l <key>                lookup value in hash table\n"
  "c                      show counts: number of entries and table size\n"
  "t                      dump whole hash table\n"
  "+                      force increase hash table (by auto-adding)\n"
  "-                      force decrease hash table (by auto-deleting)\n"
  "v <level>              set logging verbosity level 0-4\n"
  "q                      quit";


  puts("Hashing example (enter '?' for list of commands)");

  // process user commands
  for(;;)
  {
    printf("hash> ");

    // read user input
    if( !fgets(in, (int)sizeof(input_t), stdin) )
    {
      break;
    }

    // execute command
    switch( in[0] )
    {
      // help
      case '?':
        puts(help);
        break;

      // create new hash table
      case 'n':
        if( h != NULL )
        {
          printf("table exists, delete first\n");
        }
        else
        {
          h = hash_table_create(
                  true,             // dynamic table sizing
                  (hashcount_t)4,   // minimum size
                  HASHCOUNT_T_MAX,  // maximum size
                  NULL,             // use default comparator function
                  NULL,             // use default hashing function
                  del_node_data);   // hash node data deletion function

          hash_set_self_verify(true); // off by default
        }
        break;

      // delete hash table and all user data 
      case 'x':
        if( h == NULL )
        {
          printf("no table\n");
        }
        else
        {
          hash_table_destroy(h);
          h = NULL;
        }
        break;

      // add hash table entry
      case 'a':
        if( h == NULL )
        {
          printf("no hash table\n");
        }
        else if(tokenize(in+1, &tok1, &tok2, (char **) 0) != 2)
        {
          puts("what?");
        }
        else
        {
          // new key and value
          key = new_strdup(tok1);
          val = new_strdup(tok2);

          // insert into hash table, automatically allocating hnode_t
          if( !hash_insert(h, key, val) )
          {
            puts("hash_insert failed");
            del_node_data(key, val);
          }
        }
        break;

      // delete hash table entry
      case 'd':
        if( h == NULL )
        {
          printf("no hash table\n");
        }
        else if(tokenize(in+1, &tok1, (char **)0) != 1)
        {
          puts("what?");
        }
        else if( (hn = hash_lookup(h, tok1)) == NULL )
        {
          puts("hash_lookup failed");
        }
        else
        {
          key = (char *)hnode_getkey(hn);
          val = (char *)hnode_get(hn);
          printf("deleted %s -> %s\n", key, val); 
          hash_node_delete(h, hn);
        }
        break;

      // lookup hash table entry
      case 'l':
        if( h == NULL )
        {
          printf("no hash table\n");
        }
        else if(tokenize(in+1, &tok1, (char **) 0) != 1)
        {
          puts("what?");
        }
        else if( (hn = hash_lookup(h, tok1)) == NULL )
        {
          puts("hash_lookup failed");
        }
        else
        {
          val = hnode_get(hn);
          printf("%s -> %s\n", tok1, val); 
        }
        break;

      // get current number of hash table entries and current table size
      case 'c':
        if( h == NULL )
        {
          printf("no hash table\n");
        }
        else
        {
          printf("count=%lu, size=%lu\n",
              (unsigned long)hash_count(h), (unsigned long)hash_size(h));
        }
        break;

      // dump hash table entries
      case 't':
        if( h == NULL )
        {
          printf("no hash table\n");
        }
        else
        {
          hash_scan_begin(&hs, h);
          while( (hn = hash_scan_next(&hs)) != NULL )
          {
            printf("%s -> %s\n", (char *)hnode_getkey(hn),
                (char *)hnode_get(hn));
          }
        }
        break;

      // force hash table to grow
      case '+':
        if( h == NULL )
        {
          printf("no hash table\n");
        }
        else
        {
          force_grow(h);
        }
        break;

      // force hash table to shrink
      case '-':
        if( h == NULL )
        {
          printf("no hash table\n");
        }
        else
        {
          force_shrink(h);
        }
        break;

      // logging level
      case 'v':
        if( tokenize(in+1, &tok1, (char **)0) != 1 )
        {
          puts("what?");
        }
        else
        {
          n = atoi(tok1);
          LOG_SET_THRESHOLD(n);
        }
        break;

      // quit
      case 'q':
        exit(0);
        break;

      // null command
      case '\0':
      case '\n':
        break;

      // input error
      default:
        puts("?");
        break;
    }
  }

  return 0;
}

static int tokenize ( char *  string,   ...  )

static

Tokenize input.

Parameters

	string	Input string to parse.
[out]	...	Variable argument list of char** arguments terminated by a last NULL argument.

Returns

Number of tokens.

Definition at line 68 of file example_hash.c.

Referenced by main().

{
  char    **tokptr; 
  va_list   arglist;
  int       tokcount = 0;

  va_start(arglist, string);
  tokptr = va_arg(arglist, char **);
  while(tokptr)
  {
    while(*string && isspace((int)*string))
    {
      string++;
    }
    if(!*string)
    {
      break;
    }
    *tokptr = string;
    while(*string && !isspace((int)*string))
    {
      string++;
    }
    tokptr = va_arg(arglist, char **);
    tokcount++;
    if(!*string)
    {
      break;
    }
    *string++ = 0;
  }
  va_end(arglist);

  return tokcount;
}

Variable Documentation

char* Colorado14ers[][2]

static

Initial value:

=
{
  {"mt_elbert",         "14,433"},
  {"mt_massive",        "14,421"},
  {"mt_harvard",        "14,420"},
  {"blanca_peak",       "14,345"},
  {"la_plata_peak",     "14,336"},
  {"uncompahgre_peak",  "14,309"},
  {"crestone_peak",     "14,294"},
  {"mt_lincoln",        "14,286"},
  {"grays_peak",        "14,270"},
  {"mt_antero",         "14,269"},
  {"torreys_peak",      "14,267"},
  {"castle_peak",       "14,265"},
  {"quandary_peak",     "14,265"},
  {"mt_evans",          "14,264"},
  {"longs_peak",        "14,255"},
  {"mt_wilson",         "14,246"}
}

Colorado's 14,000+ foot mountains.

N.B. there are 53 of them, I'm stopping at the highest 16.

Definition at line 121 of file example_hash.c.

Referenced by force_grow().