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