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 */
_new_StringGroup(int segment_size)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 */
_del_StringGroup(StringGroup * sg)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 if(node->block)
137 free(node->block);
138 node->block = NULL;
139 };
140 /*
141 * Delete the list nodes that contained the string segments.
142 */
143 sg->node_mem = _del_FreeList(sg->node_mem, 1);
144 sg->head = NULL; /* Already deleted by deleting sg->node_mem */
145 /*
146 * Delete the container.
147 */
148 free(sg);
149 };
150 return NULL;
151 }
152
153 /*.......................................................................
154 * Make a copy of a string in the specified string group, and return
155 * a pointer to the copy.
156 *
157 * Input:
158 * sg StringGroup * The group to store the string in.
159 * string const char * The string to be recorded.
160 * remove_escapes int If true, omit backslashes which escape
161 * other characters when making the copy.
162 * Output:
163 * return char * The pointer to the copy of the string,
164 * or NULL if there was insufficient memory.
165 */
_sg_store_string(StringGroup * sg,const char * string,int remove_escapes)166 char *_sg_store_string(StringGroup *sg, const char *string, int remove_escapes)
167 {
168 char *copy; /* The recorded copy of string[] */
169 size_t len;
170 /*
171 * Check the arguments.
172 */
173 if(!sg || !string)
174 return NULL;
175 /*
176 * Get memory for the string.
177 */
178 len = strlen(string);
179 copy = _sg_alloc_string(sg, len);
180 if(copy) {
181 /*
182 * If needed, remove backslash escapes while copying the input string
183 * into the cache string.
184 */
185 if(remove_escapes) {
186 int escaped = 0; /* True if the next character should be */
187 /* escaped. */
188 const char *src = string; /* A pointer into the input string */
189 char *dst = copy; /* A pointer into the cached copy of the */
190 /* string. */
191 while(*src) {
192 if(!escaped && *src == '\\') {
193 escaped = 1;
194 src++;
195 } else {
196 escaped = 0;
197 *dst++ = *src++;
198 };
199 };
200 *dst = '\0';
201 /*
202 * If escapes have already been removed, copy the input string directly
203 * into the cache.
204 */
205 } else {
206 strlcpy(copy, string, len + 1);
207 };
208 };
209 /*
210 * Return a pointer to the copy of the string (or NULL if the allocation
211 * failed).
212 */
213 return copy;
214 }
215
216 /*.......................................................................
217 * Allocate memory for a string of a given length.
218 *
219 * Input:
220 * sg StringGroup * The group to store the string in.
221 * length int The required length of the string.
222 * Output:
223 * return char * The pointer to the copy of the string,
224 * or NULL if there was insufficient memory.
225 */
_sg_alloc_string(StringGroup * sg,int length)226 char *_sg_alloc_string(StringGroup *sg, int length)
227 {
228 StringSegment *node; /* A node of the list of string segments */
229 char *copy; /* The allocated string */
230 /*
231 * If the string is longer than block_size, then we can't record it.
232 */
233 if(length > sg->block_size || length < 0)
234 return NULL;
235 /*
236 * See if there is room to record the string in one of the existing
237 * string segments. Do this by advancing the node pointer until we find
238 * a node with length+1 bytes unused, or we get to the end of the list.
239 */
240 for(node=sg->head; node && node->unused <= length; node=node->next)
241 ;
242 /*
243 * If there wasn't room, allocate a new string segment.
244 */
245 if(!node) {
246 node = (StringSegment *) _new_FreeListNode(sg->node_mem);
247 if(!node)
248 return NULL;
249 /*
250 * Initialize the segment.
251 */
252 node->next = NULL;
253 node->block = NULL;
254 node->unused = sg->block_size;
255 /*
256 * Attempt to allocate the string segment character array.
257 */
258 node->block = (char *) malloc(sg->block_size);
259 if(!node->block)
260 return NULL;
261 /*
262 * Prepend the node to the list.
263 */
264 node->next = sg->head;
265 sg->head = node;
266 };
267 /*
268 * Get memory for the string.
269 */
270 copy = node->block + sg->block_size - node->unused;
271 node->unused -= length + 1;
272 /*
273 * Return a pointer to the string memory.
274 */
275 return copy;
276 }
277
278 /*.......................................................................
279 * Delete all of the strings that are currently stored by a specified
280 * StringGroup object.
281 *
282 * Input:
283 * sg StringGroup * The group of strings to clear.
284 */
_clr_StringGroup(StringGroup * sg)285 void _clr_StringGroup(StringGroup *sg)
286 {
287 StringSegment *node; /* A node in the list of string segments */
288 /*
289 * Mark all of the string segments as unoccupied.
290 */
291 for(node=sg->head; node; node=node->next)
292 node->unused = sg->block_size;
293 return;
294 }
295