/****************************************************************************/
/*                                                                          */
/*      NNstat -- Internet Statistics Collection Package                    */
/*                                                                          */
/*            Written by: Bob Braden & Annette DeSchon                      */
/*            USC Information Sciences Institute                            */
/*            Marina del Rey, California                                    */
/*                                                                          */
/*      Copyright (c) 1991 University of Southern California.               */
/*      All rights reserved.                                                */
/*                                                                          */
/*      Redistribution and use in source and binary forms are permitted     */
/*      provided that the above copyright notice and this paragraph are     */
/*      duplicated in all such forms and that any documentation,            */
/*      advertising materials, and other materials related to such          */
/*      distribution and use acknowledge that the software was              */
/*      developed by the University of Southern California, Information     */
/*      Sciences Institute.  The name of the University may not be used     */
/*      to endorse or promote products derived from this software           */
/*      without specific prior written permission.                          */
/*      THIS SOFTWARE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR        */
/*      IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED      */
/*      WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR          */
/*      PURPOSE.                                                            */
/*                                                                          */
/****************************************************************************/

static char rcsid[]=
  "$Header: /tmp_mnt/r/jove_staff3/mogul/code/NNstat/3.3beta/RCS/sobjma.c,v 1.6 1993/09/22 22:46:20 mogul Exp $";

 /*
  *  CHANGES:
  *    Rel 2.4:
  *  01Nov89 RTB: Change calling sequence for MA_list.
  *    Rel 3.0:
  *   ISI:  Add List routine.
  *   ISI:  Remove redundant NL when no bins. 
  *   ISI:  Read/List output to logfp, not stdout. 
  *   Aug93/DECWRL: Alpha/OSF port
  *
  */
/*
 *   Internet Statistics Facility -- Generic Operation Routines
 *
 *    This module defines a set of operations on a particular class
 *    of Statistical Objects.  In the spirit of object-oriented
 *    programming and information-hiding, these routines are
 *    the only ones which know about the internal structre of the
 *    Statistical Object (SOBJ) data structures.
 *
 */
 
/*
 *
 *          MA Object Classes == MATRIX_ALL, MATRIX_SYM     
 *
 *    Objects of the MA and MS classes are frequency matrices for 
 *    pairs of 32-bit values, using dynamically-created bins. 
 * 
 *    MA: every distinct pair (a,b) is counted in a separate bin.
 *    MS: (a,b) and (b,a) are counted in the same bin.
 * 
 *
 *    MA objects are implemented using a chained hash table.  The bins are
 *    in a space which is allocated dynamically in pages of 4K bytes. 
 *    
 *    Bins are also linked into a doubly-linked list, sorted by decreasing
 *    count field. Within the same count,they are sorted by increasing last-
 *    reference time.

 *
 *    Operations on MA/MS class objects:
 *
 *       SOBJ *Make_MA( object-name, &sym-switch, 1/0, datalen1, datalen2 )
 *
 *       Write_MA( (SOBJ *) SOBJ-ptr, &value1, len1, &value2, &len2)
 *
 *       Read_MA( fd, (SOBJ *) SOBJ-ptr )
 *
 *       Delete_MA( (SOBJ *) SOBJ-ptr )
 *
 *       Clear_MA( (SOBJ *) SOBJ-ptr )
 *
 *       List_MA( fd, OBJp )
 *
 */
 
#include <stdio.h>
#include <sys/types.h>
#include "stat.h"
#include "sobj.h"

    /*     
     *  Define MA/MS object data structures
     *
     */

#define MAX_PAGES 8   /* Max no. 256-entry (4K byte) bin pages */
#define HASHsize 255
    
#define BIN_pwr2  8   /* log2( number bins per extension page )*/
#define BIN_PAGE  (1<<BIN_pwr2)   /* Number bins per extension page */
#define BIN_MASK  BIN_PAGE -1
#define BIN_MAX   BIN_PAGE*MAX_PAGES

        /* Map bin index into bin address */    
#define BIN_ADDR(maap, i) (MAE *) ( \
             (char *) maap->maa_page[((i)>>BIN_pwr2)]+ \
             maap->maa_esize*((i)&BIN_MASK) ) 
                
        /* Hash Function ==  simple congruential hash */    
#define hashfunc( V, S)  V%S                                 

        /* Bin format */
    
#define MAE struct ma_bin_element
MAE {
    struct FBlinks mae_fb; /* Doubly-linked sort list   *5Jan88**/
    MAE  *mae_next ;    /* Hash chain field */
    MADE  mae_made ;    /* Rest... count, value concatentation, time */
        /* We chose an internal representation which is the SAME as the
         * network representation, to simplify READ operations.
         */
};

