root/libutil/gtagsop.c

/* [<][>][^][v][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. compare_path
  2. compare_lineno
  3. compare_tags
  4. seekto
  5. dbname
  6. gtags_open
  7. gtags_put
  8. gtags_delete
  9. gtags_first
  10. gtags_next
  11. gtags_close
  12. flush_pool
  13. segment_read

/*
 * Copyright (c) 1997, 1998, 1999, 2000, 2001, 2002, 2005, 2006,
 *      2007 Tama Communications Corporation
 *
 * This file is part of GNU GLOBAL.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#ifdef STDC_HEADERS
#include <stdlib.h>
#endif
#ifdef HAVE_STRING_H
#include <string.h>
#else
#include <strings.h>
#endif
#ifdef HAVE_UNISTD_H
#include <unistd.h>
#endif

#include "char.h"
#include "checkalloc.h"
#include "conf.h"
#include "compress.h"
#include "dbop.h"
#include "die.h"
#include "format.h"
#include "gparam.h"
#include "gtagsop.h"
#include "locatestring.h"
#include "makepath.h"
#include "path.h"
#include "gpathop.h"
#include "split.h"
#include "strbuf.h"
#include "strhash.h"
#include "strlimcpy.h"
#include "strmake.h"
#include "varray.h"

#define HASHBUCKETS     2048

static int compare_path(const void *, const void *);
static int compare_lineno(const void *, const void *);
static int compare_tags(const void *, const void *);
static const char *seekto(const char *, int);
static void flush_pool(GTOP *);
static void segment_read(GTOP *);

/*
 * compare_path: compare function for sorting path names.
 */
static int
compare_path(const void *s1, const void *s2)
{
        return strcmp(*(char **)s1, *(char **)s2);
}
/*
 * compare_lineno: compare function for sorting line number.
 */
static int
compare_lineno(const void *s1, const void *s2)
{
        return *(const int *)s1 - *(const int *)s2;
}
/*
 * compare_tags: compare function for sorting tags.
 */
static int
compare_tags(const void *v1, const void *v2)
{
        const GTP *e1 = v1, *e2 = v2;
        int ret;

        if ((ret = strcmp(e1->path, e2->path)) != 0)
                return ret;
        return e1->lineno - e2->lineno;
}
/*
 * seekto: seek to the specified item of tag record.
 *
 * Usage:
 *           0         1          2
 * tagline = <file id> <tag name> <line number>
 *
 * <file id>     = seekto(tagline, SEEKTO_FILEID);
 * <tag name>    = seekto(tagline, SEEKTO_TAGNAME);
 * <line number> = seekto(tagline, SEEKTO_LINENO);
 */
#define SEEKTO_FILEID   0
#define SEEKTO_TAGNAME  1
#define SEEKTO_LINENO   2

