980e4e4f138b5dbd57a7394da84257819b830e36
[mesa.git] / src / util / ralloc.c
1 /*
2 * Copyright © 2010 Intel Corporation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21 * DEALINGS IN THE SOFTWARE.
22 */
23
24 #include <assert.h>
25 #include <stdlib.h>
26 #include <stdarg.h>
27 #include <stdio.h>
28 #include <string.h>
29 #include <stdint.h>
30
31 /* Android defines SIZE_MAX in limits.h, instead of the standard stdint.h */
32 #ifdef ANDROID
33 #include <limits.h>
34 #endif
35
36 /* Some versions of MinGW are missing _vscprintf's declaration, although they
37 * still provide the symbol in the import library. */
38 #ifdef __MINGW32__
39 _CRTIMP int _vscprintf(const char *format, va_list argptr);
40 #endif
41
42 #include "ralloc.h"
43
44 #ifndef va_copy
45 #ifdef __va_copy
46 #define va_copy(dest, src) __va_copy((dest), (src))
47 #else
48 #define va_copy(dest, src) (dest) = (src)
49 #endif
50 #endif
51
52 #define CANARY 0x5A1106
53
54 struct ralloc_header
55 {
56 #ifdef DEBUG
57 /* A canary value used to determine whether a pointer is ralloc'd. */
58 unsigned canary;
59 #endif
60
61 struct ralloc_header *parent;
62
63 /* The first child (head of a linked list) */
64 struct ralloc_header *child;
65
66 /* Linked list of siblings */
67 struct ralloc_header *prev;
68 struct ralloc_header *next;
69
70 void (*destructor)(void *);
71 };
72
73 typedef struct ralloc_header ralloc_header;
74
75 static void unlink_block(ralloc_header *info);
76 static void unsafe_free(ralloc_header *info);
77
78 static ralloc_header *
79 get_header(const void *ptr)
80 {
81 ralloc_header *info = (ralloc_header *) (((char *) ptr) -
82 sizeof(ralloc_header));
83 #ifdef DEBUG
84 assert(info->canary == CANARY);
85 #endif
86 return info;
87 }
88
89 #define PTR_FROM_HEADER(info) (((char *) info) + sizeof(ralloc_header))
90
91 static void
92 add_child(ralloc_header *parent, ralloc_header *info)
93 {
94 if (parent != NULL) {
95 info->parent = parent;
96 info->next = parent->child;
97 parent->child = info;
98
99 if (info->next != NULL)
100 info->next->prev = info;
101 }
102 }
103
104 void *
105 ralloc_context(const void *ctx)
106 {
107 return ralloc_size(ctx, 0);
108 }
109
110 void *
111 ralloc_size(const void *ctx, size_t size)
112 {
113 void *block = malloc(size + sizeof(ralloc_header));
114 ralloc_header *info;
115 ralloc_header *parent;
116
117 if (unlikely(block == NULL))
118 return NULL;
119
120 info = (ralloc_header *) block;
121 /* measurements have shown that calloc is slower (because of
122 * the multiplication overflow checking?), so clear things
123 * manually
124 */
125 info->parent = NULL;
126 info->child = NULL;
127 info->prev = NULL;
128 info->next = NULL;
129 info->destructor = NULL;
130
131 parent = ctx != NULL ? get_header(ctx) : NULL;
132
133 add_child(parent, info);
134
135 #ifdef DEBUG
136 info->canary = CANARY;
137 #endif
138
139 return PTR_FROM_HEADER(info);
140 }
141
142 void *
143 rzalloc_size(const void *ctx, size_t size)
144 {
145 void *ptr = ralloc_size(ctx, size);
146
147 if (likely(ptr))
148 memset(ptr, 0, size);
149
150 return ptr;
151 }
152
153 /* helper function - assumes ptr != NULL */
154 static void *
155 resize(void *ptr, size_t size)
156 {
157 ralloc_header *child, *old, *info;
158
159 old = get_header(ptr);
160 info = realloc(old, size + sizeof(ralloc_header));
161
162 if (info == NULL)
163 return NULL;
164
165 /* Update parent and sibling's links to the reallocated node. */
166 if (info != old && info->parent != NULL) {
167 if (info->parent->child == old)
168 info->parent->child = info;
169
170 if (info->prev != NULL)
171 info->prev->next = info;
172
173 if (info->next != NULL)
174 info->next->prev = info;
175 }
176
177 /* Update child->parent links for all children */
178 for (child = info->child; child != NULL; child = child->next)
179 child->parent = info;
180
181 return PTR_FROM_HEADER(info);
182 }
183
184 void *
185 reralloc_size(const void *ctx, void *ptr, size_t size)
186 {
187 if (unlikely(ptr == NULL))
188 return ralloc_size(ctx, size);
189
190 assert(ralloc_parent(ptr) == ctx);
191 return resize(ptr, size);
192 }
193
194 void *
195 ralloc_array_size(const void *ctx, size_t size, unsigned count)
196 {
197 if (count > SIZE_MAX/size)
198 return NULL;
199
200 return ralloc_size(ctx, size * count);
201 }
202
203 void *
204 rzalloc_array_size(const void *ctx, size_t size, unsigned count)
205 {
206 if (count > SIZE_MAX/size)
207 return NULL;
208
209 return rzalloc_size(ctx, size * count);
210 }
211
212 void *
213 reralloc_array_size(const void *ctx, void *ptr, size_t size, unsigned count)
214 {
215 if (count > SIZE_MAX/size)
216 return NULL;
217
218 return reralloc_size(ctx, ptr, size * count);
219 }
220
221 void
222 ralloc_free(void *ptr)
223 {
224 ralloc_header *info;
225
226 if (ptr == NULL)
227 return;
228
229 info = get_header(ptr);
230 unlink_block(info);
231 unsafe_free(info);
232 }
233
234 static void
235 unlink_block(ralloc_header *info)
236 {
237 /* Unlink from parent & siblings */
238 if (info->parent != NULL) {
239 if (info->parent->child == info)
240 info->parent->child = info->next;
241
242 if (info->prev != NULL)
243 info->prev->next = info->next;
244
245 if (info->next != NULL)
246 info->next->prev = info->prev;
247 }
248 info->parent = NULL;
249 info->prev = NULL;
250 info->next = NULL;
251 }
252
253 static void
254 unsafe_free(ralloc_header *info)
255 {
256 /* Recursively free any children...don't waste time unlinking them. */
257 ralloc_header *temp;
258 while (info->child != NULL) {
259 temp = info->child;
260 info->child = temp->next;
261 unsafe_free(temp);
262 }
263
264 /* Free the block itself. Call the destructor first, if any. */
265 if (info->destructor != NULL)
266 info->destructor(PTR_FROM_HEADER(info));
267
268 free(info);
269 }
270
271 void
272 ralloc_steal(const void *new_ctx, void *ptr)
273 {
274 ralloc_header *info, *parent;
275
276 if (unlikely(ptr == NULL))
277 return;
278
279 info = get_header(ptr);
280 parent = get_header(new_ctx);
281
282 unlink_block(info);
283
284 add_child(parent, info);
285 }
286
287 void
288 ralloc_adopt(const void *new_ctx, void *old_ctx)
289 {
290 ralloc_header *new_info, *old_info, *child;
291
292 if (unlikely(old_ctx == NULL))
293 return;
294
295 old_info = get_header(old_ctx);
296 new_info = get_header(new_ctx);
297
298 /* If there are no children, bail. */
299 if (unlikely(old_info->child == NULL))
300 return;
301
302 /* Set all the children's parent to new_ctx; get a pointer to the last child. */
303 for (child = old_info->child; child->next != NULL; child = child->next) {
304 child->parent = new_info;
305 }
306
307 /* Connect the two lists together; parent them to new_ctx; make old_ctx empty. */
308 child->next = new_info->child;
309 child->parent = new_info;
310 new_info->child = old_info->child;
311 old_info->child = NULL;
312 }
313
314 void *
315 ralloc_parent(const void *ptr)
316 {
317 ralloc_header *info;
318
319 if (unlikely(ptr == NULL))
320 return NULL;
321
322 info = get_header(ptr);
323 return info->parent ? PTR_FROM_HEADER(info->parent) : NULL;
324 }
325
326 static void *autofree_context = NULL;
327
328 static void
329 autofree(void)
330 {
331 ralloc_free(autofree_context);
332 }
333
334 void *
335 ralloc_autofree_context(void)
336 {
337 if (unlikely(autofree_context == NULL)) {
338 autofree_context = ralloc_context(NULL);
339 atexit(autofree);
340 }
341 return autofree_context;
342 }
343
344 void
345 ralloc_set_destructor(const void *ptr, void(*destructor)(void *))
346 {
347 ralloc_header *info = get_header(ptr);
348 info->destructor = destructor;
349 }
350
351 char *
352 ralloc_strdup(const void *ctx, const char *str)
353 {
354 size_t n;
355 char *ptr;
356
357 if (unlikely(str == NULL))
358 return NULL;
359
360 n = strlen(str);
361 ptr = ralloc_array(ctx, char, n + 1);
362 memcpy(ptr, str, n);
363 ptr[n] = '\0';
364 return ptr;
365 }
366
367 char *
368 ralloc_strndup(const void *ctx, const char *str, size_t max)
369 {
370 size_t n;
371 char *ptr;
372
373 if (unlikely(str == NULL))
374 return NULL;
375
376 n = strnlen(str, max);
377 ptr = ralloc_array(ctx, char, n + 1);
378 memcpy(ptr, str, n);
379 ptr[n] = '\0';
380 return ptr;
381 }
382
383 /* helper routine for strcat/strncat - n is the exact amount to copy */
384 static bool
385 cat(char **dest, const char *str, size_t n)
386 {
387 char *both;
388 size_t existing_length;
389 assert(dest != NULL && *dest != NULL);
390
391 existing_length = strlen(*dest);
392 both = resize(*dest, existing_length + n + 1);
393 if (unlikely(both == NULL))
394 return false;
395
396 memcpy(both + existing_length, str, n);
397 both[existing_length + n] = '\0';
398
399 *dest = both;
400 return true;
401 }
402
403
404 bool
405 ralloc_strcat(char **dest, const char *str)
406 {
407 return cat(dest, str, strlen(str));
408 }
409
410 bool
411 ralloc_strncat(char **dest, const char *str, size_t n)
412 {
413 /* Clamp n to the string length */
414 size_t str_length = strlen(str);
415 if (str_length < n)
416 n = str_length;
417
418 return cat(dest, str, n);
419 }
420
421 char *
422 ralloc_asprintf(const void *ctx, const char *fmt, ...)
423 {
424 char *ptr;
425 va_list args;
426 va_start(args, fmt);
427 ptr = ralloc_vasprintf(ctx, fmt, args);
428 va_end(args);
429 return ptr;
430 }
431
432 /* Return the length of the string that would be generated by a printf-style
433 * format and argument list, not including the \0 byte.
434 */
435 static size_t
436 printf_length(const char *fmt, va_list untouched_args)
437 {
438 int size;
439 char junk;
440
441 /* Make a copy of the va_list so the original caller can still use it */
442 va_list args;
443 va_copy(args, untouched_args);
444
445 #ifdef _WIN32
446 /* We need to use _vcsprintf to calculate the size as vsnprintf returns -1
447 * if the number of characters to write is greater than count.
448 */
449 size = _vscprintf(fmt, args);
450 (void)junk;
451 #else
452 size = vsnprintf(&junk, 1, fmt, args);
453 #endif
454 assert(size >= 0);
455
456 va_end(args);
457
458 return size;
459 }
460
461 char *
462 ralloc_vasprintf(const void *ctx, const char *fmt, va_list args)
463 {
464 size_t size = printf_length(fmt, args) + 1;
465
466 char *ptr = ralloc_size(ctx, size);
467 if (ptr != NULL)
468 vsnprintf(ptr, size, fmt, args);
469
470 return ptr;
471 }
472
473 bool
474 ralloc_asprintf_append(char **str, const char *fmt, ...)
475 {
476 bool success;
477 va_list args;
478 va_start(args, fmt);
479 success = ralloc_vasprintf_append(str, fmt, args);
480 va_end(args);
481 return success;
482 }
483
484 bool
485 ralloc_vasprintf_append(char **str, const char *fmt, va_list args)
486 {
487 size_t existing_length;
488 assert(str != NULL);
489 existing_length = *str ? strlen(*str) : 0;
490 return ralloc_vasprintf_rewrite_tail(str, &existing_length, fmt, args);
491 }
492
493 bool
494 ralloc_asprintf_rewrite_tail(char **str, size_t *start, const char *fmt, ...)
495 {
496 bool success;
497 va_list args;
498 va_start(args, fmt);
499 success = ralloc_vasprintf_rewrite_tail(str, start, fmt, args);
500 va_end(args);
501 return success;
502 }
503
504 bool
505 ralloc_vasprintf_rewrite_tail(char **str, size_t *start, const char *fmt,
506 va_list args)
507 {
508 size_t new_length;
509 char *ptr;
510
511 assert(str != NULL);
512
513 if (unlikely(*str == NULL)) {
514 // Assuming a NULL context is probably bad, but it's expected behavior.
515 *str = ralloc_vasprintf(NULL, fmt, args);
516 *start = strlen(*str);
517 return true;
518 }
519
520 new_length = printf_length(fmt, args);
521
522 ptr = resize(*str, *start + new_length + 1);
523 if (unlikely(ptr == NULL))
524 return false;
525
526 vsnprintf(ptr + *start, new_length + 1, fmt, args);
527 *str = ptr;
528 *start += new_length;
529 return true;
530 }
531
532 /***************************************************************************
533 * Linear allocator for short-lived allocations.
534 ***************************************************************************
535 *
536 * The allocator consists of a parent node (2K buffer), which requires
537 * a ralloc parent, and child nodes (allocations). Child nodes can't be freed
538 * directly, because the parent doesn't track them. You have to release
539 * the parent node in order to release all its children.
540 *
541 * The allocator uses a fixed-sized buffer with a monotonically increasing
542 * offset after each allocation. If the buffer is all used, another buffer
543 * is allocated, sharing the same ralloc parent, so all buffers are at
544 * the same level in the ralloc hierarchy.
545 *
546 * The linear parent node is always the first buffer and keeps track of all
547 * other buffers.
548 */
549
550 #define ALIGN_POT(x, y) (((x) + (y) - 1) & ~((y) - 1))
551
552 #define MIN_LINEAR_BUFSIZE 2048
553 #define SUBALLOC_ALIGNMENT sizeof(uintptr_t)
554 #define LMAGIC 0x87b9c7d3
555
556 struct linear_header {
557 #ifdef DEBUG
558 unsigned magic; /* for debugging */
559 #endif
560 unsigned offset; /* points to the first unused byte in the buffer */
561 unsigned size; /* size of the buffer */
562 void *ralloc_parent; /* new buffers will use this */
563 struct linear_header *next; /* next buffer if we have more */
564 struct linear_header *latest; /* the only buffer that has free space */
565
566 /* After this structure, the buffer begins.
567 * Each suballocation consists of linear_size_chunk as its header followed
568 * by the suballocation, so it goes:
569 *
570 * - linear_size_chunk
571 * - allocated space
572 * - linear_size_chunk
573 * - allocated space
574 * etc.
575 *
576 * linear_size_chunk is only needed by linear_realloc.
577 */
578 };
579
580 struct linear_size_chunk {
581 unsigned size; /* for realloc */
582 unsigned _padding;
583 };
584
585 typedef struct linear_header linear_header;
586 typedef struct linear_size_chunk linear_size_chunk;
587
588 #define LINEAR_PARENT_TO_HEADER(parent) \
589 (linear_header*) \
590 ((char*)(parent) - sizeof(linear_size_chunk) - sizeof(linear_header))
591
592 /* Allocate the linear buffer with its header. */
593 static linear_header *
594 create_linear_node(void *ralloc_ctx, unsigned min_size)
595 {
596 linear_header *node;
597
598 min_size += sizeof(linear_size_chunk);
599
600 if (likely(min_size < MIN_LINEAR_BUFSIZE))
601 min_size = MIN_LINEAR_BUFSIZE;
602
603 node = ralloc_size(ralloc_ctx, sizeof(linear_header) + min_size);
604 if (unlikely(!node))
605 return NULL;
606
607 #ifdef DEBUG
608 node->magic = LMAGIC;
609 #endif
610 node->offset = 0;
611 node->size = min_size;
612 node->ralloc_parent = ralloc_ctx;
613 node->next = NULL;
614 node->latest = node;
615 return node;
616 }
617
618 void *
619 linear_alloc_child(void *parent, unsigned size)
620 {
621 linear_header *first = LINEAR_PARENT_TO_HEADER(parent);
622 linear_header *latest = first->latest;
623 linear_header *new_node;
624 linear_size_chunk *ptr;
625 unsigned full_size;
626
627 assert(first->magic == LMAGIC);
628 assert(!latest->next);
629
630 size = ALIGN_POT(size, SUBALLOC_ALIGNMENT);
631 full_size = sizeof(linear_size_chunk) + size;
632
633 if (unlikely(latest->offset + full_size > latest->size)) {
634 /* allocate a new node */
635 new_node = create_linear_node(latest->ralloc_parent, size);
636 if (unlikely(!new_node))
637 return NULL;
638
639 first->latest = new_node;
640 latest->latest = new_node;
641 latest->next = new_node;
642 latest = new_node;
643 }
644
645 ptr = (linear_size_chunk *)((char*)&latest[1] + latest->offset);
646 ptr->size = size;
647 latest->offset += full_size;
648 return &ptr[1];
649 }
650
651 void *
652 linear_alloc_parent(void *ralloc_ctx, unsigned size)
653 {
654 linear_header *node;
655
656 if (unlikely(!ralloc_ctx))
657 return NULL;
658
659 size = ALIGN_POT(size, SUBALLOC_ALIGNMENT);
660
661 node = create_linear_node(ralloc_ctx, size);
662 if (unlikely(!node))
663 return NULL;
664
665 return linear_alloc_child((char*)node +
666 sizeof(linear_header) +
667 sizeof(linear_size_chunk), size);
668 }
669
670 void *
671 linear_zalloc_child(void *parent, unsigned size)
672 {
673 void *ptr = linear_alloc_child(parent, size);
674
675 if (likely(ptr))
676 memset(ptr, 0, size);
677 return ptr;
678 }
679
680 void *
681 linear_zalloc_parent(void *parent, unsigned size)
682 {
683 void *ptr = linear_alloc_parent(parent, size);
684
685 if (likely(ptr))
686 memset(ptr, 0, size);
687 return ptr;
688 }
689
690 void
691 linear_free_parent(void *ptr)
692 {
693 linear_header *node;
694
695 if (unlikely(!ptr))
696 return;
697
698 node = LINEAR_PARENT_TO_HEADER(ptr);
699 assert(node->magic == LMAGIC);
700
701 while (node) {
702 void *ptr = node;
703
704 node = node->next;
705 ralloc_free(ptr);
706 }
707 }
708
709 void
710 ralloc_steal_linear_parent(void *new_ralloc_ctx, void *ptr)
711 {
712 linear_header *node;
713
714 if (unlikely(!ptr))
715 return;
716
717 node = LINEAR_PARENT_TO_HEADER(ptr);
718 assert(node->magic == LMAGIC);
719
720 while (node) {
721 ralloc_steal(new_ralloc_ctx, node);
722 node->ralloc_parent = new_ralloc_ctx;
723 node = node->next;
724 }
725 }
726
727 void *
728 ralloc_parent_of_linear_parent(void *ptr)
729 {
730 linear_header *node = LINEAR_PARENT_TO_HEADER(ptr);
731 assert(node->magic == LMAGIC);
732 return node->ralloc_parent;
733 }
734
735 void *
736 linear_realloc(void *parent, void *old, unsigned new_size)
737 {
738 unsigned old_size = 0;
739 ralloc_header *new_ptr;
740
741 new_ptr = linear_alloc_child(parent, new_size);
742
743 if (unlikely(!old))
744 return new_ptr;
745
746 old_size = ((linear_size_chunk*)old)[-1].size;
747
748 if (likely(new_ptr && old_size))
749 memcpy(new_ptr, old, MIN2(old_size, new_size));
750
751 return new_ptr;
752 }
753
754 /* All code below is pretty much copied from ralloc and only the alloc
755 * calls are different.
756 */
757
758 char *
759 linear_strdup(void *parent, const char *str)
760 {
761 unsigned n;
762 char *ptr;
763
764 if (unlikely(!str))
765 return NULL;
766
767 n = strlen(str);
768 ptr = linear_alloc_child(parent, n + 1);
769 if (unlikely(!ptr))
770 return NULL;
771
772 memcpy(ptr, str, n);
773 ptr[n] = '\0';
774 return ptr;
775 }
776
777 char *
778 linear_asprintf(void *parent, const char *fmt, ...)
779 {
780 char *ptr;
781 va_list args;
782 va_start(args, fmt);
783 ptr = linear_vasprintf(parent, fmt, args);
784 va_end(args);
785 return ptr;
786 }
787
788 char *
789 linear_vasprintf(void *parent, const char *fmt, va_list args)
790 {
791 unsigned size = printf_length(fmt, args) + 1;
792
793 char *ptr = linear_alloc_child(parent, size);
794 if (ptr != NULL)
795 vsnprintf(ptr, size, fmt, args);
796
797 return ptr;
798 }
799
800 bool
801 linear_asprintf_append(void *parent, char **str, const char *fmt, ...)
802 {
803 bool success;
804 va_list args;
805 va_start(args, fmt);
806 success = linear_vasprintf_append(parent, str, fmt, args);
807 va_end(args);
808 return success;
809 }
810
811 bool
812 linear_vasprintf_append(void *parent, char **str, const char *fmt, va_list args)
813 {
814 size_t existing_length;
815 assert(str != NULL);
816 existing_length = *str ? strlen(*str) : 0;
817 return linear_vasprintf_rewrite_tail(parent, str, &existing_length, fmt, args);
818 }
819
820 bool
821 linear_asprintf_rewrite_tail(void *parent, char **str, size_t *start,
822 const char *fmt, ...)
823 {
824 bool success;
825 va_list args;
826 va_start(args, fmt);
827 success = linear_vasprintf_rewrite_tail(parent, str, start, fmt, args);
828 va_end(args);
829 return success;
830 }
831
832 bool
833 linear_vasprintf_rewrite_tail(void *parent, char **str, size_t *start,
834 const char *fmt, va_list args)
835 {
836 size_t new_length;
837 char *ptr;
838
839 assert(str != NULL);
840
841 if (unlikely(*str == NULL)) {
842 *str = linear_vasprintf(parent, fmt, args);
843 *start = strlen(*str);
844 return true;
845 }
846
847 new_length = printf_length(fmt, args);
848
849 ptr = linear_realloc(parent, *str, *start + new_length + 1);
850 if (unlikely(ptr == NULL))
851 return false;
852
853 vsnprintf(ptr + *start, new_length + 1, fmt, args);
854 *str = ptr;
855 *start += new_length;
856 return true;
857 }
858
859 /* helper routine for strcat/strncat - n is the exact amount to copy */
860 static bool
861 linear_cat(void *parent, char **dest, const char *str, unsigned n)
862 {
863 char *both;
864 unsigned existing_length;
865 assert(dest != NULL && *dest != NULL);
866
867 existing_length = strlen(*dest);
868 both = linear_realloc(parent, *dest, existing_length + n + 1);
869 if (unlikely(both == NULL))
870 return false;
871
872 memcpy(both + existing_length, str, n);
873 both[existing_length + n] = '\0';
874
875 *dest = both;
876 return true;
877 }
878
879 bool
880 linear_strcat(void *parent, char **dest, const char *str)
881 {
882 return linear_cat(parent, dest, str, strlen(str));
883 }