|
5164
|
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 } |
