00001 #include "niml_private.h"
00002 
00003 /***************************************************************************/
00004 /************************  NIML malloc stuff *******************************/
00005 /***************************************************************************/
00006 
00007 /*-------------------------------------------------------------------------*/
00008 /** 25 Mar 2003: allow user to replace malloc, realloc, free functions    **/
00009 
00010 static void * (*user_malloc)(size_t)         = NULL ;
00011 static void * (*user_realloc)(void *,size_t) = NULL ;
00012 static void   (*user_free)(void *)           = NULL ;
00013 static int  use_userfunc                     = 0    ;
00014 static int  ni_mall_used                     = 0    ;
00015 
00016 /*-------------------------------------------------------------------------*/
00017 /*! Allow user to replace malloc(), realloc(), and free() functions used
00018     in NI_malloc(), NI_realloc(), and NI_free().
00019       - um = replacement for malloc()
00020       - ur = replacement for realloc()
00021       - uf = replacement for free()
00022       - all 3 must be non-NULL
00023       - this function must be called BEFORE any call to NI_malloc() etc.
00024         takes place, or this function will fail
00025       - return value is 1 if the replacement is accepted, 0 if not
00026       - note that NI_malloc() always 0 fills the result, even the one
00027          returned by um()
00028       - RWCox - 25 Mar 2003 (VR Day)
00029 ---------------------------------------------------------------------------*/
00030 
00031 int NI_malloc_replace( void *(*um)(size_t)        ,
00032                        void *(*ur)(void *,size_t) ,
00033                        void  (*uf)(void *)         ){
00034 
00035   if( ni_mall_used ||
00036       use_userfunc ||
00037       um == NULL   ||
00038       ur == NULL   ||
00039       uf == NULL     ) return 0 ;
00040 
00041   user_malloc  = um ;
00042   user_realloc = ur ;
00043   user_free    = uf ;
00044   use_userfunc = 1  ;
00045   return 1 ;
00046 }
00047 
00048 #if defined(NIML_OLD_MALLOC) || defined(DONT_USE_MCW_MALLOC)
00049 
00050 /*--------------------------------------------------------------------------*/
00051 /*! Allocate memory (actually uses calloc); calls exit() if it fails.
00052 ----------------------------------------------------------------------------*/
00053 
00054 void * old_NI_malloc( size_t len )
00055 {
00056    void *p ;
00057    if( use_userfunc ){
00058      p = user_malloc(len) ; if( p != NULL ) memset(p,0,len) ;
00059    } else {
00060      p = calloc(1,len) ;
00061    }
00062    if( p == NULL ){
00063      fprintf(stderr,"** ERROR: old_NI_malloc() fails. Aauugghh!\n") ;
00064      NI_sleep(333); exit(1);
00065    }
00066    ni_mall_used = 1 ; return p ;
00067 }
00068 
00069 /*--------------------------------------------------------------------------*/
00070 /*! Free memory; NULL pointer is just ignored.
00071 ----------------------------------------------------------------------------*/
00072 
00073 void NI_free( void *p )
00074 {
00075    if( p != NULL ){
00076      if( use_userfunc ) user_free(p) ;
00077      else               free(p) ;
00078    }
00079    ni_mall_used = 1 ;
00080 }
00081 
00082 /*--------------------------------------------------------------------------*/
00083 /*! Reallocate memory; calls exit() if it fails.
00084 ----------------------------------------------------------------------------*/
00085 
00086 void * old_NI_realloc( void *p , size_t len )
00087 {
00088    void *q ;
00089 
00090    if( use_userfunc ) q = user_realloc( p , len ) ;
00091    else               q = realloc( p , len ) ;
00092    if( q == NULL && len > 0 ){
00093      fprintf(stderr,"** ERROR: old_NI_realloc() fails. Ooooogg!\n");
00094      NI_sleep(333); exit(1);
00095    }
00096    ni_mall_used = 1 ; return q ;
00097 }
00098 
00099 /**** Fake routines with no meaning in this NI_malloc version ****/
00100 
00101 char * NI_malloc_status          (void){ return "disabled"; }
00102 void   NI_malloc_dump            (void){ return;      }
00103 void   NI_malloc_enable_tracking (void){ return;      }
00104 int    NI_malloc_tracking_enabled(void){ return 0;    }
00105 
00106 /*****************************************************************************/
00107 #else  /**  not NIML_OLD_MALLOC or DONT_USE_MCW_MALLOC                 *******/
00108        /**  18 Nov 2002: keep track of mallocs, as in mcw_malloc.[ch]  *******/
00109 /*****************************************************************************/
00110 
00111 #define MAGIC  ((char) 0xd7)     /* goes in extra bytes at ends of blocks */
00112 #define NEXTRA (2*sizeof(int))   /* number of extra bytes */
00113 
00114 #undef  UINT
00115 #define UINT unsigned int
00116 
00117 /*-- struct to hold info about each malloc()-ed block --*/
00118 
00119 typedef struct {
00120   void  *pmt ;   /* pointer to actually malloc-ed block
00121                     (user ptr is +NEXTRA bytes later)   */
00122   size_t psz ;   /* size of allocated block */
00123   char  *pfn ;   /* function name that called */
00124   int    pln ;   /* function line number */
00125   UINT   pss ;   /* serial number of this malloc */
00126 } NI_mallitem ;
00127 
00128 /** set hash table size (to a prime number, please) **/
00129 
00130 #undef  SLOTS
00131 #define SLOTS 1031
00132 
00133 /** #define SLOTS 2053  **/
00134 /** #define SLOTS 4099  **/
00135 /** #define SLOTS 8191  **/
00136 /** #define SLOTS 16381 **/
00137 /** #define SLOTS 32003 **/
00138 
00139 static NI_mallitem ** htab  = NULL ; /* table of lists */
00140 static int *          nhtab = NULL ; /* size of each list */
00141 static UINT          serial = 0    ; /* serial number of allocation */
00142 
00143 #undef INLINE
00144 #ifdef __GNUC__
00145 # define INLINE inline
00146 #else
00147 # define INLINE /*nada*/
00148 #endif
00149 
00150 /*** prototypes for internal routines defined below ***/
00151 
00152 static NI_mallitem * ptr_tracker( void * ) ;
00153 static NI_mallitem * find_empty_slot( int ) ;
00154 static void add_tracker( void * , size_t , char * , int ) ;
00155 static void * malloc_track( size_t , char * , int ) ;
00156 static void probe_track( NI_mallitem * , char *,int ) ;
00157 static void * realloc_track( NI_mallitem *, size_t , char *, int  ) ;
00158 static void * calloc_track( size_t , size_t , char * , int  ) ;
00159 static void free_track( NI_mallitem * ) ;
00160 static void qsort_intint( int, int *, int * ) ;
00161 
00162 #undef malloc
00163 #undef realloc
00164 #undef calloc
00165 #undef free
00166 
00167 /*---------------------------------------------------------------*/
00168 /*!  Compute a unique non-negative integer key from an address
00169 -----------------------------------------------------------------*/
00170 
00171 static INLINE UINT mallkey( char *fred )
00172 {
00173    UINT q = (UINT) fred ;
00174 
00175    q =   ((q & 0xf0f0f0f0) >> 4)   /* swap nibbles */
00176        | ((q & 0x0f0f0f0f) << 4) ;
00177 
00178    return q ;
00179 }
00180 
00181 /*----------------------------------------------------------------*/
00182 /*! Find an address in the hash table;
00183     returns a pointer to the NI_mallitem that owns it (or NULL)
00184 ------------------------------------------------------------------*/
00185 
00186 static NI_mallitem * ptr_tracker( void *fred )
00187 {
00188    int jj,kk ;
00189 
00190    if( fred == NULL ) return NULL ;
00191 
00192    jj = mallkey((char *)fred) % SLOTS ;  /* hash table location */
00193 
00194    if( htab[jj] == NULL ) return NULL ;  /* nothing there */
00195 
00196    for( kk=0 ; kk < nhtab[jj] ; kk++ )   /* scan for match */
00197      if( htab[jj][kk].pmt == fred ) return (htab[jj]+kk) ;
00198 
00199    return NULL ; /* no match found */
00200 }
00201 
00202 /*-----------------------------------------------------------------*/
00203 /*-- this macro finds an address from the user in the hash table --*/
00204 
00205 #define shift_tracker(fff)  ptr_tracker( ((char *)(fff)) - NEXTRA )
00206 
00207 /*-----------------------------------------------------------------*/
00208 /*! Find an empty entry in the hash table list [jj] and return
00209    a pointer to it.  Will create the entry, if need be.
00210 -------------------------------------------------------------------*/
00211 
00212 static NI_mallitem * find_empty_slot( int jj )
00213 {
00214    int kk ;
00215 
00216    if( htab[jj] == NULL ){                                    /* must make new list  */
00217      htab[jj] = (NI_mallitem *) malloc(sizeof(NI_mallitem)) ; /* of length 1 at [jj] */
00218     nhtab[jj] = 1 ;
00219      kk       = 0 ;
00220      htab[jj][0].pmt = NULL ;  /* mark as empty */
00221    } else {
00222      for( kk=nhtab[jj]-1 ; kk >= 0 ; kk-- )    /* scan (backwards) for NULL entry */
00223        if( htab[jj][kk].pmt == NULL ) break ;  /* found it? */
00224 
00225      if( kk < 0 ){                             /* must make list longer */
00226        kk = nhtab[jj] ; nhtab[jj]++ ;
00227        htab[jj] = (NI_mallitem *) realloc( htab[jj], sizeof(NI_mallitem)*nhtab[jj] ) ;
00228        htab[jj][kk].pmt = NULL ;  /* mark as empty */
00229      }
00230    }
00231 
00232    return (htab[jj]+kk) ;
00233 }
00234 
00235 /*----------------------------------------------------------------*/
00236 /*! Add an entry to the hash table, given the
00237    address, the user's size, and the filename and line number.
00238 ------------------------------------------------------------------*/
00239 
00240 static void add_tracker( void *fred , size_t n , char *fn , int ln )
00241 {
00242    int jj ;
00243    NI_mallitem *ip ;
00244 
00245    if( fred == NULL ) return ;   /* bad news */
00246 
00247    jj = mallkey((char *)fred) % SLOTS ;  /* which hash list to use */
00248    ip = find_empty_slot(jj) ;            /* get an empty slot in this list */
00249 
00250    /* now put the data into the hash table */
00251 
00252    ip->pmt = fred ;
00253    ip->psz = n ;
00254    ip->pfn = fn ;
00255    ip->pln = ln ;
00256    ip->pss = ++serial ;
00257 
00258    return ;
00259 }
00260 
00261 /*-----------------------------------------------------------------*/
00262 /*!  The tracking replacement for malloc().
00263 -------------------------------------------------------------------*/
00264 
00265 static void * malloc_track( size_t n , char *fn , int ln )
00266 {
00267    char *fred ;
00268    size_t nn = n + 2*NEXTRA ;
00269    int ii ;
00270 
00271    fred = (char *)malloc(nn) ;
00272    if( fred == NULL ) return NULL ;  /* real bad news */
00273 
00274    /* mark overrun buffers */
00275 
00276    memset( fred           , MAGIC , NEXTRA ) ;
00277    memset( fred+(n+NEXTRA), MAGIC , NEXTRA ) ;
00278 
00279    ni_mall_used = 1 ;
00280    add_tracker(fred,n,fn,ln) ;      /* put in hash table */
00281    return (void *)(fred+NEXTRA) ;
00282 }
00283 
00284 /*-----------------------------------------------------------------*/
00285 /*! Check an entry in the hash table for local overrun integrity.
00286 -------------------------------------------------------------------*/
00287 
00288 static void probe_track( NI_mallitem *ip , char *fn, int ln )
00289 {
00290    int ii ;
00291    size_t n ;
00292    char *fred ;
00293 
00294    if( ip == NULL ) return ; /* error */
00295    fred = (char *) ip->pmt ; if( fred == NULL ) return ;
00296    n = ip->psz ;
00297 
00298    for( ii=0 ; ii < NEXTRA ; ii++ )
00299      if( fred[ii] != MAGIC ){
00300        fprintf(stderr,"*** NI_malloc pre-corruption!  "
00301                       "serial=%u size=%u source=%s line#=%d\n",
00302                       ip->pss,(unsigned int)ip->psz,ip->pfn,ip->pln ) ;
00303        if( fn != NULL ) fprintf(stderr,"   Caller=%s line#=%d\n",fn,ln) ;
00304        break ;
00305      }
00306 
00307    for( ii=0 ; ii < NEXTRA ; ii++ )
00308      if( fred[n+NEXTRA+ii] != MAGIC ){
00309        fprintf(stderr,"*** NI_malloc post-corruption!  "
00310                       "serial=%u size=%u source=%s line#=%d\n",
00311                       ip->pss,(unsigned int)ip->psz,ip->pfn,ip->pln ) ;
00312        if( fn != NULL ) fprintf(stderr,"   Caller=%s line#=%d\n",fn,ln) ;
00313        break ;
00314      }
00315 
00316    return ;
00317 }
00318 
00319 /*-------------------------------------------------------------------*/
00320 /*! The tracking replacement for realloc().
00321 ---------------------------------------------------------------------*/
00322 
00323 static void * realloc_track( NI_mallitem *ip, size_t n, char *fn, int ln )
00324 {
00325    char *nfred , *cfred ;
00326    size_t nn = n + 2*NEXTRA ;
00327    int ii , cjj,njj , kk ;
00328 
00329    if( ip == NULL ) return NULL ;  /* should not happen */
00330 
00331    probe_track(ip,fn,ln) ;    /* check for integrity before reallocation */
00332    cfred = (char *)ip->pmt ;  /* old address */
00333 
00334    ni_mall_used = 1 ;
00335    nfred = (char *)realloc( (void *)cfred , nn ) ;
00336    if( nfred == NULL ) return NULL ;  /* this is bad - real bad */
00337 
00338    memset( nfred           , MAGIC , NEXTRA ) ;
00339    memset( nfred+(n+NEXTRA), MAGIC , NEXTRA ) ;
00340 
00341    cjj = mallkey(cfred) % SLOTS ;  /* hash table list for old */
00342    njj = mallkey(nfred) % SLOTS ;  /* and for new address */
00343 
00344    if( cjj == njj ){  /* can just update old hashtable entry */
00345 
00346      ip->pmt = nfred ;
00347      ip->psz = n ;
00348      ip->pfn = fn ;
00349      ip->pln = ln ;
00350      ip->pss = ++serial ;
00351 
00352    } else {           /* must move into a different list */
00353 
00354      add_tracker( nfred , n , fn , ln ) ;
00355 
00356      ip->pmt = NULL ; /* mark old entry as free */
00357    }
00358 
00359    return (void *)(nfred+NEXTRA) ;
00360 }
00361 
00362 /*-----------------------------------------------------------------*/
00363 /*!  Tracking replacement for calloc().
00364 -------------------------------------------------------------------*/
00365 
00366 static void * calloc_track( size_t n , size_t m , char *fn , int ln )
00367 {
00368    void *fred ;
00369    size_t nn = n*m ;
00370 
00371    fred = malloc_track(nn,fn,ln) ; if( fred == NULL ) return NULL ;
00372    memset( fred , 0 , nn ) ;
00373    return fred ;
00374 }
00375 
00376 /*-----------------------------------------------------------------*/
00377 /*!  Tracking replacement for free().
00378 -------------------------------------------------------------------*/
00379 
00380 static void free_track( NI_mallitem *ip )
00381 {
00382    char *cfred ;
00383 
00384    if( ip == NULL ) return ;
00385    cfred = (char *) ip->pmt ;
00386    if( cfred == NULL ) return ;
00387 
00388    probe_track(ip,NULL,0) ;  /* check for integrity before freeing */
00389 
00390    ni_mall_used = 1 ;
00391    free(cfred) ; ip->pmt = NULL ; return ;
00392 }
00393 
00394 /*-----------------------------------------------------------------*/
00395 /*!  Return a status string about the situation.
00396      This is stored in a static buffer, so don't free it.
00397 -------------------------------------------------------------------*/
00398 
00399 static int use_tracking = 0 ;  /* is the tracking enabled? */
00400 
00401 char * NI_malloc_status(void)
00402 {
00403    static char buf[128] = "\0" ;
00404    int jj,kk , nptr=0 ; size_t nbyt=0 ;
00405 
00406    if( ! use_tracking ) return "not enabled" ;
00407 
00408    for( jj=0 ; jj < SLOTS ; jj++ ){
00409      for( kk=0 ; kk < nhtab[jj] ; kk++ ){
00410        if( htab[jj][kk].pmt != NULL ){
00411          probe_track( htab[jj]+kk , NULL,0 ) ; /* check for integrity */
00412          nptr++ ; nbyt += htab[jj][kk].psz ;
00413        }
00414      }
00415    }
00416 
00417    sprintf(buf,"chunks=%d bytes=%u",nptr,(UINT)nbyt) ;
00418    return buf ;
00419 }
00420 
00421 /*-----------------------------------------------------------------*/
00422 /*!  Write a file with lots of info about the current status.
00423 -------------------------------------------------------------------*/
00424 
00425 void NI_malloc_dump(void)
00426 {
00427    int ii,jj,kk ;
00428    char fname[32] , *str ;
00429    FILE *fp = NULL ;
00430    int nptr=0 ;
00431    int *ss , *jk ;
00432 
00433    if( ! use_tracking ) return ;
00434 
00435    /* find and open an output file */
00436 
00437    for( ii=1 ; ii < 1000 ; ii++ ){
00438      sprintf(fname,"NI_malldump.%03d",ii) ;
00439      if( NI_is_file(fname) ) continue ;
00440      fp = fopen( fname , "w" ) ;
00441      if( fp == NULL ){
00442        fprintf(stderr,"** Unable to open file %s for malloc table dump!\n",
00443                fname ) ;
00444        return ;
00445      }
00446      break ;
00447    }
00448 
00449    if( fp == NULL ){
00450      fprintf(stderr,"** Attempt to exceed 999 malloc table dump files!\n") ;
00451      return ;
00452    }
00453 
00454    /* count number of entries in the hash table */
00455 
00456    for( jj=0 ; jj < SLOTS ; jj++ ){
00457      for( kk=0 ; kk < nhtab[jj] ; kk++ ){
00458        if( htab[jj][kk].pmt != NULL ) nptr++ ;
00459      }
00460    }
00461 
00462    if( nptr < 1 ){
00463      fprintf(fp    ,"--- Nothing is malloc()-ed !? ---\n") ;
00464      fprintf(stderr,"--- Nothing is malloc()-ed !? ---\n") ;
00465      fclose(fp) ;
00466    }
00467 
00468    /* setup to sort by serial number */
00469 
00470    ss = (int *) malloc(sizeof(int)*nptr) ;  /* serial number */
00471    jk = (int *) malloc(sizeof(int)*nptr) ;  /* holds combination of jj and kk */
00472 
00473 #define JBASE 32768  /* JBASE * SLOTS must be less than max int */
00474 
00475    /* scan table for non-NULL entries */
00476 
00477    for( ii=jj=0 ; jj < SLOTS ; jj++ ){
00478      for( kk=0 ; kk < nhtab[jj] ; kk++ ){
00479        if( htab[jj][kk].pmt != NULL ){
00480          ss[ii] = htab[jj][kk].pss ;   /* save serial number */
00481          jk[ii] = JBASE*jj + kk ;      /* save jj and kk */
00482          ii++ ;
00483        }
00484      }
00485    }
00486 
00487    qsort_intint( nptr , ss , jk ) ;  /* sort by ss, carrying jk along */
00488 
00489    /* now print table in serial number order */
00490 
00491    fprintf(fp, "MCW Malloc Table Dump:\n"
00492                "serial# size       source file          line# address    hash(j,k)\n"
00493                "------- ---------- -------------------- ----- ---------- ---------\n") ;
00494 
00495    for( ii=0 ; ii < nptr ; ii++ ){
00496      jj = jk[ii] / JBASE ;           /* retrieve jj and kk */
00497      kk = jk[ii] % JBASE ;
00498      if( htab[jj][kk].pmt != NULL ){
00499        fprintf(fp,"%7u %10u %-20.30s %5d %10p %5d %3d",
00500                htab[jj][kk].pss , (unsigned int)htab[jj][kk].psz ,
00501                htab[jj][kk].pfn , htab[jj][kk].pln , htab[jj][kk].pmt ,
00502                jj,kk ) ;
00503        fprintf(fp,"\n") ;
00504      }
00505      else
00506        fprintf(fp,"*** Error at ii=%d jj=%d kk=%d\n",ii,jj,kk) ;
00507    }
00508 
00509    free(ss) ; free(jk) ;
00510 
00511    /* and print out the summary line (to the file and screen) */
00512 
00513    str = NI_malloc_status() ;
00514    fprintf(fp,"----- Summary: %s\n",str) ;
00515    fclose(fp) ;
00516 
00517    fprintf(stderr,"** Malloc table dumped to file %s\n",fname) ;
00518    fprintf(stderr,"** Summary: %s\n",str) ;
00519 
00520    return ;
00521 }
00522 
00523 /*----------------------------------------------------------------*/
00524 /*!  Turn on use of the tracking routines.
00525 ------------------------------------------------------------------*/
00526 
00527 void NI_malloc_enable_tracking(void)       /* cannot be disabled */
00528 {
00529    char *str ;
00530 
00531    if( use_userfunc ) return ;   /* 25 Mar 2003 */
00532    ni_mall_used = 1 ;
00533 
00534    if( use_tracking ) return ;   /* 05 Nov 2001 */
00535 
00536    str = getenv("AFNI_NO_MCW_MALLOC") ;
00537    if( str == NULL )
00538      str = getenv("NIML_MALLOC_DISABLE") ;
00539 
00540    use_tracking = 1 ;
00541    if( str!=NULL && ( *str=='y' || *str=='Y') ) use_tracking = 0 ;
00542 
00543    if( use_tracking && htab == NULL ){  /* initialize hash table */
00544      int jj ;
00545      htab  = (NI_mallitem **) malloc( SLOTS * sizeof(NI_mallitem *) ) ;
00546      nhtab = (int *)          malloc( SLOTS * sizeof(int) ) ;
00547      for( jj=0 ; jj < SLOTS ; jj++ ){
00548        htab[jj] = NULL ; nhtab[jj] = 0 ;
00549      }
00550    }
00551 
00552    return ;
00553 }
00554 
00555 /*---------------------------------------------------------------*/
00556 /*! Lets the user check if the tracking routines are in use.
00557 -----------------------------------------------------------------*/
00558 
00559 int NI_malloc_tracking_enabled(void)
00560 {
00561   return (use_tracking != 0) ;
00562 }
00563 
00564 /*--------------------------------------------------------------------------*/
00565 /*! Allocate memory (actually uses calloc); calls exit() if it fails.
00566 ----------------------------------------------------------------------------*/
00567 
00568 void * hidden_NI_malloc( size_t n , char *fnam , int lnum )
00569 {
00570    void *p ;
00571 
00572         if( use_userfunc ){ p = user_malloc(n); if(p)memset(p,0,n); }
00573    else if( use_tracking )  p = calloc_track(1,n,fnam,lnum) ;
00574    else                     p = calloc(1,n) ;
00575 
00576    if( p == NULL ){
00577      fprintf(stderr,"** ERROR: NI_malloc() fails. Aauugghh!\n") ;
00578      NI_sleep(333); exit(1);
00579    }
00580 
00581 #ifdef NIML_DEBUG
00582 NI_dpr("hidden_NI_malloc: called from %s#%d\n",fnam,lnum) ;
00583 #endif
00584 
00585    return p ;
00586 }
00587 
00588 /*--------------------------------------------------------------------------*/
00589 /*! Reallocate memory; calls exit() if it fails.
00590 ----------------------------------------------------------------------------*/
00591 
00592 void * hidden_NI_realloc( void *fred , size_t n , char *fnam , int lnum )
00593 {
00594    NI_mallitem *ip ;
00595    void *q ;
00596 
00597    if( fred == NULL )
00598       return hidden_NI_malloc( n , fnam , lnum ) ;
00599 
00600    if( use_userfunc )
00601      q = user_realloc( fred , n ) ;
00602    else if( use_tracking && (ip=shift_tracker(fred)) != NULL )
00603      q = realloc_track( ip , n , fnam,lnum ) ;
00604    else
00605      q = realloc( fred , n ) ;
00606 
00607    if( q == NULL && n > 0 ){
00608       fprintf(stderr,"** ERROR: NI_realloc() fails. Ooooogg!\n");
00609       NI_sleep(333); exit(1);
00610    }
00611 
00612 #ifdef NIML_DEBUG
00613 NI_dpr("hidden_NI_realloc: called from %s#%d\n",fnam,lnum) ;
00614 #endif
00615 
00616    return q ;
00617 }
00618 
00619 /*-----------------------------------------------------------------
00620     The actual replacment for free()
00621 -------------------------------------------------------------------*/
00622 
00623 void hidden_NI_free( void *fred , char *fnam , int lnum )
00624 {
00625    NI_mallitem *ip ;
00626 
00627    if( fred == NULL ) return ;
00628 
00629    if( use_userfunc )                                          user_free(fred) ;
00630    else if( use_tracking && (ip=shift_tracker(fred)) != NULL ) free_track( ip ) ;
00631    else                                                        free( fred ) ;
00632 
00633 #ifdef NIML_DEBUG
00634 NI_dpr("hidden_NI_free: called from %s#%d\n",fnam,lnum) ;
00635 #endif
00636 
00637 }
00638 
00639 /*------------------------------------------------*/
00640 /*! Insertion_sort : sort an array of int + int.  */
00641 
00642 static void isort_intint( int n , int * ar , int * iar )
00643 {
00644    register int  j , p ;  /* array indices */
00645    register int   temp ;  /* a[j] holding place */
00646    register int  itemp ;
00647    register int * a = ar ;
00648    register int  * ia = iar ;
00649 
00650    if( n < 2 ) return ;
00651 
00652    for( j=1 ; j < n ; j++ ){
00653 
00654      if( a[j] < a[j-1] ){   /* out of order */
00655         p    = j ;
00656         temp = a[j] ; itemp = ia[j] ;
00657 
00658        do{
00659            a[p] =  a[p-1] ; /* at this point, a[p-1] > temp, so move it up */
00660           ia[p] = ia[p-1] ;
00661           p-- ;
00662         } while( p > 0 && temp < a[p-1] ) ;
00663 
00664         a[p] = temp ;       /* finally, put temp in its place */
00665        ia[p] = itemp ;
00666      }
00667    }
00668 }
00669 
00670 /*------------------------------------------------------*/
00671 /*! Recursive part of quicksort (stack implementation). */
00672 
00673 #define QS_STACK  1024  /* stack size */
00674 #define QS_SWAPF(x,y) ( temp=(x),(x)=(y),(y)= temp)
00675 #define QS_SWAPI(i,j) (itemp=(i),(i)=(j),(j)=itemp)
00676 
00677 static void qsrec_intint( int n , int * ar , int * iar , int cutoff )
00678 {
00679    register int i , j ;        /* scanning indices */
00680    register int temp , pivot ; /* holding places */
00681    register int  itemp , ipivot ;
00682    register int * a = ar ;
00683    register int  * ia = iar ;
00684 
00685    int left , right , mst , stack[QS_STACK] , nnew ;
00686 
00687    /* return if too short (insertion sort will clean up) */
00688 
00689    if( cutoff < 3 ) cutoff = 3 ;
00690    if( n < cutoff ) return ;
00691 
00692    /* initialize stack to start with whole array */
00693 
00694    stack[0] = 0   ;
00695    stack[1] = n-1 ;
00696    mst      = 2   ;
00697 
00698    /* loop while the stack is nonempty */
00699 
00700    while( mst > 0 ){
00701       right = stack[--mst] ;  /* work on subarray from left -> right */
00702       left  = stack[--mst] ;
00703 
00704       i = ( left + right ) / 2 ;           /* middle of subarray */
00705 
00706       /* sort the left, middle, and right a[]'s */
00707 
00708       if( a[left] > a[i]     ){ QS_SWAPF(a[left] ,a[i]    ); QS_SWAPI(ia[left] ,ia[i]    ); }
00709       if( a[left] > a[right] ){ QS_SWAPF(a[left] ,a[right]); QS_SWAPI(ia[left] ,ia[right]); }
00710       if( a[i] > a[right]    ){ QS_SWAPF(a[right],a[i]    ); QS_SWAPI(ia[right],ia[i]    ); }
00711 
00712       pivot  = a[i] ;                        /* a[i] is the median-of-3 pivot! */
00713       a[i]   = a[right] ;
00714       ipivot = ia[i] ;
00715       ia[i]  = ia[right] ;
00716 
00717       i = left ;                            /* initialize scanning */
00718       j = right ;
00719 
00720       /*----- partition:  move elements bigger than pivot up and elements
00721                           smaller than pivot down, scanning in from ends -----*/
00722 
00723       do{
00724         for( ; a[++i] < pivot ; ) ;  /* scan i up,   until a[i] >= pivot */
00725         for( ; a[--j] > pivot ; ) ;  /* scan j down, until a[j] <= pivot */
00726 
00727         if( j <= i ) break ;         /* if j meets i, quit */
00728 
00729         QS_SWAPF( a[i] , a[j] ) ; QS_SWAPI( ia[i] , ia[j] ) ;
00730       } while( 1 ) ;
00731 
00732       /*----- at this point, the array is partitioned -----*/
00733 
00734       a[right]  = a[i] ;           /*restore the pivot*/
00735       a[i]      = pivot ;
00736       ia[right] = ia[i] ;
00737       ia[i]     = ipivot ;
00738 
00739       /*----- push subarrays [left..i-1] and [i+1..right] onto stack, if big -----*/
00740 
00741       nnew = 0 ;
00742       if( (i-left)  > cutoff ){ stack[mst++] = left ; stack[mst++] = i-1   ; nnew++ ; }
00743       if( (right-i) > cutoff ){ stack[mst++] = i+1  ; stack[mst++] = right ; nnew++ ; }
00744 
00745       /* if just added two subarrays to stack, make sure shorter one comes first */
00746 
00747       if( nnew == 2 && stack[mst-3] - stack[mst-4] > stack[mst-1] - stack[mst-2] ){
00748          QS_SWAPI( stack[mst-4] , stack[mst-2] ) ;
00749          QS_SWAPI( stack[mst-3] , stack[mst-1] ) ;
00750       }
00751 
00752    }  /* end of while stack is non-empty */
00753 
00754 }
00755 
00756 /*-----------------------------------------------------------------*/
00757 /*! Sort an array partially recursively, and partially insertion.  */
00758 
00759 #ifndef QS_CUTOFF
00760 #define QS_CUTOFF 10
00761 #endif
00762 
00763 void qsort_intint( int n , int * a , int * ia )
00764 {
00765    qsrec_intint( n , a , ia , QS_CUTOFF ) ;
00766    isort_intint( n , a , ia ) ;
00767    return ;
00768 }
00769 
00770 /*-----------------------------------------------------------------*/
00771 /*! 17 Dec 2003: In case a true NI_free() call gets thru somehow.  */
00772 /*-----------------------------------------------------------------*/
00773 
00774 #ifdef NI_free
00775 #undef NI_free
00776 #endif
00777 void NI_free( void *p )
00778 {
00779   hidden_NI_free( p , (char *)"Nada" , 0 ) ;
00780 }
00781 
00782 #endif  /* NIML_OLD_MALLOC or DONT_USE_MCW_MALLOC */