/****************************************************************************/
/*                                                                          */
/*      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/alpha/code/NNstat/RCS/sobjfa.c,v 1.4 1993/08/31 22:48:06 mogul Exp $";

 
 /*
  *  CHANGES:
  *   01Nov89 ISI: Change FAO_list calling sequence.
  *     Rel 3.0:
  *   RTB:  Add List routine.   
  *   ISI:  Remove redundant NL when no bins.  
  *   Aug93/DECWRL: Alpha/OSF port.  XDR is a pointer type.
  */
/*
 *   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.
 *
 */
 
/*
 *
 *          FA Object Class ==  freq-all
 *
 *    Objects of the FA class are frequency distributions of 32-bit values,
 *    using dynamically-created bins.  Thus, every different value is 
 *    counted; there are no defaults. 
 *
 *    FA objects are implemented using a chained hash table.  The bins are
 *    in a space which is allocated dynamically in pages of 4K bytes. The
 *    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 FA class objects:
 *
 *       SOBJ *Make_FA( object-name, &parmlist, nparms, datalen )
 *
 *       Write_FA( (SOBJ *) SOBJ-ptr, &value, len)
 *
 *       Read_FA( fd, (SOBJ *) SOBJ-ptr )
 *
 *       Delete_FA( (SOBJ *) SOBJ-ptr )
 *
 *       Clear_FA( (SOBJ *) SOBJ-ptr )
 *
 *       List_FA( fd, OBJp )
 *
 */
 
#include <stdio.h>
#include <sys/types.h>
#include "stat.h"
#include "sobj.h"


    /*     
     *  Define FA object data structures
     *
     */
#define FAA struct stat_xarea

#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(faap, i) (FAE *) ( \
             (char *) faap->faa_page[((i)>>BIN_pwr2)]+ \
             faap->faa_esize*((i)&BIN_MASK) ) 
                
        /* Hash Function ==  simple congruential hash */    
#define hashfunc( V, S)  V%S                                 

    /* Bin format */

#define FAE struct fa_bin_element
FAE {
    struct FBlinks fae_fb; /* Doubly-linked sort list   */
    FAE   *fae_next ;      /* Hash chain field */
    long   fae_count;
    long   fae_time;
    char   fae_value[MAX_DLENG]; /* Actually reserve 4*((dleng+3)/4) bytes */
};


    /* Object area format */

FAA {
    SOBJ   faa_sobj;          /* SOBJ = standard root of area */
    
    short  faa_vsize;         /* Size of value */
    short  faa_esize;         /* Size of element */
    short  faa_hashs;         /* Size of hash table (#shorts) */
    short  faa_maxchain;      /* Max chain length  */
    
    struct FBlinks faa_head;  /* Head of sorted list */
    FAE   *faa_tail;          /* Tail of sorted list */
    long   faa_infinity;      /* Apparent infinite count */
    long   faa_cntmoves;      /* Total places moved in sorting */
    
    int    faa_currbin;       /* Index of first available bin */
    FAE  **faa_hashp;         /* Ptr to hash table */
    FAE   *faa_page[MAX_PAGES] ;  /* Ptrs to bin segments */
    /*----------------------------------------------------
                     Hash Table... 
          (a vector of pointers: the heads of hash chains)
    /*----------------------------------------------------*/
} ;


struct FA_parms {
    int  fap_nbins ;   /* Upper limit on number of bins to be kept */
} ;

SOBJ *Make_FA() ;
boolean Write_FA(), Read_FA() ;
void Clear_FA(), Delete_FA(), List_FA() ;

    /* Transfer Vector 
     *   for external access to these routines
     */
GENERICOP FAop = { Make_FA, Write_FA, Read_FA, Clear_FA, Delete_FA, List_FA } ;

    