static const char *
seekto(const char *string, int n)
{
        const char *p = string;
        while (n--) {
                p = strchr(p, ' ');
                if (p == NULL)
                        return NULL;
                p++;
        }
        return p;
}
/*
 * Tag format
 *
 * [Specification of format version 4]
 * 
 * Standard format (for GTAGS)
 * 
 *         <file id> <tag name> <line number> <line image>
 * 
 *                 * Separator is single blank.
 * 
 *         [example]
 *         +------------------------------------
 *         |110 func 10 int func(int a)
 *         |110 func 30 func(int a1, int a2)
 * 
 *         Line image might be compressed (GTAGS_COMPRESS).
 *
 * With compact option for GRTAGS, GSYMS (GTAGS_COMPACT)
 * 
 *         <file id> <tag name> <line number>,...
 * 
 *                 * Separator is single blank.
 * 
 *         [example]
 *         +------------------------------------
 *         |110 func 10,30
 * 
 *         Line numbers are sorted in a line.
 * 
 * [Specification of format version 5]
 * 
 * Standard format for GTAGS
 * 
 *         <file id> <tag name> <line number> <line image>
 * 
 *                 * Separator is single blank.
 * 
 *         [example]
 *         +------------------------------------
 *         |110 func 10 int func(int a)
 *         |110 func 30 func(int a1, int a2)
 * 
 *         Line image might be compressed (GTAGS_COMPRESS).
 *         Tag name might be compressed (GTAGS_COMPNAME).
 *
 * With compact option for GRTAGS, GSYMS (GTAGS_COMPACT)
 * 
 *         <file id> <tag name> <line number>,...
 * 
 *                 * Separator is single blank.
 * 
 *         [example]
 *         +------------------------------------
 *         |110 func 10,20
 * 
 *         Each line number might be expressed as difference from the previous
 *         line number except for the head (GTAGS_COMPLINE).
 *           ex: 10,3,2 means '10 13 15'.
 *         In addition,successive line numbers are expressed as a range.
 *           ex: 10-3 means '10 11 12 13'.
 *
 * [Description]
 * 
 * o Standard format is applied to GTAGS, and compact format is applied
 *   to GRTAGS and GSYMS by default.
 * o Above two formats are same to the first line number. So, we can use
 *   common function to sort them.
 * o Separator is single blank.
 *   This decrease disk space used a little, and make it easy to parse
 *   tag record.
 * o Use file id instead of path name.
 *   This allows blanks in path name at least in tag files.
 * o Put file id at the head of tag record.
 *   We can access file id without string processing.
 *   This is advantageous for deleting tag record when incremental updating.
 * 
 * [Concept of format version]
 *
 * Since GLOBAL's tag files are machine independent, they can be distributed
 * apart from GLOBAL itself. For example, if some network file system available,
 * client may execute global using server's tag files. In this case, both
 * GLOBAL are not necessarily the same version. So, we should assume that
 * older version of GLOBAL might access the tag files which generated
 * by new GLOBAL. To deal in such case, we decided to buried a version number
 * to both global(1) and tag files. The conclete procedure is like follows:
 *
 * 1. Gtags(1) bury the version number in tag files.
 * 2. Global(1) pick up the version number from a tag file. If the number
 *    is larger than its acceptable version number then global give up work
 *    any more and display error message.
 * 3. If version number is not found then it assumes version 1.
 *
 * [History of format version]
 *
 * GLOBAL-1.0 - 1.8     no idea about format version.
 * GLOBAL-1.9 - 2.24    understand format version.
 *                      support format version 1 (default).
 *                      if (format > 1) then print error message.
 * GLOBAL-3.0 - 4.5     support format version 1 and 2.
 *                      if (format > 2) then print error message.
 * GLOBAL-4.5.1 - 4.8.7 support format version 1, 2 and 3.
 *                      if (format > 3) then print error message.
 * GLOBAL-5.0 - 5.3     support format version only 4.
 *                      if (format !=  4) then print error message.
 * GLOBAL-5.4 -         support format version 4 and 5
 *                      if (format > 5 || format < 4) then print error message.
 *
 * In GLOBAL-5.0, we threw away the compatibility with the past formats.
 * Though we could continue the support for older formats, it seemed
 * not to be worthy. Because keeping maintaining the all formats hinders
 * new optimization and the function addition in the future.
 * Instead, the following error messages are displayed in a wrong usage.
 *       [older global and new tag file]
 *       $ global -x main
 *       GTAGS seems new format. Please install the latest GLOBAL.
 *       [new global and older tag file]
 *       $ global -x main
 *       GTAGS seems older format. Please remake tag files.
 */
static int upper_bound_version = 5;     /* acceptable format version (upper bound) */
static int lower_bound_version = 4;     /* acceptable format version (lower bound) */
static const char *tagslist[] = {"GPATH", "GTAGS", "GRTAGS", "GSYMS"};
/*
 * dbname: return db name
 *
 *      i)      db      0: GPATH, 1: GTAGS, 2: GRTAGS, 3: GSYMS
 *      r)              dbname
 */
