cde/lib/DtSearch/msgutil.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /*
  24  *   COMPONENT_NAME: austext
  25  *
  26  *   FUNCTIONS: austext_malloc
  27  *              clean_wrap
  28  *              cutnode_llist
  29  *              free_llist
  30  *              join_llists
  31  *              merge_llist
  32  *              nowstring
  33  *              pop_llist
  34  *              sort_llist
  35  *              split_llist
  36  *
  37  *   ORIGINS: 27
  38  *
  39  *
  40  *   (C) COPYRIGHT International Business Machines Corp. 1991,1995
  41  *   All Rights Reserved
  42  *   Licensed Materials - Property of IBM
  43  *   US Government Users Restricted Rights - Use, duplication or
  44  *   disclosure restricted by GSA ADP Schedule Contract with IBM Corp.
  45  */
  46 /*************************** MSGUTIL.C *************************
  47  * $XConsortium: msgutil.c /main/9 1996/11/25 18:47:48 drk $
  48  * August 1991.
  49  * Utilites for generic manipulation of linked lists and binary trees.
  50  * All utilities require that the link fields be the first fields
  51  * in each structure.  Also includes an error message mechanism
  52  * that is absolutely independent of user interface (UI)--
  53  * not even stdio is used.  The trick is to append all
  54  * error/information messages to the end of a linked list that
  55  * eventually will be returned to the UI to be displayed
  56  * in whatever manner is appropriate.  (However a generic stdio
  57  * print facility for the linked msglists is also provided
  58  * for dumping the list before crashing or when stdio is ok).
  59  *
  60  * With 2 exceptions, all messages should contain only
  61  * printable ascii characters and the space character.
  62  * Control characters and extended ascii graphics chars are verboten.
  63  * The exceptions are \n and \r, which are always permitted.
  64  *
  65  * The most common fatal error in opera and other text analysis
  66  * systems occurs when a memory allocation fails.  Therefore
  67  * this module contains a generic 'safe malloc' function
  68  * which tests for failure and prints all outstanding messages
  69  * before exiting if malloc fails.  It also uses DtSearchExit()
  70  * for the actual abort so other system dependent stuff can be
  71  * performed before going down.
  72  *
  73  * $Log$
  74  * Revision 2.4  1996/03/05  17:58:29  miker
  75  * Replace isspace() with ref to locale independent ascii_charmap[].
  76  *
  77  * Revision 2.3  1995/10/25  16:46:00  miker
  78  * Added prolog.
  79  *
  80  * Revision 2.2  1995/10/19  20:58:05  miker
  81  * Fix segfault in cleanwrap() if text contains single word > wraplen.
  82  *
  83  * Revision 2.1  1995/09/22  21:20:35  miker
  84  * Freeze DtSearch 0.1, AusText 2.1.8
  85  *
  86  * Revision 1.8  1995/09/05  18:21:23  miker
  87  * For DtSearch, rename and move universal msglist functions to msgs.c.
  88  */
  89 #include "SearchP.h"
  90 /****#include <ctype.h>****/
  91 #include <string.h>
  92 #include <stdlib.h>
  93 #define XOS_USE_NO_LOCKING
  94 #define X_INCLUDE_TIME_H
  95 #include <X11/Xos_r.h>
  96
  97 #define PROGNAME        "MSGUTIL"
  98 #define MAX_LINELEN     77
  99 #define MS_misc         1
 100
 101 CMPLL compare_llist = NULL;     /* global function pointer */
 102
 103 /************************************************/
 104 /*                                              */
 105 /*                 nowstring                    */
 106 /*                                              */
 107 /************************************************/
 108 /* Returns ptr to static string where the current time
 109  * is formatted in human readable form.  Used in audit
 110  * records, debugging logs, and error messages.
 111  */
 112 char           *nowstring (time_t * now)
 113 {
 114     static char     buf[128];
 115     time_t          mynow;
 116     struct tm *     time_ptr;
 117     _Xltimeparams   localtime_buf;
 118
 119     if (now == NULL) {
 120         now = &mynow;
 121         time (now);
 122     }
 123     time_ptr = _XLocaltime(now, localtime_buf);
 124     strftime (buf, sizeof (buf),
 125         catgets (dtsearch_catd, MS_misc, 2, "%Y/%m/%d,%H:%M:%S"),
 126         time_ptr);
 127     return buf;
 128 }  /* nowstring() */
 129
 130
 131 /************************************************/
 132 /*                                              */
 133 /*                 free_llist                   */
 134 /*                                              */
 135 /************************************************/
 136 /* Frees storage for all items in an LLIST and
 137  * sets it top-of-list pointer to NULL.  This works only for lists
 138  * created by append_msglist, append_textblobs, and other LLIST
 139  * structures where the data and the node itself
 140  * are allocated in one call to malloc().
 141  */
 142 void            free_llist (LLIST ** llhead)
 143 {
 144     LLIST          *next;
 145     LLIST          *ll = *llhead;
 146     while (ll != NULL) {
 147         next = ll->link;
 148         free (ll);
 149         ll = next;
 150     }
 151     *llhead = NULL;
 152     return;
 153 }  /* free_llist() */
 154
 155 /************************************************/
 156 /*                                              */
 157 /*                 join_llists                  */
 158 /*                                              */
 159 /************************************************/
 160 /* Merges two list by appending sublist to end of mainlist,
 161  * then setting sublist to NULL.  Originally either list can be NULL.
 162  * Mainlist is represented by ptr to ptr so it can be modified if NULL.
 163  * Sublist is ptr to ptr so it can be SET to NULL after join.
 164  * Method:
 165  * Init pp = ptr to first 'link' field in list,
 166  * i.e. the ptr to a ptr passed by the caller.
 167  * Usually this will be the addr of the top of the list pointer.
 168  * Then advance it to point to the last link in the list.
 169  *
 170  * Note that this function works for any LLIST including those
 171  * whose 'data' pointer is not allocated concurrently with the node.
 172  */
 173 void            join_llists (LLIST ** mainlist, LLIST ** sublist)
 174 {
 175     LLIST         **pp;
 176     for (pp = mainlist; *pp != NULL; pp = &((*pp)->link));
 177     *pp = *sublist;
 178     *sublist = NULL;
 179     return;
 180 }  /* join_llists() */
 181
 182
 183 /************************************************/
 184 /*                                              */
 185 /*                pop_llist                     */
 186 /*                                              */
 187 /************************************************/
 188 /* Detaches first node in an llist and returns it.
 189  * If *llistp is empty return NULL, else set *llistp to the link
 190  * cell of the first LLIST node on *llistp and return a pointer to
 191  * the first LLIST node on *llistp.  Used mainly by merge_llist(),
 192  * which is itself called by sort_llist(), but can be called by
 193  * anyone needing to remove the first element of an llist.
 194  */
 195 LLIST          *pop_llist (LLIST ** llistp)
 196 {
 197     LLIST          *first_node = *llistp;
 198     if (first_node != NULL)
 199         *llistp = first_node->link;
 200     return first_node;
 201 }  /* pop_llist() */
 202
 203
 204 /************************************************/
 205 /*                                              */
 206 /*                cutnode_llist                 */
 207 /*                                              */
 208 /************************************************/
 209 /* Detaches any specified node in an llist and rejoins the
 210  * loose ends of the llist.  *llistp may become NULL.
 211  * Returns NULL if *llistp is initially NULL or if node is not on llist,
 212  * else returns the detached node.
 213  */
 214 LLIST          *cutnode_llist (LLIST * node, LLIST ** llistp)
 215 {
 216     LLIST         **pp; /* link addr pointing to current node */
 217     for (pp = llistp; *pp != NULL; pp = &((*pp)->link)) {
 218         if (*pp == node)
 219             break;
 220     }
 221     if (*pp == NULL)
 222         return NULL;
 223     *pp = node->link;   /* join the loose ends */
 224     return node;
 225 }  /* cutnode_llist() */
 226
 227
 228 /************************************************/
 229 /*                                              */
 230 /*                 split_llist                  */
 231 /*                                              */
 232 /************************************************/
 233 /* Subroutine of sort_llist().
 234  * Find the middle node in lst. Set its 'link' pointer to NULL.
 235  * Return the remainder of lst, i.e. a pointer to the
 236  * next node after the middle node.
 237  */
 238 static LLIST   *split_llist (LLIST * lst)
 239 {
 240     LLIST          *tail = lst->link;
 241     if (lst == NULL || tail == NULL)
 242         return lst;
 243     /* advance 'tail' to end of list, and advance 'lst' only half as often */
 244     while ((tail != NULL) && ((tail = tail->link) != NULL)) {
 245         lst = lst->link;
 246         tail = tail->link;
 247     }
 248     tail = lst->link;
 249     lst->link = NULL;
 250     return tail;
 251 }  /* split_llist() */
 252
 253
 254 /************************************************/
 255 /*                                              */
 256 /*               merge_llist                    */
 257 /*                                              */
 258 /************************************************/
 259 /* Subroutine of sort_llist().  Merges two sorted LLISTs together. */
 260 static LLIST   *merge_llist (LLIST * l1, LLIST * l2)
 261 {
 262     LLIST          *myqueue = NULL;
 263     LLIST          *myend = NULL;
 264     LLIST          *mynext;
 265
 266     while ((l1 != NULL) && (l2 != NULL)) {
 267         /*
 268          * Perform ENQUEUE function. Next item popped off a list is
 269          * the next one in sorted order. It is added to END of
 270          * myqueue to maintain order. THIS IS WHERE THE ACTUAL SORT
 271          * COMPARE FUNCTION IS PERFORMED.
 272          */
 273         mynext = (compare_llist (l1, l2) < 0) ?
 274             pop_llist (&l1) : pop_llist (&l2);
 275         mynext->link = NULL;
 276         if (myqueue == NULL)
 277             myqueue = mynext;
 278         else
 279             myend->link = mynext;
 280         myend = mynext;
 281     }
 282
 283     /* attach the remainder of whichever list is left to the end of queue */
 284     if (l1 != NULL)
 285         myend->link = l1;
 286     if (l2 != NULL)
 287         myend->link = l2;
 288     return myqueue;
 289 }  /* merge_llist() */
 290
 291
 292 /************************************************/
 293 /*                                              */
 294 /*                sort_llist                    */
 295 /*                                              */
 296 /************************************************/
 297 /* Sorts a list of LLIST structures and returns ptr to sorted list.
 298  * The basic idea is to sort by recursively splitting a list
 299  * into two equal halves and sorting each of those.  The recursion
 300  * ends when there are only two small lists which are either
 301  * already sorted or are swapped.  This sort rarely runs out
 302  * of stack space because each recursion cuts the list length in
 303  * half so there are at most 1 + log-N-to-the-base-2 items on the stack.
 304  * (e.g. 64,000 nodes = max stack depth of 16:  2**16 = 64K).
 305  *
 306  * The compare function accepts pointers to two LLIST structures.
 307  * It returns <0, =0, or >0 based on whether the first structure (left)
 308  * is <, =, or > the second (right) structure in sort order.
 309  * For efficiency's sake, a pointer to the compare function is placed
 310  * in the global variable 'compare_llist' before calling
 311  * sort_llist the first time, rather than continually
 312  * passing it to all these nested functions.
 313  */
 314 LLIST          *sort_llist (LLIST * lst)
 315 {
 316     LLIST          *lst2;
 317     if ((lst == NULL) || (lst->link == NULL))
 318         return lst;
 319     lst2 = split_llist (lst);
 320     return merge_llist (sort_llist (lst), sort_llist (lst2));
 321 }  /* sort_llist() */
 322
 323
 324 /************************************************/
 325 /*                                              */
 326 /*                austext_malloc                */
 327 /*                                              */
 328 /************************************************/
 329 /* 'location' may be NULL.  Last arg (formerly msglist) is isgnored.
 330  * Renamed from safe_malloc() to force compile errors if args not changed.
 331  */
 332 void           *austext_malloc (size_t size, char *location, void *ignore)
 333 {
 334     static void    *ptr;
 335     char           *outofmem_msg;
 336
 337     if ((ptr = malloc (size)) != NULL)
 338         return ptr;
 339
 340     ptr = ((aa_argv0) ? aa_argv0 : "");
 341     if (location == NULL)
 342         location = catgets (dtsearch_catd, MS_misc, 1, "<null>");
 343     outofmem_msg = catgets (dtsearch_catd, MS_misc, 3,
 344         "*** %sOut of Memory at %s asking for %lu bytes! ***\n");
 345     fprintf (aa_stderr, outofmem_msg, ptr, location, size);
 346     fflush (aa_stderr);
 347     if (ausapi_msglist)
 348         fprintf (aa_stderr, "%s\n", DtSearchGetMessages ());
 349     fflush (aa_stderr);
 350     DtSearchExit (43);
 351     return NULL;
 352 }  /* austext_malloc */
 353
 354 /************************************************/
 355 /*                                              */
 356 /*                 clean_wrap                   */
 357 /*                                              */
 358 /************************************************/
 359 /* Utility which provides a way of breaking up long
 360  * messages which contain no control characters into lines
 361  * whose linefeed breaks occur at even word boundaries,
 362  * and whose lengths are controlled by the caller.
 363  * It should only be called when text itself may be
 364  * modified and may safely contain a linefeed (ascii 0x0A).
 365  * Converts a long text string into several lines by overlaying
 366  * the whitespace char nearest to the end of every line with \n.
 367  * Restarts length count if \n is found already within string.
 368  * Does nothing if passed wrap length = 0.
 369  * Does not append \n to end of string.  Does not alter string length.
 370  * Returns total number of lines (\n's + trailing piece of last line),
 371  * or returns 0 if wraplen == 0.
 372  */
 373 int             clean_wrap (char *string, int wraplen)
 374 {
 375     char           *nlptr, *breakptr;
 376     int             linecount = 0;
 377
 378     if (wraplen <= 0)
 379         return 0;
 380     while (strlen (string) > wraplen) {
 381         breakptr = string + wraplen;
 382
 383         /* Look for \n within the next wraplen */
 384         for (nlptr = string; nlptr < breakptr; nlptr++)
 385             if (*nlptr == '\n')
 386                 break;
 387         if (nlptr < breakptr) {
 388             string = ++nlptr;
 389             goto LINE_DONE;
 390         }
 391
 392         /* Otherwise back up to the first whitespace before last word */
 393         for (nlptr = breakptr - 1;  nlptr > string;  nlptr--)
 394             if (ascii_charmap[*nlptr] & WHITESPACE) {
 395                 *nlptr = '\n';
 396                 string = ++nlptr;
 397                 goto LINE_DONE;
 398             }
 399
 400         /* No whitespace at all in "text" before wraplen!
 401          * No choice but to overlay the last char.
 402          */
 403         *(--breakptr) = '\n';
 404         string = ++breakptr;
 405
 406 LINE_DONE:
 407         linecount++;
 408     }
 409
 410     /* Done wrapping.  now just count remaining lines in string. */
 411     while (*string != 0)
 412         if (*string++ == '\n')
 413             linecount++;
 414     if (*(string - 1) != '\n')
 415         linecount++;
 416     return linecount;
 417 }  /* clean_wrap() */
 418
 419 /********************** MSGUTIL.C *************************/