Return to stringmap.c CVS log

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

Annotation of embedaddon/iftop/stringmap.c, revision 1.1.1.1

1.1       misho       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.3 2003/11/06 23:37:20 chris 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: }