From f4092abdf94af6a99aff944d6264bc1284e8bdd4 Mon Sep 17 00:00:00 2001 From: Reinhard Tartler Date: Mon, 10 Oct 2011 17:43:39 +0200 Subject: Imported nx-X11-3.1.0-1.tar.gz Summary: Imported nx-X11-3.1.0-1.tar.gz Keywords: Imported nx-X11-3.1.0-1.tar.gz into Git repository --- nx-X11/lib/font/Type1/t1malloc.c | 759 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 759 insertions(+) create mode 100644 nx-X11/lib/font/Type1/t1malloc.c (limited to 'nx-X11/lib/font/Type1/t1malloc.c') diff --git a/nx-X11/lib/font/Type1/t1malloc.c b/nx-X11/lib/font/Type1/t1malloc.c new file mode 100644 index 000000000..20d4212cd --- /dev/null +++ b/nx-X11/lib/font/Type1/t1malloc.c @@ -0,0 +1,759 @@ +/* $Xorg: t1malloc.c,v 1.3 2000/08/17 19:46:34 cpqbld Exp $ */ +/* Copyright International Business Machines, Corp. 1991 + * All Rights Reserved + * Copyright Lexmark International, Inc. 1991 + * All Rights Reserved + * + * License to use, copy, modify, and distribute this software and its + * documentation for any purpose and without fee is hereby granted, + * provided that the above copyright notice appear in all copies and that + * both that copyright notice and this permission notice appear in + * supporting documentation, and that the name of IBM or Lexmark not be + * used in advertising or publicity pertaining to distribution of the + * software without specific, written prior permission. + * + * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF + * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY + * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, + * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS. THE ENTIRE RISK AS TO THE + * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT + * OR MAINTAIN, BELONGS TO THE LICENSEE. SHOULD ANY PORTION OF THE + * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE + * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION. IN NO EVENT SHALL + * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF + * THIS SOFTWARE. + */ +/* $XFree86: xc/lib/font/Type1/t1malloc.c,v 1.11 2002/02/18 20:51:57 herrb Exp $ */ + /* MALLOC CWEB V0004 LOTS */ +/* +:h1.MALLOC - Fast Memory Allocation + +This module is meant to provide portable C-style memory allocation +routines (malloc/free). + +&author. Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com) + +*/ + +#ifdef HAVE_CONFIG_H +#include +#endif +#ifndef FONTMODULE +#include +#else +#include "Xdefs.h" /* Bool declaration */ +#include "Xmd.h" /* INT32 declaration */ +#include "os.h" +#include "xf86_ansic.h" +#endif +#include "objects.h" /* get #define for Abort() */ + + +/* +:h3.Define NULL + +In the beginning, C compilers made no assumptions about NULL. It was +even theoretically possible that NULL would not be 0. ANSI has tied +this down a bit. The following definition seems to be the most +popular (in terms of reducing compiler complaints), however, if your +compiler is unhappy about it, you can redefine it on the command line: +*/ +#ifndef NULL +#include +#endif +/* +Of course, NULL is important because xiMalloc() is defined to return +NULL when out of memory. + +:h2.Data Structures Used to Manage Free Memory + +:h3.The "freeblock" Structure + +The list of available memory blocks is a doubly-linked list. Each +block begins with the following structure: +*/ + +struct freeblock { + long size; /* number of 'longs' in block, + including this header */ + struct freeblock *fore; /* forward in doubly-linked list */ + struct freeblock *back; /* backward in doubly-linked list */ +} ; +/* +In addition, each free block has a TRAILER that is simply the 'size' +repeated. Thus 'size' is found at the beginning of the block and at the +end of the block (size-1 longs away). 'size' includes both the header +and the trailer. + +When a block is allocated, its 'size' is turned negative (both at the +beginning and at the end). Thus, checking whether two blocks may be +combined is very simple. We merely examine both neighboring blocks' +size to see if they are positive (and hence available for combination). + +The memory address returned to the user is therefore one "long" below the +size, and one extra "long" is added to the end of the block (beyond what +the user requested) to store the trailing size. + +:h3."firstfree" and "lastfree", the Anchors to the Free List + +"firstfree" points to the first available free block; "lastfree" points +to the end of the chain of available blocks. These are linked together +by initialization code; see :hdref refid=addmem.. +*/ + +static struct freeblock firstfree = { 0L, NULL, NULL }; +static struct freeblock lastfree = { 0L, NULL, NULL }; + +/* +:h3."firstcombined" and "uncombined", Keeping Track of Uncombined Blocks + +This module is designed to make the combining of adjacent free memory +blocks be very fast. Nonetheless, combining blocks is naturally the +most expensive part of any memory system. In an X system, +it is worthwhile to defer the combination for a while, because +frequently we will end up asking for a block of exactly the same +size that we recently returned and we can save ourselves some work. + +"MAXUNCOMBINED" is the maximum number of uncombined blocks that we will +allow at any time: +*/ + +#define MAXUNCOMBINED 3 + +/* +"firstcombined" is a pointer into the free list. The uncombined blocks +are always at the front of the list. "firstcombined" points to the +first block that has been combined. +*/ +static struct freeblock *firstcombined = &lastfree; +static short uncombined = 0; /* current number of uncombined blocks */ + +/* +Uncombined blocks have a negative 'size'; in this they are like +allocated blocks. + +We store a distinctive hex pattern in 'size' when we combine a block +to help us debug: +*/ +#define COMBINED 0xBADBAD + +/* +:h3.DEBUGWORDS - Extra Memory Saved With Each Block for Debug + +We add 'DEBUGWORDS' words to each allocated block to put interesting +debug information: +*/ +#ifndef DEBUGWORDS +#define DEBUGWORDS 0 +#endif + +/* +:h3.MINEXCESS - Amount of "Excess" We Would be Willing to Ignore + +When we search the free list to find memory for a user request, we +frequently find an area that is bigger than what the user has asked for. +Normally we put the remaining words (the excess) back on the free list. +However, if the area is just slightly bigger than what the user needs, +it is counter-productive to do this, as the small amount recovered tends +to hurt by increasing memory fragmentation rather than help by providing +more available memory. "MINEXCESS" is the number of words that must be +recovered before we would bother to put the excess back on the free +list. If there is not enough excess, we just give the user more than he +asked for. +*/ + +#define MINEXCESS (7 + DEBUGWORDS) + +/* +:h3.Some Flags for Debug +*/ + +long AvailableWords = 0; /* number of words available in memory */ +char mallocdebug = 0; /* a flag that enables some chatty printf's */ + +/* +:h3.Prototypes of static functions +*/ + +static void combine ( void ); +static void freeuncombinable ( long *addr, long size ); +static void unhook ( struct freeblock *p ); +static void dumpchain ( void ); +#ifdef notused +static void reportarea ( long *area ); +#endif + +/* +:h3.whocalledme() - Debug for Memory Leaks + +This routine is 68000-specific; it copies the value of the application's +curOper variable (which is often a pointer to a character string), and +the first part of the stack at the time malloc was called into the +DEBUGWORDS area reserved with each block. +We use it to see who is malloc-ing memory without free-ing it. +*/ + +#if DEBUGWORDS + +static void +whocalledme(long *addr, /* address of memory block */ + long *stack) /* address of malloc's parameter on stack */ +{ + register long size; /* size of memory block */ + register int i; /* loop index */ + extern char *curOper; /* ptr to last operator (kept by appl.) */ + + stack--; + size = - *addr; + + addr += size - 1 - DEBUGWORDS; + *addr++ = (long) curOper; + for (i=0; i < DEBUGWORDS-1; i++) + *addr++ = *stack++; +} +#else + +#define whocalledme(addr, stack) + +#endif +/* +:h2.xiFree() - User-Callable "Return Memory" Routine + +The actual beginning of the block is one 'long' before the address we +gave to the user. The block begins and ends with '-size' in words. +*/ + +void +xiFree(long *addr) /* user's memory to be returned */ +{ + register long size; /* amount of memory in this block */ + register struct freeblock *p; /* identical to 'addr' */ + + if (addr == NULL) { /* common "mistake", so allow it (CHT) */ + printf("\nxiFree(NULL)?\n"); + return; + } + + size = *--addr; +/* +Make sure this address looks OK; 'size' must be less than zero (meaning +the block is allocated) and should be repeated at the end of the block. +*/ + if (size >= 0) + Abort("free: bad size"); + if (addr[-1 - size] != size) + Abort("free: mismatched size"); +/* +Now make this a 'freeblock' structure and tack it on the FRONT of the +free list (where uncombined blocks go): +*/ + AvailableWords -= size; /* actually INCREASES AvailableWords */ + p = (struct freeblock *) addr; + p->back = &firstfree; + (p->fore = firstfree.fore)->back = p; + firstfree.fore = p; +/* +If we have too many uncombined blocks, call combine() to combine one. +*/ + if (++uncombined > MAXUNCOMBINED) { + combine(); + if (mallocdebug) { + printf("xiFree(%p) with combine, ", (void *)addr); + dumpchain(); + } + } + else { + if (mallocdebug) { + printf("xiFree(%p), ", (void *)addr); + dumpchain(); + } + } + + return; +} + +/* +:h3.combine() - Subroutine of xiFree() to Combine Blocks + +This routine tries to combine the block just before 'firstcombined'. +In any event, that block will be moved to the end of the list (after +'firstcombined'). +*/ + +static void +combine(void) +{ + register struct freeblock *p; /* block we will try to combine */ + register long *addr; /* identical to 'p' for 'long' access */ + register long size; /* size of this block */ + register long size2; /* size of potential combinee */ + + p = firstcombined->back; + if (p == &firstfree) + Abort("why are we combining?"); + + addr = (long *) p; + size = - p->size; + if (--uncombined < 0) + Abort("too many combine()s"); + + if (addr[-1] < 0 && addr[size] < 0) { +/* +We special case the situation where no combining can be done. Then, we +just mark the chain "combined" (i.e., positive size), move the +'firstcombined' pointer back in the chain, and return. +*/ + addr[0] = addr[size - 1] = size; + firstcombined = (struct freeblock *) addr; + return; + } +/* +Otherwise, we unhook this pointer from the chain: +*/ + unhook(p); +/* +First we attempt to combine this with the block immediately above: +*/ + size2 = addr[-1]; + if (size2 > 0) { /* i.e., block above is free */ + *addr = COMBINED; /* might help debug */ + addr -= size2; + if (addr[0] != size2) + Abort("bad block above"); + unhook((struct freeblock *)addr); + size += size2; + } +/* +At this point 'addr' and 'size' may be the original block, or it may be +the newly combined block. Now we attempt to combine it with the block +below: +*/ + p = (struct freeblock *) (addr + size); + size2 = p->size; + + if (size2 > 0) { /* i.e., block below is free */ + p->size = COMBINED; + if (size2 != ((long *) p)[size2 - 1]) + Abort("bad block below"); + unhook(p); + size += size2; + } +/* +Finally we take the newly combined block and put it on the end of the +chain by calling the "freeuncombinable" subroutine: +*/ + freeuncombinable(addr, size); +} + +/* +:h3.freeuncombinable() - Free a Block That Need Not be Combined + +This block is "uncombinable" either because we have already combined +it with its eligible neighbors, or perhaps because we know it has +no neighbors. +*/ + +static void +freeuncombinable(long *addr, /* address of the block to be freed */ + long size) /* size of block in words */ +{ + register struct freeblock *p; /* a convenient synonym for 'addr' */ + +/* +Mark block allocated and combined by setting its 'size' positive: +*/ + addr[size - 1] = addr[0] = size; +/* +Now tack the block on the end of the doubly-linked free list: +*/ + p = (struct freeblock *) addr; + p->fore = &lastfree; + (p->back = lastfree.back)->fore = p; + lastfree.back = p; +/* +If we have previously had no combined blocks, we must update +'firstcombined' to point to this block: +*/ + if (firstcombined->fore == NULL) + firstcombined = p; +} + +/* +:h3.unhook() - Unhook a Block from the Doubly-linked List + +The only tricky thing here is to make sure that 'firstcombined' is +updated if this block happened to be the old 'firstcombined'. (We +would never be unhooking 'firstfree' or 'lastfree', so we do not +have to worry about the end cases.) +*/ + +static void +unhook(struct freeblock *p) /* block to unhook */ +{ + p->back->fore = p->fore; + p->fore->back = p->back; + + if (firstcombined == p) + firstcombined = p->fore; +} +/* +:h2.xiMalloc() - Main User Entry Point for Getting Memory + +We have two slightly different versions of xiMalloc(). In the case +where we have TYPE1IMAGER and a font cache, we are prepared, when nominally +out of memory, to loop calling TYPE1IMAGER's GimeSpace() to release font +cache. +*/ + +/* The following code put in by MDC on 11/10/90 */ + +#ifdef TYPE1IMAGER + +static char *malloc_local(unsigned size); + +char * +xiMalloc(unsigned size) +{ + char *memaddr; + + while ( (memaddr = malloc_local(size)) == NULL ) { + /* Ask TYPE1IMAGER to give us some of its cache back */ + if ( I_GimeSpace() == 0 ) break; /* We are really, really, out of memory */ + } + + return(memaddr); +} +#endif + +/* +Now begins the real workhorse xiMalloc() (called 'malloc_local' if +we are taking advantage of TYPE1IMAGER). Its argument is an unsigned; +at least that lets users with 16-bit integers get a 64K chunk of +memory, and it is also compatible with the definition of a "size_t" +in most systems. +*/ +#ifdef TYPE1IMAGER +static char * +malloc_local(unsigned Size) /* number of bytes the user requested */ +#else +char * +xiMalloc(unsigned Size) +#endif +{ + register long size = (long)Size; /* a working register for size */ + register struct freeblock *p; /* tentative block to be returned */ + register long excess; /* words in excess of user request */ + register long *area; /* a convenient synonym for 'p' */ + +/* +First, we increase 'size' to allow for the two size fields we will +save with the block, plus any information for debug purposes. +Then we ensure that the block will be large enough to hold our +'freeblock' information. Finally we convert it to be in words +(longs), not bytes, increased to span an integral number of double +words, so that all memory blocks dispensed with be properly aligned. +*/ + size += 2*sizeof(long) + DEBUGWORDS*sizeof(long); + if (size < sizeof(struct freeblock) + sizeof(long)) + size = sizeof(struct freeblock) + sizeof(long); + size = ((unsigned) (size + sizeof(double) - 1) / sizeof(double)) * (sizeof(double)/sizeof(long)); + +/* +For speed, we will try first to give the user back a very recently +returned block--one that is on the front of the chain before +'firstcombined'. These blocks still have negative sizes, and need +only to be "unhook"ed: +*/ + size = -size; + for (p=firstfree.fore; p != firstcombined; p=p->fore) { + if (p->size == size) { + unhook(p); + uncombined--; + if (mallocdebug) { + printf("fast xiMalloc(%ld) = %p, ", size, + (void *)p); + dumpchain(); + } + AvailableWords += size; /* decreases AvailableWords */ + whocalledme(p, &Size); + return((char *)&p->fore); + } + } +/* +Well, if we get here, there are no uncombined blocks matching the user's +request. So, we search the rest of the chain for a block that is big +enough. ('size' becomes positive again): +*/ + size = -size; + for (;; p = p->fore) { +/* +If we hit the end of the chain (p->size == 0), we are probably out of +memory. However, we should first try to combine any memory that has +not yet been combined before we give that pessimistic answer. If +we succeed in combining, we can call ourselves recursively to try to +allocate the requested amount: +*/ + if (p->size == 0) { + if (uncombined <= 0) + return(NULL); + while (firstfree.fore != firstcombined) + combine(); + return(xiMalloc(sizeof(long) * (size - 2 - DEBUGWORDS))); + } +/* +Otherwise, we keep searching until we find a big enough block: +*/ + if (p->size >= size) + break; + } +/* +At this point, 'p' contains a block at least as big as what the user +requested, so we take it off the free chain. If it is excessively big, +we return the excess to the free chain: +*/ + unhook(p); + excess = p->size - size; + area = (long *) p; + + if (excess > MINEXCESS) + freeuncombinable(area + size, excess); + else + size = p->size; + + AvailableWords -= size; +/* +Mark first and last word of block with the negative of the size, to +flag that this block is allocated: +*/ + area[size - 1] = area[0] = - size; + + if (mallocdebug) { + printf("slow xiMalloc(%ld) @ %p, ", size, (void *)area); + dumpchain(); + } + whocalledme(area, &Size); +/* +The address we return to the user is one 'long' BELOW the address of +the block. This protects our 'size' field, so we can tell the size +of the block when he returns it to us with xiFree(). Also, he better not +touch the 'size' field at the end of the block either. (That would be +nasty of him, as he would be touching memory outside of the bytes he +requested). +*/ + return((char *) (area + 1)); +} + +/* +:h2 id=addmem.addmemory() - Initialize Free Memory + +This routine should be called at initialization to initialize the +free chain. There is no standard way to do this in C. +We want the memory dispensed by malloc to be aligned on a double word +boundary (because some machines either require alignment, or are +more efficient if accesses are aligned). Since the total size of +any block created by malloc is an integral number of double words, +all we have to do to ensure alignment is to adjust each large block +added to the free chain to start on an odd long-word boundary. +(Malloc's size field will occupy the odd long and the user's memory +will then begin on an even boundary.) Since we fill in additional +size fields at the beginning and end of each of the large freeblocks, +we need only adjust the address passed to addmemory to a double word +boundary. +*/ + +#define MAXAREAS 10 /* there can be this many calls to addmemory() */ + +static long *freearea[MAXAREAS] = { NULL }; /* so we can report later */ + +void +addmemory(long *addr, /* beginning of free area */ + long size) /* number of bytes of free area */ +{ + register int i; /* loop index variable */ + register long *aaddr; /* aligned beginning of free area */ + +#if DEBUGWORDS + printf("malloc has DEBUGWORDS=%d\n", DEBUGWORDS); +#endif +/* +First link together firstfree and lastfree if necessary: +*/ + if (firstfree.fore == NULL) { + firstfree.fore = &lastfree; + lastfree.back = &firstfree; + } +/* +We'll record where the area was that was given to us for later reports: +*/ + for (i=0; i < MAXAREAS; i++) + if (freearea[i] == NULL) break; + if (i >= MAXAREAS) + Abort("too many addmemory()s"); + aaddr = (long *) ( ((long) addr + sizeof(double) - 1) & - (long)sizeof(double) ); + size -= (char *) aaddr - (char *) addr; + freearea[i] = aaddr; +/* +Convert 'size' to number of longs, and store '-size' guards at the +beginning and end of this area so we will not accidentally recombine the +first or last block: +*/ + size /= sizeof(long); + + AvailableWords += size - 2; + + aaddr[size - 1] = aaddr[0] = -size; +/* +Finally, call 'freeuncombinable' to put the remaining memory on the +free list: +*/ + freeuncombinable(aaddr + 1, size - 2); +} + +/* +:h3.delmemory() - Delete Memory Pool +*/ +void +delmemory(void) +{ + register int i; + + AvailableWords = 0; + firstfree.fore = &lastfree; + lastfree.back = &firstfree; + firstcombined = &lastfree; + uncombined = 0; + for (i=0; ifore) { + if (--i < 0) + Abort("too many uncombined areas"); + size = p->size; + printf(". . . area @ %p, size = %ld\n", (void *)p, -size); + if (size >= 0 || size != ((int *) p)[-1 - size]) + Abort("dumpchain: bad size"); + if (p->back != back) + Abort("dumpchain: bad back"); + back = p; + } + printf("DUMPING COMBINED FREE LIST:\n"); + for (; p != &lastfree; p = p->fore) { + size = p->size; + printf(". . . area @ %p, size = %ld\n", (void *)p, size); + if (size <= 0 || size != ((int *) p)[size - 1]) + Abort("dumpchain: bad size"); + if (p->back != back) + Abort("dumpchain: bad back"); + back = p; + } + if (back != lastfree.back) + Abort("dumpchain: bad lastfree"); +} + +#ifdef notused +/* +:h3.reportarea() - Display a Contiguous Set of Memory Blocks +*/ + +static void +reportarea(long *area) /* start of blocks (from addmemory) */ +{ + register long size; /* size of current block */ + register long wholesize; /* size of original area */ + register struct freeblock *p; /* pointer to block */ + + if (area == NULL) + return; + wholesize = - *area++; + wholesize -= 2; + + while (wholesize > 0) { + size = *area; + if (size < 0) { + register int i,j; + + size = -size; + printf("Allocated %5ld bytes at %p, first words=%08lx %08lx\n", + size * sizeof(long), area + 1, area[1], area[2]); +#if DEBUGWORDS + printf(" ...Last operator: %s\n", + (char *)area[size-DEBUGWORDS-1]); +#endif + for (i = size - DEBUGWORDS; i < size - 2; i += 8) { + printf(" ..."); + for (j=0; j<8; j++) + printf(" %08lx", area[i+j]); + printf("\n"); + } + + } + else { + printf("Free %ld bytes at %p\n", size * sizeof(long), + area); + if (size == 0) + Abort("zero sized memory block"); + + for (p = firstfree.fore; p != NULL; p = p->fore) + if ((long *) p == area) break; + if ((long *) p != area) + Abort("not found on forward chain"); + + for (p = lastfree.back; p != NULL; p = p->back) + if ((long *) p == area) break; + if ((long *) p != area) + Abort("not found on backward chain"); + } + if (area[0] != area[size - 1]) + Abort("unmatched check sizes"); + area += size; + wholesize -= size; + } +} + +/* +:h3.MemReport() - Display All of Memory +*/ + +void +MemReport(void) +{ + register int i; + + dumpchain(); + + for (i=0; i