/* Copyright (C) 2001-2022 Artifex Software, Inc.

   All Rights Reserved.

   This software is provided AS-IS with no warranty, either express or

   implied.

   This software is distributed under license and may not be copied,

   modified or distributed except as expressly authorized under the terms

   of the license contained in the file LICENSE in this distribution.

   Refer to licensing information at http://www.artifex.com or contact

   Artifex Software, Inc.,  1305 Grant Avenue - Suite 200, Novato,

   CA 94945, U.S.A., +1(415)492-9861, for further information.

*/

/* chunk consolidating wrapper on a base memory allocator */

/* This uses dual binary trees to handle the free list. One tree

 * holds the blocks in size order, one in location order. We use

 * a top-down semi-splaying access scheme on lookups and

 * insertions. */

#include "memory_.h"

#include "gx.h"

#include "gsstruct.h"

#include "gxobj.h"

#include "gsstype.h"

#include "gserrors.h"

#include "gsmchunk.h"

#include "gxsync.h"

#include "malloc_.h" /* For MEMENTO */

#include "assert_.h"

#include "gsmdebug.h"

/* Enable DEBUG_CHUNK to check the validity of the heap at every turn */

#undef DEBUG_CHUNK

/* Enable DEBUG_SEQ to keep sequence numbers in every block */

#undef DEBUG_SEQ

/* Enable DEBUG_CHUNK_PRINT to print the heap at every turn */

#undef DEBUG_CHUNK_PRINT

/* Enable DEBUG_CHUNK_PRINT_SLABS to list the slabs in the heap */

#undef DEBUG_CHUNK_PRINT_SLABS

#if defined(DEBUG_CHUNK_PRINT_SLABS) && !defined(DEBUG_CHUNK_PRINT)

#define DEBUG_CHUNK_PRINT

#endif

#if defined(DEBUG_CHUNK_PRINT) && !defined(DEBUG_CHUNK)

#define DEBUG_CHUNK

#endif

#if defined(DEBUG_CHUNK) && !defined(DEBUG)

#define DEBUG

#define CHUNK_FAKE_ASSERT

#endif

#ifdef DEBUG

#ifdef CHUNK_FAKE_ASSERT

#define CHUNK_ASSERT(M,A) gs_chunk_assert(M, A, #A)

static void gs_chunk_assert(gs_memory_t *m, int v, const char *s)

{

    void (*crash)(void);

    if (v)

        return;

    dmlprintf1(m, "Assert failed: %s\n", s);

    crash = NULL;

    crash();

}

#else

#define CHUNK_ASSERT(M,A) assert(A)

#endif

#endif

/* Raw memory procedures */

static gs_memory_proc_alloc_bytes(chunk_alloc_bytes_immovable);

static gs_memory_proc_resize_object(chunk_resize_object);

static gs_memory_proc_free_object(chunk_free_object);

static gs_memory_proc_stable(chunk_stable);

static gs_memory_proc_status(chunk_status);

static gs_memory_proc_free_all(chunk_free_all);

static gs_memory_proc_consolidate_free(chunk_consolidate_free);

/* Object memory procedures */

static gs_memory_proc_alloc_bytes(chunk_alloc_bytes);

static gs_memory_proc_alloc_struct(chunk_alloc_struct);

static gs_memory_proc_alloc_struct(chunk_alloc_struct_immovable);

static gs_memory_proc_alloc_byte_array(chunk_alloc_byte_array);

static gs_memory_proc_alloc_byte_array(chunk_alloc_byte_array_immovable);

static gs_memory_proc_alloc_struct_array(chunk_alloc_struct_array);

static gs_memory_proc_alloc_struct_array(chunk_alloc_struct_array_immovable);

static gs_memory_proc_object_size(chunk_object_size);

static gs_memory_proc_object_type(chunk_object_type);

static gs_memory_proc_alloc_string(chunk_alloc_string);

static gs_memory_proc_alloc_string(chunk_alloc_string_immovable);

static gs_memory_proc_resize_string(chunk_resize_string);

static gs_memory_proc_free_string(chunk_free_string);

static gs_memory_proc_register_root(chunk_register_root);

static gs_memory_proc_unregister_root(chunk_unregister_root);

static gs_memory_proc_enable_free(chunk_enable_free);

static gs_memory_proc_set_object_type(chunk_set_object_type);

static gs_memory_proc_defer_frees(chunk_defer_frees);

static const gs_memory_procs_t chunk_procs =

