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