#define mae_value  mae_made.mad_value  /* leng1+leng2 padded to fullword */
#define mae_count  mae_made.mad_count
#define mae_time   mae_made.mad_time


    /* MA/MS Object Area format */
#define MAA struct stat_xarea
MAA {
    SOBJ   maa_sobj ;         /* SOBJ = standard root of area */
    
    short  maa_esize ;        /* Size of element */
    short  maa_hashs ;        /* Size of hash table (#shorts) */
    short  maa_symswitch;     /* Symmetry switch */
    short  maa_maxchain ;     /* Max chain length  */
    
    struct FBlinks maa_head;  /* Head of sorted list */
    MAE   *maa_tail;          /* Tail of sorted list */
    long   maa_infinity;      /* Infinite count -- 'fence' */
    long   maa_cntmoves;      /* Total places moved in sorting */
        
    int    maa_currbin ;      /* Index of first available bin */
    MAE  **maa_hashp ;        /* Ptr to hash table */
    MAE   *maa_page[MAX_PAGES] ;  /* Ptrs to bin segments */
    /*----------------------------------------------------
                     Hash Table... 
          (a vector of pointers: the heads of hash chains)
    /*----------------------------------------------------*/
} ;


SOBJ *Make_MA(), *Make_MS();
boolean  Write_MA(), Read_MA();
void  Clear_MA(), Delete_MA(), List_MA();

    /* Transfer Vectors 
     *   for external access to these routines
     */
GENERICOP MAop = { Make_MA, Write_MA, Read_MA, Clear_MA, Delete_MA, List_MA } ;
GENERICOP MSop = { Make_MS, Write_MA, Read_MA, Clear_MA, Delete_MA, List_MA } ;


SOBJ *Make_MA(objname, parmp, nparms, datalen1, datalen2)
    char *objname;
    int  *parmp;
    int   nparms, datalen1, datalen2;
    {
    register MAA *maap ;
    register int i ;
    int hsize = HASHsize ;
    int vsize = ALIGN(datalen1+datalen2);

    if (datalen1 > MAX_DLENG || datalen2 > MAX_DLENG){
        SOBJ_error = "MA: Field size too big";
        return(NULL);
    }
    if (datalen2 == 0) {                           /*FIX4Jan88 */
        SOBJ_error = "MA: Missing second field";   /*FIX4Jan88 */
        return(NULL);                              /*FIX4Jan88 */
    }
    
    i = (sizeof(MAE *))*hsize + sizeof ( MAA )  ;
    if ((maap = (MAA *) malloc(i)) == NULL) {
        SOBJ_error = "MA: Memory overflow" ;
        return(NULL) ;
    }
    bzero(maap, i) ;  /* Clear entire area... */
        
    maap->maa_esize = PTRALIGN(sizeof(MAE) - 2*MAX_DLENG + vsize);
    maap->maa_hashs = hsize;
    maap->maa_currbin = 0;  
    SETMAXINT(maap->maa_infinity);
    maap->maa_tail = (MAE *) &maap->maa_head;   
    
    maap->maa_symswitch = (nparms && *parmp && (datalen1 == datalen2));         
    maap->maa_hashp =  (MAE **) ((char *) maap + sizeof(MAA) ) ;
            /* Start of hash table */
                        
    return(&maap->maa_sobj) ;  /* SUCCESS!! */
}    
     