{

    /* Raw memory procedures */

    chunk_alloc_bytes_immovable,

    chunk_resize_object,

    chunk_free_object,

    chunk_stable,

    chunk_status,

    chunk_free_all,

    chunk_consolidate_free,

    /* Object memory procedures */

    chunk_alloc_bytes,

    chunk_alloc_struct,

    chunk_alloc_struct_immovable,

    chunk_alloc_byte_array,

    chunk_alloc_byte_array_immovable,

    chunk_alloc_struct_array,

    chunk_alloc_struct_array_immovable,

    chunk_object_size,

    chunk_object_type,

    chunk_alloc_string,

    chunk_alloc_string_immovable,

    chunk_resize_string,

    chunk_free_string,

    chunk_register_root,

    chunk_unregister_root,

    chunk_enable_free,

    chunk_set_object_type,

    chunk_defer_frees

};

typedef struct chunk_obj_node_s {

    gs_memory_type_ptr_t type;

#ifdef DEBUG_SEQ

    unsigned int sequence;

#endif

    struct chunk_obj_node_s *defer_next;

    size_t size; /* Actual size of block */

    size_t padding; /* Actual size - requested size */

} chunk_obj_node_t;

typedef struct chunk_free_node_s {

    struct chunk_free_node_s *left_loc;

    struct chunk_free_node_s *right_loc;

    struct chunk_free_node_s *left_size;

    struct chunk_free_node_s *right_size;

    size_t size;                  /* size of entire freelist block */

} chunk_free_node_t;

/*

 * Note: All objects within a chunk are 'aligned' since we round_up_to_align

 * the free list pointer when removing part of a free area.

 */

typedef struct chunk_slab_s {

    struct chunk_slab_s *next;

} chunk_slab_t;

typedef struct gs_memory_chunk_s {

    gs_memory_common;           /* interface outside world sees */

    gs_memory_t *target;        /* base allocator */

    chunk_slab_t *slabs;         /* list of slabs for freeing */

    chunk_free_node_t *free_size;/* free tree */

    chunk_free_node_t *free_loc; /* free tree */

    chunk_obj_node_t *defer_finalize_list;

    chunk_obj_node_t *defer_free_list;

    size_t used;

    size_t max_used;

    size_t total_free;

#ifdef DEBUG_SEQ

    unsigned int sequence;

#endif

    int deferring;

} gs_memory_chunk_t;

#define SIZEOF_ROUND_ALIGN(a) ROUND_UP(sizeof(a), obj_align_mod)

/* ---------- Public constructors/destructors ---------- */

/* Initialize a gs_memory_chunk_t */

int

gs_memory_chunk_wrap(gs_memory_t **wrapped,      /* chunk allocator init */

                    gs_memory_t  *target)       /* base allocator */

{

    /* Use the non-GC allocator of the target. */

    gs_memory_t       *non_gc_target = target->non_gc_memory;

    gs_memory_chunk_t *cmem = NULL;

    if (non_gc_target)

        cmem = (gs_memory_chunk_t *)gs_alloc_bytes_immovable(non_gc_target,

                                                            sizeof(gs_memory_chunk_t),

                                                            "gs_memory_chunk_wrap");

    if (cmem == NULL) {

        *wrapped = NULL;

        return_error(gs_error_VMerror);

    }

    cmem->stable_memory = (gs_memory_t *)cmem;  /* we are stable */

    cmem->procs = chunk_procs;

    cmem->gs_lib_ctx = non_gc_target->gs_lib_ctx;

    cmem->non_gc_memory = (gs_memory_t *)cmem;  /* and are not subject to GC */

    cmem->thread_safe_memory = non_gc_target->thread_safe_memory;

    cmem->target = non_gc_target;

    cmem->slabs = NULL;

    cmem->free_size = NULL;

    cmem->free_loc = NULL;

    cmem->used = 0;

    cmem->max_used = 0;

    cmem->total_free = 0;

#ifdef DEBUG_SEQ

    cmem->sequence = 0;

#endif

    cmem->deferring = 0;

    cmem->defer_finalize_list = NULL;

    cmem->defer_free_list = NULL;

#ifdef DEBUG_CHUNK_PRINT

    dmlprintf1(non_gc_target, "New chunk "PRI_INTPTR"\n", (intptr_t)cmem);

#endif

    /* Init the chunk management values */

    *wrapped = (gs_memory_t *)cmem;

    return 0;

}

/* Release a chunk memory manager. */

/* Note that this has no effect on the target. */

void

gs_memory_chunk_release(gs_memory_t *mem)

{

    gs_memory_free_all((gs_memory_t *)mem, FREE_ALL_EVERYTHING,

                       "gs_memory_chunk_release");

}

/* Release chunk memory manager, and return the target */

gs_memory_t * /* Always succeeds */

