home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / the25.zip / thesrc251.zip / memory.c < prev    next >
C/C++ Source or Header  |  1998-07-08  |  27KB  |  713 lines
  1. /***********************************************************************/
  2. /* MEMORY.C - Memory management functions.                             */
  3. /***********************************************************************/
  4. /*
  5.  * THE - The Hessling Editor. A text editor similar to VM/CMS xedit.
  6.  * Copyright (C) 1991-1997 Mark Hessling
  7.  *
  8.  * This program is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU General Public License as
  10.  * published by the Free Software Foundation; either version 2 of
  11.  * the License, or any later version.
  12.  *
  13.  * This program is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16.  * General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU General Public License
  19.  * along with this program; if not, write to:
  20.  *
  21.  *    The Free Software Foundation, Inc.
  22.  *    675 Mass Ave,
  23.  *    Cambridge, MA 02139 USA.
  24.  *
  25.  *
  26.  * If you make modifications to this software that you feel increases
  27.  * it usefulness for the rest of the community, please email the
  28.  * changes, enhancements, bug fixes as well as any and all ideas to me.
  29.  * This software is going to be maintained and enhanced as deemed
  30.  * necessary by the community.
  31.  *
  32.  * Mark Hessling                 Email:             M.Hessling@qut.edu.au
  33.  * PO Box 203                    Phone:                    +617 3802 0800
  34.  * Bellara                       http://www.gu.edu.au/gext/the/markh.html
  35.  * QLD 4507                      **** Maintainer PDCurses & REXX/SQL ****
  36.  * Australia                     ************* Author of THE ************
  37.  *
  38.  * The code in this module is borrowed from:
  39.  * The Regina Rexx Interpreter
  40.  * Copyright (C) 1992-1994  Anders Christensen <anders@pvv.unit.no>
  41.  */
  42.  
  43. /*
  44.  * The routines in this file try to minimize the the number of calls
  45.  * to malloc() and free(). Since it would generally not be possible to
  46.  * release memory, unless it actually is last in the virtual memory
  47.  * that the process holds, just don't release it, and let the
  48.  * interpreter grow. Memory are allocated in only certain sizes, and
  49.  * are "freed" to a freelist, which is within the interpreter.
  50.  *
  51.  * The important routines are get_a_chunk() and give_a_chunk(), which 
  52.  * might be called a large number of times. All the other routines are
  53.  * either called once to initiate, or it is used in tracing and 
  54.  * debugging, where speed and space is not important anyway. 
  55.  *
  56.  * The algorithm works something like this: memory can only be allocated
  57.  * in predetermined sizes (8, 12, 16, 24, 32, ...) and allocation of a 
  58.  * size other than that will have to allocate something slightly bigger.
  59.  * For each size, there is a linked list of free pieces of memory of 
  60.  * that size, the first entry of each of these lists can be accessed 
  61.  * through 'flists', which is an array of pointers to these lists. 
  62.  *
  63.  * Every time someone needs a piece of memory, the first piece of the 
  64.  * freelist containing memory of suitable size (as big or slightly 
  65.  * bigger) is returned. If the list is empty, a large piece of 
  66.  * memory is allocated by malloc(), chopped up and put on the freelist
  67.  * that was empty. 
  68.  *
  69.  * When memory is released, the prime problem is to decide which 
  70.  * freelist to put it on. To manage that, each time memory is 
  71.  * allocated by malloc(), the upper and lower address of the memory 
  72.  * is put in hashtable; given a particular address, the hashtable
  73.  * can be sought using the address as hashvalue, and the result will 
  74.  * be the size of the memory chunks at that address.
  75.  *
  76.  * When dealloacting strings, we know the max-size of the string, and 
  77.  * then we can calculate which freelist the string should be put on,
  78.  * without having to search the hashtable structure. Note that there
  79.  * is no need to deallocate strings using the give_a_string() function,
  80.  * the normal give_a_chunk() will work just as well, but is somewhat
  81.  * slower. 
  82.  *
  83.  * If you don't #define FLISTS, then malloc() and free() should be
  84.  * used instead. That might be very slow on some machines, since rexx
  85.  * tend to use lots of small size memory. If you #define TRACEMEM,
  86.  * memory is traced, which also tend to be slow, since there is a lot
  87.  * of overhead in allocation and deallocation. Also note that in the
  88.  * current implementation you can use malloc()/free() in parallel with
  89.  * the routines defined here.
  90.  *
  91.  * Note that using this metod, the last piece of memory freed will be
  92.  * the first to be used when more memory is needed. 
  93.  *
  94.  * The number of calls to malloc() seems to be negligable when using 
  95.  * this metod (typical less than 100 for medium sized programs). But
  96.  * this is of course dependent on how the program uses memory. 
  97.  *
  98.  * The tracing part of this file, (#ifdef TRACEMEM) is an optional
  99.  * extention for debugging purposes. Whenever memory is allocated,
  100.  * mymalloc() allocates 16 bytes more than needed. These bytes are
  101.  * used like this:
  102.  *
  103.  *   0       4       8      12       16 bytes
  104.  *   | count |f|m|seq| prev  | next  | start of allocated memory
  105.  *
  106.  * The 'count' is the number of bytes allocated, 'f' (flag) is used in 
  107.  * garbage collection, and 'prev' and 'next' are pointers used in a 
  108.  * double linked list. seqv is a sequence number which is iterated 
  109.  * for each memoryallocation.
  110.  * 
  111.  * count is int, prev and next are char*, f is char and seqv is a 
  112.  * 16 bit integer. The 'm' is a magic number. Actually it is just 
  113.  * there to fill the space, and can be used for more useful purposed
  114.  * if needed.
  115.  *
  116.  * An additional option to TRACEMEM is filling allocated and deallocated
  117.  * memory with bitpatterns. If the PATTERN_MEMORY cpp-variable is set,
  118.  * all allocated memory is initated to NOT_USED, and deallocated memory 
  119.  * is set BEEN_USED before deallocation.
  120.  * 
  121.  * Garbage-collection is not implemented, but listleaked will list out
  122.  * every chunk of allocated memory that are not currently in use. The
  123.  * array markptrs contains a list of functions for marking memory.
  124.  * There is a potensial problem with garbage collection, since the 
  125.  * interpreter might 'loose' some memory everytime it hits a syntax
  126.  * error, like "say random(.5)". To fix that, memory should either 
  127.  * be traced and then garbage collected, or it should have a sort 
  128.  * of transaction oriented memory management (yuk!).
  129.  *
  130.  * NOTE that #define'ing TRACEMEM requires that your machine follows
  131.  *      this:  sizeof(int) = sizeof(char*) = 32 bits. It might work
  132.  *      for other machines to (having larger word size), but I don't
  133.  *      guarantee it. 
  134.  *
  135.  */
  136.  
  137. #define FLISTS
  138. #define PATTERN_MEMORY
  139.  
  140. #include <the.h>
  141. #include <proto.h>
  142.  
  143. #include <stdlib.h>
  144. #include <stdio.h>
  145. #include <assert.h>
  146. #include <string.h>
  147.  
  148. #ifdef FLISTS
  149.  
  150. /* 
  151.  * CHUNK_SIZE it the size in which memory is allocated using malloc(), 
  152.  * and that memory is then divided into pieces of the wanted size. 
  153.  * If you increase it, things will work slightly faster, but more 
  154.  * memory is wasted, and vice versa. The 'right' size is dependent on
  155.  * your machine, rexx scripts and your personal taste.
  156.  */
  157. #define CHUNK_SIZE (8192)
  158.  
  159. /*
  160.  * MAX_INTERNAL_SIZE is the max size of individual pieces of memory 
  161.  * that this system will handle itself. If bigger pieces are requested
  162.  * it will just forward the request to malloc()/free(). Note that 
  163.  * this value should be less than or equal to CHUNK_SIZE.
  164.  */
  165. #define MAX_INTERNAL_SIZE (2048)
  166.  
  167. /* 
  168.  * MEMINFO_HASHSIZE is the size of the 'hashtable' used to find the size
  169.  * of a chunk of memory, given an address of a byte within that chunk. 
  170.  * Actually, this isn't much of a real hashtable, but still. Allocating
  171.  * large value will not make much harm other than wasting memory. Using 
  172.  * too small value can seriously degrade execution. The optimal size
  173.  * is such that MEMINFO_HASHSIZE * CHUNK_SIZE is only slight bigger 
  174.  * than the actual use of memory in your rexx script (including the 
  175.  * memory that will be wasted)
  176.  */
  177. #define MEMINFO_HASHSIZE (499)
  178.  
  179. /* 
  180.  * GET_SIZE() is a 'function' that returns a index into the 'hash' 
  181.  * variable, given a specific number. The index returned will be the
  182.  * index of the ptr to the list of free memory entries that is identical
  183.  * or slightly bigger than the parameter in size.
  184.  */
  185. #define GET_SIZE(a) (hash[((a)+3)>>2])
  186.  
  187. /*
  188.  * This is the hashfunction for use with 'hashtable'. It will effectively
  189.  * just shift away some of the lower bits and fold the result around
  190.  * the 'hashtable'. Note that '13' is corresponent to CHUNK_SIZE, since
  191.  * 8192 == 1<<13, which is the optimal size. If you change one of them
  192.  * be sure to change the other. 
  193.  * 
  194.  * Maybe we could eliminate a division by letting MEMINFO_HASHSIZE have
  195.  * a number equal to a binary 'round' number (e.g. 512). There is no
  196.  * need to keep the size a prime number, since the elements in the 
  197.  * table *will* be well distributed.
  198.  */
  199. #define mem_hash_func(a) (((a)>>13)%MEMINFO_HASHSIZE)
  200.  
  201. /* 
  202.  * Here are the list of the 'approved' sizes. Memory is only allocatable
  203.  * in these sizes. If you need anything else, use the lowest number that
  204.  * is higher than what you need.
  205.  *
  206.  * Why exactly these numbers? Why not? Note that these are a subset 
  207.  * of the series {8,16,32,64,128...} and {12,24,48,96} mingled together. 
  208.  * Note that you can not allocate memory in smaller sizes than is 
  209.  * possible to fit a pointer (to char and/or void) into. Also take 
  210.  * into consideration that all these sizes should be aligned according
  211.  * to the size of ints and pointers, so don't make them too small.
  212.  */
  213. static int sizes[] = {    8,   12,   16,   24,   32,   48,   64,   96, 
  214.                         128,  192 , 256,  384,  512,  768, 1024, 1536, 
  215.                        2048, 3072, 4096 } ;
  216.  
  217. /* 
  218.  * The array of pointers to the freelists having memory of the sizes 
  219.  * specified in 'sizes'. I.e. theflists[0] is a pointer to a linked list
  220.  * of free memory chunks of size 8, flist[1] to memory of size 12 etc.
  221.  * The size of this array is the same as the size of 'sizes'.
  222.  */
  223. static char *theflists[sizeof(sizes)/sizeof(int)] = { NULL } ;
  224.  
  225. /*
  226.  * The type meminfo holds the info about the connection between the 
  227.  * address of allocated memory and the size of that memory. When new
  228.  * memory is allocated by malloc(), in size CHUNK_SIZE, a new box of
  229.  * meminfo is created, which holds the address returned from malloc()
  230.  * and the size in which the chunk was divided {8,12,16,24,32...}.
  231.  */
  232. typedef struct meminfo_type 
  233. {
  234.    char *start ;                /* start of memory's address */
  235.    char *last ;                 /* end of memory's address */
  236.    struct meminfo_type *next ;  /* next ptr in linked list */
  237.    int size ;                   /* size of chunks at that address */
  238. } meminfo ;
  239.  
  240. /* 
  241.  * The 'hashtable'. Used for quick access to the size of a chunk of
  242.  * memory, given its address.
  243.  */
  244. static meminfo *hashtable[ MEMINFO_HASHSIZE ] = { NULL } ;
  245.  
  246. /* 
  247.  * Array used for rounding a number to an 'approved' size, i.e. a size
  248.  * in which the interpreter will allocate memory. Remember that the 
  249.  * approved sizes are {8,12,16,24,32 ...}? This function will return 
  250.  * 8 for 1 through 8; 12 for 9 through 12; 16 for 13 through 16 etc.
  251.  * It is not initially set, but will be set by init_hash_table().
  252.  *
  253.  * Note: the 'step' in this table (4 as it is defined below) must not
  254.  * be bigger then the smallest gap in between two 'approved' sizes of
  255.  * memory. E.g the smallest gap as defined above is 12-8 = 4.
  256.  *
  257.  * Actually, the name is somewhat misleading, since this is not really
  258.  * a hashtable, it is just a leftover from the time when it actually
  259.  * was a hashtable. 
  260.  *
  261.  * Due to how the hash array is initialized, we have to allocate one 
  262.  * more item than is going to be used. This is really a klugde, and we 
  263.  * really ought to fix it a more clean way.
  264.  */
  265. static short hash[ CHUNK_SIZE/4 + 1 ] ;
  266. #endif
  267.  
  268. static meminfo *first_chunk=NULL;
  269. static meminfo *curr_chunk=NULL;
  270.  
  271. /*
  272.  * This function stores in a singly linked list all chunks of memory
  273.  * that are allocated with malloc(). This is so that they can all be
  274.  * free()ed by the_free_flists().
  275.  */
  276. /******************************************************************************/
  277. #ifdef HAVE_PROTO
  278. int register_mem( void *chunk )
  279. #else
  280. int register_mem( chunk )
  281. void *chunk;
  282. #endif
  283. /******************************************************************************/
  284. {
  285.    meminfo *mem=NULL;
  286.  
  287.    if ((mem = malloc( sizeof( meminfo ))) == NULL )
  288.       return(1);
  289.    mem->start = chunk;
  290.    mem->next = NULL;
  291.    if (curr_chunk)
  292.    {
  293.       curr_chunk->next = mem;
  294.    }
  295.    curr_chunk = mem;
  296.    if (first_chunk == NULL)
  297.       first_chunk = curr_chunk;
  298.    return(0);
  299. }
  300.  
  301. /*
  302.  * This function initiates the variable 'hash'. This might have been 
  303.  * done initially, since the values in this will never change. But 
  304.  * since the size is rather big. it is more efficient to spend some 
  305.  * CPU on initiating it. The startup time might be decreased by swapping
  306.  * this routine for a pre-defined variable. Perhaps it should be 
  307.  * rewritten to use two arrays, one for large pieces of memory and 
  308.  * one for small pieces. That would save space in 'hash'
  309.  *
  310.  * The values put into the array has been described above. 
  311.  */
  312. /******************************************************************************/
  313. #ifdef HAVE_PROTO
  314. void init_memory_table( void )
  315. #else
  316. void init_memory_table()
  317. #endif
  318. /******************************************************************************/
  319. {
  320.    int indeks ;   /* index into current element to be initiated */
  321.    int j ;
  322.    int size ;
  323.    int num ;
  324.  
  325.    /* 
  326.     * Set the few lowest values manually, since the algoritm breaks
  327.     * down for sufficient small values. 
  328.     */
  329.    indeks = 0 ;
  330.    hash[indeks++] = 0 ;  /* when size equals 0, well ... 8 :-) */
  331.    hash[indeks++] = 0 ;  /* for 1 <= size < 4 */
  332.    hash[indeks++] = 0 ;  /* for 4 <= size < 8 */
  333.  
  334.    /* 
  335.     * The main loop. How does this algorithm work, well, look at the 
  336.     * following table, in which all numbers should be multiplied with
  337.     * 4 to get the correct numbers. 
  338.     *
  339.     *  bin        sizes
  340.     *   0   (8) :  2
  341.     *   1  (12) :  3
  342.     *   2  (16) :  4  5
  343.     *   3  (24) :  6  7
  344.     *   4  (32) :  8  9 10 11
  345.     *   5  (48) : 12 13 14 15 
  346.     *   6  (64) : 16 17 18 19 20 21 22 23 
  347.     *   7  (96) : 24 25 26 27 28 29 30 31
  348.     *   8 (128) : 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
  349.     *   9 (192) : 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
  350.     * etc
  351.     *
  352.     * The number to the left of the colon is the index into the
  353.     * 'sizes' array, and the number in parenthesis is the size which
  354.     * 'sizes' would return for that index. The numbers to the right of
  355.     * the colon are all the elements in 'hash' that contains that
  356.     * particular index into 'sizes'.  Notice that pairs of lines have
  357.     * equal number of numbers, and that the number of numbers doubles
  358.     * for every second line.
  359.     *
  360.     * Therefore, let size be the number of elements to initialize in
  361.     * each iteration, and double it at the end of the loop. 'size'
  362.     * will then loop through 8, 16, 32, 64, 128 ... For each iteration
  363.     * of that loop, initialize 'size'/2 numbers to 'num' and then the
  364.     * next 'size'/2 numbers to 'num'+1. Increment 'num' by two for
  365.     * each iteration. The 'indeks' is the current number in hash to
  366.     * initialize.
  367.     */
  368.    size = 1 ;
  369.    num = 1 ;
  370.    for (; indeks<(CHUNK_SIZE/4); )
  371.    {
  372.       /* 
  373.        * Initalize first in each pair of bins of same length.
  374.        * I.e  8, 16, 32,  64 ... etc
  375.        */
  376.       for (j=0; j<size; j++ )
  377.          hash[indeks++] = num ;
  378.       num++ ;
  379.  
  380.       /* 
  381.        * Initialize the second in each pair: 12, 24, 48, 96 ... etc
  382.        */
  383.       for (j=0; j<size; j++ )
  384.          hash[indeks++] = num ;
  385.       num++ ;
  386.       size = size << 1 ;
  387.    }
  388.  
  389. }
  390.  
  391.  
  392.  
  393. /*
  394.  * Adds information about a chunk of memory to the hashtable memory 
  395.  * addresses and the chunksize at that address. Note that two addresses
  396.  * are sent as parameters, the start of the memory to be registerd, and
  397.  * the address under which the information is to be registered. Why? 
  398.  * Look at the following figure:
  399.  *
  400.  * 0               8K               16K                24K
  401.  * +---------------+-----------------+------------------+-------------+
  402.  * |    AAAAAAAAAAAAAAAAAA   BBBBBBBBBBBBBBBBBB
  403.  * +----+----------------+---+----------------+-------------------------+
  404.  *      3K              11K 13K              21K
  405.  * 
  406.  * Two chunks are allocated: A and B. The chunks are allocated in 8K
  407.  * blocks, but they will in general not follow the 8K boundaries of
  408.  * the machine. The 'hashtable' array have entries that _do_ follow
  409.  * the 8K boundaries of the machine. Therefore, chunk A must be
  410.  * registered under the in the 'hashtable' entries for both the 0-8K
  411.  * segment, and the 8-16K segment. And vice versa, the 8-16K segment
  412.  * may contain parts of chunk A and B.
  413.  *
  414.  * This could be avoided, if the chunks were aligned with the boundaries 
  415.  * of the computer. If you change any of the constants in this part of
  416.  * the program, be sure to tune them to match eachother!
  417.  * 
  418.  * Of course, this routines need memory to be able to register other 
  419.  * memory, so to avoid a deadlock, it calls malloc directly. It will 
  420.  * never release memory, since we can really not be sure that all 
  421.  * memory has been released.
  422.  */
  423. /******************************************************************************/
  424. #ifdef HAVE_PROTO
  425. static int add_entry( char *start, char *addr, int bin_no )
  426. #else
  427. static int add_entry( start, addr, bin_no )
  428. char *start;
  429. char *addr;
  430. int bin_no;
  431. #endif
  432. /******************************************************************************/
  433. {
  434.    meminfo *ptr ;              /* work ptr */
  435.    int tmp ;                   /* tmp storage for mem_hash_func() */
  436.    static meminfo *mem=NULL ;  /* ptr to array, empty at first */
  437.    static int indeks=128 ;      /* force it to allocate at first invocation */
  438.  
  439.    /*
  440.     * If we have used all free meminfo-boxes, allocate more. This is 
  441.     * forces upon us at the first invocation. Allocate space for 128
  442.     * at a time.
  443.     */
  444.    if (indeks>=128)
  445.    {
  446.       /* Stupid SunOS acc gives incorrect warning for the next line */
  447.       if  (!(mem = malloc( sizeof( meminfo) * 128 )))
  448.           return(1);
  449.       if (register_mem( (void *)mem ))
  450.          return(1);
  451.       indeks = 0 ;
  452.    }
  453.  
  454.    /* 
  455.     * Fill in the fields of the box, and put it in the front of the 
  456.     * requested bin in hashtable
  457.     */
  458.    ptr = &mem[ indeks++ ] ;   
  459.    ptr->next = hashtable[tmp=mem_hash_func((unsigned int)addr)] ;
  460.    ptr->size = bin_no ;
  461.    ptr->start = start ;
  462.    hashtable[tmp] = ptr ;
  463.    return(0);
  464. }
  465.  
  466. /* 
  467.  * Allocate a piece of memory. The size is given as the 'size' parameter.
  468.  * If size is more than MAX_INTERNAL_SIZE, it will call malloc()
  469.  * directly, else, it will return a piece of memory from the freelist,
  470.  * after possibly filling the freelist with more memory if is was
  471.  * empty in the first place.
  472.  */
  473. /******************************************************************************/
  474. #ifdef HAVE_PROTO
  475. void *get_a_block( int size )
  476. #else
  477. void *get_a_block( size )
  478. int size;
  479. #endif
  480. /******************************************************************************/
  481. {
  482.    register int bin ;     /* bin no in array of freelists */
  483.    register char *vptr ;  /* holds the result */
  484.    register void *result ; 
  485.  
  486.    /*
  487.     * If memory is too big, let malloc() handle the problem. 
  488.     */
  489.    if (size>MAX_INTERNAL_SIZE) 
  490.    {
  491.       if ((result=malloc( size )))
  492.          return result ;
  493.       else
  494.           return NULL;
  495.    }
  496.  
  497.    /*
  498.     * Get the first item from the appropriate freelist, and let 'vptr'
  499.     * point to it. Simultaneously set bin to the bin no in 'theflists'
  500.     * to avoid recalculating the number. If the freelist is empty 
  501.     * (i.e vptr==NULL) then allocate more memory.
  502.     */
  503.    if ((vptr=theflists[bin=GET_SIZE(size)])==NULL)
  504.    {
  505.       char *ptr ;      /* work ptr, to loop through the memory */
  506.       char *topaddr ;  /* points to last item in memory */
  507.  
  508.       /* 
  509.        * Allocate the memory, and set both vptr and initiate the 
  510.        * right element in 'theflists'. Note that the value in 'flists' is
  511.        * 'incremented' later, so it must be set to the value which now
  512.        * is to be allocated. 
  513.        */
  514.       vptr = malloc( CHUNK_SIZE + sizes[bin]) ;
  515.       if (!vptr)
  516.           return(NULL);
  517.       theflists[bin] = vptr ;
  518.  
  519.       /* 
  520.        * Calculate the top address of the memory allocated, and put 
  521.        * the memory into 'topaddr'. Then register the chunk of memory 
  522.        * in both the possible CHUNK_SIZE segments of the machine. In 
  523.        * some rare cases the last registration might not be needed,
  524.        * but do it anyway, to avoid having to determine it.
  525.        */
  526.       topaddr = vptr + CHUNK_SIZE - sizes[bin] ;
  527.       if (register_mem( vptr ))
  528.          return(NULL);
  529.       if (add_entry( vptr, vptr, bin ))
  530.          return(NULL);
  531.       if (add_entry( vptr, vptr + CHUNK_SIZE, bin ))
  532.          return(NULL);
  533.  
  534.       /*
  535.        * Then loop through the individual pieced of memory within the 
  536.        * newly allocated chunk, and make it a linked list, where the 
  537.        * last ptr in the list is NULL.
  538.        */
  539.       for (ptr=vptr; ptr<topaddr; ptr=ptr+sizes[bin] )
  540.          *(char**)ptr = ptr + sizes[bin] ;
  541.   
  542.       *((char**)(ptr-sizes[bin])) = NULL ;
  543.    }
  544.  
  545.    /*
  546.     * Update the pointer in 'flist' to point to the next entry in the
  547.     * freelist instead of the one we just allocated, and return to 
  548.     * caller.
  549.     */
  550.    theflists[bin] = (*((char**)(vptr))) ;
  551.    return (vptr) ;
  552. }
  553.  
  554.  
  555. /*
  556.  * The standard interface to freeing memory. The parameter 'ptr' is 
  557.  * a pointer to the memory to be freed, is put first in the freelist
  558.  * pointed to by the appropriate element in 'theflists'.
  559.  * 
  560.  * I am not really sure what cptr do in this, but I think it has 
  561.  * something to do with *void != *char on Crays ... The main consumer
  562.  * of CPU in this routine is the for(;;) loop, it should be rewritten.
  563.  */
  564. /******************************************************************************/
  565. #ifdef HAVE_PROTO
  566. void give_a_block( void *ptr )
  567. #else
  568. void give_a_block( ptr )
  569. void *ptr;
  570. #endif
  571. /******************************************************************************/
  572. {
  573.    char *cptr ;      /* pseudonym for 'ptr' */
  574.    meminfo *mptr ;   /* caches the right element in hashtable */
  575.  
  576.    /*
  577.     * initialize a few values, 'cptr' is easy, while 'mptr' is the
  578.     * list of values for this piece of memory, that is in the 
  579.     * hashtable that returns memory size given a specific address
  580.     */
  581.    cptr = (char*)ptr ;
  582.    mptr = hashtable[ mem_hash_func( ((unsigned int)cptr) ) ] ;
  583.  
  584.    /* 
  585.     * For each element in the list attached to the specific hashvalue, 
  586.     * loop through the list, and stop at the entry which has a start 
  587.     * address _less_ than 'cptr' and a stop address _higher_ than 
  588.     * 'cptr' (i.e. cptr is within the chunk.)
  589.     */
  590.    for ( ; (mptr) && 
  591.         ((mptr->start+CHUNK_SIZE<=cptr) || (mptr->start>cptr)) ;
  592.         mptr = mptr->next) ;
  593.  
  594.    /*
  595.     * Now, there are two possibilities, either is mptr==NULL, in which
  596.     * case this piece of memory is never registered in the system, or 
  597.     * then we have more information. In the former case, just give 
  598.     * the address to free(), hoping it knows more. In the latter, put
  599.     * the memory on the appropriate freelist. 
  600.     */
  601.    if (mptr)
  602.    {
  603.       /* 
  604.        * Link it into the first place of the freelist.
  605.        */
  606.       *((char**)cptr) = theflists[mptr->size] ;
  607.       theflists[mptr->size] = cptr ;
  608.    }
  609.    else
  610.       free( ptr ) ; 
  611. }
  612.  
  613. /*
  614.  * The interface to resizing memory. The parameter 'ptr' is
  615.  * a pointer to the memory to be resized. First, if the requested size 
  616.  * is within the size of the existing block, just return it. Otherwise
  617.  * the block is put back on the free lists and a new block allocated.
  618.  */
  619. /******************************************************************************/
  620. #ifdef HAVE_PROTO
  621. void *resize_a_block( void *ptr, int size )
  622. #else
  623. void *resize_a_block( ptr, size )
  624. void *ptr;
  625. int size;
  626. #endif
  627. /******************************************************************************/
  628. {
  629.    char *cptr ;      /* pseudonym for 'ptr' */
  630.    meminfo *mptr ;   /* caches the right element in hashtable */
  631.    register void *result ; 
  632.  
  633.    /*
  634.     * initialize a few values, 'cptr' is easy, while 'mptr' is the
  635.     * list of values for this piece of memory, that is in the 
  636.     * hashtable that returns memory size given a specific address
  637.     */
  638.    cptr = (char*)ptr ;
  639.    mptr = hashtable[ mem_hash_func( ((unsigned int)cptr) ) ] ;
  640.  
  641.    /* 
  642.     * For each element in the list attached to the specific hashvalue, 
  643.     * loop through the list, and stop at the entry which has a start 
  644.     * address _less_ than 'cptr' and a stop address _higher_ than 
  645.     * 'cptr' (i.e. cptr is within the chunk.)
  646.     */
  647.    for ( ; (mptr) && 
  648.         ((mptr->start+CHUNK_SIZE<=cptr) || (mptr->start>cptr)) ;
  649.         mptr = mptr->next) ;
  650.  
  651.    /*
  652.     * Now, there are two possibilities, either mptr==NULL, in which
  653.     * case this piece of memory was never registered in the system, or
  654.     * we have more information. In the former case, just give 
  655.     * the address to realloc(), and return. In the latter, if the
  656.     * requested size is still within the currently allocated size
  657.     * return it, or allocate a new chunk, copy the current contents
  658.     * to the new chunk and put the old piece of memory on the 
  659.     * appropriate freelist.
  660.     */
  661.    if (!mptr)
  662.       return ( realloc(ptr, size) ) ;
  663.  
  664.    /*
  665.     * If the size of the block being resized is within the current
  666.     * block size, simply return the same pointer.
  667.     */
  668.    if (size <= sizes[mptr->size])
  669.       return ptr;
  670.  
  671.    /*
  672.     * Get the new chunk of memory. This MUST be larger than the
  673.     * previous chunk to have reached here.
  674.     */
  675.    result = get_a_block( size ) ;
  676.    if (result == NULL)
  677.       return NULL;
  678.    /*
  679.     * Copy the current contents into the new chunk.
  680.     */
  681.    memcpy( result, cptr, sizes[mptr->size] ) ;
  682.  
  683.    /* 
  684.     * Put the old chunk into the first place of the freelist.
  685.     */
  686.    *((char**)cptr) = theflists[mptr->size] ;
  687.    theflists[mptr->size] = cptr ;
  688.  
  689.    return result;
  690. }
  691.  
  692. /******************************************************************************/
  693. #ifdef HAVE_PROTO
  694. void the_free_flists( void )
  695. #else
  696. void the_free_flists()
  697. #endif
  698. /******************************************************************************/
  699. {
  700.    meminfo *ptr = first_chunk;
  701.    meminfo *next = NULL;
  702.  
  703.    while( ptr )
  704.    {
  705.       next = ptr->next;
  706.       free( ptr->start );
  707.       free( ptr );
  708.       ptr = next;
  709.    }
  710.    return;
  711. }
  712.  
  713.