home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1996 February / PCWK0296.iso / sharewar / dos / program / gs300sr1 / gs300sr1.exe / ISTACK.C < prev    next >
C/C++ Source or Header  |  1994-07-27  |  15KB  |  468 lines
  1. /* Copyright (C) 1992, 1993, 1994 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* istack.c */
  20. /* Ghostscript expandable stack manager */
  21. #include "memory_.h"
  22. #include "ghost.h"
  23. #include "gsstruct.h"
  24. #include "gsutil.h"
  25. #include "errors.h"
  26. #include "ialloc.h"
  27. #include "istack.h"
  28. #include "istruct.h"        /* for gs_reloc_refs */
  29. #include "iutil.h"
  30. #include "ivmspace.h"        /* for local/global test */
  31. #include "store.h"
  32.  
  33. /* Forward references */
  34. private void init_block(P3(ref_stack *, ref *, uint));
  35.  
  36. /* GC procedures */
  37. #define sptr ((ref_stack *)vptr)
  38. private CLEAR_MARKS_PROC(ref_stack_clear_marks) {
  39.     r_clear_attrs(&sptr->current, l_mark);
  40. }
  41. private ENUM_PTRS_BEGIN(ref_stack_enum_ptrs) return 0;
  42.     case 0:
  43.         *pep = &sptr->current;
  44.         return ptr_ref_type;
  45. ENUM_PTRS_END
  46. private RELOC_PTRS_BEGIN(ref_stack_reloc_ptrs) {
  47. #if stacks_are_segmented
  48.     /* In a segmented environment, the top block can't move, */
  49.     /* so we don't need to relocate pointers to it. */
  50. #else
  51.     /* Note that the relocation must be a multiple of sizeof(ref_packed) */
  52.     /* * align_packed_per_ref, but it need not be a multiple of */
  53.     /* sizeof(ref).  Therefore, we must do the adjustments using */
  54.     /* ref_packed pointers rather than ref pointers. */
  55.     ref_packed *bot = (ref_packed *)sptr->current.value.refs;
  56.     uint reloc;
  57.     gs_reloc_refs((ref_packed *)&sptr->current,
  58.               (ref_packed *)(&sptr->current + 1),
  59.               gcst);
  60.     r_clear_attrs(&sptr->current, l_mark);
  61.     reloc = bot - (ref_packed *)sptr->current.value.refs;
  62. #define reloc_p(p)\
  63.   sptr->p = (ref *)((ref_packed *)sptr->p - reloc);
  64.     reloc_p(p);
  65.     reloc_p(bot);
  66.     reloc_p(top);
  67. #undef reloc_p
  68. #endif
  69. } RELOC_PTRS_END
  70. /* Structure type for a ref_stack. */
  71. public_st_ref_stack();
  72.  
  73. /* Initialize a stack. */
  74. void
  75. ref_stack_init(register ref_stack *pstack, ref *psb,
  76.   uint bot_guard, uint top_guard, ref *pguard, gs_ref_memory_t *mem)
  77. {    uint size = r_size(psb);
  78.     uint avail = size - (stack_block_refs + bot_guard + top_guard);
  79.     ref_stack_block *pblock = (ref_stack_block *)psb->value.refs;
  80.     s_ptr body = (s_ptr)(pblock + 1);
  81.     pstack->bot = body + bot_guard;
  82.     pstack->p = pstack->bot - 1;
  83.     pstack->top = pstack->p + avail;
  84.     pstack->current = *psb;
  85.     pstack->extension_size = 0;
  86.     pstack->extension_used = 0;
  87.  
  88.     make_int(&pstack->max_stack, avail);
  89.     pstack->requested = 0;
  90.  
  91.     pstack->bot_guard = bot_guard;
  92.     pstack->top_guard = top_guard;
  93.     pstack->block_size = size - segmented_guard(bot_guard + top_guard);
  94.     pstack->body_size = avail;
  95.     if ( pguard != 0 )
  96.       pstack->guard_value = *pguard;
  97.     else
  98.       make_tav(&pstack->guard_value, t__invalid, 0, intval, 0);
  99.     pstack->underflow_error = -1;        /* bogus, caller must set */
  100.     pstack->overflow_error = -1;        /* bogus, caller must set */
  101.     pstack->memory = mem;
  102.     init_block(pstack, psb, 0);
  103.     refset_null(pstack->bot, avail);
  104.     make_array(&pblock->next, 0, 0, NULL);
  105. }
  106.  
  107. /* Set the maximum number of elements allowed on a stack. */
  108. int
  109. ref_stack_set_max_count(ref_stack *pstack, long nmax)
  110. {    uint nmin = pstack->extension_size + (pstack->top - pstack->bot + 1);
  111.     if ( nmax < nmin )
  112.       nmax = nmin;
  113.     if ( nmax > max_uint / sizeof(ref) )
  114.       nmax = max_uint / sizeof(ref);
  115.     pstack->max_stack.value.intval = nmax;
  116.     return 0;
  117. }
  118.  
  119. /* Return the number of elements on a stack. */
  120. uint
  121. ref_stack_count(const ref_stack *pstack)
  122. {    return pstack->extension_used + (pstack->p - pstack->bot + 1);
  123. }
  124.  
  125. /* Retrieve a given element from the stack, counting from */
  126. /* 0 as the top element. */
  127. ref *
  128. ref_stack_index(const ref_stack *pstack, long idx)
  129. {    ref_stack_block *pblock;
  130.     uint used = pstack->p + 1 - pstack->bot;
  131.     if ( idx < 0 )
  132.         return NULL;
  133.     if ( idx < used )        /* common case */
  134.         return pstack->p - (uint)idx;
  135.     pblock = (ref_stack_block *)pstack->current.value.refs;
  136.     do
  137.     {    pblock = (ref_stack_block *)pblock->next.value.refs;
  138.         if ( pblock == 0 )
  139.             return NULL;
  140.         idx -= used;
  141.         used = r_size(&pblock->used);
  142.     }
  143.     while ( idx >= used );
  144.     return pblock->used.value.refs + (used - 1 - (uint)idx);
  145. }
  146.  
  147. /* Count the number of elements down to and including the first mark. */
  148. /* If no mark is found, return 0. */
  149. uint
  150. ref_stack_counttomark(const ref_stack *pstack)
  151. {    uint scanned = 0;
  152.     STACK_LOOP_BEGIN(pstack, p, used)
  153.     {    uint count = used;
  154.         p += used - 1;
  155.         for ( ; count; count--, p-- )
  156.           if ( r_has_type(p, t_mark) )
  157.             return scanned + (used - count + 1);
  158.         scanned += used;
  159.     }
  160.     STACK_LOOP_END(p, used)
  161.     return 0;
  162. }
  163.  
  164. /* Store the top elements of a stack into an array, */
  165. /* with or without store/undo checking. */
  166. /* May return e_rangecheck or e_invalidaccess. */
  167. int
  168. ref_stack_store(const ref_stack *pstack, ref *parray, uint count, uint skip,
  169.   int age, bool check, client_name_t cname)
  170. {    uint left, pass;
  171.     ref *to;
  172.     if ( count > ref_stack_count(pstack) || count > r_size(parray) )
  173.       return_error(e_rangecheck);
  174.     if ( check && r_is_global(parray) )
  175.       {    /* Pre-check the elements being stored. */
  176.         left = count, pass = skip;
  177.         STACK_LOOP_BEGIN(pstack, ptr, size)
  178.           if ( size <= pass )
  179.             pass -= size;
  180.           else
  181.             {    int code;
  182.             if ( pass != 0 )
  183.               size -= pass, pass = 0;
  184.             if ( size > left )
  185.               size = left;
  186.             left -= size;
  187.             code = refs_check_global(ptr, size);
  188.             if ( code < 0 )
  189.               return code;
  190.             if ( left == 0 )
  191.               break;
  192.             }
  193.         STACK_LOOP_END(ptr, size)
  194.       }
  195.     to = parray->value.refs + count;
  196.     left = count, pass = skip;
  197.     STACK_LOOP_BEGIN(pstack, from, size)
  198.       if ( size <= pass )
  199.         pass -= size;
  200.       else
  201.         { if ( pass != 0 )
  202.         size -= pass, pass = 0;
  203.           from += size;
  204.           if ( size > left )
  205.         size = left;
  206.           left -= size;
  207.           switch ( age )
  208.         {
  209.         case -1:    /* not an array */
  210.           while ( size-- )
  211.             { from--, to--;
  212.               ref_assign(to, from);
  213.             }
  214.           break;
  215.         case 0:        /* old array */
  216.           while ( size-- )
  217.             { from--, to--;
  218.               ref_assign_old(parray, to, from, cname);
  219.             }
  220.           break;
  221.         case 1:        /* new array */
  222.           while ( size-- )
  223.             { from--, to--;
  224.               ref_assign_new(to, from);
  225.             }
  226.           break;
  227.         }
  228.           if ( left == 0 )
  229.         break;
  230.         }
  231.     STACK_LOOP_END(from, size)
  232.     r_set_size(parray, count);
  233.     return 0;
  234. }
  235.  
  236. /* Pop a given number of elements off a stack. */
  237. /* The number must not exceed the number of elements in use. */
  238. void
  239. ref_stack_pop(register ref_stack *pstack, uint count)
  240. {    uint used;
  241.     while ( (used = pstack->p + 1 - pstack->bot) < count )
  242.     {    count -= used;
  243.         pstack->p = pstack->bot - 1;
  244.         ref_stack_pop_block(pstack);
  245.     }
  246.     pstack->p -= count;
  247. }
  248.  
  249. /* Pop the top block off a stack. */
  250. int
  251. ref_stack_pop_block(register ref_stack *pstack)
  252. {    s_ptr bot = pstack->bot;
  253.     uint count = pstack->p + 1 - bot;
  254.     ref_stack_block *pcur =
  255.       (ref_stack_block *)pstack->current.value.refs;
  256.     register ref_stack_block *pnext =
  257.       (ref_stack_block *)pcur->next.value.refs;
  258.     uint used;
  259.     ref *body;
  260.     ref next;
  261.     if ( pnext == 0 )
  262.       return_error(pstack->underflow_error);
  263.     used = r_size(&pnext->used);
  264.     body = (ref *)(pnext + 1) + flat_guard(pstack->bot_guard);
  265.     next = pcur->next;
  266.     /*
  267.      * If we're on a segmented system, the top block does not move,
  268.      * so we move up the used part of the top block, copy the contents
  269.      * of the next block under it, and free the next block.
  270.      * We also do this on non-segmented systems if the contents of the
  271.      * two blocks won't fit in a single block; in this case we copy up
  272.      * as much as will fit.  On non-segmented systems where the contents
  273.      * of both blocks fit in a single block, we copy the used part
  274.      * of the top block to the top of the next block, and free
  275.      * the top block.
  276.      */
  277.     if ( used + count > pstack->body_size )
  278.       {    /* Move as much into the top block as will fit. */
  279.         uint moved = pstack->body_size - count;
  280.         uint left;
  281.         if ( moved == 0 )
  282.           return_error(e_Fatal);
  283.         memmove(bot + moved, bot, count * sizeof(ref));
  284.         left = used - moved;
  285.         memcpy(bot, body + left, moved * sizeof(ref));
  286.         refset_null(body + left, moved);
  287.         r_dec_size(&pnext->used, moved);
  288.         pstack->p = pstack->top;
  289.         pstack->extension_used -= moved;
  290.       }
  291.     else
  292.       {
  293. #if stacks_are_segmented
  294.     /* We know there are no guard elements in the next block. */
  295.     memmove(bot + used, bot, count * sizeof(ref));
  296.     memcpy(bot, body, used * sizeof(ref));
  297.     pcur->next = pnext->next;
  298.     gs_free_ref_array(pstack->memory, &next, "ref_stack_pop_block");
  299. #else
  300.     memcpy(body + used, bot, count * sizeof(ref));
  301.     pstack->bot = bot = body;
  302.     pstack->top = bot + pstack->body_size - 1;
  303.     gs_free_ref_array(pstack->memory, &pstack->current,
  304.               "ref_stack_pop_block");
  305.     pstack->current = next;
  306. #endif
  307.     pstack->p = bot + (used + count - 1);
  308.     pstack->extension_size -= pstack->body_size;
  309.     pstack->extension_used -= used;
  310.       }
  311.     return 0;
  312. }
  313.  
  314. /* Extend a stack to recover from an overflow condition. */
  315. /* May return overflow_error or e_VMerror. */
  316. int
  317. ref_stack_extend(ref_stack *pstack, uint request)
  318. {    uint keep = (pstack->top - pstack->bot + 1) / 3;
  319.     if ( pstack->p < pstack->bot )
  320.       {    /* Adding another block can't help things. */
  321.         return_error(pstack->overflow_error);
  322.       }
  323.     if ( keep + request > pstack->body_size )
  324.       keep = pstack->body_size - request;
  325.     return ref_stack_push_block(pstack, keep);
  326. }
  327.  
  328. /* Push N empty slots onto a stack.  These slots are not initialized; */
  329. /* the caller must fill them immediately.  May return overflow_error */
  330. /* (if max_stack would be exceeded, or the stack has no allocator) */
  331. /* or e_VMerror. */
  332. int
  333. ref_stack_push(register ref_stack *pstack, uint count)
  334. {    /* Don't bother to pre-check for overflow: we must be able to */
  335.     /* back out in the case of a VMerror anyway, and */
  336.     /* ref_stack_push_block will make the check itself. */
  337.     uint needed = count;
  338.     uint added;
  339.     for ( ; (added = pstack->top - pstack->p) < needed; needed -= added )
  340.       {    int code;
  341.         pstack->p = pstack->top;
  342.         code =
  343.           ref_stack_push_block(pstack,
  344.                        (pstack->top - pstack->bot + 1) / 3);
  345.         if ( code < 0 )
  346.           {    /* Back out. */
  347.             ref_stack_pop(pstack, count - needed);
  348.             pstack->requested = count;
  349.             return code;
  350.           }
  351.       }
  352.     pstack->p += needed;
  353.     return 0;
  354. }
  355.  
  356. /* Push a block onto the stack, specifying how many elements of */
  357. /* the current top block should remain in the top block. */
  358. /* Must have keep <= count. */
  359. int
  360. ref_stack_push_block(register ref_stack *pstack, uint keep)
  361. {    uint count = pstack->p - pstack->bot + 1;
  362.     uint move = count - keep;
  363.     ref_stack_block *pcur = (ref_stack_block *)pstack->current.value.refs;
  364.     ref next;
  365.     ref_stack_block *pnext;
  366.     ref *body;
  367.     int code;
  368.     if ( keep > count )
  369.       return_error(e_Fatal);
  370.     /* Check for overflowing the maximum size. */
  371.     if ( pstack->memory == 0 ||
  372.          pstack->extension_used + (pstack->top - pstack->bot) >=
  373.            pstack->max_stack.value.intval
  374.        )
  375.       return_error(pstack->overflow_error);
  376.     code = gs_alloc_ref_array(pstack->memory, &next, 0,
  377.                   pstack->block_size, "ref_stack_push_block");
  378.     if ( code < 0 )
  379.       return code;
  380.     pnext = (ref_stack_block *)next.value.refs;
  381.     body = (ref *)(pnext + 1);
  382. #if stacks_are_segmented
  383.     /* Copy all but the top keep elements into the new block, */
  384.     /* and move the top elements down. */
  385.     /* We know there are no guard elements in the new block. */
  386.     memcpy(body, pstack->bot, move * sizeof(ref));
  387.     /* Clear the elements above the top of the new block. */
  388.     refset_null(body + move, pstack->body_size - move);
  389.     if ( keep <= move )
  390.     {    /* No overlap, memcpy is safe. */
  391.         memcpy(pstack->bot, pstack->bot + move, keep * sizeof(ref));
  392.     }
  393.     else
  394.     {    uint i;
  395.         s_ptr bot = pstack->bot;
  396.         s_ptr up = bot + move;
  397.         for ( i = 0; i < keep; i++ )
  398.             bot[i] = up[i];
  399.     }
  400.     pnext->next = pcur->next;
  401.     pnext->used = next;
  402.     pcur->next = next;
  403.     pnext->used.value.refs = body;
  404.     r_set_size(&pnext->used, move);
  405. #else
  406.     /* Copy the top keep elements into the new block, */
  407.     /* and make the new block the top block. */
  408.     init_block(pstack, &next, keep);
  409.     body += pstack->bot_guard;
  410.     memcpy(body, pstack->bot + move, keep * sizeof(ref));
  411.     /* Clear the elements above the top of the new block. */
  412.     refset_null(body + keep, pstack->body_size - keep);
  413.     /* Clear the elements above the top of the old block. */
  414.     refset_null(pstack->bot + move, keep);
  415.     pnext->next = pstack->current;
  416.     pcur->used.value.refs = pstack->bot;
  417.     r_set_size(&pcur->used, move);
  418.     pstack->current = next;
  419.     pstack->bot = body;
  420.     pstack->top = pstack->bot + pstack->body_size - 1;
  421. #endif
  422.     pstack->p = pstack->bot + keep - 1;
  423.     pstack->extension_size += pstack->body_size;
  424.     pstack->extension_used += move;
  425.     return 0;
  426. }
  427.  
  428. /* Clean up a stack for garbage collection. */
  429. void
  430. ref_stack_cleanup(ref_stack *pstack)
  431. {    ref_stack_block *pblock =
  432.       (ref_stack_block *)pstack->current.value.refs;
  433.     refset_null(pstack->p + 1, pstack->top - pstack->p);
  434.     pblock->used = pstack->current;        /* set attrs */
  435.     pblock->used.value.refs = pstack->bot;
  436.     r_set_size(&pblock->used, pstack->p + 1 - pstack->bot);
  437. }
  438.  
  439. /* ------ Internal routines ------ */
  440.  
  441. /* Initialize the guards and body of a stack block. */
  442. /* Note that this always initializes the guards, so it should not be used */
  443. /* for extension blocks in a segmented environments. */
  444. private void
  445. init_block(ref_stack *pstack, ref *psb, uint used)
  446. {    ref *brefs = psb->value.refs;
  447. #define pblock ((ref_stack_block *)brefs)
  448.     register uint i;
  449.     register ref *p;
  450.     for ( i = pstack->bot_guard, p = brefs + stack_block_refs;
  451.           i != 0; i--, p++
  452.         )
  453.         ref_assign(p, &pstack->guard_value);
  454.     /* The top guard elements will never be read, */
  455.     /* but we need to initialize them for the sake of the GC. */
  456.     /* We can use refset_null for this, because even though it uses */
  457.     /* make_null_new and stack elements must not be marked new, */
  458.     /* these slots will never actually be read or written. */
  459.     if ( pstack->top_guard )
  460.       {    ref *top = brefs + r_size(psb);
  461.         int top_guard = pstack->top_guard;
  462.         refset_null(top - top_guard, top_guard);
  463.       }
  464.     pblock->used = *psb;
  465.     pblock->used.value.refs = brefs + stack_block_refs + pstack->bot_guard;
  466.     r_set_size(&pblock->used, 0);
  467. }
  468.