SOBJ *Make_FA(objname, parmp, nparms, datalen)
    char *objname;
    struct FA_parms *parmp;
    int datalen, nparms;
    {
    register FAA *faap ;
    register int i ;
    int hsize = HASHsize ;

    if (datalen > MAX_DLENG){
        SOBJ_error = "FA: Field size too big";
        return(NULL);
    }
    i = (sizeof(FAE *))*hsize + sizeof ( FAA )  ;
    if ((faap = (FAA *) malloc(i)) == NULL) {
        SOBJ_error = "FA: Memory overflow" ;
        return(NULL) ;
    }
    bzero(faap, i) ;  /* Clear entire area... */
        
    faap->faa_vsize = ALIGN(datalen);
    faap->faa_esize = PTRALIGN(sizeof(FAE) - MAX_DLENG + faap->faa_vsize);
    faap->faa_hashs = hsize ;
    SETMAXINT(faap->faa_infinity);
    faap->faa_tail = (FAE *) &faap->faa_head;
        
    faap->faa_hashp =  (FAE **) ((char *) faap + sizeof(FAA) ) ;
            /* Start of hash table */
                        
    return(&faap->faa_sobj) ;  /* SUCCESS!! */
}    
     
     
boolean Write_FA( faap, Valuep, L)
    register FAA *faap ;
    char *Valuep ;
    int L; 
    {
    register FAE *faep, **thp, *tep;
    FAE **hp;
    int n;
    u_int32 HValue;      
    union v_union Value;
     
    ZERO_UNION(&Value);
    bcopy(Valuep, Value.v_byte, L);
    HValue = SUM_UNION(&Value);

    hp = thp = &faap->faa_hashp[ hashfunc(HValue, faap->faa_hashs) ];
    
    n = 0;  
    while (faep = *thp) {
        if ((WORD1(faep->fae_value) == WORD1(&Value))  
            && (L <= sizeof(int32) ||
              (WORD2(faep->fae_value) == WORD2(&Value)) ))
            {
                /* Found bin, so increment count */
            faep->fae_count++ ;
            faep->fae_time = CurrTime ;
            if (faep->fae_count >= 
                        (tep = (FAE *) faep->fae_fb.FB_Bp)->fae_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 (faep == faap->faa_tail) 
                    faap->faa_tail = (FAE *) faep->fae_fb.FB_Bp;
                else if (faep->fae_count == 2 && faap->faa_tail->fae_count>2)
                    faap->faa_tail = faep;      
                    
                FBrem(&faep->fae_fb);
                do {
                    tep = (FAE *) tep->fae_fb.FB_Bp;
                    faap->faa_cntmoves++;   /* Keep performance stat */
                    } while (faep->fae_count >= tep->fae_count);
                FBins(&faep->fae_fb, &tep->fae_fb);
            }
            else {
                /* Don't have to move bin at all. May still have to
                 *  adjust tail pointer...
                 */
                if (faep->fae_count == 2)
                    faap->faa_tail = faep;
            }
#ifdef TEST                       
            Valid(faap);
#endif
            return(WRRET_OK) ;
         }
        thp = &faep->fae_next ;
        n++;
    }
    
        /* No such bin... Must create new one and
         *   insert it into the hash chain and the sorted list...
         */      
    if (faap->faa_currbin >= BIN_MAX ) {
            /* We have run out of new bins. Count as orphan. */
        faap->faa_sobj.sob_orphans++ ;
        return(WRRET_OK) ;
    }
        
    if ((faep = BIN_ADDR( faap, faap->faa_currbin)) == NULL) {
            /*  must obtain new page */
        faep  = (FAE *) malloc(faap->faa_esize * BIN_PAGE) ;
        if (faep == NULL) {
            /* Cannot get new bin page. Count as orphan. */
            faap->faa_sobj.sob_orphans++ ;
            return(WRRET_OK) ;
        }
        faap->faa_page[(faap->faa_currbin >> BIN_pwr2)] = faep ;
    }
        /*
         *   Fill in new bin 
         */
    WORD1(faep->fae_value) = WORD1(&Value);  
    if (L > sizeof(int32))
        WORD2(faep->fae_value) = WORD2(&Value);
    faep->fae_count = 1 ;
    faep->fae_time = CurrTime ;
    faap->faa_currbin++ ;
        /* Insert bin at BEGINNING of 1-count segment of list  */
    tep = faap->faa_tail;
    FBins(&faep->fae_fb, &tep->fae_fb); 
#ifdef TEST                       
    Valid(faap);
#endif
        /* Prepend new bin to hash chain     */
    faep->fae_next = *hp;   
    *hp = faep ;
        /* Measure the health of the hash chains... 
         *  record maximum length of any chain
         */
    if (++n > faap->faa_maxchain) faap->faa_maxchain = n;
    return(WRRET_OK) ;  
}
    
        
void Delete_FA( faap )
    FAA *faap ;
    {
    Clear_FA(faap) ;
    free(faap) ;
}
 

