home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / historic / v92.tgz / v92.tar / v92 / src / runtime / rstruct.r < prev    next >
Text File  |  1996-03-22  |  14KB  |  491 lines
  1. /*
  2.  * File: rstruct.r
  3.  *  Contents: addmem, cplist, cpset, hmake, hchain, hfirst, hnext, hgrow,
  4.  *  hshrink, memb
  5.  */
  6.  
  7. /*
  8.  * addmem - add a new set element block in the correct spot in
  9.  *  the bucket chain.
  10.  */
  11.  
  12. novalue addmem(ps,pe,pl)
  13. union block **pl;
  14. struct b_set *ps;
  15. struct b_selem *pe;
  16.    {
  17.    ps->size++;
  18.    if (*pl != NULL )
  19.       pe->clink = *pl;
  20.    *pl = (union block *) pe;
  21.    }
  22.  
  23. /*
  24.  * cpslots(dp1, slotptr, i, j) - copy elements of sublist dp1[i:j]
  25.  *  into an array of descriptors.
  26.  */
  27.  
  28. novalue cpslots(dp1, slotptr, i, j)
  29. dptr dp1, slotptr;
  30. word i, j;
  31.    {
  32.    word size;
  33.    tended struct b_list *lp1;
  34.    tended struct b_lelem *bp1;
  35.    /*
  36.     * Get pointers to the list and list elements for the source list
  37.     *  (bp1, lp1).
  38.     */
  39.    lp1 = (struct b_list *) BlkLoc(*dp1);
  40.    bp1 = (struct b_lelem *) lp1->listhead;
  41.    size = j - i;
  42.  
  43.    /*
  44.     * Locate the block containing element i in the source list.
  45.     */
  46.    if (size > 0) {
  47.       while (i > bp1->nused) {
  48.          i -= bp1->nused;
  49.          bp1 = (struct b_lelem *) bp1->listnext;
  50.          }
  51.       }
  52.  
  53.    /*
  54.     * Copy elements from the source list into the sublist, moving to
  55.     *  the next list block in the source list when all elements in a
  56.     *  block have been copied.
  57.     */
  58.    while (size > 0) {
  59.       j = bp1->first + i - 1;
  60.       if (j >= bp1->nslots)
  61.          j -= bp1->nslots;
  62.       *slotptr++ = bp1->lslots[j];
  63.       if (++i > bp1->nused) {
  64.          i = 1;
  65.          bp1 = (struct b_lelem *) bp1->listnext;
  66.          }
  67.       size--;
  68.       }
  69.    }
  70.  
  71.  
  72. /*
  73.  * cplist(dp1,dp2,i,j) - copy sublist dp1[i:j] into dp2.
  74.  */
  75.  
  76. int cplist(dp1, dp2, i, j)
  77. dptr dp1, dp2;
  78. word i, j;
  79.    {
  80.    word size, nslots;
  81.    tended struct b_list *lp2;
  82.    tended struct b_lelem *bp2;
  83.  
  84.    /*
  85.     * Calculate the size of the sublist.
  86.     */
  87.    size = nslots = j - i;
  88.    if (nslots == 0)
  89.       nslots = MinListSlots;
  90.  
  91.    Protect(lp2 = (struct b_list *) alclist(size), return Error);
  92.    Protect(bp2 = (struct b_lelem *)alclstb(nslots,(word)0,size), return Error);
  93.    lp2->listhead = lp2->listtail = (union block *) bp2;
  94.  
  95.    cpslots(dp1, bp2->lslots, i, j);
  96.  
  97.    /*
  98.     * Fix type and location fields for the new list.
  99.     */
  100.    dp2->dword = D_List;
  101.    BlkLoc(*dp2) = (union block *) lp2;
  102.    EVValD(dp2, E_Lcreate);
  103.    return Succeeded;
  104.    }
  105.  
  106. /*
  107.  * cpset(dp1,dp2,n) - copy set dp1 to dp2, reserving memory for n entries.
  108.  */
  109. int cpset(dp1, dp2, n)
  110. dptr dp1, dp2;
  111. word n;
  112.    {
  113.    union block *src;
  114.    tended union block *dst;
  115.    tended struct b_slots *seg;
  116.    tended struct b_selem *ep, *prev;
  117.    struct b_selem *se;
  118.    register word slotnum;
  119.    register int i;
  120.  
  121.    /*
  122.     * Make a new set organized like dp1, with room for n elements.
  123.     */
  124.    dst = hmake(T_Set, BlkLoc(*dp1)->set.mask + 1, n);
  125.    if (dst == NULL)
  126.       return Error;
  127.    /*
  128.     * Copy the header and slot blocks.
  129.     */
  130.    src = BlkLoc(*dp1);
  131.    dst->set.size = src->set.size;    /* actual set size */
  132.    dst->set.mask = src->set.mask;    /* hash mask */
  133.    for (i = 0; i < HSegs && src->set.hdir[i] != NULL; i++)
  134.       memcopy((char *)dst->set.hdir[i], (char *)src->set.hdir[i],
  135.          src->set.hdir[i]->blksize);
  136.    /*
  137.     * Work down the chain of element blocks in each bucket
  138.     *    and create identical chains in new set.
  139.     */
  140.    for (i = 0; i < HSegs && (seg = dst->set.hdir[i]) != NULL; i++)
  141.       for (slotnum = segsize[i] - 1; slotnum >= 0; slotnum--)  {
  142.      prev = NULL;
  143.          for (ep = (struct b_selem *)seg->hslots[slotnum];
  144.            ep != NULL; ep = (struct b_selem *)ep->clink) {
  145.             Protect(se = alcselem(&ep->setmem, ep->hashnum), return Error);
  146.         if (prev == NULL)
  147.         seg->hslots[slotnum] = (union block *)se;
  148.         else
  149.         prev->clink = (union block *)se;
  150.             se->clink = ep->clink;
  151.         prev = se;
  152.             }
  153.          }
  154.    dp2->dword = D_Set;
  155.    BlkLoc(*dp2) = dst;
  156.    if (TooSparse(dst))
  157.       hshrink(dst);
  158.    return Succeeded;
  159.    }
  160.  
  161. /*
  162.  * hmake - make a hash structure (Set or Table) with a given number of slots.
  163.  *  If *nslots* is zero, a value appropriate for *nelem* elements is chosen.
  164.  *  A return of NULL indicates allocation failure.
  165.  */
  166. union block *hmake(tcode, nslots, nelem)
  167. int tcode;
  168. word nslots, nelem;
  169.    {
  170.    word seg, t, blksize, elemsize;
  171.    tended union block *blk;
  172.    struct b_slots *segp;
  173.  
  174.    if (nslots == 0)
  175.       nslots = (nelem + MaxHLoad - 1) / MaxHLoad;
  176.    for (seg = t = 0; seg < (HSegs - 1) && (t += segsize[seg]) < nslots; seg++)
  177.       ;
  178.    nslots = ((word)HSlots) << seg;    /* ensure legal power of 2 */
  179.    if (tcode == T_Table) {
  180.       blksize = sizeof(struct b_table);
  181.       elemsize = sizeof(struct b_telem);
  182.       }
  183.    else {    /* T_Set */
  184.       blksize = sizeof(struct b_set);
  185.       elemsize = sizeof(struct b_selem);
  186.       }
  187.    if (!reserve(Blocks, (word)(blksize + (seg + 1) * sizeof(struct b_slots)
  188.       + (nslots - HSlots * (seg + 1)) * sizeof(union block *)
  189.       + nelem * elemsize))) return NULL;
  190.    Protect(blk = alchash(tcode), return NULL);
  191.    for (; seg >= 0; seg--) {
  192.       Protect(segp = alcsegment(segsize[seg]), return NULL);
  193.       blk->set.hdir[seg] = segp;
  194.       }
  195.    blk->set.mask = nslots - 1;
  196.    return blk;
  197.    }
  198.  
  199. /*
  200.  * hchain - return a pointer to the word that points to the head of the hash
  201.  *  chain for hash number hn in hashed structure s.
  202.  */
  203.  
  204. /*
  205.  * lookup table for log to base 2; must have powers of 2 through (HSegs-1)/2.
  206.  */
  207. static unsigned char log2h[] = {
  208.    0,1,2,2, 3,3,3,3, 4,4,4,4, 4,4,4,4, 5,5,5,5, 5,5,5,5, 5,5,5,5, 5,5,5,5,
  209.    };
  210.  
  211. union block **hchain(pb, hn)
  212. union block *pb;
  213. register uword hn;
  214.    {
  215.    register struct b_set *ps;
  216.    register word slotnum, segnum, segslot;
  217.  
  218.    ps = (struct b_set *)pb;
  219.    slotnum = hn & ps->mask;
  220.    if (slotnum >= HSlots * sizeof(log2h))
  221.       segnum = log2h[slotnum >> (LogHSlots + HSegs/2)] + HSegs/2;
  222.    else
  223.       segnum = log2h[slotnum >> LogHSlots];
  224.    segslot = hn & (segsize[segnum] - 1);
  225.    return &ps->hdir[segnum]->hslots[segslot];
  226.    }
  227.  
  228. /*
  229.  * hgfirst - initialize for generating set or table, and return first element.
  230.  */
  231.  
  232. union block *hgfirst(bp, s)
  233. union block *bp;
  234. struct hgstate *s;
  235.    {
  236.    int i;
  237.  
  238.    s->segnum = 0;                /* set initial state */
  239.    s->slotnum = -1;
  240.    s->tmask = bp->table.mask;
  241.    for (i = 0; i < HSegs; i++)
  242.       s->sghash[i] = s->sgmask[i] = 0;
  243.    return hgnext(bp, s, (union block *)0);    /* get and return first value */
  244.    }
  245.  
  246. /*
  247.  * hgnext - return the next element of a set or table generation sequence.
  248.  *
  249.  *  We carefully generate each element exactly once, even if the hash chains
  250.  *  are split between calls.  We do this by recording the state of things at
  251.  *  the time of the split and checking past history when starting to process
  252.  *  a new chain.
  253.  *
  254.  *  Elements inserted or deleted between calls may or may not be generated. 
  255.  *
  256.  *  We assume that no structure *shrinks* after its initial creation; they
  257.  *  can only *grow*.
  258.  */
  259.  
  260. union block *hgnext(bp, s, ep)
  261. union block *bp;
  262. struct hgstate *s;
  263. union block *ep;
  264.    {
  265.    int i;
  266.    word d, m;
  267.    uword hn;
  268.  
  269.    /*
  270.     * Check to see if the set or table's hash buckets were split (once or
  271.     *  more) since the last call.  We notice this unless the next entry
  272.     *  has same hash value as the current one, in which case we defer it
  273.     *  by doing nothing now.
  274.     */
  275.    if (bp->table.mask != s->tmask &&
  276.       (ep->telem.clink == NULL ||
  277.       ep->telem.clink->telem.hashnum != ep->telem.hashnum)) {
  278.       /*
  279.        * Yes, they did split.  Make a note of the current state.
  280.        */
  281.       hn = ep->telem.hashnum;
  282.       for (i = 1; i < HSegs; i++)
  283.          if ((((word)HSlots) << (i - 1)) > s->tmask) {
  284.         /*
  285.          * For the newly created segments only, save the mask and
  286.          *  hash number being processed at time of creation.
  287.          */
  288.         s->sgmask[i] = s->tmask;
  289.         s->sghash[i] = hn;
  290.          }
  291.       s->tmask = bp->table.mask;
  292.       /*
  293.        * Find the next element in our original segment by starting
  294.        *  from the beginning and skipping through the current hash
  295.        *  number.  We can't just follow the link from the current
  296.        *  element, because it may have moved to a new segment.
  297.        */
  298.       ep = bp->table.hdir[s->segnum]->hslots[s->slotnum];
  299.       while (ep != NULL && ep->telem.hashnum <= hn)
  300.          ep = ep->telem.clink;
  301.       }
  302.  
  303.    else {
  304.       /*
  305.        * There was no split, or else if there was we're between items
  306.        *  that have identical hash numbers.  Find the next element in
  307.        *  the current hash chain.
  308.        */
  309.       if (ep != NULL)            /* already NULL on very first call */
  310.          ep = ep->telem.clink;        /* next element in chain, if any */
  311.    }
  312.  
  313.    /*
  314.     * If we don't yet have an element, search successive slots.
  315.     */
  316.    while (ep == NULL) {
  317.       /*
  318.        * Move to the next slot and pick the first entry.
  319.        */
  320.       s->slotnum++;
  321.       if (s->slotnum >= segsize[s->segnum]) {
  322.      s->slotnum = 0;        /* need to move to next segment */
  323.      s->segnum++;
  324.      if (s->segnum >= HSegs || bp->table.hdir[s->segnum] == NULL)
  325.         return 0;            /* return NULL at end of set/table */
  326.          }
  327.       ep = bp->table.hdir[s->segnum]->hslots[s->slotnum];
  328.       /*
  329.        * Check to see if parts of this hash chain were already processed.
  330.        *  This could happen if the elements were in a different chain,
  331.        *  but a split occurred while we were suspended.
  332.        */
  333.       for (i = s->segnum; (m = s->sgmask[i]) != 0; i--) {
  334.          d = (word)(m & s->slotnum) - (word)(m & s->sghash[i]);
  335.          if (d < 0)            /* if all elements processed earlier */
  336.             ep = NULL;            /* skip this slot */
  337.          else if (d == 0) {
  338.             /*
  339.              * This chain was split from its parent while the parent was
  340.              *  being processed.  Skip past elements already processed.
  341.              */
  342.             while (ep != NULL && ep->telem.hashnum <= s->sghash[i])
  343.                ep = ep->telem.clink;
  344.             }
  345.          }
  346.       }
  347.  
  348.    /*
  349.     * Return the element.
  350.     */
  351.    return ep;
  352.    }
  353.  
  354. /*
  355.  * hgrow - split a hashed structure (doubling the buckets) for faster access.
  356.  */
  357.  
  358. novalue hgrow(bp)
  359. union block *bp;
  360.    {
  361.    register union block **tp0, **tp1, *ep;
  362.    register word newslots, slotnum, segnum;
  363.    tended struct b_set *ps;
  364.    struct b_slots *seg, *newseg;
  365.    union block **curslot;
  366.  
  367.    ps = (struct b_set *) bp;
  368.    if (ps->hdir[HSegs-1] != NULL)
  369.       return;                /* can't split further */
  370.    newslots = ps->mask + 1;
  371.    Protect(newseg = alcsegment(newslots), return);
  372.  
  373.    curslot = newseg->hslots;
  374.    for (segnum = 0; (seg = ps->hdir[segnum]) != NULL; segnum++)
  375.       for (slotnum = 0; slotnum < segsize[segnum]; slotnum++)  {
  376.          tp0 = &seg->hslots[slotnum];    /* ptr to tail of old slot */
  377.          tp1 = curslot++;        /* ptr to tail of new slot */
  378.          for (ep = *tp0; ep != NULL; ep = ep->selem.clink) {
  379.             if ((ep->selem.hashnum & newslots) == 0) {
  380.                *tp0 = ep;        /* element does not move */
  381.                tp0 = &ep->selem.clink;
  382.                }
  383.             else {
  384.                *tp1 = ep;        /* element moves to new slot */
  385.                tp1 = &ep->selem.clink;
  386.                }
  387.             }
  388.          *tp0 = *tp1 = NULL;
  389.          }
  390.    ps->hdir[segnum] = newseg;
  391.    ps->mask = (ps->mask << 1) | 1;
  392.    }
  393.  
  394. /*
  395.  * hshrink - combine buckets in a set or table that is too sparse.
  396.  *
  397.  *  Call this only for newly created structures.  Shrinking an active structure
  398.  *  can wreak havoc on suspended generators.
  399.  */
  400. novalue hshrink(bp)
  401. union block *bp;
  402.    {
  403.    register union block **tp, *ep0, *ep1;
  404.    int topseg, curseg;
  405.    word slotnum;
  406.    tended struct b_set *ps;
  407.    struct b_slots *seg;
  408.    union block **uppslot;
  409.  
  410.    ps = (struct b_set *)bp;
  411.    topseg = 0;
  412.    for (topseg = 1; topseg < HSegs && ps->hdir[topseg] != NULL; topseg++)
  413.       ;
  414.    topseg--;
  415.    while (TooSparse(ps)) {
  416.       uppslot = ps->hdir[topseg]->hslots;
  417.       ps->hdir[topseg--] = NULL;
  418.       for (curseg = 0; (seg = ps->hdir[curseg]) != NULL; curseg++)
  419.          for (slotnum = 0; slotnum < segsize[curseg]; slotnum++)  {
  420.             tp = &seg->hslots[slotnum];        /* tail pointer */
  421.             ep0 = seg->hslots[slotnum];        /* lower slot entry pointer */
  422.             ep1 = *uppslot++;            /* upper slot entry pointer */
  423.             while (ep0 != NULL && ep1 != NULL)
  424.                if (ep0->selem.hashnum < ep1->selem.hashnum) {
  425.                   *tp = ep0;
  426.                   tp = &ep0->selem.clink;
  427.                   ep0 = ep0->selem.clink;
  428.                   }
  429.                else {
  430.                   *tp = ep1;
  431.                   tp = &ep1->selem.clink;
  432.                   ep1 = ep1->selem.clink;
  433.                   }
  434.             while (ep0 != NULL) {
  435.                *tp = ep0;
  436.                tp = &ep0->selem.clink;
  437.                ep0 = ep0->selem.clink;
  438.                }
  439.             while (ep1 != NULL) {
  440.                *tp = ep1;
  441.                tp = &ep1->selem.clink;
  442.                ep1 = ep1->selem.clink;
  443.                }
  444.             }
  445.       ps->mask >>= 1;
  446.       }
  447.    }
  448.  
  449. /*
  450.  * memb - sets res flag to 1 if x is a member of a set or table, or to 0 if not.
  451.  *  Returns a pointer to the word which points to the element, or which
  452.  *  would point to it if it were there.
  453.  */
  454.  
  455. union block **memb(pb, x, hn, res)
  456. union block *pb;
  457. dptr x;
  458. register uword hn;
  459. int *res;                /* pointer to integer result flag */
  460.    {
  461.    struct b_set *ps;
  462.    register union block **lp;
  463.    register struct b_selem *pe;
  464.    register uword eh;
  465.  
  466.    ps = (struct b_set *)pb;
  467.    lp = hchain(pb, hn);
  468.    /*
  469.     * Look for x in the hash chain.
  470.     */
  471.    *res = 0;
  472.    while ((pe = (struct b_selem *)*lp) != NULL) {
  473.       eh = pe->hashnum;
  474.       if (eh > hn)            /* too far - it isn't there */
  475.          return lp;
  476.       else if ((eh == hn) && (equiv(&pe->setmem, x)))  {
  477.          *res = 1;
  478.          return lp;
  479.          }
  480.       /*
  481.        * We haven't reached the right hashnumber yet or
  482.        *  the element isn't the right one so keep looking.
  483.        */
  484.       lp = &(pe->clink);
  485.       }
  486.    /*
  487.     *  At end of chain - not there.
  488.     */
  489.    return lp;
  490.    }
  491.