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#pragma ident	"%Z%%M%	%I%	%E% SMI"
38
39#include <stdlib.h>
40#include <stdio.h>
41#include <string.h>
42#include <errno.h>
43
44#include "freelist.h"
45#include "stringrp.h"
46
47/*
48 * StringSegment objects store lots of small strings in larger
49 * character arrays. Since the total length of all of the strings can't
50 * be known in advance, an extensible list of large character arrays,
51 * called string-segments are used.
52 */
53typedef struct StringSegment StringSegment;
54struct StringSegment {
55  StringSegment *next; /* A pointer to the next segment in the list */
56  char *block;         /* An array of characters to be shared between strings */
57  int unused;          /* The amount of unused space at the end of block[] */
58};
59
60/*
61 * StringGroup is typedef'd in stringrp.h.
62 */
63struct StringGroup {
64  FreeList *node_mem;  /* The StringSegment free-list */
65  int block_size;      /* The dimension of each character array block */
66  StringSegment *head; /* The list of character arrays */
67};
68
69/*
70 * Specify how many StringSegment's to allocate at a time.
71 */
72#define STR_SEG_BLK 20
73
74/*.......................................................................
75 * Create a new StringGroup object.
76 *
77 * Input:
78 *  segment_size    int    The length of each of the large character
79 *                         arrays in which multiple strings will be
80 *                         stored. This sets the length of longest
81 *                         string that can be stored, and for efficiency
82 *                         should be at least 10 times as large as
83 *                         the average string that will be stored.
84 * Output:
85 *  return  StringGroup *  The new object, or NULL on error.
86 */
87StringGroup *_new_StringGroup(int segment_size)
88{
89  StringGroup *sg;    /* The object to be returned */
90/*
91 * Check the arguments.
92 */
93  if(segment_size < 1) {
94    errno = EINVAL;
95    return NULL;
96  };
97/*
98 * Allocate the container.
99 */
100  sg = (StringGroup *) malloc(sizeof(StringGroup));
101  if(!sg) {
102    errno = ENOMEM;
103    return NULL;
104  };
105/*
106 * Before attempting any operation that might fail, initialize the
107 * container at least up to the point at which it can safely be passed
108 * to _del_StringGroup().
109 */
110  sg->node_mem = NULL;
111  sg->head = NULL;
112  sg->block_size = segment_size;
113/*
114 * Allocate the free list that is used to allocate list nodes.
115 */
116  sg->node_mem = _new_FreeList(sizeof(StringSegment), STR_SEG_BLK);
117  if(!sg->node_mem)
118    return _del_StringGroup(sg);
119  return sg;
120}
121
122/*.......................................................................
123 * Delete a StringGroup object.
124 *
125 * Input:
126 *  sg     StringGroup *  The object to be deleted.
127 * Output:
128 *  return StringGroup *  The deleted object (always NULL).
129 */
130StringGroup *_del_StringGroup(StringGroup *sg)
131{
132  if(sg) {
133    StringSegment *node;
134/*
135 * Delete the character arrays.
136 */
137    for(node=sg->head; node; node=node->next) {
138      if(node->block)
139	free(node->block);
140      node->block = NULL;
141    };
142/*
143 * Delete the list nodes that contained the string segments.
144 */
145    sg->node_mem = _del_FreeList(sg->node_mem, 1);
146    sg->head = NULL; /* Already deleted by deleting sg->node_mem */
147/*
148 * Delete the container.
149 */
150    free(sg);
151  };
152  return NULL;
153}
154
155/*.......................................................................
156 * Make a copy of a string in the specified string group, and return
157 * a pointer to the copy.
158 *
159 * Input:
160 *  sg      StringGroup *  The group to store the string in.
161 *  string   const char *  The string to be recorded.
162 *  remove_escapes  int    If true, omit backslashes which escape
163 *                         other characters when making the copy.
164 * Output:
165 *  return         char *  The pointer to the copy of the string,
166 *                         or NULL if there was insufficient memory.
167 */
168char *_sg_store_string(StringGroup *sg, const char *string, int remove_escapes)
169{
170  char *copy;           /* The recorded copy of string[] */
171  size_t len;
172/*
173 * Check the arguments.
174 */
175  if(!sg || !string)
176    return NULL;
177/*
178 * Get memory for the string.
179 */
180  len = strlen(string);
181  copy = _sg_alloc_string(sg, len);
182  if(copy) {
183/*
184 * If needed, remove backslash escapes while copying the input string
185 * into the cache string.
186 */
187    if(remove_escapes) {
188      int escaped = 0;             /* True if the next character should be */
189                                   /*  escaped. */
190      const char *src = string;    /* A pointer into the input string */
191      char *dst = copy;            /* A pointer into the cached copy of the */
192                                   /*  string. */
193      while(*src) {
194	if(!escaped && *src == '\\') {
195	  escaped = 1;
196	  src++;
197	} else {
198	  escaped = 0;
199	  *dst++ = *src++;
200	};
201      };
202      *dst = '\0';
203/*
204 * If escapes have already been removed, copy the input string directly
205 * into the cache.
206 */
207    } else {
208      strlcpy(copy, string, len + 1);
209    };
210  };
211/*
212 * Return a pointer to the copy of the string (or NULL if the allocation
213 * failed).
214 */
215  return copy;
216}
217
218/*.......................................................................
219 * Allocate memory for a string of a given length.
220 *
221 * Input:
222 *  sg      StringGroup *  The group to store the string in.
223 *  length          int    The required length of the string.
224 * Output:
225 *  return         char *  The pointer to the copy of the string,
226 *                         or NULL if there was insufficient memory.
227 */
228char *_sg_alloc_string(StringGroup *sg, int length)
229{
230  StringSegment *node;  /* A node of the list of string segments */
231  char *copy;           /* The allocated string */
232/*
233 * If the string is longer than block_size, then we can't record it.
234 */
235  if(length > sg->block_size || length < 0)
236    return NULL;
237/*
238 * See if there is room to record the string in one of the existing
239 * string segments. Do this by advancing the node pointer until we find
240 * a node with length+1 bytes unused, or we get to the end of the list.
241 */
242  for(node=sg->head; node && node->unused <= length; node=node->next)
243    ;
244/*
245 * If there wasn't room, allocate a new string segment.
246 */
247  if(!node) {
248    node = (StringSegment *) _new_FreeListNode(sg->node_mem);
249    if(!node)
250      return NULL;
251/*
252 * Initialize the segment.
253 */
254    node->next = NULL;
255    node->block = NULL;
256    node->unused = sg->block_size;
257/*
258 * Attempt to allocate the string segment character array.
259 */
260    node->block = (char *) malloc(sg->block_size);
261    if(!node->block)
262      return NULL;
263/*
264 * Prepend the node to the list.
265 */
266    node->next = sg->head;
267    sg->head = node;
268  };
269/*
270 * Get memory for the string.
271 */
272  copy = node->block + sg->block_size - node->unused;
273  node->unused -= length + 1;
274/*
275 * Return a pointer to the string memory.
276 */
277  return copy;
278}
279
280/*.......................................................................
281 * Delete all of the strings that are currently stored by a specified
282 * StringGroup object.
283 *
284 * Input:
285 *  sg   StringGroup *   The group of strings to clear.
286 */
287void _clr_StringGroup(StringGroup *sg)
288{
289  StringSegment *node;   /* A node in the list of string segments */
290/*
291 * Mark all of the string segments as unoccupied.
292 */
293  for(node=sg->head; node; node=node->next)
294    node->unused = sg->block_size;
295  return;
296}
297