← Back to branch summary

~ubuntu-branches/ubuntu/jaunty/graphviz/jaunty

« back to all changes in this revision

Viewing changes to tools/vmalloc/vmlast.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
Import upstream version 1.7.16

Show diffs side-by-side

added added

removed removed

Lines of Context:
tools/vmalloc/vmlast.c
 
1
#include        "vmhdr.h"
 
2
 
 
3
/*      Allocation with freeing and reallocing of last allocated block only.
 
4
**
 
5
**      Written by Kiem-Phong Vo, kpv@research.att.com, 01/16/94.
 
6
*/
 
7
 
 
8
#if __STD_C
 
9
static Void_t* lastalloc(Vmalloc_t* vm, size_t size)
 
10
#else
 
11
static Void_t* lastalloc(vm, size)
 
12
Vmalloc_t*      vm;
 
13
size_t          size;
 
14
#endif
 
15
{
 
16
        reg Block_t     *tp, *next;
 
17
        reg Seg_t       *seg, *last;
 
18
        reg size_t      s;
 
19
        reg Vmdata_t*   vd = vm->data;
 
20
        reg int         local;
 
21
        size_t          orgsize;
 
22
 
 
23
        if(!(local = vd->mode&VM_TRUST))
 
24
        {       GETLOCAL(vd,local);
 
25
                if(ISLOCK(vd,local))
 
26
                        return NIL(Void_t*);
 
27
                SETLOCK(vd,local);
 
28
                orgsize = size;
 
29
        }
 
30
 
 
31
        size = size < ALIGN ? ALIGN : ROUND(size,ALIGN);
 
32
        for(;;)
 
33
        {       for(last = NIL(Seg_t*), seg = vd->seg; seg; last = seg, seg = seg->next)
 
34
                {       if(!(tp = seg->free) || (SIZE(tp)+sizeof(Head_t)) < size)
 
35
                                continue;
 
36
                        if(last)
 
37
                        {       last->next = seg->next;
 
38
                                seg->next = vd->seg;
 
39
                                vd->seg = seg;
 
40
                        }
 
41
                        goto got_block;
 
42
                }
 
43
 
 
44
                /* there is no usable free space in region, try extending */
 
45
                if((tp = (*_Vmextend)(vm,size,NIL(Vmsearch_f))) )
 
46
                {       seg = SEG(tp);
 
47
                        goto got_block;
 
48
                }
 
49
                else if(vd->mode&VM_AGAIN)
 
50
                        vd->mode &= ~VM_AGAIN;
 
51
                else    goto done;
 
52
        }
 
53
 
 
54
got_block:
 
55
        if((s = SIZE(tp)) >= size)
 
56
        {       next = (Block_t*)((Vmuchar_t*)tp+size);
 
57
                SIZE(next) = s - size;
 
58
                SEG(next) = seg;
 
59
                seg->free = next;
 
60
        }
 
61
        else    seg->free = NIL(Block_t*);
 
62
 
 
63
        vd->free = seg->last = tp;
 
64
 
 
65
        if(!local && (vd->mode&VM_TRACE) && _Vmtrace)
 
66
                (*_Vmtrace)(vm, NIL(Vmuchar_t*), (Vmuchar_t*)tp, orgsize, 0);
 
67
 
 
68
done:
 
69
        CLRLOCK(vd,local);
 
70
        return (Void_t*)tp;
 
71
}
 
72
 
 
73
#if __STD_C
 
74
static int lastfree(Vmalloc_t* vm, reg Void_t* data )
 
75
#else
 
76
static int lastfree(vm, data)
 
77
Vmalloc_t*      vm;
 
78
reg Void_t*     data;
 
79
#endif
 
80
{
 
81
        reg Seg_t*      seg;
 
82
        reg Block_t*    fp;
 
83
        reg size_t      s;
 
84
        reg Vmdata_t*   vd = vm->data;
 
85
        reg int         local;
 
86
 
 
87
        if(!data)
 
88
                return 0;
 
89
        if(!(local = vd->mode&VM_TRUST) )
 
90
        {       if(ISLOCK(vd,0))
 
91
                        return -1;
 
92
                SETLOCK(vd,0);
 
93
        }
 
94
        if(data != (Void_t*)vd->free)
 
95
        {       if(!local && vm->disc->exceptf)
 
96
                        (void)(*vm->disc->exceptf)(vm,VM_BADADDR,data,vm->disc);
 
97
                CLRLOCK(vd,0);
 
98
                return -1;
 
99
        }
 
100
 
 
101
        seg = vd->seg;
 
102
        if(!local && (vd->mode&VM_TRACE) && _Vmtrace)
 
103
        {       if(seg->free )
 
104
                        s = (Vmuchar_t*)(seg->free) - (Vmuchar_t*)data;
 
105
                else    s = (Vmuchar_t*)BLOCK(seg->baddr) - (Vmuchar_t*)data;
 
106
                (*_Vmtrace)(vm, (Vmuchar_t*)data, NIL(Vmuchar_t*), s, 0);
 
107
        }
 
108
 
 
109
        vd->free = NIL(Block_t*);
 
110
        fp = (Block_t*)data;
 
111
        SEG(fp)  = seg;
 
112
        SIZE(fp) = ((Vmuchar_t*)BLOCK(seg->baddr) - (Vmuchar_t*)data) - sizeof(Head_t);
 
113
        seg->free = fp;
 
114
        seg->last = NIL(Block_t*);
 
115
 
 
116
        CLRLOCK(vd,0);
 
117
        return 0;
 
118
}
 
