1 /* $NetBSD: realloc.c,v 1.1.1.1 2016/01/13 21:42:18 christos Exp $ */ 2 3 /* Change the size of a block allocated by `malloc'. 4 Copyright 1990, 1991, 1992, 1993, 1994 Free Software Foundation, Inc. 5 Written May 1989 by Mike Haertel. 6 7 This library is free software; you can redistribute it and/or 8 modify it under the terms of the GNU Library General Public License as 9 published by the Free Software Foundation; either version 2 of the 10 License, or (at your option) any later version. 11 12 This library is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 Library General Public License for more details. 16 17 You should have received a copy of the GNU Library General Public 18 License along with this library; see the file COPYING.LIB. If 19 not, write to the Free Software Foundation, Inc., 675 Mass Ave, 20 Cambridge, MA 02139, USA. 21 22 The author may be reached (Email) at the address mike@ai.mit.edu, 23 or (US mail) as Mike Haertel c/o Free Software Foundation. */ 24 25 #ifndef _MALLOC_INTERNAL 26 #define _MALLOC_INTERNAL 27 #include <malloc.h> 28 #endif 29 30 #if (defined (MEMMOVE_MISSING) || \ 31 !defined(_LIBC) && !defined(STDC_HEADERS) && !defined(USG)) 32 33 /* Snarfed directly from Emacs src/dispnew.c: 34 XXX Should use system bcopy if it handles overlap. */ 35 #ifndef emacs 36 37 /* Like bcopy except never gets confused by overlap. */ 38 39 static void 40 safe_bcopy (from, to, size) 41 char *from, *to; 42 int size; 43 { 44 if (size <= 0 || from == to) 45 return; 46 47 /* If the source and destination don't overlap, then bcopy can 48 handle it. If they do overlap, but the destination is lower in 49 memory than the source, we'll assume bcopy can handle that. */ 50 if (to < from || from + size <= to) 51 bcopy (from, to, size); 52 53 /* Otherwise, we'll copy from the end. */ 54 else 55 { 56 register char *endf = from + size; 57 register char *endt = to + size; 58 59 /* If TO - FROM is large, then we should break the copy into 60 nonoverlapping chunks of TO - FROM bytes each. However, if 61 TO - FROM is small, then the bcopy function call overhead 62 makes this not worth it. The crossover point could be about 63 anywhere. Since I don't think the obvious copy loop is too 64 bad, I'm trying to err in its favor. */ 65 if (to - from < 64) 66 { 67 do 68 *--endt = *--endf; 69 while (endf != from); 70 } 71 else 72 { 73 for (;;) 74 { 75 endt -= (to - from); 76 endf -= (to - from); 77 78 if (endt < to) 79 break; 80 81 bcopy (endf, endt, to - from); 82 } 83 84 /* If SIZE wasn't a multiple of TO - FROM, there will be a 85 little left over. The amount left over is 86 (endt + (to - from)) - to, which is endt - from. */ 87 bcopy (from, to, endt - from); 88 } 89 } 90 } 91 #endif /* Not emacs. */ 92 93 #define memmove(to, from, size) safe_bcopy ((from), (to), (size)) 94 95 #endif 96 97 98 #define min(A, B) ((A) < (B) ? (A) : (B)) 99 100 /* Debugging hook for realloc. */ 101 __ptr_t (*__realloc_hook) __P ((__ptr_t __ptr, __malloc_size_t __size)); 102 103 /* Resize the given region to the new size, returning a pointer 104 to the (possibly moved) region. This is optimized for speed; 105 some benchmarks seem to indicate that greater compactness is 106 achieved by unconditionally allocating and copying to a 107 new region. This module has incestuous knowledge of the 108 internals of both free and malloc. */ 109 __ptr_t 110 realloc (ptr, size) 111 __ptr_t ptr; 112 __malloc_size_t size; 113 { 114 __ptr_t result; 115 int type; 116 __malloc_size_t block, blocks, oldlimit; 117 118 if (size == 0) 119 { 120 free (ptr); 121 return malloc (0); 122 } 123 else if (ptr == NULL) 124 return malloc (size); 125 126 if (__realloc_hook != NULL) 127 return (*__realloc_hook) (ptr, size); 128 129 block = BLOCK (ptr); 130 131 type = _heapinfo[block].busy.type; 132 switch (type) 133 { 134 case 0: 135 /* Maybe reallocate a large block to a small fragment. */ 136 if (size <= BLOCKSIZE / 2) 137 { 138 result = malloc (size); 139 if (result != NULL) 140 { 141 memcpy (result, ptr, size); 142 _free_internal (ptr); 143 return result; 144 } 145 } 146 147 /* The new size is a large allocation as well; 148 see if we can hold it in place. */ 149 blocks = BLOCKIFY (size); 150 if (blocks < _heapinfo[block].busy.info.size) 151 { 152 /* The new size is smaller; return 153 excess memory to the free list. */ 154 _heapinfo[block + blocks].busy.type = 0; 155 _heapinfo[block + blocks].busy.info.size 156 = _heapinfo[block].busy.info.size - blocks; 157 _heapinfo[block].busy.info.size = blocks; 158 /* We have just created a new chunk by splitting a chunk in two. 159 Now we will free this chunk; increment the statistics counter 160 so it doesn't become wrong when _free_internal decrements it. */ 161 ++_chunks_used; 162 _free_internal (ADDRESS (block + blocks)); 163 result = ptr; 164 } 165 else if (blocks == _heapinfo[block].busy.info.size) 166 /* No size change necessary. */ 167 result = ptr; 168 else 169 { 170 /* Won't fit, so allocate a new region that will. 171 Free the old region first in case there is sufficient 172 adjacent free space to grow without moving. */ 173 blocks = _heapinfo[block].busy.info.size; 174 /* Prevent free from actually returning memory to the system. */ 175 oldlimit = _heaplimit; 176 _heaplimit = 0; 177 _free_internal (ptr); 178 _heaplimit = oldlimit; 179 result = malloc (size); 180 if (result == NULL) 181 { 182 /* Now we're really in trouble. We have to unfree 183 the thing we just freed. Unfortunately it might 184 have been coalesced with its neighbors. */ 185 if (_heapindex == block) 186 (void) malloc (blocks * BLOCKSIZE); 187 else 188 { 189 __ptr_t previous = malloc ((block - _heapindex) * BLOCKSIZE); 190 (void) malloc (blocks * BLOCKSIZE); 191 _free_internal (previous); 192 } 193 return NULL; 194 } 195 if (ptr != result) 196 memmove (result, ptr, blocks * BLOCKSIZE); 197 } 198 break; 199 200 default: 201 /* Old size is a fragment; type is logarithm 202 to base two of the fragment size. */ 203 if (size > (__malloc_size_t) (1 << (type - 1)) && 204 size <= (__malloc_size_t) (1 << type)) 205 /* The new size is the same kind of fragment. */ 206 result = ptr; 207 else 208 { 209 /* The new size is different; allocate a new space, 210 and copy the lesser of the new size and the old. */ 211 result = malloc (size); 212 if (result == NULL) 213 return NULL; 214 memcpy (result, ptr, min (size, (__malloc_size_t) 1 << type)); 215 free (ptr); 216 } 217 break; 218 } 219 220 return result; 221 } 222