1 /* 2 * This file is the collected implementation of libdyn.a, the C 3 * Dynamic Object library. It contains everything. 4 * 5 * There are no restrictions on this code; however, if you make any 6 * changes, I request that you document them so that I do not get 7 * credit or blame for your modifications. 8 * 9 * Written by Barr3y Jaspan, Student Information Processing Board (SIPB) 10 * and MIT-Project Athena, 1989. 11 * 12 * 2002-07-17 Collected full implementation into one source file for 13 * easy inclusion into the one library still dependent on 14 * libdyn. Assume memmove. Old ChangeLog appended. 15 */ 16 17 #include <stdio.h> 18 #include <stdlib.h> 19 #include <string.h> 20 21 #include "dynP.h" 22 23 24 /* old dyn_append.c */ 25 /* 26 * This file is part of libdyn.a, the C Dynamic Object library. It 27 * contains the source code for the function DynAppend(). 28 */ 29 30 /* 31 * Made obsolete by DynInsert, now just a convenience function. 32 */ 33 int DynAppend(obj, els, num) 34 DynObjectP obj; 35 DynPtr els; 36 int num; 37 { 38 return DynInsert(obj, DynSize(obj), els, num); 39 } 40 41 42 /* old dyn_create.c */ 43 /* 44 * This file is part of libdyn.a, the C Dynamic Object library. It 45 * contains the source code for the functions DynCreate() and 46 * DynDestroy(). 47 */ 48 49 #ifndef DEFAULT_INC 50 #define DEFAULT_INC 100 51 #endif 52 53 static int default_increment = DEFAULT_INC; 54 55 DynObjectP DynCreate(el_size, inc) 56 int el_size, inc; 57 { 58 DynObjectP obj; 59 60 obj = (DynObjectP) malloc(sizeof(DynObjectRecP)); 61 if (obj == NULL) 62 return NULL; 63 64 obj->array = (DynPtr) malloc(1); 65 if (obj->array == NULL) { 66 free(obj); 67 return NULL; 68 } 69 obj->array[0] = '\0'; 70 71 obj->el_size = el_size; 72 obj->num_el = obj->size = 0; 73 obj->debug = obj->paranoid = 0; 74 obj->inc = (inc) ? inc : default_increment; 75 obj->initzero = 0; 76 77 return obj; 78 } 79 80 DynObjectP DynCopy(obj) 81 DynObjectP obj; 82 { 83 DynObjectP obj1; 84 85 obj1 = (DynObjectP) malloc(sizeof(DynObjectRecP)); 86 if (obj1 == NULL) 87 return NULL; 88 89 obj1->el_size = obj->el_size; 90 obj1->num_el = obj->num_el; 91 obj1->size = obj->size; 92 obj1->inc = obj->inc; 93 obj1->debug = obj->debug; 94 obj1->paranoid = obj->paranoid; 95 obj1->initzero = obj->initzero; 96 obj1->array = (char *) malloc((size_t) (obj1->el_size * obj1->size)); 97 if (obj1->array == NULL) { 98 free(obj1); 99 return NULL; 100 } 101 memcpy(obj1->array, obj->array, 102 (size_t) (obj1->el_size * obj1->size)); 103 104 return obj1; 105 } 106 107 int DynDestroy(obj) 108 /*@only@*/DynObjectP obj; 109 { 110 if (obj->paranoid) { 111 if (obj->debug) 112 fprintf(stderr, "dyn: destroy: zeroing %d bytes from %p.\n", 113 obj->el_size * obj->size, obj->array); 114 memset(obj->array, 0, (size_t) (obj->el_size * obj->size)); 115 } 116 free(obj->array); 117 free(obj); 118 return DYN_OK; 119 } 120 121 int DynRelease(obj) 122 DynObjectP obj; 123 { 124 if (obj->debug) 125 fprintf(stderr, "dyn: release: freeing object structure.\n"); 126 free(obj); 127 return DYN_OK; 128 } 129 130 131 /* old dyn_debug.c */ 132 /* 133 * This file is part of libdyn.a, the C Dynamic Object library. It 134 * contains the source code for the function DynDebug(). 135 */ 136 137 int DynDebug(obj, state) 138 DynObjectP obj; 139 int state; 140 { 141 obj->debug = state; 142 143 fprintf(stderr, "dyn: debug: Debug state set to %d.\n", state); 144 return DYN_OK; 145 } 146 147 148 /* old dyn_delete.c */ 149 /* 150 * This file is part of libdyn.a, the C Dynamic Object library. It 151 * contains the source code for the function DynDelete(). 152 */ 153 154 /* 155 * Checkers! Get away from that "hard disk erase" button! 156 * (Stupid dog. He almost did it to me again ...) 157 */ 158 int DynDelete(obj, idx) 159 DynObjectP obj; 160 int idx; 161 { 162 if (idx < 0) { 163 if (obj->debug) 164 fprintf(stderr, "dyn: delete: bad index %d\n", idx); 165 return DYN_BADINDEX; 166 } 167 168 if (idx >= obj->num_el) { 169 if (obj->debug) 170 fprintf(stderr, "dyn: delete: Highest index is %d.\n", 171 obj->num_el); 172 return DYN_BADINDEX; 173 } 174 175 if (idx == obj->num_el-1) { 176 if (obj->paranoid) { 177 if (obj->debug) 178 fprintf(stderr, "dyn: delete: last element, zeroing.\n"); 179 memset(obj->array + idx*obj->el_size, 0, (size_t) obj->el_size); 180 } 181 else { 182 if (obj->debug) 183 fprintf(stderr, "dyn: delete: last element, punting.\n"); 184 } 185 } 186 else { 187 if (obj->debug) 188 fprintf(stderr, 189 "dyn: delete: copying %d bytes from %p + %d to + %d.\n", 190 obj->el_size*(obj->num_el - idx), obj->array, 191 (idx+1)*obj->el_size, idx*obj->el_size); 192 193 memmove(obj->array + idx*obj->el_size, 194 obj->array + (idx+1)*obj->el_size, 195 (size_t) obj->el_size*(obj->num_el - idx)); 196 if (obj->paranoid) { 197 if (obj->debug) 198 fprintf(stderr, 199 "dyn: delete: zeroing %d bytes from %p + %d\n", 200 obj->el_size, obj->array, 201 obj->el_size*(obj->num_el - 1)); 202 memset(obj->array + obj->el_size*(obj->num_el - 1), 0, 203 (size_t) obj->el_size); 204 } 205 } 206 207 --obj->num_el; 208 209 if (obj->debug) 210 fprintf(stderr, "dyn: delete: done.\n"); 211 212 return DYN_OK; 213 } 214 215 216 /* old dyn_initzero.c */ 217 /* 218 * This file is part of libdyn.a, the C Dynamic Object library. It 219 * contains the source code for the function DynInitZero(). 220 */ 221 222 int DynInitzero(obj, state) 223 DynObjectP obj; 224 int state; 225 { 226 obj->initzero = state; 227 228 if (obj->debug) 229 fprintf(stderr, "dyn: initzero: initzero set to %d.\n", state); 230 return DYN_OK; 231 } 232 233 234 /* old dyn_insert.c */ 235 /* 236 * This file is part of libdyn.a, the C Dynamic Object library. It 237 * contains the source code for the function DynInsert(). 238 */ 239 240 int DynInsert(obj, idx, els_in, num) 241 DynObjectP obj; 242 void *els_in; 243 int idx, num; 244 { 245 DynPtr els = (DynPtr) els_in; 246 int ret; 247 248 if (idx < 0 || idx > obj->num_el) { 249 if (obj->debug) 250 fprintf(stderr, "dyn: insert: index %d is not in [0,%d]\n", 251 idx, obj->num_el); 252 return DYN_BADINDEX; 253 } 254 255 if (num < 1) { 256 if (obj->debug) 257 fprintf(stderr, "dyn: insert: cannot insert %d elements\n", 258 num); 259 return DYN_BADVALUE; 260 } 261 262 if (obj->debug) 263 fprintf(stderr,"dyn: insert: Moving %d bytes from %p + %d to + %d\n", 264 (obj->num_el-idx)*obj->el_size, obj->array, 265 obj->el_size*idx, obj->el_size*(idx+num)); 266 267 if ((ret = _DynResize(obj, obj->num_el + num)) != DYN_OK) 268 return ret; 269 memmove(obj->array + obj->el_size*(idx + num), 270 obj->array + obj->el_size*idx, 271 (size_t) ((obj->num_el-idx)*obj->el_size)); 272 273 if (obj->debug) 274 fprintf(stderr, "dyn: insert: Copying %d bytes from %p to %p + %d\n", 275 obj->el_size*num, els, obj->array, obj->el_size*idx); 276 277 memmove(obj->array + obj->el_size*idx, els, (size_t) (obj->el_size*num)); 278 obj->num_el += num; 279 280 if (obj->debug) 281 fprintf(stderr, "dyn: insert: done.\n"); 282 283 return DYN_OK; 284 } 285 286 287 /* old dyn_paranoid.c */ 288 /* 289 * This file is part of libdyn.a, the C Dynamic Object library. It 290 * contains the source code for the function DynDebug(). 291 */ 292 293 int DynParanoid(obj, state) 294 DynObjectP obj; 295 int state; 296 { 297 obj->paranoid = state; 298 299 if (obj->debug) 300 fprintf(stderr, "dyn: paranoid: Paranoia set to %d.\n", state); 301 return DYN_OK; 302 } 303 304 305 /* old dyn_put.c */ 306 /* 307 * This file is part of libdyn.a, the C Dynamic Object library. It 308 * contains the source code for the functions DynGet() and DynAdd(). 309 */ 310 311 DynPtr DynArray(obj) 312 DynObjectP obj; 313 { 314 if (obj->debug) 315 fprintf(stderr, "dyn: array: returning array pointer %p.\n", 316 obj->array); 317 318 return obj->array; 319 } 320 321 DynPtr DynGet(obj, num) 322 DynObjectP obj; 323 int num; 324 { 325 if (num < 0) { 326 if (obj->debug) 327 fprintf(stderr, "dyn: get: bad index %d\n", num); 328 return NULL; 329 } 330 331 if (num >= obj->num_el) { 332 if (obj->debug) 333 fprintf(stderr, "dyn: get: highest element is %d.\n", 334 obj->num_el); 335 return NULL; 336 } 337 338 if (obj->debug) 339 fprintf(stderr, "dyn: get: Returning address %p + %d.\n", 340 obj->array, obj->el_size*num); 341 342 return (DynPtr) obj->array + obj->el_size*num; 343 } 344 345 int DynAdd(obj, el) 346 DynObjectP obj; 347 void *el; 348 { 349 int ret; 350 351 ret = DynPut(obj, el, obj->num_el); 352 if (ret != DYN_OK) 353 return ret; 354 355 ++obj->num_el; 356 return ret; 357 } 358 359 /* 360 * WARNING! There is a reason this function is not documented in the 361 * man page. If DynPut used to mutate already existing elements, 362 * everything will go fine. If it is used to add new elements 363 * directly, however, the state within the object (such as 364 * obj->num_el) will not be updated properly and many other functions 365 * in the library will lose. Have a nice day. 366 */ 367 int DynPut(obj, el_in, idx) 368 DynObjectP obj; 369 void *el_in; 370 int idx; 371 { 372 DynPtr el = (DynPtr) el_in; 373 int ret; 374 375 if (obj->debug) 376 fprintf(stderr, "dyn: put: Writing %d bytes from %p to %p + %d\n", 377 obj->el_size, el, obj->array, idx*obj->el_size); 378 379 if ((ret = _DynResize(obj, idx)) != DYN_OK) 380 return ret; 381 382 memmove(obj->array + idx*obj->el_size, el, (size_t) obj->el_size); 383 384 if (obj->debug) 385 fprintf(stderr, "dyn: put: done.\n"); 386 387 return DYN_OK; 388 } 389 390 391 /* old dyn_realloc.c */ 392 /* 393 * This file is part of libdyn.a, the C Dynamic Object library. It 394 * contains the source code for the internal function _DynRealloc(). 395 */ 396 397 /* 398 * Resize the array so that element req exists. 399 */ 400 int _DynResize(obj, req) 401 DynObjectP obj; 402 int req; 403 { 404 int size; 405 406 if (obj->size > req) 407 return DYN_OK; 408 else if (obj->inc > 0) 409 return _DynRealloc(obj, (req - obj->size) / obj->inc + 1); 410 else { 411 if (obj->size == 0) 412 size = -obj->inc; 413 else 414 size = obj->size; 415 416 /*@-shiftsigned@*/ 417 while (size <= req) 418 size <<= 1; 419 /*@=shiftsigned@*/ 420 421 return _DynRealloc(obj, size); 422 } 423 } 424 425 /* 426 * Resize the array by num_incs units. If obj->inc is positive, this 427 * means make it obj->inc*num_incs elements larger. If obj->inc is 428 * negative, this means make the array num_incs elements long. 429 * 430 * Ideally, this function should not be called from outside the 431 * library. However, nothing will break if it is. 432 */ 433 int _DynRealloc(obj, num_incs) 434 DynObjectP obj; 435 int num_incs; 436 { 437 DynPtr temp; 438 int new_size_in_bytes; 439 440 if (obj->inc > 0) 441 new_size_in_bytes = obj->el_size*(obj->size + obj->inc*num_incs); 442 else 443 new_size_in_bytes = obj->el_size*num_incs; 444 445 if (obj->debug) 446 fprintf(stderr, 447 "dyn: alloc: Increasing object by %d bytes (%d incs).\n", 448 new_size_in_bytes - obj->el_size*obj->size, 449 num_incs); 450 451 temp = (DynPtr) realloc(obj->array, (size_t) new_size_in_bytes); 452 if (temp == NULL) { 453 if (obj->debug) 454 fprintf(stderr, "dyn: alloc: Out of memory.\n"); 455 return DYN_NOMEM; 456 } 457 else { 458 obj->array = temp; 459 if (obj->inc > 0) 460 obj->size += obj->inc*num_incs; 461 else 462 obj->size = num_incs; 463 } 464 465 if (obj->debug) 466 fprintf(stderr, "dyn: alloc: done.\n"); 467 468 return DYN_OK; 469 } 470 471 472 /* old dyn_size.c */ 473 /* 474 * This file is part of libdyn.a, the C Dynamic Object library. It 475 * contains the source code for the function DynSize(). 476 */ 477 478 int DynSize(obj) 479 DynObjectP obj; 480 { 481 if (obj->debug) 482 fprintf(stderr, "dyn: size: returning size %d.\n", obj->num_el); 483 484 return obj->num_el; 485 } 486 487 int DynCapacity(obj) 488 DynObjectP obj; 489 { 490 if (obj->debug) 491 fprintf(stderr, "dyn: capacity: returning cap of %d.\n", obj->size); 492 493 return obj->size; 494 } 495 496 /* Old change log, as it relates to source code; build system stuff 497 discarded. 498 499 2001-10-09 Ken Raeburn <raeburn@mit.edu> 500 501 * dyn.h, dynP.h: Make prototypes unconditional. Don't define 502 P(). 503 504 2001-04-25 Ezra Peisach <epeisach@mit.edu> 505 506 * dyn.h: Lclint annotate functions. 507 508 * dyn_create.c (DynCreate): Do not assume that malloc(0) is valid 509 and returns a valid pointer. Fix memory leak if malloc fails. 510 511 * dyn_realloc.c (_DynResize): Turn off warning of shifting a 512 signed variable. 513 514 Thu Nov 9 15:31:31 2000 Ezra Peisach <epeisach@mit.edu> 515 516 * dyn_create.c (DynCopy): Arguments to memcpy were reversed. Found 517 while playing with lclint. 518 519 2000-11-09 Ezra Peisach <epeisach@mit.edu> 520 521 * dyn_create.c, dyn_delete.c, dyn_insert.c, dyn_put.c, 522 dyn_realloc.c: Cast arguments to malloc(), realloc(), memmove() to 523 size_t. 524 525 * dynP.h: Provide full prototypes for _DynRealloc() and _DynResize(). 526 527 * dyn.h: Add prototype for DynAppend. 528 529 2000-06-29 Ezra Peisach <epeisach@mit.edu> 530 531 * dyn_insert.c, dyn_put.c: Include string.h for memmove prototype. 532 533 2000-06-28 Ezra Peisach <epeisach@mit.edu> 534 535 * dyn_create.c, dyn_delete.c, dyn_insert.c, dyn_put.c: Use %p 536 format for displaying pointers. 537 538 2000-06-26 Ezra Peisach <epeisach@mit.edu> 539 540 * dyn_realloc.c: Remove unused variable. 541 542 Sat Dec 6 22:50:03 1997 Ezra Peisach <epeisach@mit.edu> 543 544 * dyn_delete.c: Include <string.h> 545 546 Mon Jul 22 21:37:52 1996 Ezra Peisach <epeisach@mit.edu> 547 548 * dyn.h: If __STDC__ is not defined, generate prototypes implying 549 functions and not variables. 550 551 Mon Jul 22 04:20:48 1996 Marc Horowitz <marc@mit.edu> 552 553 * dyn_insert.c (DynInsert): what used to be #ifdef POSIX, should 554 be #ifdef HAVE_MEMMOVE 555 */ 556