119
 
 
120
#if __STD_C
 
121
static Void_t* lastresize(Vmalloc_t* vm, reg Void_t* data, size_t size, int type )
 
122
#else
 
123
static Void_t* lastresize(vm, data, size, type )
 
124
Vmalloc_t*      vm;
 
125
reg Void_t*     data;
 
126
size_t          size;
 
127
int             type;
 
128
#endif
 
129
{
 
130
        reg Block_t*    tp;
 
131
        reg Seg_t       *seg;
 
132
        reg int         *d, *ed;
 
133
        reg size_t      oldsize;
 
134
        reg ssize_t     s, ds;
 
135
        reg Vmdata_t*   vd = vm->data;
 
136
        reg int         local;
 
137
        reg Void_t*     addr;
 
138
        Void_t*         orgdata;
 
139
        size_t          orgsize;
 
140
 
 
141
        if(!data)
 
142
        {       oldsize = 0;
 
143
                data = lastalloc(vm,size);
 
144
                goto done;
 
145
        }
 
146
        if(size <= 0)
 
147
        {       (void)lastfree(vm,data);
 
148
                return NIL(Void_t*);
 
149
        }
 
150
 
 
151
        if(!(local = vd->mode&VM_TRUST))
 
152
        {       if(ISLOCK(vd,0))
 
153
                        return NIL(Void_t*);
 
154
                SETLOCK(vd,0);
 
155
                orgdata = data;
 
156
                orgsize = size;
 
157
        }
 
158
 
 
159
        if(data == (Void_t*)vd->free)
 
160
                seg = vd->seg;
 
161
        else
 
162
        {       /* see if it was one of ours */
 
163
                for(seg = vd->seg; seg; seg = seg->next)
 
164
                        if(data >= seg->addr && data < (Void_t*)seg->baddr)
 
165
                                break;
 
166
                if(!seg || (VLONG(data)%ALIGN) != 0 ||
 
167
                   (seg->last && (Vmuchar_t*)data > (Vmuchar_t*)seg->last) )
 
168
                {       CLRLOCK(vd,0);
 
169
                        return NIL(Void_t*);
 
170
                }
 
171
        }
 
172
 
 
173
        /* set 's' to be the current available space */
 
174
        if(data != seg->last)
 
175
        {       if(seg->last && (Vmuchar_t*)data < (Vmuchar_t*)seg->last)
 
176
                        oldsize = (Vmuchar_t*)seg->last - (Vmuchar_t*)data;
 
177
                else    oldsize = (Vmuchar_t*)BLOCK(seg->baddr) - (Vmuchar_t*)data;
 
178
                s = -1;
 
179
        }
 
180
        else
 
181
        {       s = (Vmuchar_t*)BLOCK(seg->baddr) - (Vmuchar_t*)data;
 
182
                if(!(tp = seg->free) )
 
183
                        oldsize = s;
 
184
                else
 
185
                {       oldsize = (Vmuchar_t*)tp - (Vmuchar_t*)data;
 
186
                        seg->free = NIL(Block_t*);
 
187
                }
 
188
        }
 
189
 
 
190
        size = size < ALIGN ? ALIGN : ROUND(size,ALIGN);
 
191
        if(s < 0 || (ssize_t)size > s)
 
192
        {       if(s >= 0) /* amount to extend */
 
193
                {       ds = size-s; ds = ROUND(ds,vd->incr);
 
194
                        addr = (*vm->disc->memoryf)(vm, seg->addr, seg->extent,
 
195
                                                    seg->extent+ds, vm->disc);
 
196
                        if(addr == seg->addr)
 
197
                        {       s += ds;
 
198
                                seg->size += ds;
 
199
                                seg->extent += ds;
 
200
                                seg->baddr += ds;
 
201
                                SIZE(BLOCK(seg->baddr)) = BUSY;
 
202
                        }
 
203
                        else    goto do_alloc;
 
204
                }
 
205
                else
 
206
                { do_alloc:
 
207
                        if(!(type&(VM_RSMOVE|VM_RSCOPY)) )
 
208
                                data = NIL(Void_t*);
 
209
                        else
 
210
                        {       tp = vd->free;
 
211
                                if(!(addr = KPVALLOC(vm,size,lastalloc)) )
 
212
                                {       vd->free = tp;
 
213
                                        data = NIL(Void_t*);
 
214
                                }
 
215
                                else
 
216
                                {       if(type&VM_RSCOPY)
 
217
                                        {       ed = (int*)data;
 
218
                                                d = (int*)addr;
 
219
                                                ds = oldsize < size ? oldsize : size;
 
220
                                                INTCOPY(d,ed,ds);
 
221
                                        }
 
222
 
 
223
                                        if(s >= 0 && seg != vd->seg)
 
224
                                        {       tp = (Block_t*)data;
 
225
                                                SEG(tp) = seg;
 
226
                                                SIZE(tp) = s - sizeof(Head_t);
 
227
                                                seg->free = tp;
 
228
                                        }
 
229
 
 
230
                                        /* new block and size */
 
231
                                        data = addr;
 
232
                                        seg = vd->seg;
 
233
                                        s = (Vmuchar_t*)BLOCK(seg->baddr) -
 
234
                                            (Vmuchar_t*)data;
 
235
                                        seg->free = NIL(Block_t*);
 
236
                                }
 
237
                        }
 
238
                }
 
239
        }
 
240
 
 
241
        if(data)
 
242
        {       if(s >= (ssize_t)(size+sizeof(Head_t)) )
 
243
                {       tp = (Block_t*)((Vmuchar_t*)data + size);
 
244
                        SEG(tp) = seg;
 
245
                        SIZE(tp) = (s - size) - sizeof(Head_t);
 
246
                        seg->free = tp;
 
247
                }
 
248
 
 
249
                vd->free = seg->last = (Block_t*)data;
 
250
 
 
251
                if(!local && (vd->mode&VM_TRACE) && _Vmtrace)
 
252
                        (*_Vmtrace)(vm,(Vmuchar_t*)orgdata,(Vmuchar_t*)data,orgsize,0);
 
253
        }
 
254
 
 
255
        CLRLOCK(vd,0);
 
256
 
 
257
done:   if(data && (type&VM_RSZERO) && size > oldsize)
 
258
        {       d  = (int*)((char*)data + oldsize);
 
259
                size -= oldsize;
 
260
                INTZERO(d,size);
 
261
        }
 
262
 
 
263
        return data;
 
264
}
 