gs_memory_chunk_unwrap(gs_memory_t *mem)

{

    gs_memory_t *tmem;

    /* If this isn't a chunk, nothing to unwrap */

    if (mem->procs.status != chunk_status)

        return mem;

    tmem = ((gs_memory_chunk_t *)mem)->target;

    gs_memory_chunk_release(mem);

    return tmem;

}

/* ---------- Accessors ------------- */

/* Retrieve this allocator's target */

gs_memory_t *

gs_memory_chunk_target(const gs_memory_t *mem)

{

    gs_memory_chunk_t *cmem = (gs_memory_chunk_t *)mem;

    return cmem->target;

}

/* -------- Private members --------- */

/* Note that all of the data is 'immovable' and is opaque to the base allocator */

/* thus even if it is a GC type of allocator, no GC functions will be applied   */

/* All allocations are done in the target */

/* Procedures */

static void

chunk_mem_node_free_all_slabs(gs_memory_chunk_t *cmem)

{

    chunk_slab_t *slab, *next;

    gs_memory_t *const target = cmem->target;

    for (slab = cmem->slabs; slab != NULL; slab = next) {

        next = slab->next;

        gs_free_object(target, slab, "chunk_mem_node_free_all_slabs");

    }

    cmem->slabs = NULL;

    cmem->free_size = NULL;

    cmem->free_loc = NULL;

    cmem->total_free = 0;

    cmem->used = 0;

}

static void

chunk_free_all(gs_memory_t * mem, uint free_mask, client_name_t cname)

{

    gs_memory_chunk_t * const cmem = (gs_memory_chunk_t *)mem;

    gs_memory_t * const target = cmem->target;

    if (free_mask & FREE_ALL_DATA)

        chunk_mem_node_free_all_slabs(cmem);

    /* Only free the structures and the allocator itself. */

    if (mem->stable_memory) {

        if (mem->stable_memory != mem)

            gs_memory_free_all(mem->stable_memory, free_mask, cname);

        if (free_mask & FREE_ALL_ALLOCATOR)

            mem->stable_memory = 0;

    }

    if (free_mask & FREE_ALL_STRUCTURES) {

        cmem->target = 0;

    }

    if (free_mask & FREE_ALL_ALLOCATOR)

        gs_free_object(target, cmem, cname);

}

extern const gs_memory_struct_type_t st_bytes;

#ifdef DEBUG

static int dump_free_loc(gs_memory_t *mem, chunk_free_node_t *node, int depth, void **limit, uint *total)

{

#ifdef DEBUG_CHUNK_PRINT

    int i;

#endif

    int count;

    if (node == NULL)

        return 0;

    count = dump_free_loc(mem, node->left_loc, depth + 1 + (depth&1), limit, total);

    *total += node->size;

#ifdef DEBUG_CHUNK_PRINT

    if (depth != 0) {

        for (i = (depth-1)>>1; i != 0; i--)

            dmlprintf(mem, " ");

        if (depth & 1)

            dmlprintf(mem, "/");

        else

            dmlprintf(mem, "\\");

    }

    dmlprintf3(mem, PRI_INTPTR"+%x->"PRI_INTPTR"\n", (intptr_t)node, node->size, (intptr_t)((byte *)node)+node->size);

#endif

    CHUNK_ASSERT(mem, *limit < (void *)node);

    *limit = ((byte *)node)+node->size;

    return 1 + count + dump_free_loc(mem, node->right_loc, depth + 2 + (depth&1), limit, total);

}

static int dump_free_size(gs_memory_t *mem, chunk_free_node_t *node, int depth, uint *size, void **addr)

{

#ifdef DEBUG_CHUNK_PRINT

    int i;

#endif

    int count;

    if (node == NULL)

        return 0;

    count = dump_free_size(mem, node->left_size, depth + 1 + (depth&1), size, addr);

#ifdef DEBUG_CHUNK_PRINT

    if (depth != 0) {

        for (i = (depth-1)>>1; i != 0; i--)

            dmlprintf(mem, " ");

        if (depth & 1)

            dmlprintf(mem, "/");

        else

            dmlprintf(mem, "\\");

    }

    dmlprintf3(mem, PRI_INTPTR"+%x->"PRI_INTPTR"\n", (intptr_t)node, node->size, (intptr_t)((byte *)node)+node->size);

#endif

    CHUNK_ASSERT(mem, *size < node->size || (*size == node->size && *addr < (void *)node));

    *size = node->size;

    *addr = node;

    return 1 + count + dump_free_size(mem, node->right_size, depth + 2 + (depth&1), size, addr);

}

#ifdef DEBUG_CHUNK_PRINT

static size_t