const char *
dbname(int db)
{
        assert(db >= 0 && db < GTAGLIM);
        return tagslist[db];
}
/*
 * gtags_open: open global tag.
 *
 *      i)      dbpath  dbpath directory
 *      i)      root    root directory (needed when compact format)
 *      i)      db      GTAGS, GRTAGS, GSYMS
 *      i)      mode    GTAGS_READ: read only
 *                      GTAGS_CREATE: create tag
 *                      GTAGS_MODIFY: modify tag
 *      r)              GTOP structure
 *
 * when error occurred, gtagopen doesn't return.
 */
GTOP *
gtags_open(const char *dbpath, const char *root, int db, int mode)
{
        GTOP *gtop;
        int dbmode;

        gtop = (GTOP *)check_calloc(sizeof(GTOP), 1);
        gtop->db = db;
        gtop->mode = mode;
        gtop->format_version = 4;
        /*
         * Open tag file allowing duplicate records.
         */
        switch (gtop->mode) {
        case GTAGS_READ:
                dbmode = 0;
                break;
        case GTAGS_CREATE:
                dbmode = 1;
                break;
        case GTAGS_MODIFY:
                dbmode = 2;
                break;
        default:
                assert(0);
        }
        gtop->dbop = dbop_open(makepath(dbpath, dbname(db), NULL), dbmode, 0644, DBOP_DUP);
        if (gtop->dbop == NULL) {
                if (dbmode == 1)
                        die("cannot make %s.", dbname(db));
                die("%s not found.", dbname(db));
        }
        if (gtop->mode == GTAGS_CREATE) {
                /*
                 * Decide format.
                 */
                gtop->format = 0;
                gtop->format_version = 5;
                if (gtop->db == GTAGS)
                        gtop->format |= GTAGS_COMPRESS;
                gtop->format |= GTAGS_COMPNAME;
                if (gtop->db == GRTAGS || gtop->db == GSYMS) {
                        gtop->format |= GTAGS_COMPACT;
                        gtop->format |= GTAGS_COMPLINE;
                }
                if (gtop->format & GTAGS_COMPACT)
                        dbop_putoption(gtop->dbop, COMPACTKEY, NULL);
                if (gtop->format & GTAGS_COMPRESS) {
                        dbop_putoption(gtop->dbop, COMPRESSKEY, DEFAULT_ABBREVIATION);
                        abbrev_open(DEFAULT_ABBREVIATION);
                }
                if (gtop->format & GTAGS_COMPLINE)
                        dbop_putoption(gtop->dbop, COMPLINEKEY, NULL);
                if (gtop->format & GTAGS_COMPNAME)
                        dbop_putoption(gtop->dbop, COMPNAMEKEY, NULL);
                dbop_putversion(gtop->dbop, gtop->format_version); 
        } else {
                /*
                 * recognize format version of GTAGS. 'format version record'
                 * is saved as a META record in GTAGS and GRTAGS.
                 * if 'format version record' is not found, it's assumed
                 * version 1.
                 */
                const char *p;
                /*
                 * check format version.
                 */
                gtop->format_version = dbop_getversion(gtop->dbop);
                if (gtop->format_version > upper_bound_version)
                        die("%s seems new format. Please install the latest GLOBAL.", dbname(gtop->db));
                else if (gtop->format_version < lower_bound_version)
                        die("%s seems older format. Please remake tag files.", dbname(gtop->db));
                gtop->format = 0;
                if (dbop_getoption(gtop->dbop, COMPACTKEY) != NULL)
                        gtop->format |= GTAGS_COMPACT;
                if ((p = dbop_getoption(gtop->dbop, COMPRESSKEY)) != NULL) {
                        abbrev_open(p);
                        gtop->format |= GTAGS_COMPRESS;
                }
                if (dbop_getoption(gtop->dbop, COMPLINEKEY) != NULL)
                        gtop->format |= GTAGS_COMPLINE;
                if (dbop_getoption(gtop->dbop, COMPNAMEKEY) != NULL)
                        gtop->format |= GTAGS_COMPNAME;
        }
        if (gpath_open(dbpath, dbmode) < 0) {
                if (dbmode == 1)
                        die("cannot create GPATH.");
                else
                        die("GPATH not found.");
        }
        if (gtop->mode != GTAGS_READ)
                gtop->sb = strbuf_open(0);      /* This buffer is used for working area. */
        /*
         * Stuff for compact format.
         */
        if (gtop->format & GTAGS_COMPACT) {
                assert(root != NULL);
                strlimcpy(gtop->root, root, sizeof(gtop->root));
                if (gtop->mode != GTAGS_READ)
                        gtop->path_hash = strhash_open(HASHBUCKETS);
        }
        return gtop;
}
/*
 * gtags_put: put tag record with packing.
 *
 *      i)      gtop    descripter of GTOP
 *      i)      key     tag name
 *      i)      ctags_x tag line (ctags -x format)
 */