265
 
 
266
 
 
267
#if __STD_C
 
268
static long lastaddr(Vmalloc_t* vm, Void_t* addr)
 
269
#else
 
270
static long lastaddr(vm, addr)
 
271
Vmalloc_t*      vm;
 
272
Void_t*         addr;
 
273
#endif
 
274
{
 
275
        reg Vmdata_t*   vd = vm->data;
 
276
 
 
277
        if(!(vd->mode&VM_TRUST) && ISLOCK(vd,0))
 
278
                return -1L;
 
279
        if(!vd->free || addr < (Void_t*)vd->free || addr >= (Void_t*)vd->seg->baddr)
 
280
                return -1L;
 
281
        else    return (Vmuchar_t*)addr - (Vmuchar_t*)vd->free;
 
282
}
 
283
 
 
284
#if __STD_C
 
285
static long lastsize(Vmalloc_t* vm, Void_t* addr)
 
286
#else
 
287
static long lastsize(vm, addr)
 
288
Vmalloc_t*      vm;
 
289
Void_t*         addr;
 
290
#endif
 
291
{
 
292
        reg Vmdata_t*   vd = vm->data;
 
293
 
 
294
        if(!(vd->mode&VM_TRUST) && ISLOCK(vd,0))
 
295
                return -1L;
 
296
        if(!vd->free || addr != (Void_t*)vd->free )
 
297
                return -1L;
 
298
        else if(vd->seg->free)
 
299
                return (Vmuchar_t*)vd->seg->free - (Vmuchar_t*)addr;
 
300
        else    return (Vmuchar_t*)vd->seg->baddr - (Vmuchar_t*)addr - sizeof(Head_t);
 
301
}
 
302
 
 
303
#if __STD_C
 
304
static int lastcompact(Vmalloc_t* vm)
 
305
#else
 
306
static int lastcompact(vm)
 
307
Vmalloc_t*      vm;
 
