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