SOBJ *Make_MS(objname, parmp, nparms, datalen1, datalen2)
    char *objname;
    int  *parmp;
    int   nparms, datalen1, datalen2;
    {
    int   symswitch = 1;
    
        /* Just call Make_MA with sym switch set... */
     return(Make_MA(objname, &symswitch, 1, datalen1, datalen2));
}

     
boolean Write_MA( maap, Valuep1, L1, Valuep2, L2)
    register MAA *maap ;
    char *Valuep1, *Valuep2 ;
    int L1, L2; 
    {
    register MAE *maep, **thp, *tep;
    MAE **hp;
    register int L = L1;
    int n;
    u_int32 HValue;      
    union v_union Values;
    
    ZERO_UNION(&Values); ZERO_UN2(&Values);
    
    if (maap->maa_symswitch && CLC(Valuep1, Valuep2, L1) > 0) {
            /*  Symmetry-switch set (this can only happen if L1 == L2).
             *   Reverse order if Value2 < Value 1.
             */
        Bcopy(Valuep2, Values.v_byte, L);
        Bcopy(Valuep1, &Values.v_byte[L1], L);
    }
    else {
        Bcopy(Valuep1, Values.v_byte, L);
        Bcopy(Valuep2, &Values.v_byte[L1], L2);
    }
    
    L = L1+L2;
    HValue = SUM_UN2(&Values) + SUM_UNION(&Values);

    hp = thp = &maap->maa_hashp[ hashfunc(HValue, maap->maa_hashs) ];
    
    n = 0;  
    while (maep = *thp) {
        if ((WORD1(maep->mae_value) == WORD1(&Values))  
            && (L <= sizeof(int32) ||
              ((WORD2(maep->mae_value) == WORD2(&Values))
               && (L <= 2*sizeof(int32) ||
                 ((WORD3(maep->mae_value) == WORD3(&Values))
                  && (L <= 3*sizeof(int32) ||
                    ((WORD4(maep->mae_value) == WORD4(&Values))
            )))))))                                  /* Lisp, anyone? */
            {
                /* Found bin, so increment count */
            maep->mae_count++ ;
            maep->mae_time = CurrTime ;
            if (maep->mae_count >= 
                        (tep = (MAE *) maep->mae_fb.FB_Bp)->mae_count) {
                    /* Bin is now out of sorts.  Move it up in list.
                     *  Note that head of list has artificial infinite
                     *  count as 'fence', so cannot get here if bin is
                     *  already first in list. 
                     * 
                     *  First, adjust tail pointer if necessary.
                     */
                if (maep == maap->maa_tail) 
                    maap->maa_tail = (MAE *) maep->mae_fb.FB_Bp;
                else if (maep->mae_count == 2 && maap->maa_tail->mae_count>2)
                    maap->maa_tail = maep;      
                    
                FBrem(&maep->mae_fb);
                do {
                    tep = (MAE *) tep->mae_fb.FB_Bp;
                    maap->maa_cntmoves++;   /* Keep performance stat */
                    } while (maep->mae_count >= tep->mae_count);
                FBins(&maep->mae_fb, &tep->mae_fb);
            }
            else {
                /* Don't have to move bin at all. May still have to
                 *  adjust tail pointer...
                 */
                if (maep->mae_count == 2)
                    maap->maa_tail = maep;
            }
            return(WRRET_OK) ;
         }
        thp = &maep->mae_next ;
        n++;
    }
    
        /* No such bin... Must create new one and insert into hash list...
         */      
    if (maap->maa_currbin >= BIN_MAX ) {
            /* We have run out of new bins. Count as orphan. */
        maap->maa_sobj.sob_orphans++ ;
        return(WRRET_OK) ;
    }
        
    if ((maep = BIN_ADDR( maap, maap->maa_currbin)) == NULL) {
            /*  must obtain new page */
        maep  = (MAE *) malloc(maap->maa_esize * BIN_PAGE) ;
        if (maep == NULL) {
            /* Cannot get new bin page. Count as orphan. */
            maap->maa_sobj.sob_orphans++ ;
            return(WRRET_OK) ;
        }
        maap->maa_page[(maap->maa_currbin >> BIN_pwr2)] = maep ;
    }               
        /*
         *   Fill in new bin 
         */
    WORD1(maep->mae_value) = WORD1(&Values);  
    if (L > sizeof(int32)) {
        WORD2(maep->mae_value) = WORD2(&Values);
        if (L > 2*sizeof(int32)) {
            WORD3(maep->mae_value) = WORD3(&Values); 
            if (L > 3*sizeof(int32)) {
                WORD4(maep->mae_value) = WORD4(&Values);
            }
        }
    }
    maep->mae_count = 1 ;
    maep->mae_time = CurrTime ;
    maap->maa_currbin++ ;
        /* Insert bin at BEGINNING of 1-count segment of list  */
    tep = maap->maa_tail;
    FBins(&maep->mae_fb, &tep->mae_fb); 
    
        /* PREPEND new bin to hash chain (take advantage of ref. locality) */
    maep->mae_next = *hp;  
    *hp = maep ;
        /* Measure the health of the hash chains... 
         *  record maximum length of any chain
         */
    if (++n > maap->maa_maxchain) maap->maa_maxchain = n;
    return(WRRET_OK) ;  
}
    
    
int CLC(p1, p2, n)
    register u_char *p1, *p2;
    register int n;
    {
    register int diff;
    while (--n >= 0)
        if (diff = *p1++ - *p2++)  return(diff);
    return(0);
}

        
void Delete_MA( maap )
    MAA *maap ;
    {
    Clear_MA(maap) ;
    free(maap) ;
}


void Clear_MA( maap )
    register MAA *maap ;
    {       
    register int i ;
    register MAE *maep ;
    
    bzero(maap->maa_hashp, (sizeof(MAE *))*maap->maa_hashs);
    maap->maa_currbin = maap->maa_maxchain =  maap->maa_cntmoves = 0;   
    maap->maa_head.FB_Bp = maap->maa_head.FB_Fp = NULL;
    maap->maa_tail = (MAE *) &maap->maa_head;
    
    for (i = 0;i<MAX_PAGES;i++) {
        if (maep = maap->maa_page[i]) {
            free(maep) ;
            maap->maa_page[i] = NULL ;
        }
        else break ;
    }
}
    
