home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 5 / FreshFish_July-August1994.bin / bbs / util / vim-2.0.lha / Vim-2.0 / src / storage.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-15  |  22.8 KB  |  981 lines
  1. /* vi:ts=4:sw=4
  2.  *
  3.  * VIM - Vi IMproved
  4.  *
  5.  * Code Contributions By:    Bram Moolenaar            mool@oce.nl
  6.  *                            Tim Thompson            twitch!tjt
  7.  *                            Tony Andrews            onecom!wldrdg!tony 
  8.  *                            G. R. (Fred) Walter        watmath!watcgl!grwalter 
  9.  */
  10.  
  11. /*
  12.  * storage.c: allocation of lines and management of them
  13.  *
  14.  * part 1: storage allocation for the lines and blocks of the current file
  15.  * part 2: managing of the pointer blocks
  16.  */
  17.  
  18. #include "vim.h"
  19. #include "globals.h"
  20. #include "proto.h"
  21.  
  22. /***************************************************************************
  23.  * part 1: storage allocation for the lines and blocks of the current file *
  24.  ***************************************************************************/
  25.  
  26. /*
  27.  * Memory is allocated in relatively large blocks. These blocks are linked
  28.  * in the allocated block list, headed by block_head. They are all freed
  29.  * when abandoning a file, so we don't have to free every single line. The
  30.  * list is kept sorted on memory address.
  31.  * block_alloc() allocates a block.
  32.  * m_blockfree() frees all blocks.
  33.  *
  34.  * The available chunks of memory are kept in free chunk lists. There is
  35.  * one free list for each block of allocated memory. The list is kept sorted
  36.  * on memory address.
  37.  * alloc_line() gets a chunk from the free lists.
  38.  * free_line() returns a chunk to the free lists.
  39.  * m_search points to the chunk before the chunk that was freed/allocated the
  40.  * last time.
  41.  * mb_current points to the b_head where m_search points into the free list.
  42.  *
  43.  *
  44.  *    block_head     /---> block #1     /---> block #2
  45.  *       mb_next ---/       mb_next ---/       mb_next ---> NULL
  46.  *       mb_info            mb_info            mb_info
  47.  *          |                  |                  |
  48.  *          V                  V                  V
  49.  *        NULL          free chunk #1.1      free chunk #2.1
  50.  *                             |                  |
  51.  *                             V                  V
  52.  *                      free chunk #1.2          NULL
  53.  *                             |
  54.  *                             V
  55.  *                            NULL
  56.  *
  57.  * When a single free chunk list would have been used, it could take a lot
  58.  * of time in free_line() to find the correct place to insert a chunk in the
  59.  * free list. The single free list would become very long when many lines are
  60.  * changed (e.g. with :%s/^M$//).
  61.  */
  62.  
  63.     /*
  64.      * this blocksize is used when allocating new lines
  65.      * When reading files larger blocks are used (see fileio.c)
  66.      * on the Amiga the blocksize must not be a multiple of 256
  67.      * with MS-Dos the blocksize must be larger than 255
  68.      * For Unix it does not really matter
  69.      */
  70. #define MEMBLOCKSIZE 2044
  71.  
  72. typedef struct m_info info_t;
  73.  
  74. /*
  75.  * There are two types of in-use memory chunks:
  76.  *    1. those that are allocated by readfile(). These are always preceded
  77.  *        by a NUL character and end in a NUL character. The chunk must not
  78.  *        contain other NUL characters. The preceding NUL is used to
  79.  *        determine the chunk type. The ending NUL is used to determine the
  80.  *        end of the chunk. The preceding NUL is not part of the chunk, the
  81.  *        ending NUL is. 
  82.  *  2. the other chunks have been allocated with alloc_line(). They are
  83.  *        preceded by a non-NUL character. This is used to determine the chunk
  84.  *        type. The non-NUL may be part of a size field or may be an extra 0xff
  85.  *        byte. The chunk always ends in a NUL character and may also contain
  86.  *        a NUL character. The size field contains the size of the chunk,
  87.  *        including the size field. The trailing NUL may be used by a possibly
  88.  *        follwing type 1 chunk. The preceding size, the optional 0xff and the
  89.  *        trailing NUL are all part of the chunk.
  90.  *
  91.  * When the chunk is not in-use it is preceded with the m_info structure.
  92.  * The m_next field links it in one of the free chunk lists. It must still
  93.  * end in a NUL byte, because it may be followed by a type 1 chunk!
  94.  *
  95.  * When in-use we must make sure there is a non-NUL byte in front of type
  96.  * 2 chunks.
  97.  *
  98.  * On the Amiga this means that the size must not be a multiple of 256.
  99.  * This is done by multiplying the size by 2 and adding one.
  100.  *
  101.  * On MS-DOS the size must be larger than 255. This is done by adding 256
  102.  * to the size.
  103.  *
  104.  * On Unix systems an extra 0xff byte is added. This costs 4 bytes because
  105.  * pointers must be kept long-aligned.
  106.  *
  107.  * On most unix systems structures have to be longword (32 or 64 bit) aligned.
  108.  * On most other systems they are short (16 bit) aligned.
  109.  */
  110.  
  111. #ifdef UNIX
  112. # define ALIGN_LONG        /* longword alignment and use filler byte */
  113. # define ALIGN_SIZE (sizeof(long))
  114. # define ALIGN_MASK (ALIGN_SIZE - 1)
  115. #else
  116. # ifdef AMIGA
  117. #  define LOWBYTE        /* size must not be multiple of 256 */
  118. # else
  119. #  ifdef MSDOS
  120. #   define HIGHBYTE        /* size must be larger than 255 */
  121. #  else
  122.     you must define something!
  123. #  endif
  124. # endif
  125. #endif
  126.  
  127. /*
  128.  * stucture used to link chunks in one of the free chunk lists.
  129.  */
  130. struct m_info
  131. {
  132. #ifdef ALIGN_LONG
  133.     u_long     m_size;    /* size of the chunk (including m_info) */
  134. #else
  135.     u_short  m_size;    /* size of the chunk (including m_info) */
  136. #endif
  137.     info_t    *m_next;    /* pointer to next free chunk in the list */
  138. };
  139.  
  140. #ifdef ALIGN_LONG
  141.     /* size of m_size + room for 0xff byte */
  142. # define M_OFFSET (sizeof(u_long) * 2)
  143. #else
  144.     /* size of m_size */
  145. # define M_OFFSET (sizeof(u_short))
  146. #endif
  147.  
  148. /*
  149.  * structure used to link blocks in the list of allocated blocks.
  150.  */
  151. struct m_block
  152. {
  153.     struct m_block    *mb_next;    /* pointer to next allocated block */
  154.     info_t            mb_info;    /* head of free chuck list for this block */
  155. };
  156.  
  157. static struct m_block block_head = {NULL, {0, NULL}};
  158.                                 /* head of allocated memory block list */
  159.  
  160. static info_t *m_search = NULL;     /* pointer to chunk before previously
  161.                                        allocated/freed chunk */
  162. static struct m_block *mb_current = NULL;    /* block where m_search points in */
  163.  
  164. /*
  165.  * Allocate a block of memory and link it in the allocated block list.
  166.  */
  167.     char *
  168. m_blockalloc(size, message)
  169.     u_long    size;
  170.     int        message;
  171. {
  172.     struct m_block *p;
  173.     struct m_block *mp, *next;
  174.  
  175.     p = (struct m_block *)lalloc(size + sizeof(struct m_block), message);
  176.     if (p != NULL)
  177.     {
  178.          /* Insert the block into the allocated block list, keeping it
  179.                      sorted on address. */
  180.         for (mp = &block_head; (next = mp->mb_next) != NULL && next < p; mp = next)
  181.             ;
  182.         p->mb_next = next;                /* link in block list */
  183.         mp->mb_next = p;
  184.         p->mb_info.m_next = NULL;        /* clear free list */
  185.         p->mb_info.m_size = 0;
  186.         mb_current = p;                    /* remember current block */
  187.         m_search = NULL;
  188.         p++;                            /* return usable memory */
  189.     }
  190.     return (char *)p;
  191. }
  192.  
  193. /*
  194.  * free all allocated memory blocks
  195.  */
  196.     void
  197. m_blockfree()
  198. {
  199.     struct m_block *p, *np;
  200.  
  201.     for (p = block_head.mb_next; p != NULL; p = np)
  202.     {
  203.         np = p->mb_next;
  204.         free((char *)p);
  205.     }
  206.     block_head.mb_next = NULL;
  207.     m_search = NULL;
  208.     mb_current = NULL;
  209. }
  210.  
  211. /*
  212.  * Free a chunk of memory which was
  213.  *  1. inserted with readfile(); these are preceded with a NUL byte
  214.  *  2. allocated with alloc_line(); these are preceded with a non-NUL byte
  215.  * Insert the chunk into the correct free list, keeping it sorted on address.
  216.  */
  217.     void
  218. free_line(ptr)
  219.     char *ptr;
  220. {
  221.     register info_t        *next;
  222.     register info_t        *prev, *curr;
  223.     register info_t        *mp;
  224.     long                len;
  225.     struct m_block        *nextb;
  226.  
  227.     if (ptr == NULL || ptr == IObuff)
  228.         return;    /* illegal address can happen in out-of-memory situations */
  229.  
  230.     if (*(ptr - 1) == NUL)        /* type 1 chunk: no size field */
  231.     {
  232. #ifdef ALIGN_LONG        /* use longword alignment */
  233.         long c;
  234.  
  235.         len = strlen(ptr) + 1;
  236.         if ((c = ((long)ptr & ALIGN_MASK)) != 0)     /* lose some bytes */
  237.         {
  238.             c = ALIGN_SIZE - c;
  239.             ptr += c;
  240.             len -= c;
  241.         }
  242. #else            /* use short (16 bit) alignment */
  243.         len = strlen(ptr) + 1;
  244.         if (len > 0xff00)        /* can't handle this large (cannot happen?) */
  245.             len = 0xff00;
  246.         if ((long)ptr & 1)                    /* lose a byte */
  247.         {
  248.             ++ptr;
  249.             --len;
  250.         }
  251. #endif    /* ALIGN_LONG */
  252.  
  253.         /* we must be able to store size, pointer and a trailing NUL */
  254.         /* otherwise we can't fit it in the free list */
  255.         if (len <= (long)sizeof(info_t))
  256.             return;            /* these bytes are not used until you quit the file */
  257.         mp = (info_t *)ptr;
  258.         mp->m_size = len;
  259.     }
  260. #ifdef ALIGN_LONG
  261.     else if ((*(ptr - 1) & 0xff) == 0xff)    /* type 2 chunk: has size field */
  262.     {
  263.         mp = (info_t *)(ptr - M_OFFSET);
  264.     }
  265.     else        /* illegal situation: there is no NUL or 0xff in front of the line */
  266.     {
  267.         emsg("Illegal chunk");
  268.         return;
  269.     }
  270. #endif
  271. #ifdef LOWBYTE
  272.     else             /* type 2 chunk: has size field */
  273.     {
  274.         mp = (info_t *)(ptr - M_OFFSET);
  275.         mp->m_size >>= 1;
  276.     }
  277. #endif
  278. #ifdef HIGHBYTE
  279.     else             /* type 2 chunk: has size field */
  280.     {
  281.         mp = (info_t *)(ptr - M_OFFSET);
  282.         mp->m_size -= 256;
  283.     }
  284. #endif
  285.  
  286.         /* find block where chunk could be a part off */
  287.         /* if we change mb_current, m_search is set to NULL */
  288.     if (mb_current == NULL || mp < (info_t *)mb_current)
  289.     {
  290.         mb_current = block_head.mb_next;
  291.         m_search = NULL;
  292.     }
  293.     if ((nextb = mb_current->mb_next) != NULL && (info_t *)nextb < mp)
  294.     {
  295.         mb_current = nextb;
  296.         m_search = NULL;
  297.     }
  298.     while ((nextb = mb_current->mb_next) != NULL && (info_t *)nextb < mp)
  299.         mb_current = nextb;
  300.  
  301.     curr = NULL;
  302.     /* if mp is smaller than m_search->m_next we go to the start of the free list */
  303.     if (m_search == NULL || mp < (m_search->m_next))
  304.         next = &(mb_current->mb_info);
  305.     else
  306.         next = m_search;
  307.     /*
  308.      * The following loop is executed very often.
  309.      * Therefore it has been optimized at the cost of readability.
  310.      * Keep it fast!
  311.      */
  312. #ifdef SLOW_BUT_EASY_TO_READ
  313.     do
  314.     {
  315.         prev = curr;
  316.         curr = next;
  317.         next = next->m_next;
  318.     }
  319.     while (mp > next && next != NULL);
  320. #else
  321.     do                                        /* first, middle, last */
  322.     {
  323.         prev = next->m_next;                /* curr, next, prev */
  324.         if (prev == NULL || mp <= prev)
  325.         {
  326.             prev = curr;
  327.             curr = next;
  328.             next = next->m_next;
  329.             break;
  330.         }
  331.         curr = prev->m_next;                /* next, prev, curr */
  332.         if (curr == NULL || mp <= curr)
  333.         {
  334.             prev = next;
  335.             curr = prev->m_next;
  336.             next = curr->m_next;
  337.             break;
  338.         }
  339.         next = curr->m_next;                /* prev, curr, next */
  340.     }
  341.     while (mp > next && next != NULL);
  342. #endif
  343.  
  344. /* if *mp and *next are concatenated, join them into one chunk */
  345.     if ((char *)mp + mp->m_size == (char *)next)
  346.     {
  347.         mp->m_size += next->m_size;
  348.         mp->m_next = next->m_next;
  349.     }
  350.     else
  351.         mp->m_next = next;
  352.  
  353. /* if *curr and *mp are concatenated, join them */
  354.     if (prev != NULL && (char *)curr + curr->m_size == (char *)mp)
  355.     {
  356.         curr->m_size += mp->m_size;
  357.         curr->m_next = mp->m_next;
  358.         m_search = prev;
  359.     }
  360.     else
  361.     {
  362.         curr->m_next = mp;
  363.         m_search = curr;    /* put m_search before freed chunk */
  364.     }
  365. }
  366.  
  367. /*
  368.  * Allocate and initialize a new line structure with room for at least
  369.  * 'size' characters.
  370.  */
  371.     char *
  372. alloc_line(size)
  373.     register unsigned size;
  374. {
  375.     register info_t *mp, *mprev, *mp2;
  376.     struct m_block    *mbp;
  377.     int                 size_align;
  378.  
  379. /*
  380.  * Add room for size field, optional 0xff byte and trailing NUL byte.
  381.  * Adjust for minimal size (must be able to store info_t
  382.  * plus a trailing NUL, so the chunk can be released again)
  383.  */
  384.     size += M_OFFSET + 1;
  385.     if (size < sizeof(info_t) + 1)
  386.       size = sizeof(info_t) + 1;
  387.  
  388. /*
  389.  * round size up for alignment
  390.  */
  391. #ifdef ALIGN_LONG            /* use longword alignment */
  392.     size_align = (size + ALIGN_MASK) & ~ALIGN_MASK;
  393. #else /* ALIGN_LONG */    /* use short (16 bit) alignment */
  394.     size_align = (size + 1) & ~1;
  395. #endif    /* ALIGN_LONG */
  396.  
  397. /* if m_search is NULL (uninitialized free list) we start at block_head */
  398.     if (mb_current == NULL || m_search == NULL)
  399.     {
  400.         mb_current = &block_head;
  401.         m_search = &(block_head.mb_info);
  402.     }
  403.  
  404. /* search for space in free list */
  405.     mprev = m_search;
  406.     mbp = mb_current;
  407.     mp = m_search->m_next;
  408.     if (mp == NULL)
  409.     {
  410.         if (mbp->mb_next)
  411.             mbp = mbp->mb_next;
  412.         else
  413.             mbp = &block_head;
  414.         mp = m_search = &(mbp->mb_info);
  415.     }
  416.     while (mp->m_size < size)
  417.     {
  418.         if (mp == m_search)        /* back where we started in free chunk list */
  419.         {
  420.             if (mbp->mb_next)
  421.                 mbp = mbp->mb_next;
  422.             else
  423.                 mbp = &block_head;
  424.             mp = m_search = &(mbp->mb_info);
  425.             if (mbp == mb_current)    /* back where we started in block list */
  426.             {
  427.                 int        n = (size_align > (MEMBLOCKSIZE / 4) ? size_align : MEMBLOCKSIZE);
  428.  
  429.                 mp = (info_t *)m_blockalloc((u_long)n, TRUE);
  430.                 if (mp == NULL)
  431.                     return (NULL);
  432. #ifdef HIGHBYTE
  433.                 mp->m_size = n + 256;
  434. #endif
  435. #ifdef LOWBYTE
  436.                 mp->m_size = (n << 1) + 1;
  437. #endif
  438. #ifdef ALIGN_LONG
  439.                 mp->m_size = n;
  440.                 *((u_char *)mp + M_OFFSET - 1) = 0xff;
  441. #endif
  442.                 free_line((char *)mp + M_OFFSET);
  443.                 mp = m_search;
  444.                 mbp = mb_current;
  445.             }
  446.         }
  447.         mprev = mp;
  448.         if ((mp = mp->m_next) == NULL)        /* at end of the list */
  449.             mp = &(mbp->mb_info);            /* wrap around to begin */
  450.     }
  451.  
  452. /* if the chunk we found is large enough, split it up in two */
  453.     if ((long)mp->m_size - size_align >= (long)(sizeof(info_t) + 1))
  454.     {
  455.         mp2 = (info_t *)((char *)mp + size_align);
  456.         mp2->m_size = mp->m_size - size_align;
  457.         mp2->m_next = mp->m_next;
  458.         mprev->m_next = mp2;
  459.         mp->m_size = size_align;
  460.     }
  461.     else                    /* remove *mp from the free list */
  462.     {
  463.         mprev->m_next = mp->m_next;
  464.     }
  465.     m_search = mprev;
  466.     mb_current = mbp;
  467.  
  468. #ifdef HIGHBYTE
  469.     mp->m_size += 256;
  470. #endif
  471. #ifdef LOWBYTE
  472.     mp->m_size = (mp->m_size << 1) + 1;
  473. #endif
  474.     mp = (info_t *)((char *)mp + M_OFFSET);
  475. #ifdef ALIGN_LONG
  476.     *((u_char *)mp - 1) = 0xff;            /* mark type 2 chunk */
  477. #endif
  478.     *(char *)mp = NUL;                    /* set the first byte to NUL */
  479.  
  480.     return ((char *)mp);
  481. }
  482.  
  483. /*
  484.  * save_line(): allocate memory with alloc_line() and copy the
  485.  * string 'src' into it.
  486.  */
  487.     char *
  488. save_line(src)
  489.     register char *src;
  490. {
  491.     register char *dst;
  492.     register unsigned len;
  493.  
  494.     len = strlen(src);
  495.     if ((dst = alloc_line(len)) != NULL)
  496.         memmove(dst, src, (size_t)(len + 1));
  497.     return (dst);
  498. }
  499.  
  500. /******************************************
  501.  * part 2: managing of the pointer blocks *
  502.  ******************************************/
  503.  
  504. typedef struct block block_t;
  505.  
  506. #ifdef BLOCK_SIZE
  507. # undef BLOCK_SIZE    /* for Linux: is in limits.h */
  508. #endif
  509.  
  510. #define BLOCK_SIZE 40
  511.  
  512. struct block
  513. {
  514.     char    *b_ptr[BLOCK_SIZE];        /* pointers to the lines */
  515.     char     b_flags[BLOCK_SIZE];    /* see below */
  516.     u_short  b_count;                /* current number of pointers in b_ptr */
  517.     block_t *b_next;                /* pointer to next block */
  518.     block_t *b_prev;                /* pointer to previous block */
  519. };
  520.  
  521. #define B_MARKED    0x01        /* mark for :global command */
  522.  
  523. static block_t *first_block;    /* pointer to first block in block list */
  524. static block_t *last_block;        /* pointer to last block in block list */
  525.  
  526. static block_t *curr_block;        /* block used by nr2ptr */
  527. static linenr_t curr_count;        /* first line number of block curr_block */
  528. static linenr_t curr_count_max;    /* curr_count + curr_block->b_count */
  529.  
  530. static block_t *alloc_block __ARGS((void));
  531.  
  532.     static block_t *
  533. alloc_block()
  534. {
  535.     block_t *p;
  536.  
  537.     p = (block_t *)(alloc_line((unsigned)sizeof(block_t)));
  538.     if (p != NULL)
  539.     {
  540.         memset((char *)p, 0, sizeof(block_t));
  541.     }
  542.     return (p);
  543. }
  544.  
  545. /*
  546.  * filealloc() - construct an initial empty file buffer
  547.  */
  548.     void
  549. filealloc()
  550. {
  551.     first_block = last_block = alloc_block();
  552.     if (first_block == NULL || (first_block->b_ptr[0] = alloc_line(0)) == NULL)
  553.         getout(1);
  554.     first_block->b_count = 1;
  555.     Curpos.lnum = 1;
  556.     Curswant = Curpos.col = 0;
  557.     Topline = 1;
  558.     Botline = 2;
  559.     line_count = 1;
  560.     curr_count = 0;
  561.     clrallmarks();
  562.     clrtags();
  563.     UNCHANGED;
  564. }
  565.  
  566. /*
  567.  * freeall() - free the current buffer
  568.  *
  569.  * Free all lines in the current buffer.
  570.  */
  571.     void
  572. freeall()
  573. {
  574.     m_blockfree();
  575.     line_count = 0;
  576.     s_ins(0, 0, TRUE);    /* invalidate Line arrays */
  577.     u_clearall();
  578. }
  579.  
  580. /*
  581.  * Get the pointer to the line 'nr'.
  582.  * This function is used a lot for sequential access (writeit, search),
  583.  * so that is what it is optimized for.
  584.  */
  585.     char *
  586. nr2ptr(nr)
  587.     register linenr_t nr;
  588. {
  589.     register linenr_t count = curr_count;
  590.  
  591.     /*
  592.      * if we don't have a current block or the line is not in the current block,
  593.      * make the block containing the line the current block.
  594.      */
  595.     if (count == 0 || nr >= curr_count_max || nr < count)
  596.     {
  597.         register block_t *bp = curr_block;
  598.  
  599.         if (nr < 1 || nr > line_count)
  600.         {
  601.             emsg("nr2ptr: illegal nr");
  602.             return (IObuff);    /* always return a valid ptr */
  603.         }
  604.  
  605.         /*
  606.          * three ways to find the pointer:
  607.          * 1. first pointer in the next block (fast for sequential access)
  608.          * 2. search forward
  609.          * 3. search backward
  610.          */
  611.         if (count && nr == count + bp->b_count)        /* in next block */
  612.         {
  613.             count = nr;
  614.             bp = bp->b_next;
  615.         }
  616.         else if (nr <= (count + line_count) / 2 ||
  617.                 (nr <= count && nr <= count / 2))
  618.         {
  619.                                                     /* search forward */
  620.             if (nr < count || count == 0)
  621.             {
  622.                 count = 1;
  623.                 bp = first_block;
  624.             }
  625.             while (bp != NULL)
  626.             {
  627.                 count += bp->b_count;
  628.                 if (nr < count)
  629.                 {
  630.                     count -= bp->b_count;
  631.                     break;
  632.                 }
  633.                 bp = bp->b_next;
  634.             }
  635.         }
  636.         else
  637.         {                                            /* search backward */
  638.             if (nr < count)
  639.                 bp = bp->b_prev;
  640.             else
  641.             {
  642.                 bp = last_block;
  643.                 count = line_count + 1;
  644.             }
  645.             while (bp != NULL)
  646.             {
  647.                 count -= bp->b_count;
  648.                 if (nr >= count)
  649.                     break;
  650.                 bp = bp->b_prev;
  651.             }
  652.         }
  653.         
  654.         if (bp == NULL)
  655.         {
  656.             emsg("nr2ptr: strorage corrupt");
  657.             curr_count = 0;
  658.             return (IObuff);
  659.         }
  660.         curr_count = count;
  661.         curr_count_max = count + bp->b_count;
  662.         curr_block = bp;
  663.     }
  664.     return (curr_block->b_ptr[nr - count]);
  665. }
  666.  
  667. /*
  668.  * pos2ptr: get pointer to position 'pos'
  669.  */
  670.     char *
  671. pos2ptr(pos)
  672.     FPOS    *pos;
  673. {
  674.     return (nr2ptr(pos->lnum) + pos->col);
  675. }
  676.  
  677.     char *
  678. Curpos2ptr()
  679. {
  680.     return (nr2ptr(Curpos.lnum) + Curpos.col);
  681. }
  682.  
  683. /*
  684.  * set the B_MARKED flag for line 'lnum'
  685.  */
  686.     void
  687. setmarked(lnum)
  688.     linenr_t lnum;
  689. {
  690.     nr2ptr(lnum);
  691.     curr_block->b_flags[lnum - curr_count] |= B_MARKED;
  692. }
  693.  
  694. /*
  695.  * find the first line with its B_MARKED flag set
  696.  */
  697.     linenr_t
  698. firstmarked()
  699. {
  700.     register block_t    *bp;
  701.     register linenr_t    lnum;
  702.     register u_short    i;
  703.  
  704.     for (bp = first_block, lnum = 1; bp != NULL; bp = bp->b_next)
  705.         for (i = 0; i < bp->b_count; ++i, ++lnum)
  706.             if (bp->b_flags[i] & B_MARKED)
  707.             {
  708.                 bp->b_flags[i] &= ~B_MARKED;
  709.                 return lnum;
  710.             }
  711.     return (linenr_t) 0;
  712. }
  713.  
  714. /*
  715.  * clear all B_MARKED flags
  716.  */
  717.     void
  718. clearmarked()
  719. {
  720.     register block_t    *bp;
  721.     register int        i;
  722.  
  723.     for (bp = first_block; bp != NULL; bp = bp->b_next)
  724.         for (i = bp->b_count; --i >= 0; )
  725.                 bp->b_flags[i] &= ~B_MARKED;
  726. }
  727.  
  728. /*
  729.  * a pointer to a line is converted into a line number
  730.  * we start at line number 'start'
  731.  * this is a bit slow, but it is used for marks and undo only
  732.  */
  733.     linenr_t
  734. ptr2nr(ptr, start)
  735.     char *ptr;
  736.     linenr_t start;
  737. {
  738.     block_t *bp;
  739.     register linenr_t nr;
  740.     register char **pp;
  741.     register int    i;
  742.  
  743.     if (ptr == NULL)
  744.         return (linenr_t)0;
  745.  
  746.     if (start == 0)
  747.         start = 1;
  748.     nr2ptr(start);        /* set curr_block and curr_count */
  749.  
  750.     for (nr = curr_count, bp = curr_block; bp != NULL; bp = bp->b_next)
  751.         for (pp = bp->b_ptr, i = bp->b_count; --i >= 0; ++nr)
  752.             if (*pp++ == ptr)
  753.                 return (nr);
  754.     return (linenr_t)0;
  755. }
  756.  
  757. /*
  758.  * appendline: add a line
  759.  *    return TRUE when succesful
  760.  */
  761.     int
  762. appendline(after, s)
  763.     linenr_t    after;
  764.     char        *s;
  765. {
  766.     register block_t    *bp;
  767.     block_t             *nbp;
  768.     linenr_t            count;
  769.     register int        i;
  770.  
  771.     if (s == NULL)        /* don't insert NULL pointers! */
  772.         return FALSE;
  773.     if (after == 0)     /* insert in front of first line */
  774.     {
  775.         bp = first_block;
  776.         count = 1;
  777.         if (bufempty())     /* simply replace dummy line */
  778.         {
  779.             free_line(bp->b_ptr[0]);
  780.             bp->b_ptr[0] = s;
  781.             return TRUE;
  782.         }
  783.         curr_count = 0; /* curr_block will become invalid */
  784.     }
  785.     else
  786.     {
  787.         (void)nr2ptr(after);    /* find block */
  788.         bp = curr_block;
  789.         count = curr_count;
  790.     }
  791.  
  792.     ++line_count;
  793.     i = bp->b_count;
  794.     if (i < BLOCK_SIZE)            /* there is place in the current block */
  795. /* move ptrs one place forward to make space for new one */
  796.     {
  797.         register char **pp;
  798.         register char *fp;
  799.  
  800.         pp = &(bp->b_ptr[i]);
  801.         fp = &(bp->b_flags[i]);
  802.         for (i += count - after - 1; --i >= 0; --pp, --fp)
  803.         {
  804.             *pp = *(pp - 1);
  805.             *fp = *(fp - 1);
  806.         }
  807.         *pp = s;
  808.         *fp = 0;
  809.         ++bp->b_count;
  810.         ++curr_count_max;
  811.         return TRUE;
  812.     }
  813.  
  814. /* need to allocate a new block */
  815.     nbp = alloc_block();
  816.     if (nbp == NULL)
  817.     {
  818.         --line_count;
  819.         free_line(s);
  820.         return FALSE;
  821.     }
  822.  
  823. /* put new block in linked list */
  824.     if (after == 0) /* put new block in front of linked list */
  825.     {
  826.         bp->b_prev = nbp;
  827.         nbp->b_next = bp;
  828.         first_block = nbp;
  829.         nbp->b_ptr[0] = s;
  830.         nbp->b_count = 1;
  831.         return TRUE;
  832.     }
  833.  
  834.     /* insert new block in linked list after bp */
  835.     nbp->b_next = bp->b_next;
  836.     bp->b_next = nbp;
  837.     nbp->b_prev = bp;
  838.     if (nbp->b_next == NULL)
  839.         last_block = nbp;
  840.     else
  841.         nbp->b_next->b_prev = nbp;
  842.  
  843.     if (after - count + 1 == BLOCK_SIZE) /* put s in new block */
  844.     {
  845.         nbp->b_ptr[0] = s;
  846.         nbp->b_count = 1;
  847.         return TRUE;
  848.     }
  849.  
  850.     /* move some ptrs from full block to new block */
  851.     {
  852.         register int j = 0;
  853.  
  854.         bp->b_count = after - count + 1;    /* number of ptrs remaining */
  855.         i = BLOCK_SIZE - bp->b_count;        /* number of ptrs to be moved */
  856.         nbp->b_count = i;
  857.         while (--i >= 0)
  858.         {
  859.             j = bp->b_count + i;
  860.             nbp->b_ptr[i] = bp->b_ptr[j];
  861.             nbp->b_flags[i] = bp->b_flags[j];
  862.         }
  863.         bp->b_ptr[j] = s;
  864.         bp->b_flags[j] = 0;
  865.         ++bp->b_count;
  866.         curr_count_max = curr_count + bp->b_count;
  867.     }
  868.     return TRUE;
  869. }
  870.  
  871. /*
  872.  * delsline: delete line from storage
  873.  *
  874.  * the line is turned over to the caller
  875.  */
  876.     char *
  877. delsline(nr, delmarks)
  878.     linenr_t    nr;
  879.     int            delmarks;
  880. {
  881.     char    *ptr;
  882.     register block_t    *bp;
  883.     register char **pp;
  884.     register char *fp;
  885.     register int i;
  886.  
  887.     if (nr < 1 || nr > line_count)
  888.     {
  889.         emsg("delsline: nr wrong");
  890.         return (alloc_line(0));
  891.     }
  892.     ptr = nr2ptr(nr);
  893.     if (delmarks)
  894.         adjustmark(ptr, NULL);            /* remove marks for this line (slow!) */
  895.     bp = curr_block;
  896.     if (line_count == 1)    /* don't delete the last line in the file */
  897.     {
  898.         bp->b_ptr[0] = alloc_line(0);
  899.         return (ptr);
  900.     }
  901.     --line_count;
  902.  
  903.     /* move the rest of the ptrs in this block one down */
  904.     pp = &(bp->b_ptr[nr - curr_count]);
  905.     fp = &(bp->b_flags[nr - curr_count]);
  906.     for (i = bp->b_count + curr_count - nr - 1; --i >= 0; ++pp, ++fp)
  907.     {
  908.         *pp = *(pp + 1);
  909.         *fp = *(fp + 1);
  910.     }
  911.     if (--bp->b_count == 0) /* the block became empty, remove it from the list */
  912.     {
  913.         if (bp->b_prev == NULL)
  914.             first_block = bp->b_next;
  915.         else
  916.             bp->b_prev->b_next = bp->b_next;
  917.         if (bp->b_next == NULL)
  918.             last_block = bp->b_prev;
  919.         else
  920.             bp->b_next->b_prev = bp->b_prev;
  921.         free_line((char *)bp);
  922.         curr_count = 0; /* curr_block invalid */
  923.     }
  924.     else
  925.         --curr_count_max;
  926.     return (ptr);
  927. }
  928.  
  929. /*
  930.  * replace the line "lnum" with the line "new".
  931.  * return the old line (which should be freed by the caller)
  932.  */
  933.     char *
  934. replaceline(lnum, new)
  935.     linenr_t lnum;
  936.     char *new;
  937. {
  938.     char *old;
  939.  
  940.     old = nr2ptr(lnum);
  941.     if (new == NULL || curr_count == 0)    /* we don't want NULL pointers in the list */
  942.         return (alloc_line(0)); /* be friendly to the caller */
  943.  
  944.     curr_block->b_ptr[lnum - curr_count] = new;
  945.     curr_block->b_flags[lnum - curr_count] = 0;
  946.     adjustmark(old, new);
  947.     return (old);
  948. }
  949.  
  950. /*
  951.  * canincrease(n) - returns TRUE if the current line can be increased 'n'
  952.  * bytes
  953.  *
  954.  * This routine returns immediately if the requested space is available. If not,
  955.  * it attempts to allocate the space and adjust the data structures
  956.  * accordingly. If everything fails it returns FALSE.
  957.  */
  958.     int
  959. canincrease(n)
  960.     int    n;
  961. {
  962.     register char    *old;
  963.     register char    *new;        /* pointer to new space */
  964.     register unsigned newsize;
  965.  
  966.     old = nr2ptr(Curpos.lnum);
  967.     newsize = strlen(old) + n;
  968.  
  969.     new = alloc_line(newsize);
  970.     if (new == NULL)
  971.         return FALSE;
  972.  
  973.     strcpy(new, old);
  974.     adjustmark(old, new);
  975.     free_line(old);
  976.     curr_block->b_ptr[Curpos.lnum - curr_count] = new;
  977.     curr_block->b_flags[Curpos.lnum - curr_count] = 0;
  978.  
  979.     return TRUE;
  980. }
  981.