largest_free_block(chunk_free_node_t *size)

{

    if (size == NULL)

        return 0;

    while (1) {

        if (size->right_size == NULL)

            return size->size;

        size = size->right_size;

    }

}

#endif

void

gs_memory_chunk_dump_memory(const gs_memory_t *mem)

{

    const gs_memory_chunk_t *cmem = (const gs_memory_chunk_t *)mem;

    int count1, count2;

    void *limit = NULL;

    void *addr = NULL;

    uint size = 1;

    uint total = 0;

#ifdef DEBUG_CHUNK_PRINT

    dmlprintf1(cmem->target, "Chunk "PRI_INTPTR":\n", (intptr_t)cmem);

    dmlprintf3(cmem->target, "Used=%"PRIxSIZE", Max Used=%"PRIxSIZE", Total Free=%"PRIxSIZE"\n", cmem->used, cmem->max_used, cmem->total_free);

    dmlprintf1(cmem->target, "Largest free block=%d bytes\n", largest_free_block(cmem->free_size));

#ifdef DEBUG_CHUNK_PRINT_SLABS

    {

        chunk_slab_t *slab;

        dmlprintf(cmem->target, "Slabs:\n");

        for (slab = cmem->slabs; slab != NULL; slab = slab->next)

            dmlprintf1(cmem->target, " "PRI_INTPTR"\n", (intptr_t)slab);

    }

#endif

    dmlprintf(cmem->target, "Locs:\n");

#endif

    count1 = dump_free_loc(cmem->target, cmem->free_loc, 0, &limit, &total);

#ifdef DEBUG_CHUNK_PRINT

    dmlprintf(cmem->target, "Sizes:\n");

#endif

    count2 = dump_free_size(cmem->target, cmem->free_size, 0, &size, &addr);

    if (count1 != count2) {

        void (*crash)(void) = NULL;

        dmlprintf2(cmem->target, "Tree mismatch! %d vs %d\n", count1, count2);

        crash();

    }

    if (total != cmem->total_free) {

        void (*crash)(void) = NULL;

        dmlprintf2(cmem->target, "Free size mismatch! %u vs %lu\n", total, cmem->total_free);

        crash();

    }

}

#endif

/* round up objects to make sure we have room for a header left */

inline static uint

round_up_to_align(uint size)

{

    uint num_node_headers = (size + SIZEOF_ROUND_ALIGN(chunk_obj_node_t) - 1) / SIZEOF_ROUND_ALIGN(chunk_obj_node_t);

    return num_node_headers * SIZEOF_ROUND_ALIGN(chunk_obj_node_t);

}

static inline int CMP_SIZE(const chunk_free_node_t * a, const chunk_free_node_t * b)

{

    if (a->size > b->size)

        return 1;

    if (a->size < b->size)

        return 0;

    return (a > b);

}

static void insert_free_size(gs_memory_chunk_t *cmem, chunk_free_node_t *node)

{

    chunk_free_node_t **ap;

    chunk_free_node_t *a, *b, *c;

    node->left_size  = NULL;

    node->right_size = NULL;

    /* Insert into size */

    ap = &cmem->free_size;

    while ((a = *ap) != NULL) {

        if (CMP_SIZE(a, node)) {

            b = a->left_size;

            if (b == NULL) {

                ap = &a->left_size;

                break; /* Stop searching */

            }

            if (CMP_SIZE(b, node)) {

                c = b->left_size;

                if (c == NULL) {

                    ap = &b->left_size;

                    break;

                }

                /* Splay:        a             c

                 *            b     Z   =>  W     b

                 *          c   Y               X   a

                 *         W X                     Y Z

                 */

                *ap = c;

                a->left_size  = b->right_size;

                b->left_size  = c->right_size;

                b->right_size = a;

                c->right_size = b;

                if (CMP_SIZE(c, node))

                    ap = &c->left_size;

                else

                    ap = &b->left_size;

            } else {

                c = b->right_size;

                if (c == NULL) {

                    ap = &b->right_size;

                    break;

                }

                /* Splay:         a             c

                 *            b       Z  =>   b   a

                 *          W   c            W X Y Z

                 *             X Y

                 */

                *ap = c;

                a->left_size  = c->right_size;

                b->right_size = c->left_size;

                c->left_size  = b;

                c->right_size = a;

                if (CMP_SIZE(c, node))

                    ap = &b->right_size;

                else

                    ap = &a->left_size;

            }

        } else {

            b = a->right_size;

            if (b == NULL)

            {

                ap = &a->right_size;

                break;

            }

            if (CMP_SIZE(b, node)) {

                c = b->left_size;

                if (c == NULL) {

                    ap = &b->left_size;

                    break;

                }

                /* Splay:      a                c

                 *         W       b    =>    a   b

                 *               c   Z       W X Y Z

                 *              X Y

                 */

                *ap = c;

                a->right_size = c->left_size;

                b->left_size  = c->right_size;

                c->left_size  = a;

                c->right_size = b;

                if (CMP_SIZE(c, node))

                    ap = &a->right_size;

                else

                    ap = &b->left_size;

            } else {

                c = b->right_size;

                if (c == NULL) {

                    ap = &b->right_size;

                    break;

                }

                /* Splay:    a                   c

                 *        W     b      =>     b     Z

                 *            X   c         a   Y

                 *               Y Z       W X

                 */

                *ap = c;

                a->right_size = b->left_size;

                b->right_size = c->left_size;

                b->left_size  = a;

                c->left_size  = b;

                if (CMP_SIZE(c, node))

                    ap = &b->right_size;

                else

                    ap = &c->right_size;

            }

        }

    }

    *ap = node;

}

