/****************************************************************************/ /* */ /* 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/select.c,v 1.5 1993/08/31 23:54:44 mogul Exp $"; /* CHANGES: * Rel 3.0: * ISI: Create SELECT object. * Aug93/DECWRL: Alpha/OSF port. */ /********************************************************************** * * SELECT Object Class: Maps Set of values -> case * * Objects of the SELECT class are invoked implicitly by "select" * statements. They are a generalization of SF objects, in which * a many->one mapping is performed from value to integer case number. * * SELECT objects are implemented using using a chained hash table * (the algorithm is from FA2). The bins are in a space which is * allocated dynamically in pages of 4K bytes. * * This code is taken more or less directly from FO, except that * the hash table of SELECT parameter values is built one entry at a * time by each call to Make_Case(). * * * Operations on SELECT class objects: * * SOBJ *Make_SELECT( object-name, &dummy, 0, datalen ) * * int Write_SELECT( (SOBJ *) SOBJ-ptr, &value , length) * Returns case number 1...N, or 0 for default. * * boolean Read_SELECT( fd, (SOBJ *) SOBJ-ptr ) * * Delete_SELECT( (SOBJ *) SOBJ-ptr ) * * Clear_SELECT( (SOBJ *) SOBJ-ptr ) * * boolean Make_Case( (SOBJ *) SOBJ-ptr ) * */ #include #include #include "stat.h" #include "sobj.h" SOBJ *Make_SELECT(); int Write_SELECT(); void Clear_SELECT(), Delete_SELECT(), List_SELECT(); boolean Read_SELECT(); /* Tranfer Vector * for external access to these routines */ GENERICOP SELECTop = { Make_SELECT, Write_SELECT, Read_SELECT, Clear_SELECT, Delete_SELECT, List_SELECT }; /* * Define SELECT object data structures * */ /* * Define SELECTA object data structures * */ #define SELECTA 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<sela_page[((i)>>BIN_pwr2)]+ \ selap->sela_esize*((i)&BIN_MASK) ) /* Hash Function == simple congruential hash */ #define hashfunc( V, S) V%S /* Bin format */ #define SELECTE struct Sel_bin_element SELECTE { SELECTE *sele_next ; /* Hash chain field */ int32 sele_caseno; /* Case index */ int32 sele_count; int32 sele_value[(MAX_DLENG+3)/4]; /* Actually reserve 4*((dleng+3)/4) bytes */ }; /* Object area format */ SELECTA { SOBJ sela_sobj ; /* SOBJ = standard root of area */ short sela_vsize ; /* Size of value */ short sela_esize ; /* Size of element */ short sela_hashs ; /* Size of hash table (#shorts) */ short sela_unused; u_int32 sela_default; /* Count of default cases */ int sela_currbin ; /* Index of first available bin */ SELECTE **sela_hashp ; /* Ptr to hash table */ SELECTE *sela_page[MAX_PAGES] ; /* Ptrs to bin segments */ /*---------------------------------------------------- Hash Table... (a vector of pointers: the heads of hash chains) /*----------------------------------------------------*/ } ; SOBJ *Make_SELECT(objname, parmp, nparms, datalen) char *objname; int datalen, nparms, *parmp; { register SELECTA *selap ; register int i ; int hsize = HASHsize ; if (datalen > MAX_DLENG){ SOBJ_error = "SELECT: Field size too big"; return(NULL); } i = (sizeof(SELECTE *))*hsize + sizeof ( SELECTA ) ; if ((selap = (SELECTA *) malloc(i)) == NULL) { SOBJ_error = "SELECT: Memory overflow" ; return(NULL) ; } bzero(selap, i) ; /* Clear entire area... */ selap->sela_vsize = ALIGN(datalen); selap->sela_esize = PTRALIGN(sizeof(SELECTE) - MAX_DLENG + selap->sela_vsize); selap->sela_hashs = hsize ; selap->sela_currbin = 0 ; selap->sela_hashp = (SELECTE **) ((char *) selap + sizeof(SELECTA) ) ; /* Start of hash table */ return(&selap->sela_sobj) ; /* SUCCESS!! */ } boolean Write_SELECT( selap, Valuep, L) register SELECTA *selap ; char *Valuep ; register int L; { register SELECTE *selep, **hp ; u_int32 HValue; union v_union Value; ZERO_UNION(&Value); bcopy(Valuep, Value.v_byte, L); HValue = SUM_UNION(&Value); hp = &selap->sela_hashp[ hashfunc(HValue, selap->sela_hashs) ]; while (selep = *hp) { if ((selep->sele_value[0] == WORD1(&Value)) && (L <= sizeof(int32) || (selep->sele_value[1] == WORD2(&Value)) )) { /* Found bin, so increment count */ selep->sele_count++ ; return(selep->sele_caseno) ; } hp = &selep->sele_next ; } /* No such bin... Use default. */ selap->sela_default++; return(0); } /* Write_SELECT() */ void Delete_SELECT( selap ) SELECTA *selap ; { register int i ; register SELECTE *selep ; for (i = 0;isela_page[i]) { free(selep) ; selap->sela_page[i] = NULL ; } else break ; } free(selap) ; } void Clear_SELECT( selap ) register SELECTA *selap ; { register int i; for (i = 0; isela_currbin; i++) { (BIN_ADDR(selap, i))->sele_count = 0; } selap->sela_default = 0; } #define OUTSIZE 256 boolean Read_SELECT(fd, selap) XDR *fd; register SELECTA *selap ; { if (!PutReadResp(fd, SELr_SIZE, &selap->sela_sobj)) return(FALSE); if (ISTTY(fd)) { printf(" #bins= %d\n", selap->sela_currbin) ; } return(TRUE); } /* * Make_Case() * * This special entry point for a SELECT object is used to incrementally * build the bins. Each Make_Case() call adds the values for a particular * case. */ boolean Make_Case( selap, caseno, parmp, nparms) register SELECTA *selap; int caseno, nparms; u_int32 *parmp; { register SELECTE **hp, *selep; int datalen = selap->sela_sobj.sob_dleng; int offset = PARMALIGN(datalen); int vsize = ALIGN(datalen); int nbins = nparms/(vsize>>2); u_int32 HValue; union v_union Value; u_char *pp; int i; ZERO_UNION(&Value); pp = ( u_char *) parmp + offset; for (i = 0; i < nbins ; i++) { bcopy(pp, Value.v_byte, datalen); HValue = SUM_UNION(&Value); hp = &selap->sela_hashp[ hashfunc(HValue, selap->sela_hashs) ]; while (selep = *hp) { /* Check to see if it is there already... */ if ((selep->sele_value[0] == WORD1(&Value)) && (datalen <= sizeof(int32) || (selep->sele_value[1] == WORD2(&Value)) )) { /* Duplicate... error! */ SOBJ_error = "Duplicate case value for field"; return(FALSE); } hp = &selep->sele_next ; } /* Now construct new bin for value... */ if (selap->sela_currbin >= BIN_MAX ) { /* We have run out of new bins.*/ return(FALSE) ; } if ((selep = BIN_ADDR( selap, selap->sela_currbin)) == NULL) { /* must obtain new page */ selep = (SELECTE *) malloc(selap->sela_esize * BIN_PAGE) ; if (selep == NULL) return(FALSE) ; selap->sela_page[(selap->sela_currbin >> BIN_pwr2)] = selep ; } /* * Fill in new bin */ selep->sele_value[0] = WORD1(&Value); if (datalen > sizeof(int32)) selep->sele_value[1] = WORD2(&Value); selep->sele_count = 0 ; selep->sele_caseno = caseno; selap->sela_currbin++ ; /* Append new bin to hash chain */ *hp = selep ; selep->sele_next = NULL; pp += vsize; } /* end of loop over values */ return(TRUE) ; } /* Make_Case() */ void List_SELECT(fd, OBJp) XDR *fd; OBJ *OBJp; { /* No remote formatting for SELECT object */ }