Mercurial > octave-nkf
comparison liboctave/UMFPACK/UMFPACK/Source/umf_mem_alloc_tail_block.c @ 5164:57077d0ddc8e
[project @ 2005-02-25 19:55:24 by jwe]
author | jwe |
---|---|
date | Fri, 25 Feb 2005 19:55:28 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
5163:9f3299378193 | 5164:57077d0ddc8e |
---|---|
1 /* ========================================================================== */ | |
2 /* === UMF_mem_alloc_tail_block ============================================= */ | |
3 /* ========================================================================== */ | |
4 | |
5 /* -------------------------------------------------------------------------- */ | |
6 /* UMFPACK Version 4.4, Copyright (c) 2005 by Timothy A. Davis. CISE Dept, */ | |
7 /* Univ. of Florida. All Rights Reserved. See ../Doc/License for License. */ | |
8 /* web: http://www.cise.ufl.edu/research/sparse/umfpack */ | |
9 /* -------------------------------------------------------------------------- */ | |
10 | |
11 /* The UMF_mem_* routines manage the Numeric->Memory memory space. */ | |
12 | |
13 #include "umf_internal.h" | |
14 | |
15 /* allocate nunits from tail of Numeric->Memory */ | |
16 /* (requires nunits+1, for header). */ | |
17 /* Returns the index into Numeric->Memory if successful, or 0 on failure. */ | |
18 | |
19 GLOBAL Int UMF_mem_alloc_tail_block | |
20 ( | |
21 NumericType *Numeric, | |
22 Int nunits | |
23 ) | |
24 { | |
25 Int bigsize, usage ; | |
26 Unit *p, *pnext, *pbig ; | |
27 | |
28 ASSERT (Numeric != (NumericType *) NULL) ; | |
29 ASSERT (Numeric->Memory != (Unit *) NULL) ; | |
30 | |
31 #ifndef NDEBUG | |
32 if (UMF_allocfail) | |
33 { | |
34 /* pretend to fail, to test garbage_collection */ | |
35 DEBUGm2 (("UMF_mem_alloc_tail_block: pretend to fail\n")) ; | |
36 UMF_allocfail = FALSE ; /* don't fail the next time */ | |
37 return (0) ; | |
38 } | |
39 DEBUG2 (("UMF_mem_alloc_tail_block, size: "ID" + 1 = "ID": ", | |
40 nunits, nunits+1)) ; | |
41 #endif | |
42 | |
43 bigsize = 0 ; | |
44 pbig = (Unit *) NULL ; | |
45 | |
46 ASSERT (nunits > 0) ; /* size must be positive */ | |
47 if (Numeric->ibig != EMPTY) | |
48 { | |
49 ASSERT (Numeric->ibig > Numeric->itail) ; | |
50 ASSERT (Numeric->ibig < Numeric->size) ; | |
51 pbig = Numeric->Memory + Numeric->ibig ; | |
52 bigsize = -pbig->header.size ; | |
53 ASSERT (bigsize > 0) ; /* Numeric->ibig is free */ | |
54 ASSERT (pbig->header.prevsize >= 0) ; /* prev. is not free */ | |
55 } | |
56 | |
57 if (pbig && bigsize >= nunits) | |
58 { | |
59 | |
60 /* use the biggest block, somewhere in middle of memory */ | |
61 p = pbig ; | |
62 pnext = p + 1 + bigsize ; | |
63 /* next is in range */ | |
64 ASSERT (pnext < Numeric->Memory + Numeric->size) ; | |
65 /* prevsize of next = this size */ | |
66 ASSERT (pnext->header.prevsize == bigsize) ; | |
67 /* next is not free */ | |
68 ASSERT (pnext->header.size > 0) ; | |
69 bigsize -= nunits + 1 ; | |
70 | |
71 if (bigsize < 4) | |
72 { | |
73 /* internal fragmentation would be too small */ | |
74 /* allocate the entire free block */ | |
75 p->header.size = -p->header.size ; | |
76 DEBUG2 (("GET BLOCK: p: "ID" size: "ID", all of big: "ID" size: " | |
77 ID"\n", (Int) (p-Numeric->Memory), nunits, Numeric->ibig, | |
78 p->header.size)) ; | |
79 /* no more biggest block */ | |
80 Numeric->ibig = EMPTY ; | |
81 | |
82 } | |
83 else | |
84 { | |
85 | |
86 /* allocate just the first nunits Units of the free block */ | |
87 p->header.size = nunits ; | |
88 /* make a new free block */ | |
89 Numeric->ibig += nunits + 1 ; | |
90 pbig = Numeric->Memory + Numeric->ibig ; | |
91 pbig->header.size = -bigsize ; | |
92 pbig->header.prevsize = nunits ; | |
93 pnext->header.prevsize = bigsize ; | |
94 DEBUG2 (("GET BLOCK: p: "ID" size: "ID", some of big: "ID" left: " | |
95 ID"\n", (Int) (p-Numeric->Memory), nunits, Numeric->ibig, | |
96 bigsize)) ; | |
97 } | |
98 | |
99 } | |
100 else | |
101 { | |
102 | |
103 /* allocate from the top of tail */ | |
104 pnext = Numeric->Memory + Numeric->itail ; | |
105 DEBUG2 (("GET BLOCK: from tail ")) ; | |
106 if ((nunits + 1) > (Numeric->itail - Numeric->ihead)) | |
107 { | |
108 DEBUG2 (("\n")) ; | |
109 return (0) ; | |
110 } | |
111 Numeric->itail -= (nunits + 1) ; | |
112 p = Numeric->Memory + Numeric->itail ; | |
113 p->header.size = nunits ; | |
114 p->header.prevsize = 0 ; | |
115 pnext->header.prevsize = nunits ; | |
116 DEBUG2 (("p: "ID" size: "ID", new tail "ID"\n", | |
117 (Int) (p-Numeric->Memory), nunits, Numeric->itail)) ; | |
118 } | |
119 | |
120 Numeric->tail_usage += p->header.size + 1 ; | |
121 usage = Numeric->ihead + Numeric->tail_usage ; | |
122 Numeric->max_usage = MAX (Numeric->max_usage, usage) ; | |
123 | |
124 #ifndef NDEBUG | |
125 UMF_debug -= 10 ; | |
126 UMF_dump_memory (Numeric) ; | |
127 UMF_debug += 10 ; | |
128 #endif | |
129 | |
130 /* p points to the header. Add one to point to the usable block itself. */ | |
131 /* return the offset into Numeric->Memory */ | |
132 return ((p - Numeric->Memory) + 1) ; | |
133 } |