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