Return to stringmap.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / iftop

iftop

    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.1.1.1 2012/02/21 16:57:34 misho 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 an existing key
   57:  * or NULL if it was inserted. 
   58:  */
   59: item *stringmap_insert(stringmap S, const char *k, const item d) {
   60:     if (!S) return 0;
   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: }