cde/lib/DtSearch/msgutil.c

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