static void insert_free_loc(gs_memory_chunk_t *cmem, chunk_free_node_t *node)

{

    chunk_free_node_t **ap;

    chunk_free_node_t *a, *b, *c;

    node->left_loc   = NULL;

    node->right_loc  = NULL;

    /* Insert into loc */

    ap = &cmem->free_loc;

    while ((a = *ap) != NULL) {

        if (a > node) {

            b = a->left_loc;

            if (b == NULL) {

                ap = &a->left_loc;

                break; /* Stop searching */

            }

            if (b > node) {

                c = b->left_loc;

                if (c == NULL) {

                    ap = &b->left_loc;

                    break;

                }

                /* Splay:        a             c

                 *            b     Z   =>  W     b

                 *          c   Y               X   a

                 *         W X                     Y Z

                 */

                *ap = c;

                a->left_loc  = b->right_loc;

                b->left_loc  = c->right_loc;

                b->right_loc = a;

                c->right_loc = b;

                if (c > node)

                    ap = &c->left_loc;

                else

                    ap = &b->left_loc;

            } else {

                c = b->right_loc;

                if (c == NULL) {

                    ap = &b->right_loc;

                    break;

                }

                /* Splay:         a             c

                 *            b       Z  =>   b   a

                 *          W   c            W X Y Z

                 *             X Y

                 */

                *ap = c;

                a->left_loc  = c->right_loc;

                b->right_loc = c->left_loc;

                c->left_loc  = b;

                c->right_loc = a;

                if (c > node)

                    ap = &b->right_loc;

                else

                    ap = &a->left_loc;

            }

        } else {

            b = a->right_loc;

            if (b == NULL)

            {

                ap = &a->right_loc;

                break;

            }

            if (b > node) {

                c = b->left_loc;

                if (c == NULL) {

                    ap = &b->left_loc;

                    break;

                }

                /* Splay:      a                c

                 *         W       b    =>    a   b

                 *               c   Z       W X Y Z

                 *              X Y

                 */

                *ap = c;

                a->right_loc = c->left_loc;

                b->left_loc  = c->right_loc;

                c->left_loc  = a;

                c->right_loc = b;

                if (c > node)

                    ap = &a->right_loc;

                else

                    ap = &b->left_loc;

            } else {

                c = b->right_loc;

                if (c == NULL) {

                    ap = &b->right_loc;

                    break;

                }

                /* Splay:    a                   c

                 *        W     b      =>     b     Z

                 *            X   c         a   Y

                 *               Y Z       W X

                 */

                *ap = c;

                a->right_loc = b->left_loc;

                b->right_loc = c->left_loc;

                b->left_loc  = a;

                c->left_loc  = b;

                if (c > node)

                    ap = &b->right_loc;

                else

                    ap = &c->right_loc;

            }

        }

    }

    *ap = node;

}

static void insert_free(gs_memory_chunk_t *cmem, chunk_free_node_t *node, uint size)

{

    node->size = size;

    insert_free_size(cmem, node);

    insert_free_loc(cmem, node);

}

static void remove_free_loc(gs_memory_chunk_t *cmem, chunk_free_node_t *node)

{

    chunk_free_node_t **ap = &cmem->free_loc;

    while (*ap != node)

    {

        if (*ap > node)

            ap = &(*ap)->left_loc;

        else

            ap = &(*ap)->right_loc;

    }

    if (node->left_loc == NULL)

        *ap = node->right_loc;

    else if (node->right_loc == NULL)

        *ap = node->left_loc;

    else {

        /* Find the in-order predecessor to node and use that to replace node */

        chunk_free_node_t **bp;

        chunk_free_node_t  *b;

        bp = &node->left_loc;

        while ((*bp)->right_loc)

            bp = &(*bp)->right_loc;

        b = (*bp);

        *bp = b->left_loc;

        b->left_loc = node->left_loc;

        b->right_loc = node->right_loc;

        *ap = b;

    }

}