308
#endif
 
309
{
 
310
        reg Block_t*    fp;
 
311
        reg Seg_t       *seg, *next;
 
312
        reg size_t      s;
 
313
        reg Vmdata_t*   vd = vm->data;
 
314
 
 
315
        if(!(vd->mode&VM_TRUST))
 
316
        {       if(ISLOCK(vd,0))
 
317
                        return -1;
 
318
                SETLOCK(vd,0);
 
319
        }
 
320
 
 
321
        for(seg = vd->seg; seg; seg = next)
 
322
        {       next = seg->next;
 
323
 
 
324
                if(!(fp = seg->free))
 
325
                        continue;
 
326
 
 
327
                seg->free = NIL(Block_t*);
 
328
                if(seg->size == (s = SIZE(fp)&~BITS))
 
329
                        s = seg->extent;
 
330
                else    s += sizeof(Head_t);
 
331
 
 
332
                if((*_Vmtruncate)(vm,seg,s,1) < 0)
 
333
                        seg->free = fp;
 
334
        }
 
335
 
 
336
        if((vd->mode&VM_TRACE) && _Vmtrace)
 
337
                (*_Vmtrace)(vm,(Vmuchar_t*)0,(Vmuchar_t*)0,0,0);
 
338
 
 
339
        CLRLOCK(vd,0);
 
340
        return 0;
 
341
}
 
342
 
 
343
#if __STD_C
 
344
static Void_t* lastalign(Vmalloc_t* vm, size_t size, size_t align)
 
345
#else
 
346
static Void_t* lastalign(vm, size, align)
 
347
Vmalloc_t*      vm;
 
348
size_t          size;
 
349
size_t          align;
 
350
#endif
 
351
{
 
352
        reg Vmuchar_t*  data;
 
353
        reg size_t      s, orgsize, orgalign;
 
354
        reg Seg_t*      seg;
 
355
        reg Block_t*    next;
 
356
        reg int         local;
 
357
        reg Vmdata_t*   vd = vm->data;
 
358
 
 
359
        if(size <= 0 || align <= 0)
 
360
                return NIL(Void_t*);
 
361
 
 
362
        if(!(local = vd->mode&VM_TRUST) )
 
363
        {       GETLOCAL(vd,local);
 
364
                if(ISLOCK(vd,local) )
 
365
                        return NIL(Void_t*);
 
366
                SETLOCK(vd,local);
 
367
                orgsize = size;
 
368
                orgalign = align;
 
369
        }
 
370
 
 
371
        size = size <= TINYSIZE ? TINYSIZE : ROUND(size,ALIGN);
 
372
        align = MULTIPLE(align,ALIGN);
 
373
 
 
374
        s = size + align; 
 
375
        if(!(data = (Vmuchar_t*)KPVALLOC(vm,s,lastalloc)) )
 
376
                goto done;
 
377
 
 
378
        /* find the segment containing this block */
 
379
        for(seg = vd->seg; seg; seg = seg->next)
 
380
                if(seg->last == (Block_t*)data)
 
381
                        break;
 
382
        /**/ASSERT(seg);
 
383
 
 
384
        /* get a suitably aligned address */
 
385
        if((s = (size_t)(VLONG(data)%align)) != 0)
 
386
                data += align-s; /**/ASSERT((VLONG(data)%align) == 0);
 
387
 
 
388
        /* free the unused tail */
 
389
        next = (Block_t*)(data+size);
 
390
        if((s = (seg->baddr - (Vmuchar_t*)next)) >= sizeof(Block_t))
 
391
        {       SEG(next) = seg;
 
392
                SIZE(next) = s - sizeof(Head_t);
 
393
                seg->free = next;
 
394
        }
 
395
 
 
396
        vd->free = seg->last = (Block_t*)data;
 
397
 
 
398
        if(!local && !(vd->mode&VM_TRUST) && _Vmtrace && (vd->mode&VM_TRACE) )
 
399
                (*_Vmtrace)(vm,NIL(Vmuchar_t*),data,orgsize,orgalign);
 
400
 
 
401
done:
 
402
        CLRLOCK(vd,local);
 
403
 
 
404
        return (Void_t*)data;
 
405
}
 
406
 
 
407
/* Public method for free-1 allocation */
 
408
static Vmethod_t _Vmlast =
 
409
{
 
410
        lastalloc,
 
411
        lastresize,
 
412
        lastfree,
 
413
        lastaddr,
 
414
        lastsize,
 
415
        lastcompact,
 
416
        lastalign,
 
417
        VM_MTLAST
 
418
};
 
419
 
 
420
__DEFINE__(Vmethod_t*,Vmlast,&_Vmlast);