#define OUTSIZE 256 

boolean  Read_MA(fd, maap)
    XDR *fd;
    register MAA  *maap ;
    {
    register MAE *maep ;
    char outp[OUTSIZE];
    int  outl = (ISTTY(fd))?OUTSIZE:0;
    MADE made;
    OBJ  xobj;
    EnumHandle enumh = NULL; 
    extern MakeCols();
        
    bzero(made.mad_value, 2*MAX_DLENG);
    if (outl)
        enumh = ExistEnumObj(maap->maa_sobj.sob_name);
        
    if (!PutReadResp(fd, MAr_SIZE(maap->maa_currbin, 
                maap->maa_sobj.sob_dleng+maap->maa_sobj.sob_dleng2), maap)) 
        return(FALSE);
    
    if (ISTTY(fd)) {
        MakeCols(NULL);  /* Initialize formatting */
        fprintf(logfp, "  #bins= %d  Maxchain = %d  TotalSortMoves = %d\n",
                maap->maa_currbin, maap->maa_maxchain, maap->maa_cntmoves) ;
    }       
    else if (!xdr_int(fd, &maap->maa_currbin) ) 
        return(FALSE) ;
            /* XDR count field for element array that follows
             */  
        
    SetupXRep(&xobj, maap);
    
    if ((maep = (MAE *) maap->maa_head.FB_Fp) == NULL) return(TRUE);  
    while (maep) {      /* run down the sorted list... */
        if (!MA_list(fd, outp, outl, &maep->mae_made, &xobj.obj_state, enumh)) {
            return(FALSE);
        }
        if (outl) log(outp, logfp);
        maep = (MAE *) maep->mae_fb.FB_Fp;                  
    } ;
    if (outl) log("\n", logfp);
    return(TRUE);   
}   


void
List_MA(fd, OBJp)
XDR *fd;
OBJ *OBJp;
{
   MADE  bin;
   int   j, count;
   EnumHandle isEnum;
   char maout[256];

   isEnum = ExistEnumObj(OBJp->obj_name);
   
   count = get_long(fd, maout, "  #bins");
   log(maout, logfp);
   
   MakeCols(NULL);
   for (j=0;j<count;j++) {
      if (!MA_list(fd, maout, sizeof(maout), &bin, &OBJp->obj_state, isEnum))
         {
         printf(" BAD MA_list! ");
         break;
         }
      else
         log(maout, logfp);
    }
    if (count) log("\n", logfp);
} /* List_MA() */


    /*
     *  MA_list() --  I/O routine for single entry of matrix-all read data
     *
     */
boolean MA_list(fd, outp, outl, maep, objstp, enumh)
    register XDR *fd;
    char *outp;
    int outl;
    MADE  *maep;
    struct Obj_state *objstp;
    EnumHandle    enumh;
{
    register char *cp = outp;
    char *Enump, *FindEnum();
    int i;
    
    if (maep == NULL) return(FALSE);
    if (fd) {
        if (!xdr_u_int(fd, &maep->mad_count) ||
            !xdr_opaque(fd, maep->mad_value, objstp->dleng+objstp->dleng2) || 
            !xdr_int(fd, &maep->mad_time) )
            return(FALSE);
    }
        
    if (outl) {
        if (outl < 80) return(FALSE);
        *cp++ = '[';
        print_val(cp, maep->mad_value, objstp->datatype, objstp->dleng);
        if (Enump = FindEnum(enumh, maep->mad_value, objstp->dleng)) {
            strcat(cp, " \"");
            strcat(cp,  Enump);
            strcat(cp, "\"");
            cp = endof(cp);
        }
        strcat(cp, (tersemode)?":":" : ");
        print_val(endof(cp), maep->mad_value+objstp->dleng, objstp->datatyp2, 
                                 objstp->dleng2);
        
        sprintf(cp = endof(cp), "]= %d ", maep->mad_count);
        if ((i = Align(outp)) != 0)
           sprintf(endof(cp), "%*c", i, ' ');
           
        print_percent(endof(cp), objstp->totalno, maep->mad_count);
        sprintf(endof(cp), "@-%dsec ", objstp->currtime - maep->mad_time);
        MakeCols(outp);
    }
    return(TRUE);
} /* MA_list() */


Bcopy( sa, da, N)
	register char *sa, *da;
	int N;
	{
	switch (N) {
	
	case 6: *da++ = *sa++; *da++ = *sa++;
	case 4: *da++ = *sa++; *da++ = *sa++;
	case 2: *da++ = *sa++; 
	case 1: *da++ = *sa++;
	}
}