Logo Search packages:      
Sourcecode: tcptrace version File versions  Download package

dyncounter.c

/*
 * Copyright (c) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001,
 *               2002, 2003, 2004
 *    Ohio University.
 *
 * ---
 * 
 * Starting with the release of tcptrace version 6 in 2001, tcptrace
 * is licensed under the GNU General Public License (GPL).  We believe
 * that, among the available licenses, the GPL will do the best job of
 * allowing tcptrace to continue to be a valuable, freely-available
 * and well-maintained tool for the networking community.
 *
 * Previous versions of tcptrace were released under a license that
 * was much less restrictive with respect to how tcptrace could be
 * used in commercial products.  Because of this, I am willing to
 * consider alternate license arrangements as allowed in Section 10 of
 * the GNU GPL.  Before I would consider licensing tcptrace under an
 * alternate agreement with a particular individual or company,
 * however, I would have to be convinced that such an alternative
 * would be to the greater benefit of the networking community.
 * 
 * ---
 *
 * This file is part of Tcptrace.
 *
 * Tcptrace was originally written and continues to be maintained by
 * Shawn Ostermann with the help of a group of devoted students and
 * users (see the file 'THANKS').  The work on tcptrace has been made
 * possible over the years through the generous support of NASA GRC,
 * the National Science Foundation, and Sun Microsystems.
 *
 * Tcptrace is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Tcptrace is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Tcptrace (in the file 'COPYING'); if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 * MA 02111-1307 USA
 * 
 * Author:  Shawn Ostermann
 *          School of Electrical Engineering and Computer Science
 *          Ohio University
 *          Athens, OH
 *          ostermann@cs.ohiou.edu
 *          http://www.tcptrace.org/
 */
#include "tcptrace.h"
static char const GCC_UNUSED copyright[] =
    "@(#)Copyright (c) 2004 -- Ohio University.\n";
static char const GCC_UNUSED rcsid[] =
    "@(#)$Header: /usr/local/cvs/tcptrace/dyncounter.c,v 1.7 2003/11/19 14:38:01 sdo Exp $";

/* dynamic counters/arrays */
/* uses a 10-ary tree to manage a sparse counter space */
#include "dyncounter.h"


static int ldebug = 0;

/* external routines */
void *MallocZ(int nbytes);


/* WIDTH of the nodes (designed for 10, caveat emptor!) */
/* (sdo: tested at 2, 5, 10, 100) */
#define CARDINALITY 10


/* 10-ary tree node */
struct node {
    u_long depth;       /* 1, 10, 100, 1000 ... 10,000,000 */
    union {
      struct node *down[CARDINALITY];     /* if depth != 1 */
      u_long value[CARDINALITY];    /* if depth == 1 */
    } un;

    struct node *nextleaf;    /* linked list of leaves, for NextCounter() */
    u_long prefix;            /* from trees above */
};


/* dynamically-sized counter structure */
struct dyn_counter {
    u_long gran;        /* granularity of the IX */
    u_long maxix;       /* NOT scaled */
    u_long minix;       /* NOT scaled */
    u_long maxcount;
    u_long total_count;       /* sum of the "AddToCounters" call values */
    struct node *tree;

    /* linked list of leaves */
    struct node *firstleaf;
    struct node *lastleaf;
};


/* local routines */
static struct dyn_counter *MakeCounterStruct(void);
static struct node *NewNode(u_long depth);
static u_long *FindTwig(struct node *lastnode, u_long ix);
static struct node *FindLeaf( struct dyn_counter *pdc, struct node **ptree,
                        u_long depth, u_long value, int fcreate);
static u_long *FindCounter(struct dyn_counter **ppdc, u_long ix, int fcreate);
static void PrintTree(struct node *tree);
static void PrintTreeRecurse(struct node *tree, u_long depth);
static void FinishTree(struct dyn_counter *pdc);
static void FinishTreeRecurse(struct dyn_counter *pdc, struct node *pnode,
                        u_long prefix, u_long depth);