static void remove_free_size(gs_memory_chunk_t *cmem, chunk_free_node_t *node)

{

    chunk_free_node_t **ap = &cmem->free_size;

    while (*ap != node)

    {

        if (CMP_SIZE(*ap, node))

            ap = &(*ap)->left_size;

        else

            ap = &(*ap)->right_size;

    }

    if (node->left_size == NULL)

        *ap = node->right_size;

    else if (node->right_size == NULL)

        *ap = node->left_size;

    else {

        /* Find the in-order predecessor to node and use that to replace node */

        chunk_free_node_t **bp;

        chunk_free_node_t  *b;

        bp = &node->left_size;

        while ((*bp)->right_size)

            bp = &(*bp)->right_size;

        b = (*bp);

        *bp = b->left_size;

        b->left_size = node->left_size;

        b->right_size = node->right_size;

        *ap = b;

    }

}

static void remove_free_size_fast(gs_memory_chunk_t *cmem, chunk_free_node_t **ap)

{

    chunk_free_node_t *node = *ap;

    if (node->left_size == NULL)

        *ap = node->right_size;

    else if (node->right_size == NULL)

        *ap = node->left_size;

    else {

        /* Find the in-order predecessor to node and use that to replace node */

        chunk_free_node_t **bp;

        chunk_free_node_t  *b;

        bp = &node->left_size;

        while ((*bp)->right_size)

            bp = &(*bp)->right_size;

        b = (*bp);

        *bp = b->left_size;

        b->left_size = node->left_size;

        b->right_size = node->right_size;

        *ap = b;

    }

}

static void remove_free(gs_memory_chunk_t *cmem, chunk_free_node_t *node)

{

    remove_free_loc(cmem, node);

    remove_free_size(cmem, node);

}

#if defined(MEMENTO) || defined(SINGLE_OBJECT_MEMORY_BLOCKS_ONLY)

#define SINGLE_OBJECT_CHUNK(size) (1)

#else

#define SINGLE_OBJECT_CHUNK(size) ((size) > (CHUNK_SIZE>>1))

#endif

/* All of the allocation routines reduce to this function */

static byte *

chunk_obj_alloc(gs_memory_t *mem, size_t size, gs_memory_type_ptr_t type, client_name_t cname)

