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     ! 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: }