stringmap.c

   1 /*
   2  * stringmap.c: sucky implementation of binary trees
   3  *
   4  * This makes no attempt to balance the tree, so has bad worst-case behaviour.
   5  * Also, I haven't implemented removal of items from the tree. So sue me.
   6  *
   7  * Copyright (c) 2001 Chris Lightfoot. All rights reserved.
   8  *
   9  */
  10
  11 static const char rcsid[] = "$Id: stringmap.c,v 1.4 2010/11/27 11:06:12 pdw Exp $";
  12
  13
  14 #include <stdlib.h>
  15 #include <string.h>
  16
  17 #include "stringmap.h"
  18 #include "vector.h"
  19 #include "iftop.h"
  20
  21 /* stringmap_new:
  22  * Allocate memory for a new stringmap. */
  23 stringmap stringmap_new() {
  24     stringmap S;
  25
  26     S = xcalloc(sizeof *S, 1);
  27
  28     return S;
  29 }
  30
  31 /* stringmap_delete:
  32  * Free memory for a stringmap. */
  33 void stringmap_delete(stringmap S) {
  34     if (!S) return;
  35     if (S->l) stringmap_delete(S->l);
  36     if (S->g) stringmap_delete(S->g);
  37
  38     xfree(S->key);
  39     xfree(S);
  40 }
  41
  42 /* stringmap_delete_free:
  43  * Free memory for a stringmap, and the objects contained in it, assuming that
  44  * they are pointers to memory allocated by xmalloc(3). */
  45 void stringmap_delete_free(stringmap S) {
  46     if (!S) return;
  47     if (S->l) stringmap_delete_free(S->l);
  48     if (S->g) stringmap_delete_free(S->g);
  49
  50     xfree(S->key);
  51     xfree(S->d.v);
  52     xfree(S);
  53 }
  54
  55 /* stringmap_insert:
  56  * Insert into S an item having key k and value d. Returns a pointer to
  57  * the existing item value, or NULL if a new item was created.
  58  */
  59 item *stringmap_insert(stringmap S, const char *k, const item d) {
  60     if (!S) return NULL;
  61     if (S->key == NULL) {
  62         S->key = xstrdup(k);
  63         S->d   = d;
  64         return NULL;
  65     } else {
  66         stringmap S2;
  67         for (S2 = S;;) {
  68             int i = strcmp(k, S2->key);
  69             if (i == 0) {
  70                 return &(S2->d);
  71             }
  72             else if (i < 0) {
  73                 if (S2->l) S2 = S2->l;
  74                 else {
  75                     if (!(S2->l = stringmap_new())) return NULL;
  76                     S2->l->key = xstrdup(k);
  77                     S2->l->d   = d;
  78                     return NULL;
  79                 }
  80             } else if (i > 0) {
  81                 if (S2->g) S2 = S2->g;
  82                 else {
  83                     if (!(S2->g = stringmap_new())) return NULL;
  84                     S2->g->key = xstrdup(k);
  85                     S2->g->d   = d;
  86                     return NULL;
  87                 }
  88             }
  89         }
  90     }
  91 }
  92
  93 /* stringmap_find:
  94  * Find in d an item having key k in the stringmap S, returning the item found
  95  * on success NULL if no key was found. */
  96 stringmap stringmap_find(const stringmap S, const char *k) {
  97     stringmap S2;
  98     int i;
  99     if (!S || S->key == NULL) return 0;
 100     for (S2 = S;;) {
 101         i = strcmp(k, S2->key);
 102         if (i == 0) return S2;
 103         else if (i < 0) {
 104             if (S2->l) S2 = S2->l;
 105             else return NULL;
 106         } else if (i > 0) {
 107             if (S2->g) S2 = S2->g;
 108             else return NULL;
 109         }
 110     }
 111 }