void
gtags_put(GTOP *gtop, const char *key, const char *ctags_x)     /* virtually const */
{
        SPLIT ptable;

        if (split((char *)ctags_x, 4, &ptable) != 4) {
                recover(&ptable);
                die("illegal tag format.\n'%s'", ctags_x);
        }
        if (gtop->format & GTAGS_COMPACT) {
                int *lno;
                struct sh_entry *entry;
                /*
                 * Flush the pool when path is changed.
                 * Line numbers in the pool will be sorted and duplicated
                 * records will be combined.
                 *
                 * pool    "funcA"   | 1| 3| 7|23|11| 2|...
                 *           v
                 * output  funcA 33 1,2,3,7,11,23...
                 */
                if (gtop->cur_path[0] && strcmp(gtop->cur_path, ptable.part[PART_PATH].start)) {
                        flush_pool(gtop);
                        strhash_reset(gtop->path_hash);
                }
                strlimcpy(gtop->cur_path, ptable.part[PART_PATH].start, sizeof(gtop->cur_path));
                /*
                 * Register each record into the pool.
                 *
                 * Pool image:
                 *
                 * tagname   lno
                 * ------------------------------
                 * "funcA"   | 1| 3| 7|23|11| 2|...
                 * "funcB"   |34| 2| 5|66| 3|...
                 * ...
                 */
                entry = strhash_assign(gtop->path_hash, key, 1);
                if (entry->value == NULL)
                        entry->value = varray_open(sizeof(int), 100);
                lno = varray_append((VARRAY *)entry->value);
                *lno = atoi(ptable.part[PART_LNO].start);
        } else {
                const char *s_fid = gpath_path2fid(ptable.part[PART_PATH].start, NULL);

                if (s_fid == NULL)
                        die("GPATH is corrupted.('%s' not found)", ptable.part[PART_PATH].start);
                strbuf_reset(gtop->sb);
                strbuf_puts(gtop->sb, s_fid);
                strbuf_putc(gtop->sb, ' ');
                if (gtop->format & GTAGS_COMPNAME)
                        strbuf_puts(gtop->sb, compress(ptable.part[PART_TAG].start, key));
                else
                        strbuf_puts(gtop->sb, ptable.part[PART_TAG].start);
                strbuf_putc(gtop->sb, ' ');
                strbuf_puts(gtop->sb, ptable.part[PART_LNO].start);
                strbuf_putc(gtop->sb, ' ');
                strbuf_puts(gtop->sb, gtop->format & GTAGS_COMPRESS ?
                        compress(ptable.part[PART_LINE].start, key) :
                        ptable.part[PART_LINE].start);
                dbop_put(gtop->dbop, key, strbuf_value(gtop->sb));
        }
        recover(&ptable);
}
/*
 * gtags_delete: delete records belong to set of fid.
 *
 *      i)      gtop    GTOP structure
 *      i)      deleteset bit array of fid
 */
