![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to buildobj.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / b / STREAMS / conf / bin / src|
Return to buildobj.c CVS log | Up to [MW Coherent from dump] / coherent / b / STREAMS / conf / bin / src |
1.1 root 1: /*
2: * Implementation of functions prototyped in "buildobj.h"
3: */
4: /*
5: *-IMPORTS:
6: * <sys/compat.h>
7: * USE_PROTO
8: * VOID
9: * ARGS ()
10: * <stdlib.h>
11: * NULL
12: * size_t
13: * free ()
14: * malloc ()
15: * <string.h>
16: * memcpy ()
17: * memset ()
18: */
19:
20: #include <sys/compat.h>
21: #include <stdlib.h>
22: #include <string.h>
23:
24: #include "buildobj.h"
25:
26:
27: /*
28: * Structures that are only really visible inside this compilation unit.
29: *
30: * Note that "o_prev" is used only for nested build contexts, which are
31: * special, although it could be used for all objects if we wanted to spend
32: * the space on allowing stacklike allocation (which we don't, normally).
33: */
34:
35:
36: typedef struct buildchunk bchunk_t;
37: typedef struct objinfo obj_t;
38:
39: struct objinfo {
40: obj_t * o_prev; /* previous object */
41: VOID * o_base; /* base of object */
42: size_t o_size; /* size of object */
43: unsigned char o_building; /* object being built */
44: };
45:
46: struct builder {
47: bchunk_t * b_first; /* first allocated chunk */
48: bchunk_t * b_last; /* last allocated chunk */
49: size_t b_chunksize; /* recommended chunk size */
50: size_t b_align; /* allocation alignment factor */
51:
52: obj_t b_obj; /* current object */
53: bchunk_t * b_chunkp; /* chunk of last/current object */
54: };
55:
56: struct buildchunk {
57: bchunk_t * bc_next; /* next memory chunk */
58: char * bc_base; /* base of chunk space */
59: size_t bc_free; /* amount of free space */
60: };
61:
62:
63: /*
64: * This internal function allocates a new chunk of memory to be parcelled out
65: * to clients. Allocate "b_chunksize" bytes of memory to give out, and copy
66: * any partial allocation over to the new chunk (since we typically only
67: * allocate new chunks when a request to expand a previous allocation
68: * overflows the biggest available block of space).
69: */
70:
71: #if USE_PROTO
72: bchunk_t * (BUILD_CHUNK) (build_t * heap, bchunk_t * bchunkp)
73: #else
74: bchunk_t *
75: BUILD_CHUNK ARGS ((heap, bchunkp))
76: build_t * heap;
77: bchunk_t * bchunkp;
78: #endif
79: {
80:
81: /*
82: * Ok, let's add a new chunk.
83: */
84:
85: if ((bchunkp = (bchunk_t *) malloc (heap->b_chunksize +
86: sizeof (bchunk_t))) == NULL)
87: return NULL;
88:
89: bchunkp->bc_base = (char *) (bchunkp + 1);
90: bchunkp->bc_free = heap->b_chunksize;
91:
92: /*
93: * Copy any previously existing data to the new chunk.
94: */
95:
96: if (heap->b_obj.o_size > 0) {
97:
98: memcpy (bchunkp->bc_base, heap->b_obj.o_base,
99: heap->b_obj.o_size);
100:
101: bchunkp->bc_base += heap->b_obj.o_size;
102: bchunkp->bc_free -= heap->b_obj.o_size;
103: }
104:
105:
106: heap->b_chunkp = bchunkp;
107: heap->b_obj.o_base = (char *) (bchunkp + 1);
108:
109: return bchunkp;
110: }
111:
112:
113: /*
114: * This internal function increases the size of an allocation. If a request
115: * causes an allocation to expand beyond the end of the current chunk, try and
116: * find another chunk that can hold it, and if that fails allocate a new chunk
117: * which is guaranteed to be large enough.
118: *
119: * The client's data is copied to the new space, appended to any previously
120: * allocated data in the same group.
121: */
122:
123: #if USE_PROTO
124: int (BUILD_ADD) (build_t * heap, size_t size, CONST VOID * init)
125: #else
126: int
127: BUILD_ADD ARGS ((heap, size, init))
128: build_t * heap;
129: size_t size;
130: CONST VOID * init;
131: #endif
132: {
133: bchunk_t * bchunkp;
134: size_t total = size + heap->b_obj.o_size;
135:
136: if (size == 0)
137: return BUILD_OK;
138:
139: if (total < size || total + sizeof (bchunk_t) < total)
140: return BUILD_SIZE_OVERFLOW;
141:
142: /*
143: * First, try to fit the expanded allocation in the current chunk.
144: * If there are no chunks allocated yet, let's start.
145: */
146:
147: bchunkp = heap->b_chunkp;
148:
149: if ((bchunkp != NULL && bchunkp->bc_free < size) || bchunkp == NULL) {
150: /*
151: * First, try and find an already allocated chunk that will
152: * hold the expanded allocation.
153: */
154:
155: while (bchunkp != NULL) {
156:
157: if (bchunkp->bc_free >= total) {
158: /*
159: * Transfer existing object information to new
160: * chunk.
161: */
162:
163: if (heap->b_obj.o_size > 0)
164: memcpy (bchunkp->bc_base,
165: heap->b_obj.o_base,
166: heap->b_obj.o_size);
167:
168: heap->b_obj.o_base = bchunkp->bc_base;
169: heap->b_chunkp = bchunkp;
170:
171: bchunkp->bc_base += heap->b_obj.o_size;
172: bchunkp->bc_free -= heap->b_obj.o_size;
173:
174: goto gotmem;
175: }
176:
177: bchunkp = bchunkp->bc_next;
178: }
179:
180: if (total > heap->b_chunksize)
181: heap->b_chunksize = total + (total >> 1);
182:
183: if ((bchunkp = BUILD_CHUNK (heap, bchunkp)) == NULL)
184: return BUILD_NO_MEMORY;
185: }
186:
187: gotmem:
188: /*
189: * OK, let's initialise the new space.
190: */
191:
192: if (init == INIT_ZERO) {
193: /*
194: * The client passed us the special pointer value that means
195: * we should zero the new space.
196: */
197:
198: memset (bchunkp->bc_base, 0, size);
199: } else {
200: /*
201: * The client has given us explicit initialisation values.
202: */
203:
204: memcpy (bchunkp->bc_base, init, size);
205: }
206:
207: bchunkp->bc_base += size;
208: bchunkp->bc_free -= size;
209: heap->b_obj.o_size += size;
210:
211: return BUILD_OK;
212: }
213:
214:
215: /*
216: * Local function which recovers a chunk number from an object address. Note
217: * that we *cannot* do this by merely scanning the chunks looking for one that
218: * encloses the object pointer we have, because relational comparisons between
219: * distinctly-allocated objects yields an undefined result (ie, we could get
220: * false positives).
221: *
222: * However, we can solve the problem by requiring the object pointer to be the
223: * most recent allocation in a given chunk, and passing in the size of the
224: * object. This way, we can test for a match via equality, which is a stronger
225: * test, because two object pointers compare equal if and only if they point
226: * at the same object.
227: *
228: * [ Note that the converse is controversial; it does not appear to be
229: * mandated by ISO C, and the notion of object identity is hotly debated
230: * in C++ circles. Since we will be using pointers that have been derived
231: * via convential means we can ignore such notions of aliasing. ]
232: */
233:
234: #if USE_PROTO
235: LOCAL bchunk_t * (FIND_CHUNK) (build_t * heap, VOID * obj, size_t size)
236: #else
237: LOCAL bchunk_t *
238: FIND_CHUNK ARGS ((heap, obj, size))
239: build_t * heap;
240: VOID * obj;
241: size_t size;
242: #endif
243: {
244: bchunk_t * scan;
245:
246: for (scan = heap->b_first ; scan != NULL ; scan = scan->bc_next)
247: if (scan->bc_base - size == obj)
248: return scan;
249:
250: return NULL;
251: }
252:
253:
254: /*
255: * This function allocates a control block for building variable-sized
256: * objects with. The "chunksize" is the default amount of memory to request
257: * from the C library in a block which other functions will parcel out to
258: * clients.
259: */
260:
261: #if USE_PROTO
262: build_t * (builder_alloc) (size_t chunksize, size_t align)
263: #else
264: build_t *
265: builder_alloc ARGS ((chunksize, align))
266: size_t chunksize;
267: size_t align;
268: #endif
269: {
270: build_t * buildp;
271:
272: if (chunksize < 256)
273: chunksize = 256;
274:
275: if ((buildp = (build_t *) malloc (sizeof (build_t))) != NULL) {
276:
277: buildp->b_first = buildp->b_last = NULL;
278: buildp->b_chunksize = chunksize;
279: buildp->b_align = align == 0 ? 1 : align;
280:
281: buildp->b_obj.o_building = 0;
282: buildp->b_obj.o_prev = NULL; /* no previous object */
283: buildp->b_obj.o_base = NULL; /* not building an object */
284: }
285:
286: return buildp;
287: }
288:
289:
290: /*
291: * Free the basic object builder structure and all the chunk memory that it
292: * attached to itself during its lifetime.
293: */
294:
295: #if USE_PROTO
296: void (builder_free) (build_t * heap)
297: #else
298: void
299: builder_free ARGS ((heap))
300: build_t * heap;
301: #endif
302: {
303: bchunk_t * scan;
304: bchunk_t * next;
305:
306: if (heap == NULL)
307: return;
308:
309: for (scan = heap->b_first ; scan != NULL ; scan = next) {
310:
311: next = scan->bc_next;
312: free (scan);
313: }
314:
315: free (heap);
316: }
317:
318:
319: /*
320: * Simple function to allocate just a single chunk.
321: */
322:
323: #if USE_PROTO
324: VOID * (build_malloc) (build_t * heap, size_t size)
325: #else
326: VOID *
327: build_malloc ARGS ((heap, size))
328: build_t * heap;
329: size_t size;
330: #endif
331: {
332: if (heap == NULL || heap->b_obj.o_building != 0 ||
333: (heap->b_obj.o_base != NULL && heap->b_obj.o_prev != NULL))
334: return NULL;
335:
336: heap->b_obj.o_size = 0;
337: heap->b_obj.o_base = NULL;
338:
339: heap->b_chunkp = heap->b_first;
340:
341: #ifdef __COHERENT__
342: return BUILD_ADD (heap, size, NULL) == 0 ? heap->b_obj.o_base :
343: (VOID *) NULL;
344: #else
345: return BUILD_ADD (heap, size, NULL) == 0 ? heap->b_obj.o_base : NULL;
346: #endif
347: }
348:
349:
350: /*
351: * Begin building some variable-sized object with an initial allocation of
352: * "size" bytes. All previous allocations must be complete before beginning a
353: * new allocation.
354: */
355:
356: #if USE_PROTO
357: int (build_begin) (build_t * heap, size_t size, CONST VOID * init)
358: #else
359: int
360: build_begin ARGS ((heap, size, init))
361: build_t * heap;
362: size_t size;
363: CONST VOID * init;
364: #endif
365: {
366: if (heap == NULL)
367: return BUILD_NULL_HEAP;
368: if (heap->b_obj.o_building != 0)
369: return BUILD_OBJECT_BEGUN;
370:
371: /*
372: * We only allow one object to be built per inner nesting level; since
373: * object descriptors are normally not needed, levels that can be
374: * unwound have to be pushed/popped manually. However, only one object
375: * can be built at an inner level or else the stack could not be
376: * unwound.
377: */
378:
379: if (heap->b_obj.o_base != NULL &&
380: heap->b_obj.o_prev != NULL)
381: return BUILD_BAD_NESTING;
382:
383: heap->b_obj.o_size = 0;
384: heap->b_obj.o_base = NULL;
385: heap->b_obj.o_building = 1;
386:
387: heap->b_chunkp = heap->b_first;
388:
389: return BUILD_ADD (heap, size, init);
390: }
391:
392:
393: /*
394: * Add "size" bytes to the current variable-sized object.
395: */
396:
397: #if USE_PROTO
398: int (build_add) (build_t * heap, size_t size, CONST VOID * init)
399: #else
400: int
401: build_add ARGS ((heap, size, init))
402: build_t * heap;
403: size_t size;
404: CONST VOID * init;
405: #endif
406: {
407: if (heap == NULL)
408: return BUILD_NULL_HEAP;
409: if (heap->b_obj.o_building == 0)
410: return BUILD_NO_OBJECT;
411:
412: return BUILD_ADD (heap, size, init);
413: }
414:
415:
416: /*
417: * Special-case function to add a single character to an object efficiently.
418: * This is useful for functions which must build strings on the fly without
419: * any easy way of predetermining the size.
420: */
421:
422: #if USE_PROTO
423: int (build_addchar) (build_t * heap, char ch)
424: #else
425: int
426: build_addchar ARGS ((heap, ch))
427: build_t * heap;
428: char ch;
429: #endif
430: {
431: bchunk_t * bchunkp;
432:
433: if (heap == NULL)
434: return BUILD_NULL_HEAP;
435: if (heap->b_obj.o_building == 0)
436: return BUILD_NO_OBJECT;
437:
438: /*
439: * Like BUILD_ADD (), but faster in the simplest case.
440: */
441:
442: if ((bchunkp = heap->b_chunkp) == NULL || bchunkp->bc_free == 0)
443: if ((bchunkp = BUILD_CHUNK (heap, bchunkp)) == NULL)
444: return BUILD_NO_MEMORY;
445:
446: * bchunkp->bc_base ++ = ch;
447: bchunkp->bc_free --;
448: heap->b_obj.o_size ++;
449:
450: return BUILD_OK;
451: }
452:
453:
454: /*
455: * End construction of an object, optionally returning the size in bytes
456: * occupied.
457: */
458:
459: #if USE_PROTO
460: VOID * (build_end) (build_t * heap, size_t * size)
461: #else
462: VOID *
463: build_end ARGS ((heap, size))
464: build_t * heap;
465: size_t * size;
466: #endif
467: {
468: size_t adjust;
469:
470: if (heap == NULL || heap->b_obj.o_building == 0)
471: return NULL;
472:
473: if (size != NULL)
474: * size = heap->b_obj.o_size;
475:
476: if ((adjust = heap->b_obj.o_size & (heap->b_align - 1)) != 0) {
477: /*
478: * Waste some space at the end to make the alignment happen.
479: */
480:
481: adjust = heap->b_align - adjust;
482:
483: heap->b_obj.o_size += adjust;
484: heap->b_chunkp->bc_base += adjust;
485: heap->b_chunkp->bc_free -= adjust;
486: }
487:
488: heap->b_obj.o_building = 0;
489: return heap->b_obj.o_base;
490: }
491:
492:
493:
494: /*
495: * Return the storage of the most recently constructed object to the free
496: * pool. Note that the GNU obstack system allows an object heap to be cut back
497: * to any arbitrary point in a stack-like fashion; we don't, because we try
498: * and squeeze space into end-of-chunk areas that the GNU system would leave
499: * alone. Perhaps later we can add options to allow this.
500: */
501:
502: #if USE_PROTO
503: int (build_release) (build_t * heap, CONST VOID * base)
504: #else
505: int
506: build_release ARGS ((heap, base))
507: build_t * heap;
508: CONST VOID * base;
509: #endif
510: {
511: if (heap == NULL)
512: return BUILD_NULL_HEAP;
513: if (base == NULL)
514: return BUILD_NULL_BASE;
515: if (heap->b_obj.o_building == 1)
516: return BUILD_OBJECT_BEGUN;
517: if (heap->b_obj.o_base != base)
518: return BUILD_NOT_LAST;
519:
520: /*
521: * Return "heap->b_size" bytes to the chunk that the last object was
522: * constructed in. We also forget that the object was ever built,
523: * which will allow nested builds to happen.
524: */
525:
526: heap->b_chunkp->bc_base -= heap->b_obj.o_size;
527: heap->b_chunkp->bc_free += heap->b_obj.o_size;
528:
529: heap->b_obj.o_base = NULL;
530: heap->b_obj.o_size = 0;
531:
532: return BUILD_OK;
533: }
534:
535:
536: /*
537: * Temporarily suspend construction of an object and begin nested construction
538: * of another object. Once a nested build context has been entered, only one
539: * object may be allowed to be built (although it may be thrown away and
540: * another one begun).
541: */
542:
543: #if USE_PROTO
544: int (build_push) (build_t * heap)
545: #else
546: int
547: build_push ARGS ((heap))
548: build_t * heap;
549: #endif
550: {
551: obj_t temp;
552: int err;
553:
554: if (heap == NULL)
555: return BUILD_NULL_HEAP;
556:
557: /*
558: * We will need to find some space in the heap for the saved build
559: * context. We take a snapshot of the allocation context in a local
560: * variable for eventual storage in the heap, and start a "new"
561: * allocation. Then, calling BUILD_ADD () will find space for the
562: * snapshot and copy it.
563: */
564:
565: temp = heap->b_obj;
566:
567: heap->b_obj.o_size = 0;
568:
569: if ((err = BUILD_ADD (heap, sizeof (temp), & temp)) != 0) {
570: /*
571: * We couldn't create space for the saved context, so restore
572: * the state and return the error to the caller.
573: */
574:
575: heap->b_obj = temp;
576: } else {
577: /*
578: * Record the location where the saved snapshot was stored as
579: * the back-link in the snapshot chain. Then, we clear the
580: * top object record for use in at most one nested allocation.
581: */
582:
583: heap->b_obj.o_prev = (obj_t *) heap->b_obj.o_base;
584:
585: heap->b_obj.o_size = 0;
586: heap->b_obj.o_base = NULL;
587: }
588:
589: return err;
590: }
591:
592:
593: /*
594: * Undo the actions of build_push (). If there is an allocation in the current
595: * top-level object record, discard it implicitly.
596: */
597:
598: #if USE_PROTO
599: int (build_pop) (build_t * heap)
600: #else
601: int
602: build_pop ARGS ((heap))
603: build_t * heap;
604: #endif
605: {
606: bchunk_t * temp;
607:
608: if (heap == NULL)
609: return BUILD_NULL_HEAP;
610: if (heap->b_obj.o_prev == NULL)
611: return BUILD_STACK_EMPTY;
612:
613: /*
614: * Before we retrieve the previous object context, we have to find
615: * the chunk it is stored in (so that we can discard the saved
616: * context record).
617: */
618:
619: if ((temp = FIND_CHUNK (heap, heap->b_obj.o_prev,
620: sizeof (obj_t))) == NULL)
621: return BUILD_CORRUPT;
622:
623: /*
624: * Implicitly discard top object.
625: */
626:
627: if (heap->b_obj.o_base != NULL) {
628:
629: heap->b_chunkp->bc_base -= heap->b_obj.o_size;
630: heap->b_chunkp->bc_free += heap->b_obj.o_size;
631: }
632:
633:
634: /*
635: * Free saved record and recover the data stored there. We do it in
636: * that backwards order to avoid storing too many temporary pointers,
637: * and because it is safe for us (we won't be interrupted, and our
638: * code doesn't overwrite newly-freed memory).
639: */
640:
641: temp->bc_base -= sizeof (obj_t);
642: temp->bc_free += sizeof (obj_t);
643:
644: heap->b_obj = * heap->b_obj.o_prev;
645:
646:
647: /*
648: * We don't store the previous chunk pointer in the object record
649: * because we can recover it easily if necessary (and it often isn't).
650: */
651:
652: if (heap->b_obj.o_base != NULL &&
653: (heap->b_chunkp = FIND_CHUNK (heap, heap->b_obj.o_base,
654: heap->b_obj.o_size)) == NULL)
655: return BUILD_CORRUPT;
656:
657: return 0;
658: }
659:
660:
661: /*
662: * Return a human-readable string from an error code.
663: */
664:
665: #if USE_PROTO
666: CONST char * (build_error) (int errcode)
667: #else
668: CONST char *
669: build_error ARGS ((errcode))
670: int errcode;
671: #endif
672: {
673: static CONST char * errors [] = {
674: /*
675: * Error strings to match the error enumeration, from 0 to
676: * the maximum negative error code, plus an extra code for
677: * invalid error codes.
678: */
679:
680: "no error",
681: "\"heap\" parameter is NULL",
682: "\"base\" parameter is NULL",
683: "object already under construction",
684: "object construction not begun",
685: "insufficient memory to satisfy request",
686: "overflow of \"size_t\" would result",
687: "not most recently built object",
688: "can build only one object in inner nesting level",
689: "pop of empty saved object stack",
690: "heap appears to be corrupt",
691: "<not a valid error>"
692: };
693:
694: #define ARRAY_LEN(a) (sizeof (a) / sizeof (* (a)))
695:
696: return (errcode > 0 || - errcode >= ARRAY_LEN (errors) ?
697: errors [ARRAY_LEN (errors) - 1] : errors [- errcode]);
698: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.