void Clear_FA( faap )
    register FAA *faap ;
    {       
    register int i ;
    register FAE *faep ;
    
    bzero(faap->faa_hashp, (sizeof(FAE *))*faap->faa_hashs);
    faap->faa_currbin = faap->faa_maxchain = faap->faa_cntmoves = 0;
    faap->faa_head.FB_Bp = faap->faa_head.FB_Fp = NULL;
    faap->faa_tail = (FAE *) &faap->faa_head;
    
    for (i = 0;i<MAX_PAGES;i++) {
        if (faep = faap->faa_page[i]) {
            free(faep) ;
            faap->faa_page[i] = NULL ;
        }
        else break ;
    }
}
    
#define OUTSIZE 256 

boolean Read_FA(fd, faap)
    XDR *fd;
    register FAA  *faap ;
    {
    register FAE *faep ;
    char outp[OUTSIZE];
    int  outl = (ISTTY(fd))?OUTSIZE:0;
    FADE fade;
    OBJ  xobj;
    EnumHandle isenum = (ExistEnumObj(faap->faa_sobj.sob_name));
    extern MakeCols();
        
    bzero(fade.fad_value, MAX_DLENG);
    
    if (!PutReadResp(fd, FAr_SIZE(faap->faa_currbin, faap->faa_sobj.sob_dleng),
                    faap))
        return(FALSE);
    
    if (ISTTY(fd)) {
        MakeCols(NULL);  /* Initialize formatting */
        fprintf(logfp, "  #bins= %d  Maxchain = %d  TotalSortMoves = %d\n", 
            faap->faa_currbin, faap->faa_maxchain, faap->faa_cntmoves) ;
    }       
    else if (!xdr_int(fd, &faap->faa_currbin) ) 
        return(FALSE) ;
            /* XDR count field for element array that follows
             */  
        
    SetupXRep(&xobj, faap);
    
    if ((faep = (FAE *) faap->faa_head.FB_Fp) == NULL) return(TRUE);  
    while (faep) {                           
        fade.fad_count = faep->fae_count;
        fade.fad_time = faep->fae_time;
        bcopy(faep->fae_value, fade.fad_value, faap->faa_sobj.sob_dleng);
            
        if (!FAO_list(fd, outp, outl, &fade, &xobj.obj_state, 
                                                         isenum, FAOBJ)) {
            return(FALSE);
        }
        if (outl) log(outp, logfp);
        faep =  (FAE *) faep->fae_fb.FB_Fp;   
                    
    } ;
    if (outl) log("\n", logfp); 
    return(TRUE);
} /* Read_FA() */  

    
void
List_FA(fd, OBJp)
XDR *fd;
OBJ *OBJp;
{
   FADE  bin;
   int   j, count;
   EnumHandle isEnum;
   char out[OUTSIZE];

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


#ifdef TEST                       
Valid(faap)
    register FAA *faap;
    {
    register FAE *faep = (FAE *) &faap->faa_head, *tep;
    
    while (tep = (FAE *) faep->fae_fb.FB_Fp) {
        if (tep->fae_count > faep->fae_count) ERROR();
        faep = tep;
    }
}

ERROR()
  {
  printf("error");
 }
#endif