void
gtags_delete(GTOP *gtop, IDSET *deleteset)
{
        const char *tagline;
        int fid;

        for (tagline = dbop_first(gtop->dbop, NULL, NULL, 0); tagline; tagline = dbop_next(gtop->dbop)) {
                /*
                 * Extract path from the tag line.
                 */
                fid = atoi(tagline);
                /*
                 * If the file id exists in the deleteset, delete the tagline.
                 */
                if (idset_contains(deleteset, fid))
                        dbop_delete(gtop->dbop, NULL);
        }
}
/*
 * gtags_first: return first record
 *
 *      i)      gtop    GTOP structure
 *      i)      pattern tag name
 *              o may be regular expression
 *              o may be NULL
 *      i)      flags   GTOP_PREFIX     prefix read
 *                      GTOP_KEY        read key only
 *                      GTOP_PATH       read path only
 *                      GTOP_NOREGEX    don't use regular expression.
 *                      GTOP_IGNORECASE ignore case distinction.
 *                      GTOP_BASICREGEX use basic regular expression.
 *                      GTOP_NOSORT     don't sort
 *      r)              record
 */
GTP *
gtags_first(GTOP *gtop, const char *pattern, int flags)
{
        int dbflags = 0;
        int regflags = 0;
        char prefix[IDENTLEN+1];
        static regex_t reg;
        regex_t *preg = &reg;
        const char *key = NULL;
        const char *tagline;

        /* Settlement for last time if any */
        if (gtop->path_hash) {
                strhash_close(gtop->path_hash);
                gtop->path_hash = NULL;
        }
        if (gtop->path_array) {
                free(gtop->path_array);
                gtop->path_array = NULL;
        }

        gtop->flags = flags;
        if (flags & GTOP_PREFIX && pattern != NULL)
                dbflags |= DBOP_PREFIX;
        if (flags & GTOP_KEY)
                dbflags |= DBOP_KEY;

        if (!(flags & GTOP_BASICREGEX))
                regflags |= REG_EXTENDED;
        if (flags & GTOP_IGNORECASE)
                regflags |= REG_ICASE;
        if (gtop->format & GTAGS_COMPACT)
                gtop->fp = NULL;
        /*
         * Get key and compiled regular expression for dbop_xxxx().
         */
        if (flags & GTOP_NOREGEX) {
                key = pattern;
                preg = NULL;
        } else if (pattern == NULL || !strcmp(pattern, ".*")) {
                /*
                 * Since the regular expression '.*' matches to any record,
                 * we take sequential read method.
                 */
                key = NULL;
                preg = NULL;
        } else if (isregex(pattern) && regcomp(preg, pattern, regflags) == 0) {
                const char *p;
                /*
                 * If the pattern include '^' + some non regular expression
                 * characters like '^aaa[0-9]', we take prefix read method
                 * with the non regular expression part as the prefix.
                 */
                if (!(flags & GTOP_IGNORECASE) && *pattern == '^' && *(p = pattern + 1) && !isregexchar(*p)) {
                        int i = 0;

                        while (*p && !isregexchar(*p) && i < IDENTLEN)
                                prefix[i++] = *p++;
                        prefix[i] = '\0';
                        key = prefix;
                        dbflags |= DBOP_PREFIX;
                } else {
                        key = NULL;
                }
        } else {
                key = pattern;
                preg = NULL;
        }
        /*
         * If GTOP_PATH is set, at first, we collect all path names in a pool and
         * sort them. gtags_first() and gtags_next() returns one of the pool.
         */
        if (gtop->flags & GTOP_PATH) {
                struct sh_entry *entry;
                char *p;
                const char *cp;
                unsigned long i;

                gtop->path_hash = strhash_open(HASHBUCKETS);
                /*
                 * Pool path names.
                 *
                 * fid          path name
                 * +--------------------------
                 * |100         ./aaa/a.c
                 * |105         ./aaa/b.c
                 *  ...
                 */
                for (tagline = dbop_first(gtop->dbop, key, preg, dbflags);
                     tagline != NULL;
                     tagline = dbop_next(gtop->dbop))
                {
                        /* extract file id */
                        p = locatestring(tagline, " ", MATCH_FIRST);
                        if (p == NULL)
                                die("Illegal tag record. '%s'\n", tagline);
                        *p = '\0';
                        entry = strhash_assign(gtop->path_hash, tagline, 1);
                        /* new entry: get path name and set. */
                        if (entry->value == NULL) {
                                cp = gpath_fid2path(tagline, NULL);
                                if (cp == NULL)
                                        die("GPATH is corrupted.(file id '%s' not found)", tagline);
                                entry->value = strhash_strdup(gtop->path_hash, cp, 0);
                        }
                }
                /*
                 * Sort path names.
                 *
                 * fid          path name       path_array (sort)
                 * +--------------------------  +---+
                 * |100         ./aaa/a.c <-------* |
                 * |105         ./aaa/b.c <-------* |
                 *  ...                         ...
                 */
                gtop->path_array = (char **)check_malloc(gtop->path_hash->entries * sizeof(char *));
                i = 0;
                for (entry = strhash_first(gtop->path_hash); entry != NULL; entry = strhash_next(gtop->path_hash))
                        gtop->path_array[i++] = entry->value;
                if (i != gtop->path_hash->entries)
                        die("Something is wrong. 'i = %lu, entries = %lu'" , i, gtop->path_hash->entries);
                if (!(gtop->flags & GTOP_NOSORT))
                        qsort(gtop->path_array, gtop->path_hash->entries, sizeof(char *), compare_path);
                gtop->path_count = gtop->path_hash->entries;
                gtop->path_index = 0;

                if (gtop->path_index >= gtop->path_count)
                        return NULL;
                gtop->gtp.path = gtop->path_array[gtop->path_index++];
                return &gtop->gtp;
        } else if (gtop->flags & GTOP_KEY) {
                return ((gtop->gtp.tag = dbop_first(gtop->dbop, key, preg, dbflags)) == NULL)
                        ? NULL : &gtop->gtp;
        } else {
                if (gtop->vb == NULL)
                        gtop->vb = varray_open(sizeof(GTP), 200);
                else
                        varray_reset(gtop->vb);
                if (gtop->segment_pool == NULL)
                        gtop->segment_pool = pool_open();
                else
                        pool_reset(gtop->segment_pool);
                if (gtop->path_hash == NULL)
                        gtop->path_hash = strhash_open(HASHBUCKETS);
                else
                        strhash_reset(gtop->path_hash);
                tagline = dbop_first(gtop->dbop, key, preg, dbflags);
                if (tagline == NULL)
                        return NULL;
                /*
                 * Dbop_next() wil read the same record again.
                 */
                dbop_unread(gtop->dbop);
                /*
                 * Read a tag segment with sorting.
                 */
                segment_read(gtop);
                return  &gtop->gtp_array[gtop->gtp_index++];
        }
}
/*
 * gtags_next: return next record.
 *
 *      i)      gtop    GTOP structure
 *      r)              record
 *                      NULL end of tag
 */