static void PrintLeafList(struct dyn_counter *pdc);
static struct node *NextCounterRecurse(struct node *node, u_long nextix,
                               u_long *pix, u_long *pcount);
static struct node *MakeDepth(struct node *node, u_long depth);
static void DestroyTree(struct node *pnode);
static void MakeCounter(struct dyn_counter **ppdc, u_long ix,
                  u_long val, u_long granularity, char set);






/* add a value to a counter */
void
AddToCounter(
    struct dyn_counter **ppdc,
    u_long ix,
    u_long val,
    u_long granularity)
{
    if (ldebug)
      fprintf(stderr,"AddToCounter(%p, %lu, %lu) called\n", *ppdc, ix, val);

    MakeCounter(ppdc,ix,val,granularity,0);
}



/* set a value in a counter */
void
SetCounter(
    struct dyn_counter **ppdc,
    u_long ix,
    u_long val,
    u_long granularity)
{
    if (ldebug)
      fprintf(stderr,"SetCounter(%p, %lu, %lu) called\n", *ppdc, ix, val);

    MakeCounter(ppdc,ix,val,granularity,1);
}



/* read only, doesn't MAKE anything */
u_long
LookupCounter(
    struct dyn_counter *pdc,
    u_long ix)
{
    u_long *pdigit;

    if (ldebug)
      fprintf(stderr,"LookupCounter(p,%lu) called\n", ix);

    /* try to find the counter */
    pdigit = FindCounter(&pdc,
                   ix,
                   0);  /* do NOT create */

    if (pdigit == NULL) {
      /* no leaf node == no such counter */
      if (ldebug)
          fprintf(stderr,"LookupCounter(p,%lu): no such leaf\n", ix);
      return(0);
    }

    return(*pdigit);
}


int
NextCounter(
    struct dyn_counter **ppdc,
    void *pvoidcookie,
    u_long *pix,
    u_long *pcount)
{
    struct dyn_counter *pdc;
    struct node *node;
    u_long nextix;

    if (ldebug)
      fprintf(stderr,"NextCounter(p,%p,%lu,%lu) called\n",
            *((char **)pvoidcookie), *pix, *pcount);

    /* if the counter tree doesn't exist yet, create it */
    if (*ppdc == NULL) {
      *ppdc = MakeCounterStruct();
    }
    pdc = *ppdc;

    /* scale ix by granularity */
    *pix /= pdc->gran;

    /* make sure the linked list of leaves is up to date */
    if (pdc->firstleaf == NULL) {
      FinishTree(pdc);
      if (ldebug) {
          PrintLeafList(pdc);
          PrintTree(pdc->tree);
      }
    }

    /* if cookie is NULL, start at the head */
    if ((*((struct node **)pvoidcookie)) == NULL) {
      node = pdc->firstleaf;
      nextix = 0;
    } else {
      node = *((struct node **)pvoidcookie);
      nextix = ((*pix) % CARDINALITY) + 1;
    }


    /* sanity check on cookie */
    if (node->depth != 1) {
      fprintf(stderr,"NextCounter: invalid cookie!\n");
      exit(1);
    }

    /* recurse and solve */
    node = NextCounterRecurse(node,nextix,pix,pcount);

    if (node == NULL)
      return(0);        /* no more */

    /* scale ix by granularity */
    *pix *= pdc->gran;

    /* remember cookie for next time */
    *((struct node **)pvoidcookie) = node;

    return(1);
}


/* access routine - maximum counter value */
u_long
GetMaxCount(
    struct dyn_counter *pdc)
{
    return(pdc->maxcount);
}


/* access routine - return MAX index */
u_long
GetMaxIx(
    struct dyn_counter *pdc)
{
    return(pdc->maxix);
}