{

    gs_memory_chunk_t  *cmem = (gs_memory_chunk_t *)mem;

    chunk_free_node_t **ap, **okp;

    chunk_free_node_t  *a, *b, *c;

    size_t newsize;

    chunk_obj_node_t *obj = NULL;

    newsize = round_up_to_align(size + SIZEOF_ROUND_ALIGN(chunk_obj_node_t));  /* space we will need */

    /* When we free this block it might have to go in free - so it had

     * better be large enough to accommodate a complete free node! */

    if (newsize < SIZEOF_ROUND_ALIGN(chunk_free_node_t))

        newsize = SIZEOF_ROUND_ALIGN(chunk_free_node_t);

    /* Protect against overflow */

    if (newsize < size)

        return NULL;

#ifdef DEBUG_SEQ

    cmem->sequence++;

#endif

#ifdef DEBUG_CHUNK_PRINT

#ifdef DEBUG_SEQ

    dmlprintf4(mem, "Event %x: malloc(chunk="PRI_INTPTR", size=%"PRIxSIZE", cname=%s)\n",

               cmem->sequence, (intptr_t)cmem, newsize, cname);

#else

    dmlprintf3(mem, "malloc(chunk="PRI_INTPTR", size=%"PRIxSIZE", cname=%s)\n",

               (intptr_t)cmem, newsize, cname);

#endif

#endif

    /* Large blocks are allocated directly */

    if (SINGLE_OBJECT_CHUNK(newsize)) {

        obj = (chunk_obj_node_t *)gs_alloc_bytes_immovable(cmem->target, newsize, cname);

        if (obj == NULL)

            return NULL;

    } else {

        /* Find the smallest free block that's large enough */

        /* okp points to the parent pointer to the block we pick */

        ap = &cmem->free_size;

        okp = NULL;

        while ((a = *ap) != NULL) {

            if (a->size >= newsize) {

                b = a->left_size;

                if (b == NULL) {

                    okp = ap; /* a will do */

                    break; /* Stop searching */

                }

                if (b->size >= newsize) {

                    c = b->left_size;

                    if (c == NULL) {

                        okp = &a->left_size; /* b is as good as we're going to get */

                        break;

                    }

                    /* Splay:        a             c

                     *            b     Z   =>  W     b

                     *          c   Y               X   a

                     *         W X                     Y Z

                     */

                    *ap = c;

                    a->left_size  = b->right_size;

                    b->left_size  = c->right_size;

                    b->right_size = a;

                    c->right_size = b;

                    if (c->size >= newsize) {

                        okp = ap; /* c is the best so far */

                        ap = &c->left_size;

                    } else {

                        okp = &c->right_size; /* b is the best so far */

                        ap = &b->left_size;

                    }

                } else {

                    c = b->right_size;

                    if (c == NULL) {

                        okp = ap; /* a is as good as we are going to get */

                        break;

                    }

                    /* Splay:         a             c

                     *            b       Z  =>   b   a

                     *          W   c            W X Y Z

                     *             X Y

                     */

                    *ap = c;

                    a->left_size  = c->right_size;

                    b->right_size = c->left_size;

                    c->left_size  = b;

                    c->right_size = a;

                    if (c->size >= newsize) {

                        okp = ap; /* c is the best so far */

                        ap = &b->right_size;

                    } else {

                        okp = &c->right_size; /* a is the best so far */

                        ap = &a->left_size;

                    }

                }

            } else {

                b = a->right_size;

                if (b == NULL)

                    break; /* No better match to be found */

                if (b->size >= newsize) {

                    c = b->left_size;

                    if (c == NULL) {

                        okp = &a->right_size; /* b is as good as we're going to get */

                        break;

                    }

                    /* Splay:      a                c

                     *         W       b    =>    a   b

                     *               c   Z       W X Y Z

                     *              X Y

                     */

                    *ap = c;

                    a->right_size = c->left_size;

                    b->left_size  = c->right_size;

                    c->left_size  = a;

                    c->right_size = b;

                    if (c->size >= newsize) {

                        okp = ap; /* c is the best so far */

                        ap = &a->right_size;

                    } else {

                        okp = &c->right_size; /* b is the best so far */

                        ap = &b->left_size;

                    }

                } else {

                    c = b->right_size;

                    if (c == NULL)

                        break; /* No better match to be found */

                    /* Splay:    a                   c

                     *        W     b      =>     b     Z

                     *            X   c         a   Y

                     *               Y Z       W X

                     */

                    *ap = c;

                    a->right_size = b->left_size;

                    b->right_size = c->left_size;

                    b->left_size  = a;

                    c->left_size  = b;

                    if (c->size >= newsize) {

                        okp = ap; /* c is the best so far */

                        ap = &b->right_size;

                    } else

                        ap = &c->right_size;

                }

            }

        }

        /* So *okp points to the most appropriate free tree entry. */

        if (okp == NULL) {

            /* No appropriate free space slot. We need to allocate a new slab. */

            chunk_slab_t *slab;

            uint slab_size = newsize + SIZEOF_ROUND_ALIGN(chunk_slab_t);

            if (slab_size <= (CHUNK_SIZE>>1))

                slab_size = CHUNK_SIZE;

            slab = (chunk_slab_t *)gs_alloc_bytes_immovable(cmem->target, slab_size, cname);

            if (slab == NULL)

                return NULL;

            slab->next = cmem->slabs;

            cmem->slabs = slab;

            obj = (chunk_obj_node_t *)(((byte *)slab) + SIZEOF_ROUND_ALIGN(chunk_slab_t));

            if (slab_size != newsize + SIZEOF_ROUND_ALIGN(chunk_slab_t)) {

                insert_free(cmem, (chunk_free_node_t *)(((byte *)obj)+newsize), slab_size - newsize - SIZEOF_ROUND_ALIGN(chunk_slab_t));

                cmem->total_free += slab_size - newsize - SIZEOF_ROUND_ALIGN(chunk_slab_t);

            }

        } else {

            chunk_free_node_t *ok = *okp;

            obj = (chunk_obj_node_t *)(void *)ok;

            if (ok->size >= newsize + SIZEOF_ROUND_ALIGN(chunk_free_node_t)) {

                chunk_free_node_t *tail = (chunk_free_node_t *)(((byte *)ok) + newsize);

                uint tail_size = ok->size - newsize;

                remove_free_size_fast(cmem, okp);

                remove_free_loc(cmem, ok);

                insert_free(cmem, tail, tail_size);

            } else {

                newsize = ok->size;

                remove_free_size_fast(cmem, okp);

                remove_free_loc(cmem, ok);

            }

            cmem->total_free -= newsize;

        }

    }

    if (gs_alloc_debug) {

        memset((byte *)(obj) + SIZEOF_ROUND_ALIGN(chunk_obj_node_t), 0xa1, newsize - SIZEOF_ROUND_ALIGN(chunk_obj_node_t));

        memset((byte *)(obj) + SIZEOF_ROUND_ALIGN(chunk_obj_node_t), 0xac, size);

    }

    cmem->used += newsize;

    obj->size = newsize; /* actual size */

    obj->padding = newsize - size; /* actual size - client requested size */

    obj->type = type;    /* and client desired type */

    obj->defer_next = NULL;

#ifdef DEBUG_SEQ

    obj->sequence = cmem->sequence;

#endif

    if (gs_debug_c('A'))

        dmlprintf3(mem, "[a+]chunk_obj_alloc (%s)(%"PRIuSIZE") = "PRI_INTPTR": OK.\n",

                   client_name_string(cname), size, (intptr_t) obj);

#ifdef DEBUG_CHUNK_PRINT

#ifdef DEBUG_SEQ

    dmlprintf5(mem, "Event %x: malloced(chunk="PRI_INTPTR", addr="PRI_INTPTR", size=%"PRIxSIZE", cname=%s)\n",

               obj->sequence, (intptr_t)cmem, (intptr_t)obj, obj->size, cname);

#else

    dmlprintf4(mem, "malloced(chunk="PRI_INTPTR", addr="PRI_INTPTR", size=%"PRIxSIZE", cname=%s)\n",

               (intptr_t)cmem, (intptr_t)obj, obj->size, cname);

#endif

#endif

#ifdef DEBUG_CHUNK

    gs_memory_chunk_dump_memory(cmem);

#endif

    return (byte *)Memento_label((byte *)(obj) + SIZEOF_ROUND_ALIGN(chunk_obj_node_t), cname);

}

