1 /* -*- Mode: C -*- */
2
3 /* filament.c --- a bit like a string, but different =)O|
4 * Copyright (C) 1999 Gary V. Vaughan
5 * Originally by Gary V. Vaughan, 1999
6 * This file is part of Snprintfv
7 *
8 * Snprintfv is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License as
10 * published by the Free Software Foundation; either version 2 of the
11 * License, or (at your option) any later version.
12 *
13 * Snprintfv program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program. If not, see <http://www.gnu.org/licenses>.
20 *
21 * As a special exception to the GNU General Public License, if you
22 * distribute this file as part of a program that also links with and
23 * uses the libopts library from AutoGen, you may include it under
24 * the same distribution terms used by the libopts library.
25 */
26
27 /* Commentary:
28 *
29 * Try to exploit usage patterns to optimise string handling, and
30 * as a happy consequence handle NUL's embedded in strings properly.
31 *
32 * o Since finding the length of a (long) string is time consuming and
33 * requires careful coding to cache the result in local scope: We
34 * keep count of the length of a Filament all the time, so finding the
35 * length is O(1) at the expense of a little bookkeeping while
36 * manipulating the Filament contents.
37 *
38 * o Constantly resizing a block of memory to hold a string is memory
39 * efficient, but slow: Filaments are only ever expanded in size,
40 * doubling at each step to minimise the number of times the block
41 * needs to be reallocated and the contents copied (this problem is
42 * especially poignant for very large strings).
43 *
44 * o Most strings tend to be either relatively small and short-lived,
45 * or else long-lived but growing in asymptotically in size: To
46 * care for the former case, Filaments start off with a modest static
47 * buffer for the string contents to avoid any mallocations (except
48 * the initial one to get the structure!); the latter case is handled
49 * gracefully by the resizing algorithm in the previous point.
50 *
51 * o Extracting a C-style NUL terminated string from the Filament is
52 * an extremely common operation: We ensure there is always a
53 * terminating NUL character after the last character in the string
54 * so that the conversion can be performed quickly.
55 *
56 * In summary, Filaments are good where you need to do a lot of length
57 * calculations with your strings and/or gradually append more text
58 * onto existing strings. Filaments are also an easy way to get 8-bit
59 * clean strings is a more lightweight approach isn't required.
60 *
61 * They probably don't buy much if you need to do insertions and partial
62 * deletions, but optimising for that is a whole other problem!
63 */
64
65 /* Code: */
66
67 #ifdef HAVE_CONFIG_H
68 # include <config.h>
69 #endif
70
71 #ifdef WITH_DMALLOC
72 # include <dmalloc.h>
73 #endif
74
75 #include "mem.h"
76 #include "filament.h"
77
78
79
80 /**
81 * filnew: constructor
82 * @init: address of the first byte to copy into the new object.
83 * @len: the number of bytes to copy into the new object.
84 *
85 * Create a new Filament object, initialised to hold a copy of the
86 * first @len bytes starting at address @init. If @init is NULL, or
87 * @len is 0 (or less), then the initialised Filament will return the
88 * empty string, "", if its value is queried.
89 *
90 * Return value:
91 * A newly created Filament object is returned.
92 **/
93 Filament *
filnew(const char * const init,size_t len)94 filnew (const char *const init, size_t len)
95 {
96 Filament *new;
97
98 new = snv_new (Filament, 1);
99
100 new->value = new->buffer;
101 new->length = 0;
102 new->size = FILAMENT_BUFSIZ;
103
104 return (init || len) ? filinit (new, init, len) : new;
105 }
106
107 /**
108 * filinit:
109 * @fil: The Filament object to initialise.
110 * @init: address of the first byte to copy into the new object.
111 * @len: the number of bytes to copy into the new object.
112 *
113 * Initialise a Filament object to hold a copy of the first @len bytes
114 * starting at address @init. If @init is NULL, or @len is 0 (or less),
115 * then the Filament will be reset to hold the empty string, "".
116 *
117 * Return value:
118 * The initialised Filament object is returned.
119 **/
120 Filament *
filinit(Filament * fil,const char * const init,size_t len)121 filinit (Filament *fil, const char *const init, size_t len)
122 {
123 if (init == NULL || len < 1)
124 {
125 /* Recycle any dynamic memory assigned to the previous
126 contents of @fil, and point back into the static buffer. */
127 if (fil->value != fil->buffer)
128 snv_delete (fil->value);
129
130 fil->value = fil->buffer;
131 fil->length = 0;
132 fil->size = FILAMENT_BUFSIZ;
133 }
134 else
135 {
136 if (len < FILAMENT_BUFSIZ)
137 {
138 /* We have initialisation data which will easily fit into
139 the static buffer: recycle any memory already assigned
140 and initialise in the static buffer. */
141 if (fil->value != fil->buffer)
142 {
143 snv_delete (fil->value);
144 fil->value = fil->buffer;
145 fil->size = FILAMENT_BUFSIZ;
146 }
147 }
148 else
149 {
150 /* If we get to here then we never try to shrink the already
151 allocated dynamic buffer (if any), we just leave it in
152 place all ready to expand into later... */
153 fil_maybe_extend (fil, len, false);
154 }
155
156 snv_assert (len < fil->size);
157
158 fil->length = len;
159 memcpy (fil->value, init, len);
160 }
161
162 return fil;
163 }
164
165 /**
166 * fildelete: destructor
167 * @fil: The Filament object for recycling.
168 *
169 * The memory being used by @fil is recycled.
170 *
171 * Return value:
172 * The original contents of @fil are converted to a null terminated
173 * string which is returned, either to be freed itself or else used
174 * as a normal C string. The entire Filament contents are copied into
175 * this string including any embedded nulls.
176 **/
177 char *
fildelete(Filament * fil)178 fildelete (Filament *fil)
179 {
180 char *value;
181
182 if (fil->value == fil->buffer)
183 {
184 value = memcpy (snv_new (char, 1 + fil->length),
185 fil->buffer, 1 + fil->length);
186 value[fil->length] = '\0';
187 }
188 else
189 value = filval (fil);
190
191 snv_delete (fil);
192
193 return value;
194 }
195
196 /**
197 * _fil_extend:
198 * @fil: The Filament object which may need more string space.
199 * @len: The length of the data to be stored in @fil.
200 * @copy: whether to copy data from the static buffer on reallocation.
201 *
202 * This function will will assign a bigger block of memory to @fil
203 * considering the space left in @fil and @len, the length required
204 * for the prospective contents.
205 */
206 void
_fil_extend(Filament * fil,size_t len,bool copy)207 _fil_extend (Filament *fil, size_t len, bool copy)
208 {
209 /* Usually we will simply double the amount of space previously
210 allocated, but if the extra data is larger than the current
211 size it *still* won't fit, so in that case we allocate enough
212 room plus some we leave the current free space to expand into. */
213 fil->size += MAX (len, fil->size);
214
215 if (fil->value == fil->buffer)
216 {
217 fil->value = snv_new (char, fil->size);
218 if (copy)
219 memcpy (fil->value, fil->buffer, fil->length);
220 }
221 else
222 fil->value = snv_renew (char, fil->value, fil->size);
223 }
224
225 /*
226 * Local Variables:
227 * mode: C
228 * c-file-style: "gnu"
229 * indent-tabs-mode: nil
230 * End:
231 * end of snprintfv/filament.c */
232