/* access routine - return MIN index */
u_long
GetMinIx(
    struct dyn_counter *pdc)
{
    return(pdc->minix);
}


/* access routine - return stored granularity */
u_long
GetGran(
    struct dyn_counter *pdc)
{
    if (pdc == NULL)
      return(1);
    return(pdc->gran);
}


/* access routine - total value added with AddToCounter() */
u_long
GetTotalCounter(
    struct dyn_counter *pdc)
{
    if (pdc == NULL)
      return(0);
    return(pdc->total_count);
}


void
DestroyCounters(
    dyn_counter *phandle)
{
    if (!*phandle)
      return;
    
    if ((*phandle)->tree)
      DestroyTree((*phandle)->tree);

    free(*phandle);
    *phandle = NULL;
}


static struct dyn_counter *
MakeCounterStruct()
{
    struct dyn_counter *pdc = MallocZ(sizeof(struct dyn_counter));

    pdc->minix = 0xffffffff;

    return(pdc);
}


static void
DestroyTree(
    struct node *pnode)
{
    int i;

    if (pnode == NULL)
      return;
    
    if (pnode->depth > 1) {
      /* recurse and delete */
      for (i=0; i < CARDINALITY; ++i) {
          DestroyTree(pnode->un.down[i]);
      }
    }

    /* destroy ME */
    free(pnode);
    return;
}





/* the heart of the routines, a 10-ary recursize search */
static struct node *
FindLeaf(
    struct dyn_counter *pdc,
    struct node **ptree,
    u_long depth,
    u_long value,
    int fcreate)
{
    u_long hidigit;
    u_long lowdigits;
    u_long valdepth;
    u_long valunits;
    u_long temp_value;

    if (ldebug)
      fprintf(stderr,"FindLeaf(%p(depth %lu), %lu, %s) called\n",
            *ptree,
            *ptree?((*ptree)->depth):0,
            value,
            fcreate?"CREATE":"NOCREATE");


    /* if the tree is empty and we haven't asked to "create", then not found */
    if ((*ptree == NULL) && (!fcreate))
      return(NULL);

    /* determine the units of the MSDigit (the depth) */
    valdepth = 1;
    valunits = 1;
    temp_value = value;
    while (temp_value >= CARDINALITY) {
      temp_value /= CARDINALITY;
      ++valdepth;
      valunits *= CARDINALITY;
    }

    if (ldebug)
      fprintf(stderr,"FindLeaf: value:%lu  depth:%lu  units:%lu\n",
            value, valdepth, valunits);


    /* is the tree deep enough? */
    if ((*ptree == NULL) || (valdepth > (*ptree)->depth)) {
      u_long correct_depth;

      /* the correct depth is the MAX of: */
      /* - the depth of the number we're looking for */
      /* - the value of "depth" passed down */
      correct_depth = depth;
      if (valdepth > correct_depth)
          correct_depth = valdepth;

      /* if the tree isn't that deep and we haven't asked to create, then not found */
      if (!fcreate)
          return(NULL);

      /* increase the depth of this branch */
      *ptree = MakeDepth((*ptree), correct_depth);

      /* linked list of leaves no longer valid! */
      pdc->firstleaf = NULL;

      /* adjust */
      depth = correct_depth;
    }

    /* if we're at the leaf depth, then we're done */
    if ((*ptree)->depth == 1)
      return(*ptree);

    /* if the "depth" of val is less than the depth of this node,
       recurse down the "0" branch without changing the number */
    if (valdepth < (*ptree)->depth) {
      return(FindLeaf(pdc,
                  &(*ptree)->un.down[0],
                  depth-1,
                  value,
                  fcreate));
    }

    /* (else), already the correct level */

    /* break the number into the MSDigit and LSDigits */
    hidigit = value / valunits;
    lowdigits = value % valunits;

    if (ldebug)
      fprintf(stderr,"for value %lu,  depth:%lu  units:%lu  hidigit:%lu  lowdigits:%lu\n",
            value, valdepth, valunits, hidigit, lowdigits);

    /* recurse */
    return(FindLeaf(pdc,
                &(*ptree)->un.down[hidigit],
                depth-1,
                lowdigits,
                fcreate));
}

