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