A Simple Associative Array Library in C

Originally published on: Thu, 19 Nov 2009 02:35:02 +0000

I often need to use associative arrays when writing C code. You might be more familiar with these constructs under other names ( dictionaries, maps, hashmaps, hashes, ...etc. ) I will use the term map in place of the words associative array.

A map is a collection of key / value pairs or name / value pairs. My implementation of a map structure allows strings as the only data that can be stored in the name and value.

Many implementations of maps use a hashed lookup to speed up execution. I have opted to use a simple forward-chained linked-list of map structures. When searching for an item in a map, the search will sequentially pass over every item in the list of map entries until a match is found. If no match is found, an empty string is returned.

This implementation is complete enough for my needs.

map_lib.h

map_lib.c

// map_lib
// A simple associative-array library for C
//
// License: MIT / X11
// Copyright (c) 2009 by James K. Lawless
// jimbo@radiks.net http://www.radiks.net/~jimbo
// http://www.mailsend-online.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following
// conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include "map_lib.h"

struct map_t *map_create() {
   struct map_t *m;
   m=(struct map_t *)malloc(sizeof(struct map_t));
   m->name=NULL;
   m->value=NULL;
   m->nxt=NULL;
}

void map_set(struct map_t *m,char *name,char *value) {
   struct map_t *map;

   if(m->name==NULL) {
      m->name=(char *)malloc(strlen(name)+1);
      strcpy(m->name,name);
      m->value=(char *)malloc(strlen(value)+1);
      strcpy(m->value,value);
      m->nxt=NULL;
      return;
   }
   for(map=m;;map=map->nxt) {
      if(!stricmp(name,map->name)) {
         if(map->value!=NULL) {
            free(map->value);
            map->value=(char *)malloc(strlen(value)+1);
            strcpy(map->value,value);
            return;
         }
      }
      if(map->nxt==NULL) {
         map->nxt=(struct map_t *)malloc(sizeof(struct map_t));
         map=map->nxt;
         map->name=(char *)malloc(strlen(name)+1);
         strcpy(map->name,name);
         map->value=(char *)malloc(strlen(value)+1);
         strcpy(map->value,value);
         map->nxt=NULL;
         return;
      }
   }
}

char *map_get(struct map_t *m,char *name) {
   struct map_t *map;
   for(map=m;map!=NULL;map=map->nxt) {
      if(!stricmp(name,map->name)) {
         return map->value;
      }
   }
   return "";
}

Here's a simple test program that loads and displays a map with name/value pairs. The names are all numbers. The values are words that sound like the numbers ( homonyms ).

map_stuff.c

#include <stdio.h>
#include "map_lib.h"

void display_both(struct map_t *m,char *key);

int main(int argc,char **argv) {
   struct map_t *test;

   test=map_create();
   map_set(test,"One","Won");
   map_set(test,"Two","Too");
   map_set(test,"Four","Fore");

      // display them out of order
   display_both(test,"Two");
   display_both(test,"Four");
   display_both(test,"One");

   printf("\n");

      // reset an existing entry
   map_set(test,"Two","To");

   display_both(test,"Two");
   display_both(test,"Four");
   display_both(test,"One");

   printf("\n");

   display_both(test,"Eight");

   map_set(test,"Eight","Ate");

   printf("\n");

   display_both(test,"Eight");
}

void display_both(struct map_t *m,char *first) {
   printf("%s %s\n",first,map_get(m,first));
}

The output from the above program is as follows:

Two Too
Four Fore
One Won

Two To
Four Fore
One Won

Eight

Eight Ate

I did not provide any kind of iterator functions in the library. If I need to iterate through a given map, I will just use a for-loop and will use the ->nxt element to reach each successive entry.

I will use the above library in later posts.

The source and sample executable file for map_lib can be downloaded in a single archive at: http://www.mailsend-online.com/wp/map_lib.zip

Unless otherwise noted, all code and text entries are Copyright Š2009 by James K. Lawless

Save to del.icio.us
Save to StumbleUpon
Digg it
Save to Reddit
Share on Facebook
Share on Twitter
More bookmarks