GTP *
gtags_next(GTOP *gtop)
{
        if (gtop->flags & GTOP_PATH) {
                if (gtop->path_index >= gtop->path_count)
                        return NULL;
                gtop->gtp.path = gtop->path_array[gtop->path_index++];
                return &gtop->gtp;
        } else if (gtop->flags & GTOP_KEY) {
                return ((gtop->gtp.tag = dbop_next(gtop->dbop)) == NULL)
                        ? NULL : &gtop->gtp;
        } else {
                /*
                 * End of segment.
                 * Reset resources and read new segment again.
                 */
                if (gtop->gtp_index >= gtop->gtp_count) {
                        varray_reset(gtop->vb);
                        pool_reset(gtop->segment_pool);
                        /* strhash_reset(gtop->path_hash); */
                        segment_read(gtop);
                }
                if (gtop->gtp_index >= gtop->gtp_count)
                        return NULL;
                return &gtop->gtp_array[gtop->gtp_index++];
        }
}
/*
 * gtags_close: close tag file
 *
 *      i)      gtop    GTOP structure
 */
void
gtags_close(GTOP *gtop)
{
        if (gtop->format & GTAGS_COMPACT && gtop->fp != NULL)
                fclose(gtop->fp);
        if (gtop->format & GTAGS_COMPRESS)
                abbrev_close();
        if (gtop->format & GTAGS_COMPACT && gtop->cur_path[0])
                flush_pool(gtop);
        if (gtop->segment_pool)
                pool_close(gtop->segment_pool);
        if (gtop->path_array)
                free(gtop->path_array);
        if (gtop->sb)
                strbuf_close(gtop->sb);
        if (gtop->vb)
                varray_close(gtop->vb);
        if (gtop->path_hash)
                strhash_close(gtop->path_hash);
        gpath_close();
        dbop_close(gtop->dbop);
        free(gtop);
}
/*
 * flush_pool: flush the pool and write is as compact format.
 *
 *      i)      gtop    descripter of GTOP
 */
