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 */
DynAppend(obj,els,num)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
DynCreate(el_size,inc)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
DynCopy(obj)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
DynDestroy(obj)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
DynRelease(obj)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
DynDebug(obj,state)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 */
DynDelete(obj,idx)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
DynInitzero(obj,state)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
DynInsert(obj,idx,els_in,num)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
DynParanoid(obj,state)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
DynArray(obj)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
DynGet(obj,num)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
DynAdd(obj,el)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 */
DynPut(obj,el_in,idx)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 */
_DynResize(obj,req)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 */
_DynRealloc(obj,num_incs)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
DynSize(obj)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
DynCapacity(obj)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