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 */
53 typedef struct StringSegment StringSegment;
54 struct 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 */
63 struct 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 */
_new_StringGroup(int segment_size)87 StringGroup *_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 */
_del_StringGroup(StringGroup * sg)130 StringGroup *_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 */
_sg_store_string(StringGroup * sg,const char * string,int remove_escapes)168 char *_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 */
_sg_alloc_string(StringGroup * sg,int length)228 char *_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 */
_clr_StringGroup(StringGroup * sg)287 void _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