static byte *

chunk_alloc_bytes_immovable(gs_memory_t * mem, size_t size, client_name_t cname)

{

    return chunk_obj_alloc(mem, size, &st_bytes, cname);

}

static byte *

chunk_alloc_bytes(gs_memory_t * mem, size_t size, client_name_t cname)

{

    return chunk_obj_alloc(mem, size, &st_bytes, cname);

}

static void *

chunk_alloc_struct_immovable(gs_memory_t * mem, gs_memory_type_ptr_t pstype,

                             client_name_t cname)

{

    return chunk_obj_alloc(mem, pstype->ssize, pstype, cname);

}

static void *

chunk_alloc_struct(gs_memory_t * mem, gs_memory_type_ptr_t pstype,

                   client_name_t cname)

{

    return chunk_obj_alloc(mem, pstype->ssize, pstype, cname);

}

static byte *

chunk_alloc_byte_array_immovable(gs_memory_t * mem, size_t num_elements,

                                 size_t elt_size, client_name_t cname)

{

    return chunk_alloc_bytes(mem, num_elements * elt_size, cname);

}

static byte *

chunk_alloc_byte_array(gs_memory_t * mem, size_t num_elements, size_t elt_size,

                   client_name_t cname)

{

    return chunk_alloc_bytes(mem, num_elements * elt_size, cname);

}

static void *

chunk_alloc_struct_array_immovable(gs_memory_t * mem, size_t num_elements,

                                   gs_memory_type_ptr_t pstype, client_name_t cname)

{

    return chunk_obj_alloc(mem, num_elements * pstype->ssize, pstype, cname);

}

static void *

chunk_alloc_struct_array(gs_memory_t * mem, size_t num_elements,

                         gs_memory_type_ptr_t pstype, client_name_t cname)

{

    return chunk_obj_alloc(mem, num_elements * pstype->ssize, pstype, cname);

}

static void *

chunk_resize_object(gs_memory_t * mem, void *ptr, size_t new_num_elements, client_name_t cname)

{

    void *new_ptr = NULL;

    if (ptr != NULL) {

        /* This isn't particularly efficient, but it is rarely used */

        chunk_obj_node_t *obj = (chunk_obj_node_t *)(((byte *)ptr) - SIZEOF_ROUND_ALIGN(chunk_obj_node_t));

        size_t new_size = (obj->type->ssize * new_num_elements);

        size_t old_size = obj->size - obj->padding;

        /* get the type from the old object */

        gs_memory_type_ptr_t type = obj->type;

        gs_memory_chunk_t *cmem = (gs_memory_chunk_t *)mem;

        size_t save_max_used = cmem->max_used;

        if (new_size == old_size)

            return ptr;

        if ((new_ptr = chunk_obj_alloc(mem, new_size, type, cname)) == 0)

            return NULL;