static struct node *
MakeDepth(
    struct node *node,
    u_long depth)
{
    struct node *newroot;

    if ((node != NULL) && (node->depth >= depth))
      return(node);

    /* ELSE, insert a new level and recurse */
    newroot = NewNode(depth);
    
    /* attach the old part of the tree */
    if (depth > 1)
      newroot->un.down[0] = MakeDepth(node,depth-1);

    /* return the new root */
    return(newroot);
}
    



static struct node *
NewNode(
    u_long depth)
{
    struct node *pn;

    if (ldebug)
      fprintf(stderr,"NewNode(%lu) called\n", depth);

    pn = MallocZ(sizeof(struct node));

    pn->depth = depth;

    return(pn);
}


static u_long *
FindTwig(
    struct node *lastnode,
    u_long ix)
{
    unsigned digit;

    if (ldebug)
      fprintf(stderr,"FindTwig(%p(depth %lu), %lu) called\n",
            lastnode, lastnode->depth, ix);

    if (lastnode->depth != 1) {
      fprintf(stderr,"FindTwig: internal error, not at a leaf node\n");
      exit(2);
    }

    digit = ix % CARDINALITY;
    return(&(lastnode->un.value[digit]));
}


static u_long *
FindCounter(
    struct dyn_counter **ppdc,
    u_long ix,
    int fcreate)
{
    struct dyn_counter *pdc;
    struct node *pnode;
    u_long *pcounter;

    if (ldebug)
      fprintf(stderr,"FindCounter(p, %lu) called\n", ix);

    /* if the counter tree doesn't exist yet, create it */
    if (*ppdc == NULL) {
      *ppdc = MakeCounterStruct();
    }
    pdc = *ppdc;

    /* track MAX and MIN */
    if (ix > pdc->maxix)
      pdc->maxix = ix;
    if (ix < pdc->minix)
      pdc->minix = ix;

    if (ldebug>1)
      PrintTree(pdc->tree);

    /* scale (TRUNCATE) the index by the granularity */
    ix /= (*ppdc)->gran;

    /* find the leaf node */
    pnode = FindLeaf(pdc, &pdc->tree,
                 pdc->tree?pdc->tree->depth:1,
                 ix, fcreate);
    if (pnode == NULL)
      return(NULL);

    /* find the right counter */
    pcounter = FindTwig(pnode, ix);

    return(pcounter);
}


static void Indent(int depth)
{
    int i;

    for (i=0; i < depth; ++i)
      fputc(' ', stderr);
}


static void PrintTree(
    struct node *tree)
{
    PrintTreeRecurse(tree,0);
}


static void
PrintTreeRecurse(
    struct node *tree,
    u_long indent)
{
    int i;

    if (tree == NULL) {
      Indent(indent);
      fprintf(stderr,"NULL\n");
      return;
    }

    Indent(indent);
    fprintf(stderr,"Node %p, depth:%lu, prefix:%lu\n", tree, tree->depth, tree->prefix);

    if (tree->depth == 1) {
      for (i=0; i < CARDINALITY; ++i) {
          Indent(indent);
          fprintf(stderr,"Leaf[%d]: %lu (value:%lu)\n",
                i,
                tree->un.value[i],
                tree->prefix*CARDINALITY+i);
      }
    } else {
      for (i=0; i < CARDINALITY; ++i) {
          Indent(indent);
          fprintf(stderr,"Branch %d (prefix %lu, depth %lu)\n",
                i, tree->prefix*CARDINALITY+i, tree->depth);
          PrintTreeRecurse(tree->un.down[i],
                       indent+3);
      }
    }
}


