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