static void
flush_pool(GTOP *gtop)
{
        struct sh_entry *entry;
        const char *s_fid = gpath_path2fid(gtop->cur_path, NULL);
        int header_offset;
        int i, last;

        if (s_fid == NULL)
                die("GPATH is corrupted.('%s' not found)", gtop->cur_path);
        /*
         * Write records as compact format and free line number table
         * for each entry in the pool.
         */
        for (entry = strhash_first(gtop->path_hash); entry; entry = strhash_next(gtop->path_hash)) {
                VARRAY *vb = (VARRAY *)entry->value;
                int *lno_array = varray_assign(vb, 0, 0);
                const char *key = entry->name;

                /*
                 * extract method when class method definition.
                 *
                 * Ex: Class::method(...)
                 *
                 * key  = 'method'
                 * data = 'Class::method  103 ./class.cpp ...'
                 */
                if (gtop->flags & GTAGS_EXTRACTMETHOD) {
                        if ((key = locatestring(entry->name, ".", MATCH_LAST)) != NULL)
                                key++;
                        else if ((key = locatestring(entry->name, "::", MATCH_LAST)) != NULL)
                                key += 2;
                        else
                                key = entry->name;
                }
                /* Sort line number table */
                qsort(lno_array, vb->length, sizeof(int), compare_lineno); 

                strbuf_reset(gtop->sb);
                strbuf_puts(gtop->sb, s_fid);
                strbuf_putc(gtop->sb, ' ');
                if (gtop->format & GTAGS_COMPNAME) {
                        strbuf_puts(gtop->sb, compress(entry->name, key));
                } else {
                        strbuf_puts(gtop->sb, entry->name);
                }
                strbuf_putc(gtop->sb, ' ');
                header_offset = strbuf_getlen(gtop->sb);
                /*
                 * If GTAGS_COMPLINE flag is set, each line number is expressed as the
                 * difference from the previous line number except for the head.
                 * GTAGS_COMPLINE is set by default in format version 5.
                 */
                if (gtop->format & GTAGS_COMPLINE) {
                        int cont = 0;

                        last = 0;                       /* line 0 doesn't exist */
                        for (i = 0; i < vb->length; i++) {
                                int n = lno_array[i];

                                if (n == last)
                                        continue;
                                if (last > 0 && n == last + 1) {
                                        if (!cont) {
                                                /*
                                                 * Don't use range expression at the head.
                                                 */
                                                if (strbuf_getlen(gtop->sb) == header_offset)
                                                        strbuf_putn(gtop->sb, n);
                                                else
                                                        cont = last;
                                        }
                                } else {
                                        /*
                                         * Range expression. ex: 10-2 means 10 11 12
                                         */
                                        if (cont) {
                                                strbuf_putc(gtop->sb, '-');
                                                strbuf_putn(gtop->sb, last - cont);
                                                cont = 0;
                                        }
                                        if (strbuf_getlen(gtop->sb) > header_offset) {
                                                strbuf_putc(gtop->sb, ',');
                                                strbuf_putn(gtop->sb, n - last);
                                        } else {
                                                strbuf_putn(gtop->sb, n);
                                        }
                                        if (strbuf_getlen(gtop->sb) > DBOP_PAGESIZE / 4) {
                                                dbop_put(gtop->dbop, key, strbuf_value(gtop->sb));
                                                strbuf_setlen(gtop->sb, header_offset);
                                        }
                                }
                                last = n;
                        }
                        if (cont) {
                                strbuf_putc(gtop->sb, '-');
                                strbuf_putn(gtop->sb, last - cont);
                        }
                } else {
                        /*
                         * This code is to support older format (version 4).
                         */
                        last = 0;                       /* line 0 doesn't exist */
                        for (i = 0; i < vb->length; i++) {
                                int n = lno_array[i];

                                if (n == last)
                                        continue;
                                if (strbuf_getlen(gtop->sb) > header_offset)
                                        strbuf_putc(gtop->sb, ',');
                                strbuf_putn(gtop->sb, n);
                                if (strbuf_getlen(gtop->sb) > DBOP_PAGESIZE / 4) {
                                        dbop_put(gtop->dbop, key, strbuf_value(gtop->sb));
                                        strbuf_setlen(gtop->sb, header_offset);
                                }
                                last = n;
                        }
                }
                if (strbuf_getlen(gtop->sb) > header_offset)
                        dbop_put(gtop->dbop, key, strbuf_value(gtop->sb));
                /* Free line number table */
                varray_close(vb);
        }
}
/*
 * Read a tag segment with sorting.
 *
 *      i)      gtop    GTOP structure
 *      o)      gtop->gtp_array         segment table
 *      o)      gtop->gtp_count         segment table size
 *      o)      gtop->gtp_index         segment table index (initial value = 0)
 *      o)      gtop->cur_tagname       current tag name
 *
 * A segment is a set of tag records which have same tag name.
 * This function read a segment from tag file, sort it and put it on segment table.
 * This function can treat both of standard format and compact format.
 *
 * Sorting is done by three keys.
 *      1st key: tag name
 *      2nd key: file name
 *      3rd key: line number
 * Since all records in a segment have same tag name, you need not think about 1st key.
 */