static void
FinishTree(
    struct dyn_counter *pdc)
{
    FinishTreeRecurse(pdc, pdc->tree, 0, pdc->tree->depth);
}


static void
FinishTreeRecurse(
    struct dyn_counter *pdc,
    struct node *pnode,
    u_long prefix,
    u_long depth)
{
    int i;

    /* special case, empty tree */
    if (pnode == NULL)
      return;

    /* sanity check, verify depth */
    if (pnode->depth != depth) {
      fprintf(stderr,"FinishTree: bad depth at node %p (%lu should be %lu)\n",
            pnode, pnode->depth, depth);
      PrintTree(pdc->tree);
      exit(-3);
    }

    /* insert prefix */
    pnode->prefix = prefix;

    /* if we're a leaf, add to end of the list */
    if (pnode->depth == 1) {
      if (pdc->firstleaf == NULL) {
          pdc->firstleaf = pdc->lastleaf = pnode;
          if (ldebug)
            fprintf(stderr,"FinishTree: Making %p the head\n", pnode);
      } else {
          pdc->lastleaf->nextleaf = pnode;
          pdc->lastleaf = pnode;
          if (ldebug)
            fprintf(stderr,"FinishTree: Making %p the tail\n", pnode);
      }
      return;
    }

    /* recurse down all branches */
    for (i=0; i < CARDINALITY; ++i) {
      FinishTreeRecurse(pdc, pnode->un.down[i], prefix*CARDINALITY+i, depth-1);
    }
}


static void
PrintLeafList(
    struct dyn_counter *ptree)
{
    struct node *pnode = ptree->firstleaf;
    
    fprintf(stderr,"Leaf Linked List...\n");
    while(pnode) {
      fprintf(stderr,"   pnode:%p  prefix:%lu\n", pnode, pnode->prefix);
      pnode = pnode->nextleaf;
    }
}



static struct node *
NextCounterRecurse(
    struct node *node,
    u_long nextix,
    u_long *pix,
    u_long *pcount)
{
    int i;

    if (ldebug)
      fprintf(stderr,"NextCounterRecurse(%p,%lu,%lu,%lu) called\n",
            node, nextix, *pix, *pcount);

    /* base case, NULL */
    if (node == NULL)
      return(NULL);
    

    /* first, check the rest of THIS leaf node */
    for (i=nextix; i < CARDINALITY; ++i) {
      if (node->un.value[i] != 0) {
          *pix = node->prefix*CARDINALITY+i;
          *pcount = node->un.value[i];
          return(node);
      }
    }

    /* check each counter in the NEXT leaf */
    return(NextCounterRecurse(node->nextleaf, 0, pix, pcount));
}


/* internal counter access routine */
static void
MakeCounter(
    struct dyn_counter **ppdc,
    u_long ix,
    u_long val,
    u_long granularity,
    char is_set) /* "set" as opposed to "add" */
{
    u_long *pcounter;

    /* if the counter tree doesn't exist yet, create it */
    if (*ppdc == NULL) {
      *ppdc = MakeCounterStruct();
    }

    /* check granularity */
    if ((*ppdc)->gran == 0) {
      (*ppdc)->gran = granularity;
    } else {
      /* error check */
      if ((*ppdc)->gran != granularity) {
          fprintf(stderr,"DYNCOUNTER: internal error, granularity changed\n");
          exit(-1);
      }
    }

    /* find/create the counter */
    pcounter = FindCounter(ppdc, ix, 1);

    /* add or set */
    if (is_set) {
      /* counter = val */
      *pcounter = val;
    } else {
      /* counter += val */
      *pcounter += val;
      (*ppdc)->total_count += val;
    }


    /* check MAX counter value */
    if (*pcounter > (*ppdc)->maxcount)
      (*ppdc)->maxcount = *pcounter;

    return;
}

Generated by  Doxygen 1.6.0   Back to index