![[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.