sort.c

   1 /*
   2 *   $Id: sort.c 747 2009-11-06 02:33:37Z dhiebert $
   3 *
   4 *   Copyright (c) 1996-2002, Darren Hiebert
   5 *
   6 *   This source code is released for free distribution under the terms of the
   7 *   GNU General Public License.
   8 *
   9 *   This module contains functions to sort the tag entries.
  10 */
  11
  12 /*
  13 *   INCLUDE FILES
  14 */
  15 #include "general.h"  /* must always come first */
  16
  17 #if defined (HAVE_STDLIB_H)
  18 # include <stdlib.h>  /* to declare malloc () */
  19 #endif
  20 #include <string.h>
  21 #include <stdio.h>
  22
  23 #include "debug.h"
  24 #include "entry.h"
  25 #include "options.h"
  26 #include "read.h"
  27 #include "routines.h"
  28 #include "sort.h"
  29
  30 /*
  31 *   FUNCTION DEFINITIONS
  32 */
  33
  34 extern void catFile (const char *const name)
  35 {
  36         FILE *const fp = fopen (name, "r");
  37
  38         if (fp != NULL)
  39         {
  40                 int c;
  41                 while ((c = getc (fp)) != EOF)
  42                         putchar (c);
  43                 fflush (stdout);
  44                 fclose (fp);
  45         }
  46 }
  47
  48 #ifdef EXTERNAL_SORT
  49
  50 #ifdef NON_CONST_PUTENV_PROTOTYPE
  51 # define PE_CONST
  52 #else
  53 # define PE_CONST const
  54 #endif
  55
  56 extern void externalSortTags (const boolean toStdout)
  57 {
  58         const char *const sortNormalCommand = "sort -u -o";
  59         const char *const sortFoldedCommand = "sort -u -f -o";
  60         const char *sortCommand =
  61                 Option.sorted == SO_FOLDSORTED ? sortFoldedCommand : sortNormalCommand;
  62         PE_CONST char *const sortOrder1 = "LC_COLLATE=C";
  63         PE_CONST char *const sortOrder2 = "LC_ALL=C";
  64         const size_t length = 4 + strlen (sortOrder1) + strlen (sortOrder2) +
  65                         strlen (sortCommand) + (2 * strlen (tagFileName ()));
  66         char *const cmd = (char *) malloc (length + 1);
  67         int ret = -1;
  68
  69         if (cmd != NULL)
  70         {
  71                 /*  Ensure ASCII value sort order.
  72                  */
  73 #ifdef HAVE_SETENV
  74                 setenv ("LC_COLLATE", "C", 1);
  75                 setenv ("LC_ALL", "C", 1);
  76                 sprintf (cmd, "%s %s %s", sortCommand, tagFileName (), tagFileName ());
  77 #else
  78 # ifdef HAVE_PUTENV
  79                 putenv (sortOrder1);
  80                 putenv (sortOrder2);
  81                 sprintf (cmd, "%s %s %s", sortCommand, tagFileName (), tagFileName ());
  82 # else
  83                 sprintf (cmd, "%s %s %s %s %s", sortOrder1, sortOrder2, sortCommand,
  84                                 tagFileName (), tagFileName ());
  85 # endif
  86 #endif
  87                 verbose ("system (\"%s\")\n", cmd);
  88                 ret = system (cmd);
  89                 free (cmd);
  90
  91         }
  92         if (ret != 0)
  93                 error (FATAL | PERROR, "cannot sort tag file");
  94         else if (toStdout)
  95                 catFile (tagFileName ());
  96 }
  97
  98 #else
  99
 100 /*
 101  *  These functions provide a basic internal sort. No great memory
 102  *  optimization is performed (e.g. recursive subdivided sorts),
 103  *  so have lots of memory if you have large tag files.
 104  */
 105
 106 static void failedSort (FILE *const fp, const char* msg)
 107 {
 108         const char* const cannotSort = "cannot sort tag file";
 109         if (fp != NULL)
 110                 fclose (fp);
 111         if (msg == NULL)
 112                 error (FATAL | PERROR, "%s", cannotSort);
 113         else
 114                 error (FATAL, "%s: %s", msg, cannotSort);
 115 }
 116
 117 static int compareTagsFolded(const void *const one, const void *const two)
 118 {
 119         const char *const line1 = *(const char* const*) one;
 120         const char *const line2 = *(const char* const*) two;
 121
 122         return struppercmp (line1, line2);
 123 }
 124
 125 static int compareTags (const void *const one, const void *const two)
 126 {
 127         const char *const line1 = *(const char* const*) one;
 128         const char *const line2 = *(const char* const*) two;
 129
 130         return strcmp (line1, line2);
 131 }
 132
 133 static void writeSortedTags (
 134                 char **const table, const size_t numTags, const boolean toStdout)
 135 {
 136         FILE *fp;
 137         size_t i;
 138
 139         /*  Write the sorted lines back into the tag file.
 140          */
 141         if (toStdout)
 142                 fp = stdout;
 143         else
 144         {
 145                 fp = fopen (tagFileName (), "w");
 146                 if (fp == NULL)
 147                         failedSort (fp, NULL);
 148         }
 149         for (i = 0 ; i < numTags ; ++i)
 150         {
 151                 /*  Here we filter out identical tag *lines* (including search
 152                  *  pattern) if this is not an xref file.
 153                  */
 154                 if (i == 0  ||  Option.xref  ||  strcmp (table [i], table [i-1]) != 0)
 155                         if (fputs (table [i], fp) == EOF)
 156                                 failedSort (fp, NULL);
 157         }
 158         if (toStdout)
 159                 fflush (fp);
 160         else
 161                 fclose (fp);
 162 }
 163
 164 extern void internalSortTags (const boolean toStdout)
 165 {
 166         vString *vLine = vStringNew ();
 167         FILE *fp = NULL;
 168         const char *line;
 169         size_t i;
 170         int (*cmpFunc)(const void *, const void *);
 171
 172         /*  Allocate a table of line pointers to be sorted.
 173          */
 174         size_t numTags = TagFile.numTags.added + TagFile.numTags.prev;
 175         const size_t tableSize = numTags * sizeof (char *);
 176         char **const table = (char **) malloc (tableSize);  /* line pointers */
 177         DebugStatement ( size_t mallocSize = tableSize; )  /* cumulative total */
 178
 179
 180         cmpFunc = Option.sorted == SO_FOLDSORTED ? compareTagsFolded : compareTags;
 181         if (table == NULL)
 182                 failedSort (fp, "out of memory");
 183
 184         /*  Open the tag file and place its lines into allocated buffers.
 185          */
 186         fp = fopen (tagFileName (), "r");
 187         if (fp == NULL)
 188                 failedSort (fp, NULL);
 189         for (i = 0  ;  i < numTags  &&  ! feof (fp)  ;  )
 190         {
 191                 line = readLine (vLine, fp);
 192                 if (line == NULL)
 193                 {
 194                         if (! feof (fp))
 195                                 failedSort (fp, NULL);
 196                         break;
 197                 }
 198                 else if (*line == '\0'  ||  strcmp (line, "\n") == 0)
 199                         ;  /* ignore blank lines */
 200                 else
 201                 {
 202                         const size_t stringSize = strlen (line) + 1;
 203
 204                         table [i] = (char *) malloc (stringSize);
 205                         if (table [i] == NULL)
 206                                 failedSort (fp, "out of memory");
 207                         DebugStatement ( mallocSize += stringSize; )
 208                         strcpy (table [i], line);
 209                         ++i;
 210                 }
 211         }
 212         numTags = i;
 213         fclose (fp);
 214         vStringDelete (vLine);
 215
 216         /*  Sort the lines.
 217          */
 218         qsort (table, numTags, sizeof (*table), cmpFunc);
 219
 220         writeSortedTags (table, numTags, toStdout);
 221
 222         PrintStatus (("sort memory: %ld bytes\n", (long) mallocSize));
 223         for (i = 0 ; i < numTags ; ++i)
 224                 free (table [i]);
 225         free (table);
 226 }
 227
 228 #endif
 229
 230 /* vi:set tabstop=4 shiftwidth=4: */