usr/src/lib/libtecla/common/stringrp.c

   1 /*
   2  * Copyright (c) 2000, 2001, 2002, 2003, 2004 by Martin C. Shepherd.
   3  *
   4  * All rights reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, and/or sell copies of the Software, and to permit persons
  11  * to whom the Software is furnished to do so, provided that the above
  12  * copyright notice(s) and this permission notice appear in all copies of
  13  * the Software and that both the above copyright notice(s) and this
  14  * permission notice appear in supporting documentation.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  17  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT
  19  * OF THIRD PARTY RIGHTS. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
  20  * HOLDERS INCLUDED IN THIS NOTICE BE LIABLE FOR ANY CLAIM, OR ANY SPECIAL
  21  * INDIRECT OR CONSEQUENTIAL DAMAGES, OR ANY DAMAGES WHATSOEVER RESULTING
  22  * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
  23  * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
  24  * WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  25  *
  26  * Except as contained in this notice, the name of a copyright holder
  27  * shall not be used in advertising or otherwise to promote the sale, use
  28  * or other dealings in this Software without prior written authorization
  29  * of the copyright holder.
  30  */
  31
  32 /*
  33  * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
  34  * Use is subject to license terms.
  35  */
  36
  37 #include <stdlib.h>
  38 #include <stdio.h>
  39 #include <string.h>
  40 #include <errno.h>
  41
  42 #include "freelist.h"
  43 #include "stringrp.h"
  44
  45 /*
  46  * StringSegment objects store lots of small strings in larger
  47  * character arrays. Since the total length of all of the strings can't
  48  * be known in advance, an extensible list of large character arrays,
  49  * called string-segments are used.
  50  */
  51 typedef struct StringSegment StringSegment;
  52 struct StringSegment {
  53   StringSegment *next; /* A pointer to the next segment in the list */
  54   char *block;         /* An array of characters to be shared between strings */
  55   int unused;          /* The amount of unused space at the end of block[] */
  56 };
  57
  58 /*
  59  * StringGroup is typedef'd in stringrp.h.
  60  */
  61 struct StringGroup {
  62   FreeList *node_mem;  /* The StringSegment free-list */
  63   int block_size;      /* The dimension of each character array block */
  64   StringSegment *head; /* The list of character arrays */
  65 };
  66
  67 /*
  68  * Specify how many StringSegment's to allocate at a time.
  69  */
  70 #define STR_SEG_BLK 20
  71
  72 /*.......................................................................
  73  * Create a new StringGroup object.
  74  *
  75  * Input:
  76  *  segment_size    int    The length of each of the large character
  77  *                         arrays in which multiple strings will be
  78  *                         stored. This sets the length of longest
  79  *                         string that can be stored, and for efficiency
  80  *                         should be at least 10 times as large as
  81  *                         the average string that will be stored.
  82  * Output:
  83  *  return  StringGroup *  The new object, or NULL on error.
  84  */
  85 StringGroup *_new_StringGroup(int segment_size)
  86 {
  87   StringGroup *sg;    /* The object to be returned */
  88 /*
  89  * Check the arguments.
  90  */
  91   if(segment_size < 1) {
  92     errno = EINVAL;
  93     return NULL;
  94   };
  95 /*
  96  * Allocate the container.
  97  */
  98   sg = (StringGroup *) malloc(sizeof(StringGroup));
  99   if(!sg) {
 100     errno = ENOMEM;
 101     return NULL;
 102   };
 103 /*
 104  * Before attempting any operation that might fail, initialize the
 105  * container at least up to the point at which it can safely be passed
 106  * to _del_StringGroup().
 107  */
 108   sg->node_mem = NULL;
 109   sg->head = NULL;
 110   sg->block_size = segment_size;
 111 /*
 112  * Allocate the free list that is used to allocate list nodes.
 113  */
 114   sg->node_mem = _new_FreeList(sizeof(StringSegment), STR_SEG_BLK);
 115   if(!sg->node_mem)
 116     return _del_StringGroup(sg);
 117   return sg;
 118 }
 119
 120 /*.......................................................................
 121  * Delete a StringGroup object.
 122  *
 123  * Input:
 124  *  sg     StringGroup *  The object to be deleted.
 125  * Output:
 126  *  return StringGroup *  The deleted object (always NULL).
 127  */
 128 StringGroup *_del_StringGroup(StringGroup *sg)
 129 {
 130   if(sg) {
 131     StringSegment *node;
 132 /*
 133  * Delete the character arrays.
 134  */
 135     for(node=sg->head; node; node=node->next) {
 136       free(node->block);
 137       node->block = NULL;
 138     };
 139 /*
 140  * Delete the list nodes that contained the string segments.
 141  */
 142     sg->node_mem = _del_FreeList(sg->node_mem, 1);
 143     sg->head = NULL; /* Already deleted by deleting sg->node_mem */
 144 /*
 145  * Delete the container.
 146  */
 147     free(sg);
 148   };
 149   return NULL;
 150 }
 151
 152 /*.......................................................................
 153  * Make a copy of a string in the specified string group, and return
 154  * a pointer to the copy.
 155  *
 156  * Input:
 157  *  sg      StringGroup *  The group to store the string in.
 158  *  string   const char *  The string to be recorded.
 159  *  remove_escapes  int    If true, omit backslashes which escape
 160  *                         other characters when making the copy.
 161  * Output:
 162  *  return         char *  The pointer to the copy of the string,
 163  *                         or NULL if there was insufficient memory.
 164  */
 165 char *_sg_store_string(StringGroup *sg, const char *string, int remove_escapes)
 166 {
 167   char *copy;           /* The recorded copy of string[] */
 168   size_t len;
 169 /*
 170  * Check the arguments.
 171  */
 172   if(!sg || !string)
 173     return NULL;
 174 /*
 175  * Get memory for the string.
 176  */
 177   len = strlen(string);
 178   copy = _sg_alloc_string(sg, len);
 179   if(copy) {
 180 /*
 181  * If needed, remove backslash escapes while copying the input string
 182  * into the cache string.
 183  */
 184     if(remove_escapes) {
 185       int escaped = 0;             /* True if the next character should be */
 186                                    /*  escaped. */
 187       const char *src = string;    /* A pointer into the input string */
 188       char *dst = copy;            /* A pointer into the cached copy of the */
 189                                    /*  string. */
 190       while(*src) {
 191         if(!escaped && *src == '\\') {
 192           escaped = 1;
 193           src++;
 194         } else {
 195           escaped = 0;
 196           *dst++ = *src++;
 197         };
 198       };
 199       *dst = '\0';
 200 /*
 201  * If escapes have already been removed, copy the input string directly
 202  * into the cache.
 203  */
 204     } else {
 205       strlcpy(copy, string, len + 1);
 206     };
 207   };
 208 /*
 209  * Return a pointer to the copy of the string (or NULL if the allocation
 210  * failed).
 211  */
 212   return copy;
 213 }
 214
 215 /*.......................................................................
 216  * Allocate memory for a string of a given length.
 217  *
 218  * Input:
 219  *  sg      StringGroup *  The group to store the string in.
 220  *  length          int    The required length of the string.
 221  * Output:
 222  *  return         char *  The pointer to the copy of the string,
 223  *                         or NULL if there was insufficient memory.
 224  */
 225 char *_sg_alloc_string(StringGroup *sg, int length)
 226 {
 227   StringSegment *node;  /* A node of the list of string segments */
 228   char *copy;           /* The allocated string */
 229 /*
 230  * If the string is longer than block_size, then we can't record it.
 231  */
 232   if(length > sg->block_size || length < 0)
 233     return NULL;
 234 /*
 235  * See if there is room to record the string in one of the existing
 236  * string segments. Do this by advancing the node pointer until we find
 237  * a node with length+1 bytes unused, or we get to the end of the list.
 238  */
 239   for(node=sg->head; node && node->unused <= length; node=node->next)
 240     ;
 241 /*
 242  * If there wasn't room, allocate a new string segment.
 243  */
 244   if(!node) {
 245     node = (StringSegment *) _new_FreeListNode(sg->node_mem);
 246     if(!node)
 247       return NULL;
 248 /*
 249  * Initialize the segment.
 250  */
 251     node->next = NULL;
 252     node->block = NULL;
 253     node->unused = sg->block_size;
 254 /*
 255  * Attempt to allocate the string segment character array.
 256  */
 257     node->block = (char *) malloc(sg->block_size);
 258     if(!node->block)
 259       return NULL;
 260 /*
 261  * Prepend the node to the list.
 262  */
 263     node->next = sg->head;
 264     sg->head = node;
 265   };
 266 /*
 267  * Get memory for the string.
 268  */
 269   copy = node->block + sg->block_size - node->unused;
 270   node->unused -= length + 1;
 271 /*
 272  * Return a pointer to the string memory.
 273  */
 274   return copy;
 275 }
 276
 277 /*.......................................................................
 278  * Delete all of the strings that are currently stored by a specified
 279  * StringGroup object.
 280  *
 281  * Input:
 282  *  sg   StringGroup *   The group of strings to clear.
 283  */
 284 void _clr_StringGroup(StringGroup *sg)
 285 {
 286   StringSegment *node;   /* A node in the list of string segments */
 287 /*
 288  * Mark all of the string segments as unoccupied.
 289  */
 290   for(node=sg->head; node; node=node->next)
 291     node->unused = sg->block_size;
 292   return;
 293 }