diff options
| author | Eric Andersen <andersen@codepoet.org> | 2001-01-11 11:42:17 +0000 | 
|---|---|---|
| committer | Eric Andersen <andersen@codepoet.org> | 2001-01-11 11:42:17 +0000 | 
| commit | ae97a89e1a1a9833080dccc81f6cd26784e1b964 (patch) | |
| tree | 6ff1ddc7e3980591c7fd0bbd5d9b8ac82da12886 /libc/stdlib | |
| parent | abdc3e4d06db2b9d93c509774fc7c4fde918ec8e (diff) | |
A large update from Manuel Novoa III <mnovoa3@bellsouth.net>.
Diffstat (limited to 'libc/stdlib')
| -rw-r--r-- | libc/stdlib/Makefile | 6 | ||||
| -rw-r--r-- | libc/stdlib/atexit.c | 82 | ||||
| -rw-r--r-- | libc/stdlib/malloc-930716/Makefile | 51 | ||||
| -rw-r--r-- | libc/stdlib/malloc-930716/README | 40 | ||||
| -rw-r--r-- | libc/stdlib/malloc-930716/calloc.c | 25 | ||||
| -rw-r--r-- | libc/stdlib/malloc-930716/free.c | 156 | ||||
| -rw-r--r-- | libc/stdlib/malloc-930716/malloc.c | 254 | ||||
| -rw-r--r-- | libc/stdlib/malloc-930716/malloc.h | 107 | ||||
| -rw-r--r-- | libc/stdlib/malloc-930716/memalign.c | 61 | ||||
| -rw-r--r-- | libc/stdlib/malloc-930716/morecore.c | 28 | ||||
| -rw-r--r-- | libc/stdlib/malloc-930716/realloc.c | 131 | ||||
| -rw-r--r-- | libc/stdlib/malloc-930716/valloc.c | 62 | ||||
| -rw-r--r-- | libc/stdlib/malloc-simple/Makefile | 4 | ||||
| -rw-r--r-- | libc/stdlib/malloc/Makefile | 4 | ||||
| -rw-r--r-- | libc/stdlib/qsort.c | 220 | ||||
| -rw-r--r-- | libc/stdlib/system.c | 2 | 
16 files changed, 1020 insertions, 213 deletions
diff --git a/libc/stdlib/Makefile b/libc/stdlib/Makefile index 5d7c9405a..52d00f876 100644 --- a/libc/stdlib/Makefile +++ b/libc/stdlib/Makefile @@ -33,7 +33,7 @@ MSRC1=strto_ll.c  MOBJ1=strtoll.o strtoull.o strto_ll.o  MSRC2=atexit.c -MOBJ2=on_exit.o atexit.o __do_exit.o exit.o +MOBJ2=atexit.o exit.o  CSRC =	abort.c getenv.c mktemp.c qsort.c realpath.c abs.c bsearch.c \ @@ -65,8 +65,8 @@ $(MOBJ2): $(MSRC2)  	$(CC) $(CFLAGS) -DL_$* $< -c -o $*.o  	$(STRIPTOOL) -x -R .note -R .comment $*.o -$(COBJS): -	$(CC) $(CFLAGS) $< -c $*.c -o $*.o +$(COBJS): %.o : %.c +	$(CC) $(CFLAGS) -c $< -o $@  	$(STRIPTOOL) -x -R .note -R .comment $*.o  $(OBJ): Makefile diff --git a/libc/stdlib/atexit.c b/libc/stdlib/atexit.c index 1c164ff86..20195fa96 100644 --- a/libc/stdlib/atexit.c +++ b/libc/stdlib/atexit.c @@ -4,11 +4,12 @@   */  /* - * This deals with both the atexit and on_exit function calls - *  - * Note calls installed with atexit are called with the same args as on_exit - * fuctions; the void* is given the NULL value. - *  + * Manuel Novoa III       Dec 2000 + * + * Modifications: + *   Made atexit handling conform to standards... i.e. no args. + *   Removed on_exit since it did not match gnu libc definition. + *   Combined atexit and __do_exit into one object file.   */  #include <errno.h> @@ -16,93 +17,58 @@  /* ATEXIT.H */  #define MAXONEXIT 20			/* AIUI Posix requires 10 */ -typedef void (*vfuncp) (); +typedef void (*vfuncp) (void);  extern vfuncp __cleanup;  extern void __do_exit();  extern void _exit __P((int __status)) __attribute__ ((__noreturn__)); -extern struct exit_table { -	vfuncp called; -	void *argument; -} __on_exit_table[MAXONEXIT]; - -extern int __on_exit_count; +extern vfuncp __atexit_table[MAXONEXIT]; +extern int __atexit_count;  /* End ATEXIT.H */  #ifdef L_atexit -vfuncp __cleanup; - -int atexit(ptr) -vfuncp ptr; +int atexit(vfuncp ptr)  { -	if (__on_exit_count < 0 || __on_exit_count >= MAXONEXIT) { +	if ((__atexit_count < 0) || (__atexit_count >= MAXONEXIT)) {  		errno = ENOMEM;  		return -1;  	} -	__cleanup = __do_exit;  	if (ptr) { -		__on_exit_table[__on_exit_count].called = ptr; -		__on_exit_table[__on_exit_count].argument = 0; -		__on_exit_count++; +		__cleanup = __do_exit; +		__atexit_table[__atexit_count++] = ptr;  	}  	return 0;  } -#endif +vfuncp __atexit_table[MAXONEXIT]; +int __atexit_count = 0; -#ifdef L_on_exit -int on_exit(ptr, arg) -vfuncp ptr; -void *arg; +void __do_exit(int rv)  { -	if (__on_exit_count < 0 || __on_exit_count >= MAXONEXIT) { -		errno = ENOMEM; -		return -1; -	} -	__cleanup = __do_exit; -	if (ptr) { -		__on_exit_table[__on_exit_count].called = ptr; -		__on_exit_table[__on_exit_count].argument = arg; -		__on_exit_count++; -	} -	return 0; -} +	int count = __atexit_count - 1; -#endif - -#ifdef L___do_exit - -int __on_exit_count = 0; -struct exit_table __on_exit_table[MAXONEXIT]; - -void __do_exit(rv) -int rv; -{ -	register int count = __on_exit_count - 1; -	register vfuncp ptr; - -	__on_exit_count = -1;		/* ensure no more will be added */ +	__atexit_count = -1;		/* ensure no more will be added */  	__cleanup = 0;				/* Calling exit won't re-do this */  	/* In reverse order */  	for (; count >= 0; count--) { -		ptr = __on_exit_table[count].called; -		(*ptr) (rv, __on_exit_table[count].argument); +		(*__atexit_table[count])();  	}  } -  #endif  #ifdef L_exit +void __stdio_close_all(void);	/* note: see _start.S - could be faked */ -void exit(rv) -int rv; +vfuncp __cleanup = 0; + +void exit(int rv)  {  	if (__cleanup)  		__cleanup(); +	__stdio_close_all();  	_exit(rv);  } -  #endif diff --git a/libc/stdlib/malloc-930716/Makefile b/libc/stdlib/malloc-930716/Makefile new file mode 100644 index 000000000..a4ae21798 --- /dev/null +++ b/libc/stdlib/malloc-930716/Makefile @@ -0,0 +1,51 @@ +# Makefile for uClibc +# +# Copyright (C) 2000 by Lineo, inc. +# +# This program is free software; you can redistribute it and/or modify it under +# the terms of the GNU Library General Public License as published by the Free +# Software Foundation; either version 2 of the License, or (at your option) any +# later version. +# +# This program is distributed in the hope that it will be useful, but WITHOUT +# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS +# FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more +# details. +# +# You should have received a copy of the GNU Library General Public License +# along with this program; if not, write to the Free Software Foundation, Inc., +# 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +# +# Derived in part from the Linux-8086 C library, the GNU C Library, and several +# other sundry sources.  Files within this library are copyright by their +# respective copyright holders. + +TOPDIR=../../ +include $(TOPDIR)Rules.mak +LIBC=$(TOPDIR)libc.a + +CSRC=calloc.c free.c malloc.c memalign.c morecore.c realloc.c valloc.c +COBJS=$(patsubst %.c,%.o, $(CSRC)) + +MSRC=../malloc/alloc.c +MOBJ=malloc_dbg.o free_dbg.o calloc_dbg.o +OBJS=$(COBJS) $(MOBJ) + +all: $(OBJS) $(LIBC) + +$(LIBC): ar-target + +ar-target: $(OBJS) +	$(AR) $(ARFLAGS) $(LIBC) $(OBJS) + +$(MOBJ): $(MSRC) +	$(CC) $(CFLAGS) -DL_$* $< -c -o $*.o +	$(STRIPTOOL) -x -R .note -R .comment $*.o + +$(COBJS): %.o : %.c +	$(CC) $(CFLAGS) -c $< -o $@ +	$(STRIPTOOL) -x -R .note -R .comment $*.o + +clean: +	rm -f *.[oa] *~ core + diff --git a/libc/stdlib/malloc-930716/README b/libc/stdlib/malloc-930716/README new file mode 100644 index 000000000..39c048312 --- /dev/null +++ b/libc/stdlib/malloc-930716/README @@ -0,0 +1,40 @@ +This is a fast malloc implementation that I wrote several years ago. +I later used it as the basis of GNU malloc.  My version differs from +the GNU version in that it does not support debugging hooks, and does +not record statistics.  Therefore it is slightly faster. + +In order to safely link programs using this malloc with a C library +that provides a different malloc, you need to make sure that +malloc(), free(), and realloc() are defined in a single object file. +Otherwise when linking you might get a combination of this malloc() +with the library's free().  The Makefile builds such an object file, +alloc.o. + +If you are using this malloc as the allocator for a C library of your +own, and are not linking with another C library, then you don't need +alloc.o.  If you are building a C library, you should also write a +replacement for the file "morecore.c" that doesn't pollute the name +space. + +The header file "malloc.h" in this directory is NOT intended to be a +public header file; it is for internal use by malloc and its +friends.  Don't install malloc.h in a public include directory! + +When porting this allocator to a new machine or operating system, you +should inspect the definition of BLOCKSIZE in malloc.h to make sure +it is greater than or equal to your target machine's virtual memory +page size; otherwise valloc() won't work properly.  (If you don't +care about valloc() then BLOCKSIZE doesn't matter.) + +You will also need to provide a machine-dependent _default_morecore() +function; see morecore.c for a sample version that works on Unix. +Your morecore function should return a pointer to a newly allocated +region of the given size, aligned on the most pessimistic alignment +boundary for the machine.  Subsequent calls to morecore should return +contiguous memory, and calls to morecore with a negative argument +should return memory to the system.  If no memory is available +morecore should return NULL. + +Bug reports to Mike Haertel, mike@cs.uoregon.edu. +This version is dated March 26, 1993; include this +date with your bug report. diff --git a/libc/stdlib/malloc-930716/calloc.c b/libc/stdlib/malloc-930716/calloc.c new file mode 100644 index 000000000..152fe09c6 --- /dev/null +++ b/libc/stdlib/malloc-930716/calloc.c @@ -0,0 +1,25 @@ +/* calloc.c - C standard library routine. +   Copyright (c) 1989, 1993  Michael J. Haertel +   You may redistribute this library under the terms of the +   GNU Library General Public License (version 2 or any later +   version) as published by the Free Software Foundation. +   THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED +   WARRANTY.  IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR +   WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS +   SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ + +#include <string.h> +#include "malloc.h" + +/* Allocate space for the given number of elements of the given +   size, initializing the whole region to binary zeroes. */ +void * +calloc(size_t nelem, size_t size) +{ +    void *result; + +    result = malloc(size * nelem); +    if (result) +	memset(result, 0, nelem * size); +    return result; +} diff --git a/libc/stdlib/malloc-930716/free.c b/libc/stdlib/malloc-930716/free.c new file mode 100644 index 000000000..fbc98b714 --- /dev/null +++ b/libc/stdlib/malloc-930716/free.c @@ -0,0 +1,156 @@ +/* free.c - C standard library routine. +   Copyright (c) 1989, 1993  Michael J. Haertel +   You may redistribute this library under the terms of the +   GNU Library General Public License (version 2 or any later +   version) as published by the Free Software Foundation. +   THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED +   WARRANTY.  IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR +   WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS +   SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ + +#include <limits.h> +#include <stddef.h> +#include <stdlib.h> +#include "malloc.h" + +/* Return memory to the heap. */ +void +_free_internal (void *ptr) +{ +    int block, blocks, i, type; +    struct list *prev, *next; + +    if (!ptr) +	return; + +    block = BLOCK(ptr); + +    switch (type = _heapinfo[block].busy.type) { +    case 0: +	/* Find the free cluster previous to this one in the free list. +	   Start searching at the last block referenced; this may benefit +	   programs with locality of allocation. */ +	i = _heapindex; +	if (i > block) +	    while (i > block) +		i = _heapinfo[i].free.prev; +	else { +	    do +		i = _heapinfo[i].free.next; +	    while (i > 0 && i < block); +	    i = _heapinfo[i].free.prev; +	} + +	/* Determine how to link this block into the free list. */ +	if (block == i + _heapinfo[i].free.size) { +	    /* Coalesce this block with its predecessor. */ +	    _heapinfo[i].free.size += _heapinfo[block].busy.info.size; +	    block = i; +	} else { +	    /* Really link this block back into the free list. */ +	    _heapinfo[block].free.size = _heapinfo[block].busy.info.size; +	    _heapinfo[block].free.next = _heapinfo[i].free.next; +	    _heapinfo[block].free.prev = i; +	    _heapinfo[i].free.next = block; +	    _heapinfo[_heapinfo[block].free.next].free.prev = block; +	} + +	/* Now that the block is linked in, see if we can coalesce it +	   with its successor (by deleting its successor from the list +	   and adding in its size). */ +	if (block + _heapinfo[block].free.size == _heapinfo[block].free.next) { +	    _heapinfo[block].free.size +		+= _heapinfo[_heapinfo[block].free.next].free.size; +	    _heapinfo[block].free.next +		= _heapinfo[_heapinfo[block].free.next].free.next; +	    _heapinfo[_heapinfo[block].free.next].free.prev = block; +	} + +	/* Now see if we can return stuff to the system. */ +	blocks = _heapinfo[block].free.size; +	if (blocks >= FINAL_FREE_BLOCKS && block + blocks == _heaplimit +	    && (*__morecore)(0) == ADDRESS(block + blocks)) { +	    _heaplimit -= blocks; +	    (*__morecore)(-blocks * BLOCKSIZE); +	    _heapinfo[_heapinfo[block].free.prev].free.next +		= _heapinfo[block].free.next; +	    _heapinfo[_heapinfo[block].free.next].free.prev +		= _heapinfo[block].free.prev; +	    block = _heapinfo[block].free.prev; +	} + +	/* Set the next search to begin at this block. */ +	_heapindex = block; +	break; + +    default: +	/* Get the address of the first free fragment in this block. */ +	prev = (struct list *) ((char *) ADDRESS(block) +				+ (_heapinfo[block].busy.info.frag.first +				   << type)); + +	if (_heapinfo[block].busy.info.frag.nfree == (BLOCKSIZE >> type) - 1 +	&& _fragblocks[type] > 1) { +	    /* If all fragments of this block are free, remove them +	       from the fragment list and free the whole block. */ +	    --_fragblocks[type]; +	    for (next = prev, i = 1; i < BLOCKSIZE >> type; ++i) +		next = next->next; +	    prev->prev->next = next; +	    if (next) +		next->prev = prev->prev; +	    _heapinfo[block].busy.type = 0; +	    _heapinfo[block].busy.info.size = 1; +	    free(ADDRESS(block)); +	} else if (_heapinfo[block].busy.info.frag.nfree) { +	    /* If some fragments of this block are free, link this fragment +	       into the fragment list after the first free fragment of +	       this block. */ +	    next = ptr; +	    next->next = prev->next; +	    next->prev = prev; +	    prev->next = next; +	    if (next->next) +		next->next->prev = next; +	    ++_heapinfo[block].busy.info.frag.nfree; +	} else { +	    /* No fragments of this block are free, so link this fragment +	       into the fragment list and announce that it is the first +	       free fragment of this block. */ +	    prev = (struct list *) ptr; +	    _heapinfo[block].busy.info.frag.nfree = 1; +	    _heapinfo[block].busy.info.frag.first +		= (unsigned int) ((char *) ptr - (char *) NULL) % BLOCKSIZE +		  >> type; +	    prev->next = _fraghead[type].next; +	    prev->prev = &_fraghead[type]; +	    prev->prev->next = prev; +	    if (prev->next) +		prev->next->prev = prev; +	} +	break; +    } +} + +struct alignlist *_aligned_blocks = NULL; + +void +free (void *ptr) +{ +  register struct alignlist *l; +   +  if (ptr == NULL) +    return; +	  +  for (l = _aligned_blocks; l != NULL; l = l->next) +  { +    if (l->aligned == ptr) +    { +      l->aligned = NULL;	/* Mark the slot in the list as free.  */ +      ptr = l->exact; +      break; +    } +  } + +  _free_internal (ptr); +} diff --git a/libc/stdlib/malloc-930716/malloc.c b/libc/stdlib/malloc-930716/malloc.c new file mode 100644 index 000000000..e8f7c7004 --- /dev/null +++ b/libc/stdlib/malloc-930716/malloc.c @@ -0,0 +1,254 @@ +/* malloc.c - C standard library routine. +   Copyright (c) 1989, 1993  Michael J. Haertel +   You may redistribute this library under the terms of the +   GNU Library General Public License (version 2 or any later +   version) as published by the Free Software Foundation. +   THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED +   WARRANTY.  IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR +   WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS +   SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ + +#include <limits.h> +#include <stddef.h> +#include <stdlib.h> +#include <string.h> +#include "malloc.h" + +/* How to really get more memory. */ +void *(*__morecore)(long) = __default_morecore_init; + +/* Pointer to the base of the first block. */ +char *_heapbase; + +/* Block information table. */ +union info *_heapinfo; + +/* Number of info entries. */ +static int heapsize; + +/* Search index in the info table. */ +int _heapindex; + +/* Limit of valid info table indices. */ +int _heaplimit; + +/* Count of large blocks allocated for each fragment size. */ +int _fragblocks[BLOCKLOG]; + +/* Free lists for each fragment size. */ +struct list _fraghead[BLOCKLOG]; + +/* Are we experienced? */ +static int initialized; + +/* Aligned allocation. */ +static void * +align(size_t size) +{ +    void *result; +    unsigned int adj; + +    result = (*__morecore)(size); +    adj = (unsigned int) ((char *) result - (char *) NULL) % BLOCKSIZE; +    if (adj != 0) { +	(*__morecore)(adj = BLOCKSIZE - adj); +	result = (char *) result + adj; +    } +    return result; +} + +/* Set everything up and remember that we have. */ +static int +initialize(void) +{ +    heapsize = HEAP / BLOCKSIZE; +    _heapinfo = align(heapsize * sizeof (union info)); +    if (!_heapinfo) +	return 0; +    memset(_heapinfo, 0, heapsize * sizeof (union info)); +    _heapinfo[0].free.size = 0; +    _heapinfo[0].free.next = _heapinfo[0].free.prev = 0; +    _heapindex = 0; +    _heapbase = (char *) _heapinfo; +    initialized = 1; +    return 1; +} + +/* Get neatly aligned memory, initializing or growing the +   heap info table as necessary. */ +static void * +morecore(size_t size) +{ +    void *result; +    union info *newinfo, *oldinfo; +    int newsize; + +    result = align(size); +    if (!result) +	return NULL; + +    /* Check if we need to grow the info table. */ +    if (BLOCK((char *) result + size) > heapsize) { +	newsize = heapsize; +	while (BLOCK((char *) result + size) > newsize) +	    newsize *= 2; +	newinfo = align(newsize * sizeof (union info)); +	if (!newinfo) { +	    (*__morecore)(-size); +	    return NULL; +	} +	memset(newinfo, 0, newsize * sizeof (union info)); +	memcpy(newinfo, _heapinfo, heapsize * sizeof (union info)); +	oldinfo = _heapinfo; +	newinfo[BLOCK(oldinfo)].busy.type = 0; +	newinfo[BLOCK(oldinfo)].busy.info.size +	    = BLOCKIFY(heapsize * sizeof (union info)); +	_heapinfo = newinfo; +#if 0 +	free(oldinfo); +#else +	_free_internal (oldinfo); +#endif +	heapsize = newsize; +    } + +    _heaplimit = BLOCK((char *) result + size); +    return result; +} + +/* Allocate memory from the heap. */ +void * +malloc (size_t size) +{ +    void *result; +    int log, block, blocks, i, lastblocks, start; +    struct list *next; + +    if (!initialized && !initialize()) +	return NULL; + +    /* Some programs will call malloc (0). We let them pass. */ +#if 0 +    if (size == 0) +	return NULL; +#endif + +    if (size < sizeof (struct list)) +	size = sizeof (struct list); + +    /* Determine the allocation policy based on the request size. */ +    if (size <= BLOCKSIZE / 2) { +	/* Small allocation to receive a fragment of a block. Determine +	   the logarithm to base two of the fragment size. */ +	--size; +	for (log = 1; (size >>= 1) != 0; ++log) +	    ; + +	/* Look in the fragment lists for a free fragment of the +	   desired size. */ +	if ((next = _fraghead[log].next) != 0) { +	    /* There are free fragments of this size.  Pop a fragment +	       out of the fragment list and return it.  Update the block's +	       nfree and first counters. */ +	    result = next; +	    next->prev->next = next->next; +	    if (next->next) +		next->next->prev = next->prev; +	    block = BLOCK(result); +	    if (--_heapinfo[block].busy.info.frag.nfree) +		_heapinfo[block].busy.info.frag.first +		    = (unsigned int) ((char *) next->next - (char *) NULL) +		      % BLOCKSIZE >> log; +	} else { +	    /* No free fragments of the desired size, so get a new block +	       and break it into fragments, returning the first. */ +	    result = malloc(BLOCKSIZE); +	    if (!result) +		return NULL; +	    ++_fragblocks[log]; + +	    /* Link all fragments but the first into the free list. */ +	    next = (struct list *) ((char *) result + (1 << log)); +	    next->next = 0; +	    next->prev = &_fraghead[log]; +	    _fraghead[log].next = next; + +	    for (i = 2; i < BLOCKSIZE >> log; ++i) { +		next = (struct list *) ((char *) result + (i << log)); +		next->next = _fraghead[log].next; +		next->prev = &_fraghead[log]; +		next->prev->next = next; +		next->next->prev = next; +	    } + +	    /* Initialize the nfree and first counters for this block. */ +	    block = BLOCK(result); +	    _heapinfo[block].busy.type = log; +	    _heapinfo[block].busy.info.frag.nfree = i - 1; +	    _heapinfo[block].busy.info.frag.first = i - 1; +	} +    } else { +	/* Large allocation to receive one or more blocks.  Search +	   the free list in a circle starting at the last place visited. +	   If we loop completely around without finding a large enough +	   space we will have to get more memory from the system. */ +	blocks = BLOCKIFY(size); +	start = block = _heapindex; +	while (_heapinfo[block].free.size < blocks) { +	    block = _heapinfo[block].free.next; +	    if (block == start) { +		/* Need to get more from the system.  Check to see if +		   the new core will be contiguous with the final free +		   block; if so we don't need to get as much. */ +		block = _heapinfo[0].free.prev; +		lastblocks = _heapinfo[block].free.size; +		if (_heaplimit && block + lastblocks == _heaplimit +		    && (*__morecore)(0) == ADDRESS(block + lastblocks) +		    && morecore((blocks - lastblocks) * BLOCKSIZE)) { +		    /* Note that morecore() can change the location of +		       the final block if it moves the info table and the +		       old one gets coalesced into the final block. */ +		    block = _heapinfo[0].free.prev; +		    _heapinfo[block].free.size += blocks - lastblocks; +		    continue; +		} +		result = morecore(blocks * BLOCKSIZE); +		if (!result) +		    return NULL; +		block = BLOCK(result); +		_heapinfo[block].busy.type = 0; +		_heapinfo[block].busy.info.size = blocks; +		return result; +	    } +	} + +	/* At this point we have found a suitable free list entry. +	   Figure out how to remove what we need from the list. */ +	result = ADDRESS(block); +	if (_heapinfo[block].free.size > blocks) { +	    /* The block we found has a bit left over, so relink the +	       tail end back into the free list. */ +	    _heapinfo[block + blocks].free.size +		= _heapinfo[block].free.size - blocks; +	    _heapinfo[block + blocks].free.next +		= _heapinfo[block].free.next; +	    _heapinfo[block + blocks].free.prev +		= _heapinfo[block].free.prev; +	    _heapinfo[_heapinfo[block].free.prev].free.next +		= _heapinfo[_heapinfo[block].free.next].free.prev +		    = _heapindex = block + blocks; +	} else { +	    /* The block exactly matches our requirements, so +	       just remove it from the list. */ +	    _heapinfo[_heapinfo[block].free.next].free.prev +		= _heapinfo[block].free.prev; +	    _heapinfo[_heapinfo[block].free.prev].free.next +		= _heapindex = _heapinfo[block].free.next; +	} + +	_heapinfo[block].busy.type = 0; +	_heapinfo[block].busy.info.size = blocks; +    } + +    return result; +} diff --git a/libc/stdlib/malloc-930716/malloc.h b/libc/stdlib/malloc-930716/malloc.h new file mode 100644 index 000000000..34458c062 --- /dev/null +++ b/libc/stdlib/malloc-930716/malloc.h @@ -0,0 +1,107 @@ +/* malloc.h - declarations for the allocator. +   Copyright (c) 1989, 1993  Michael J. Haertel +   You may redistribute this library under the terms of the +   GNU Library General Public License (version 2 or any later +   version) as published by the Free Software Foundation. +   THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED +   WARRANTY.  IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR +   WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS +   SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ + +#include <sys/cdefs.h> + +/* Underlying allocation function; successive calls should return +   contiguous pieces of memory. */ +extern void *(*__morecore)(long); + +/* Default value of previous. */ +extern void *__default_morecore_init(long); +extern void *__default_morecore(long); + +/* The allocator divides the heap into blocks of fixed size; large +   requests receive one or more whole blocks, and small requests +   receive a fragment of a block.  Fragment sizes are powers of two, +   and all fragments of a block are the same size.  When all the +   fragments in a block have been freed, the block itself is freed. +   WARNING: BLOCKSIZE must be set greater than or equal to the +   machine's page size for valloc() to work correctly.  The default +   definition here is 4096 bytes. */ +#define INT_BIT (CHAR_BIT * sizeof (int)) +#define BLOCKLOG (INT_BIT > 16 ? 12 : 9) +#define BLOCKSIZE (1 << BLOCKLOG) +#define BLOCKIFY(SIZE) (((SIZE) + BLOCKSIZE - 1) / BLOCKSIZE) + +/* Determine the amount of memory spanned by the initial heap table +   (not an absolute limit). */ +#define HEAP (INT_BIT > 16 ? 4194304 : 65536) + +/* Number of contiguous free blocks allowed to build up at the end of +   memory before they will be returned to the system. */ +#define FINAL_FREE_BLOCKS 8 + +/* Data structure giving per-block information. */ +union info { +    struct { +	int type;		/* Zero for a large block, or positive +				   giving the logarithm to the base two +				   of the fragment size. */ +	union { +	    struct { +		int nfree;	/* Free fragments in a fragmented block. */ +		int first;	/* First free fragment of the block. */ +	    } frag; +	    int size;		/* Size (in blocks) of a large cluster. */ +	} info; +    } busy; +    struct { +	int size;		/* Size (in blocks) of a free cluster. */ +	int next;		/* Index of next free cluster. */ +	int prev;		/* Index of previous free cluster. */ +    } free; +}; + +/* Pointer to first block of the heap. */ +extern char *_heapbase; + +/* Table indexed by block number giving per-block information. */ +extern union info *_heapinfo; + +/* Address to block number and vice versa. */ +#define BLOCK(A) (((char *) (A) - _heapbase) / BLOCKSIZE + 1) +#define ADDRESS(B) ((void *) (((B) - 1) * BLOCKSIZE + _heapbase)) + +/* Current search index for the heap table. */ +extern int _heapindex; + +/* Limit of valid info table indices. */ +extern int _heaplimit; + +/* Doubly linked lists of free fragments. */ +struct list { +    struct list *next; +    struct list *prev; +}; + +/* Count of blocks for each fragment size. */ +extern int _fragblocks[]; + +/* Free list headers for each fragment size. */ +extern struct list _fraghead[]; + +/* List of blocks allocated with `memalign' (or `valloc').  */ +struct alignlist +{  +  struct alignlist *next; +  __ptr_t aligned;	/* The address that memaligned returned.  */ +  __ptr_t exact;	/* The address that malloc returned.  */ +}; +extern struct alignlist *_aligned_blocks; + +extern void _free_internal __P ((__ptr_t __ptr)); + +extern void free (void *); +extern void * malloc (size_t); +extern void * calloc (size_t, size_t); +extern void * valloc (size_t); +extern void * memalign (size_t, size_t); +extern void * realloc (void *, size_t); diff --git a/libc/stdlib/malloc-930716/memalign.c b/libc/stdlib/malloc-930716/memalign.c new file mode 100644 index 000000000..1098f5890 --- /dev/null +++ b/libc/stdlib/malloc-930716/memalign.c @@ -0,0 +1,61 @@ +/* Copyright (C) 1991, 1992 Free Software Foundation, Inc. + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with this library; see the file COPYING.LIB.  If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA.  */ + +#include <stdlib.h> +#include "malloc.h" + +__ptr_t +memalign (alignment, size) +     size_t alignment; +     size_t size; +{ +  __ptr_t result; +  unsigned long int adj; + +  result = malloc (size + alignment - 1); +  if (result == NULL) +    return NULL; +  adj = (unsigned long int) ((unsigned long int) ((char *) result - +						(char *) NULL)) % alignment; +  if (adj != 0) +    { +      struct alignlist *l; +      for (l = _aligned_blocks; l != NULL; l = l->next) +	if (l->aligned == NULL) +	  /* This slot is free.  Use it.  */ +	  break; +      if (l == NULL) +	{ +	  l = (struct alignlist *) malloc (sizeof (struct alignlist)); +	  if (l == NULL) +	    { +#if 1 +	      free (result); +#else +	      _free_internal (result); +#endif +	      return NULL; +	    } +	  l->next = _aligned_blocks; +	  _aligned_blocks = l; +	} +      l->exact = result; +      result = l->aligned = (char *) result + alignment - adj; +    } + +  return result; +} diff --git a/libc/stdlib/malloc-930716/morecore.c b/libc/stdlib/malloc-930716/morecore.c new file mode 100644 index 000000000..e2ad4464b --- /dev/null +++ b/libc/stdlib/malloc-930716/morecore.c @@ -0,0 +1,28 @@ +/* morecore.c - C library support routine for UNIX. +   Copyright (c) 1989, 1993  Michael J. Haertel +   You may redistribute this library under the terms of the +   GNU Library General Public License (version 2 or any later +   version) as published by the Free Software Foundation. +   THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED +   WARRANTY.  IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR +   WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS +   SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ + +#include <limits.h> +#include <stddef.h> +#include "malloc.h" + +extern void *sbrk(int); + +/* Note that morecore has to take a signed argument so +   that negative values can return memory to the system. */ +void * +__default_morecore_init(long size) +{ +    void *result; + +    result = sbrk(size); +    if (result == (void *) -1) +	return NULL; +    return result; +} diff --git a/libc/stdlib/malloc-930716/realloc.c b/libc/stdlib/malloc-930716/realloc.c new file mode 100644 index 000000000..1453e813c --- /dev/null +++ b/libc/stdlib/malloc-930716/realloc.c @@ -0,0 +1,131 @@ +/* realloc.c - C standard library routine. +   Copyright (c) 1989, 1993  Michael J. Haertel +   You may redistribute this library under the terms of the +   GNU Library General Public License (version 2 or any later +   version) as published by the Free Software Foundation. +   THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT ANY EXPRESS OR IMPLIED +   WARRANTY.  IN PARTICULAR, THE AUTHOR MAKES NO REPRESENTATION OR +   WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY OF THIS +   SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. */ + +#include <limits.h> +#include <stddef.h> +#include <stdlib.h> +#include <string.h> +#include "malloc.h" + +#define MIN(A, B) ((A) < (B) ? (A) : (B)) + +/* Resize the given region to the new size, returning a pointer +   to the (possibly moved) region.  This is optimized for speed; +   some benchmarks seem to indicate that greater compactness is +   achieved by unconditionally allocating and copying to a +   new region. */ +void * +realloc (void *ptr, size_t size) +{ +    void *result, *previous; +    int block, blocks, type; +    int oldlimit; + +    if (!ptr) +	return malloc(size); +    if (!size) { +	free(ptr); +	return malloc(0); +    } + +    block = BLOCK(ptr); + +    switch (type = _heapinfo[block].busy.type) { +    case 0: +	/* Maybe reallocate a large block to a small fragment. */ +	if (size <= BLOCKSIZE / 2) { +	    if ((result = malloc(size)) != NULL) { +	    	memcpy(result, ptr, size); +#if 1 +	    	free(ptr); +#else +	    	_free_internal(ptr); +#endif + +	    } +	    return result; +	} + +	/* The new size is a large allocation as well; see if +	   we can hold it in place. */ +	blocks = BLOCKIFY(size); +	if (blocks < _heapinfo[block].busy.info.size) { +	    /* The new size is smaller; return excess memory +	       to the free list. */ +	    _heapinfo[block + blocks].busy.type = 0; +	    _heapinfo[block + blocks].busy.info.size +		= _heapinfo[block].busy.info.size - blocks; +	    _heapinfo[block].busy.info.size = blocks; +#if 1 +	    free(ADDRESS(block + blocks)); +#else +	    _free_internal(ADDRESS(block + blocks)); +#endif +	    return ptr; +	} else if (blocks == _heapinfo[block].busy.info.size) +	    /* No size change necessary. */ +	    return ptr; +	else { +	    /* Won't fit, so allocate a new region that will.  Free +	       the old region first in case there is sufficient adjacent +	       free space to grow without moving. */ +	    blocks = _heapinfo[block].busy.info.size; +	    /* Prevent free from actually returning memory to the system. */ +	    oldlimit = _heaplimit; +	    _heaplimit = 0; +#if 1 +	    free(ptr); +#else +	    _free_internal(ptr); +#endif +	    _heaplimit = oldlimit; +	    result = malloc(size); +	    if (!result) { +		/* Now we're really in trouble.  We have to unfree +		   the thing we just freed.  Unfortunately it might +		   have been coalesced with its neighbors. */ +		if (_heapindex == block) +		    malloc(blocks * BLOCKSIZE); +		else { +		    previous = malloc((block - _heapindex) * BLOCKSIZE); +		    malloc(blocks * BLOCKSIZE); +#if 1 +		    free(previous); +#else +		    _free_internal(previous); +#endif +		}	     +		return NULL; +	    } +	    if (ptr != result) +		memmove(result, ptr, blocks * BLOCKSIZE); +	    return result; +	} +	break; + +    default: +	/* Old size is a fragment; type is logarithm to base two of +	   the fragment size. */ +	if ((size > 1 << (type - 1)) && (size <= 1 << type)) +	    /* New size is the same kind of fragment. */ +	    return ptr; +	else { +	    /* New size is different; allocate a new space, and copy +	       the lesser of the new size and the old. */ +	    result = malloc(size); +	    if (!result) +		return NULL; +	    memcpy(result, ptr, MIN(size, 1 << type)); +	    free(ptr); +	    return result; +	} +	break; +    } +} diff --git a/libc/stdlib/malloc-930716/valloc.c b/libc/stdlib/malloc-930716/valloc.c new file mode 100644 index 000000000..dad12a1d2 --- /dev/null +++ b/libc/stdlib/malloc-930716/valloc.c @@ -0,0 +1,62 @@ +/* Allocate memory on a page boundary. +   Copyright (C) 1991, 1992 Free Software Foundation, Inc. + +This library is free software; you can redistribute it and/or +modify it under the terms of the GNU Library General Public License as +published by the Free Software Foundation; either version 2 of the +License, or (at your option) any later version. + +This library is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU +Library General Public License for more details. + +You should have received a copy of the GNU Library General Public +License along with this library; see the file COPYING.LIB.  If +not, write to the Free Software Foundation, Inc., 675 Mass Ave, +Cambridge, MA 02139, USA. + +   The author may be reached (Email) at the address mike@ai.mit.edu, +   or (US mail) as Mike Haertel c/o Free Software Foundation.  */ + +#include <stdlib.h> +#include "malloc.h" + +#ifdef	 emacs +#include "config.h" +#endif + +#ifdef	__GNU_LIBRARY__ +extern size_t __getpagesize __P ((void)); +#else +#ifndef	USG +extern size_t getpagesize __P ((void)); +#define	__getpagesize()	getpagesize() +#else +#include <sys/param.h> +#ifdef	EXEC_PAGESIZE +#define	__getpagesize()	EXEC_PAGESIZE +#else /* No EXEC_PAGESIZE.  */ +#ifdef	NBPG +#ifndef	CLSIZE +#define	CLSIZE	1 +#endif /* No CLSIZE.  */ +#define	__getpagesize()	(NBPG * CLSIZE) +#else /* No NBPG.  */ +#define	__getpagesize()	NBPC +#endif /* NBPG.  */ +#endif /* EXEC_PAGESIZE.  */ +#endif /* USG.  */ +#endif + +static size_t pagesize; + +__ptr_t +valloc (size) +     size_t size; +{ +  if (pagesize == 0) +    pagesize = __getpagesize (); + +  return memalign (pagesize, size); +} diff --git a/libc/stdlib/malloc-simple/Makefile b/libc/stdlib/malloc-simple/Makefile index 294902b97..cc2c132b2 100644 --- a/libc/stdlib/malloc-simple/Makefile +++ b/libc/stdlib/malloc-simple/Makefile @@ -40,8 +40,8 @@ $(MOBJ): $(MSRC)  	$(CC) $(CFLAGS) -DL_$* $< -c -o $*.o  	$(STRIPTOOL) -x -R .note -R .comment $*.o -$(COBJS): -	$(CC) $(CFLAGS) $< -c $*.c -o $*.o +$(COBJS): %.o : %.c +	$(CC) $(CFLAGS) -c $< -o $@  	$(STRIPTOOL) -x -R .note -R .comment $*.o  clean: diff --git a/libc/stdlib/malloc/Makefile b/libc/stdlib/malloc/Makefile index d7ae2732d..0128bc545 100644 --- a/libc/stdlib/malloc/Makefile +++ b/libc/stdlib/malloc/Makefile @@ -42,8 +42,8 @@ $(MOBJ): $(MSRC)  	$(CC) $(CFLAGS) -DL_$* $< -c -o $*.o  	$(STRIPTOOL) -x -R .note -R .comment $*.o -$(COBJS): -	$(CC) $(CFLAGS) $< -c $*.c -o $*.o +$(COBJS): %.o : %.c +	$(CC) $(CFLAGS) -c $< -o $@  	$(STRIPTOOL) -x -R .note -R .comment $*.o  clean: diff --git a/libc/stdlib/qsort.c b/libc/stdlib/qsort.c index 7cb1d8ab4..7390c3bd3 100644 --- a/libc/stdlib/qsort.c +++ b/libc/stdlib/qsort.c @@ -1,148 +1,72 @@ -/* - * This file lifted in toto from 'Dlibs' on the atari ST  (RdeBath) - * - *  - *    Dale Schumacher                         399 Beacon Ave. - *    (alias: Dalnefre')                      St. Paul, MN  55104 - *    dal@syntel.UUCP                         United States of America - *  "It's not reality that's important, but how you perceive things." - */ -#include <string.h> - -char *_qbuf = 0;				/* pointer to storage for qsort() */ - -#define	PIVOT			((i+j)>>1) -#define moveitem(dst,src,size)	if(dst != src) memcpy(dst, src, size) - -static void _wqsort(base, lo, hi, cmp) -register int *base; -register int lo; -register int hi; -register int (*cmp) (); -{ -	int k; -	register int i, j, t; -	register int *p = &k; - -	while (hi > lo) { -		i = lo; -		j = hi; -		t = PIVOT; -		*p = base[t]; -		base[t] = base[i]; -		base[i] = *p; -		while (i < j) { -			while (((*cmp) ((base + j), p)) > 0) -				--j; -			base[i] = base[j]; -			while ((i < j) && (((*cmp) ((base + i), p)) <= 0)) -				++i; -			base[j] = base[i]; -		} -		base[i] = *p; -		if ((i - lo) < (hi - i)) { -			_wqsort(base, lo, (i - 1), cmp); -			lo = i + 1; -		} else { -			_wqsort(base, (i + 1), hi, cmp); -			hi = i - 1; -		} -	} -} - -static void _lqsort(base, lo, hi, cmp) -register long *base; -register int lo; -register int hi; -register int (*cmp) (); -{ -	long k; -	register int i, j, t; -	register long *p = &k; - -	while (hi > lo) { -		i = lo; -		j = hi; -		t = PIVOT; -		*p = base[t]; -		base[t] = base[i]; -		base[i] = *p; -		while (i < j) { -			while (((*cmp) ((base + j), p)) > 0) -				--j; -			base[i] = base[j]; -			while ((i < j) && (((*cmp) ((base + i), p)) <= 0)) -				++i; -			base[j] = base[i]; -		} -		base[i] = *p; -		if ((i - lo) < (hi - i)) { -			_lqsort(base, lo, (i - 1), cmp); -			lo = i + 1; -		} else { -			_lqsort(base, (i + 1), hi, cmp); -			hi = i - 1; -		} -	} -} - -static void _nqsort(base, lo, hi, size, cmp) -register char *base; -register int lo; -register int hi; -register int size; -register int (*cmp) (); -{ -	register int i, j; -	register char *p = _qbuf; - -	while (hi > lo) { -		i = lo; -		j = hi; -		p = (base + size * PIVOT); -		moveitem(_qbuf, p, size); -		moveitem(p, (base + size * i), size); -		moveitem((base + size * i), _qbuf, size); -		p = _qbuf; -		while (i < j) { -			while (((*cmp) ((base + size * j), p)) > 0) -				--j; -			moveitem((base + size * i), (base + size * j), size); -			while ((i < j) && (((*cmp) ((base + size * i), p)) <= 0)) -				++i; -			moveitem((base + size * j), (base + size * i), size); -		} -		moveitem((base + size * i), p, size); -		if ((i - lo) < (hi - i)) { -			_nqsort(base, lo, (i - 1), size, cmp); -			lo = i + 1; -		} else { -			_nqsort(base, (i + 1), hi, size, cmp); -			hi = i - 1; -		} -	} -} - -extern int qsort(base, num, size, cmp) -char *base; -int num; -int size; -int (*cmp) (); -{ -	char _qtemp[128]; - -	if (_qbuf == 0) { -		if (size > sizeof(_qtemp))	/* records too large! */ -			return 1; -		_qbuf = _qtemp; -	} -	if (size == 2) -		_wqsort(base, 0, num - 1, cmp); -	else if (size == 4) -		_lqsort(base, 0, num - 1, cmp); -	else -		_nqsort(base, 0, num - 1, size, cmp); -	if (_qbuf == _qtemp) -		_qbuf = 0; -	return 0; -} +/* +++Date last modified: 05-Jul-1997 */
 +
 +/*
 +**  ssort()  --  Fast, small, qsort()-compatible Shell sort
 +**
 +**  by Ray Gardner,  public domain   5/90
 +*/
 +
 +/*
 + * Manuel Novoa III       Dec 2000
 + *
 + * There were several problems with the qsort code contained in uClibc.
 + * It assumed sizeof(int) was 2 and sizeof(long) was 4.  It then had three
 + * seperate quiicksort routines based on the width of the data passed: 2, 4,
 + * or anything else <= 128.  If the width was > 128, it returned -1 (although
 + * qsort should not return a value) and did no sorting.  On i386 with
 + * -Os -fomit-frame-pointer -ffunction-sections, the text segment of qsort.o
 + * was 1358 bytes, with an additional 4 bytes in bss.
 + *
 + * I decided to completely replace the existing code with a small
 + * implementation of a shell sort.  It is a drop-in replacement for the
 + * standard qsort and, with the same gcc flags as above, the text segment
 + * size on i386 is only 183 bytes.
 + *
 + * Grabbed original file rg_ssort.c from snippets.org.
 + * Modified original code to avoid possible overflow in wgap calculation.
 + * Modified wgap calculation in loop and eliminated variables gap and wnel.
 + */
 +
 +
 +#include <stdlib.h>
 +
 +void qsort (void  *base,
 +            size_t nel,
 +            size_t width,
 +            int (*comp)(const void *, const void *))
 +{
 +	size_t wgap, i, j, k;
 +	char *a, *b, tmp;
 +
 +#if 0
 +	/* Note: still conceivable that nel * width could overflow! */
 +	assert(width > 0);
 +#endif
 +
 +	if (nel > 1) {
 +		for (wgap = 0; ++wgap < (nel-1)/3 ; wgap *= 3) {}
 +		wgap *= width;
 +		nel *= width;			/* convert nel to 'wnel' */
 +		do {
 +			for (i = wgap; i < nel; i += width) {
 +				for (j = i - wgap; ;j -= wgap) {
 +					a = j + ((char *)base);
 +					b = a + wgap;
 +					if ( (*comp)(a, b) <= 0 ) {
 +						break;
 +					}
 +					k = width;
 +					do {
 +						tmp = *a;
 +						*a++ = *b;
 +						*b++ = tmp;
 +					} while ( --k );
 +					if (j < wgap) {
 +						break;
 +					}
 +				}
 +			}
 +			wgap = (wgap - width)/3;
 +		} while (wgap);
 +	}
 +}
 diff --git a/libc/stdlib/system.c b/libc/stdlib/system.c index 061dbc914..5b279976c 100644 --- a/libc/stdlib/system.c +++ b/libc/stdlib/system.c @@ -35,7 +35,9 @@ char *command;  	signal(SIGQUIT, SIG_IGN);  	signal(SIGINT, SIG_IGN); +#if 0  	printf("Waiting for child %d\n", pid); +#endif  	if (wait4(pid, &wait_val, 0, 0) == -1)  		wait_val = -1;  | 