void
segment_read(GTOP *gtop)
{
        const char *tagline, *fid, *path, *lineno;
        GTP *gtp;
        struct sh_entry *sh;

        /*
         * Save tag lines.
         */
        gtop->cur_tagname[0] = '\0';
        while ((tagline = dbop_next(gtop->dbop)) != NULL) {
                /*
                 * get tag name and line number.
                 *
                 * tagline = <file id> <tag name> <line number>
                 */
                if (gtop->cur_tagname[0] == '\0') {
                        strlimcpy(gtop->cur_tagname, gtop->dbop->lastkey, sizeof(gtop->cur_tagname));
                } else if (strcmp(gtop->cur_tagname, gtop->dbop->lastkey) != 0) {
                        /*
                         * Dbop_next() wil read the same record again.
                         */
                        dbop_unread(gtop->dbop);
                        break;
                }
                gtp = varray_append(gtop->vb);
                gtp->tagline = pool_strdup(gtop->segment_pool, tagline, 0);
                gtp->tag = (const char *)gtop->cur_tagname;
                /*
                 * convert fid into hashed path name to save memory.
                 */
                fid = (const char *)strmake(tagline, " ");
                path = gpath_fid2path(fid, NULL);
                if (path == NULL)
                        die("gtags_first: path not found. (fid=%s)", fid);
                sh = strhash_assign(gtop->path_hash, path, 1);
                gtp->path = sh->name;
                lineno = seekto(gtp->tagline, SEEKTO_LINENO);
                if (lineno == NULL)
                        die("illegal tag record.\n%s", tagline);
                gtp->lineno = atoi(lineno);
        }
        /*
         * Sort tag lines.
         */
        gtop->gtp_array = varray_assign(gtop->vb, 0, 0);
        gtop->gtp_count = gtop->vb->length;
        gtop->gtp_index = 0;
        if (!(gtop->flags & GTOP_NOSORT))
                qsort(gtop->gtp_array, gtop->gtp_count, sizeof(GTP), compare_tags);
}

/* [<][>][^][v][top][bottom][index][help] */