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 */ 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 */ 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 */ 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 */ 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 */ 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