GetFEM  5.4.2
bgeot_small_vector.cc
1 /*===========================================================================
2 
3  Copyright (C) 2004-2020 Julien Pommier
4 
5  This file is a part of GetFEM
6 
7  GetFEM is free software; you can redistribute it and/or modify it
8  under the terms of the GNU Lesser General Public License as published
9  by the Free Software Foundation; either version 3 of the License, or
10  (at your option) any later version along with the GCC Runtime Library
11  Exception either version 3.1 or (at your option) any later version.
12  This program is distributed in the hope that it will be useful, but
13  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14  or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
15  License and GCC Runtime Library Exception for more details.
16  You should have received a copy of the GNU Lesser General Public License
17  along with this program; if not, write to the Free Software Foundation,
18  Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
19 
20 ===========================================================================*/
21 
23 namespace bgeot {
24  block_allocator *static_block_allocator::palloc = 0;
25 
26  block_allocator::block_allocator() {
27  for (size_type i=0; i < OBJ_SIZE_LIMIT; ++i)
28  first_unfilled[i] = i ? size_type(-1) : 0;
29  /* bloc 0 is reserved for objects of size 0 -- it won't grow */
30  blocks.push_back(block(0)); blocks.front().init();
31  }
32  block_allocator::~block_allocator() {
33  for (size_type i=0; i < blocks.size(); ++i)
34  if (!blocks[i].empty()) blocks[i].clear();
35  static_block_allocator::palloc = 0;
36  }
37  block_allocator::node_id block_allocator::allocate(block_allocator::size_type n) {
38  if (n == 0) return 0;
39  GMM_ASSERT1(n < OBJ_SIZE_LIMIT,
40  "attempt to allocate a supposedly \"small\" object of "
41  << n << " bytes\n");
42  if (first_unfilled[n] == size_type(-1)) {
43  blocks.push_back(block(n)); blocks.back().init();
44  insert_block_into_unfilled(gmm::uint32_type(blocks.size()-1));
45  GMM_ASSERT1(first_unfilled[n] <
46  (node_id(1)<<(sizeof(node_id)*CHAR_BIT - p2_BLOCKSZ)),
47  "allocation slots exhausted for objects of size " << n
48  << " (" << first_unfilled[n] << " allocated!),\n" << "either"
49  " increase the limit or check for a leak in your code.");
50  }
51  block &b = blocks[first_unfilled[n]]; SVEC_ASSERT(b.objsz == n);
52  if (b.empty()) b.init(); /* realloc memory if needed */
53  size_type vid = b.first_unused_chunk; SVEC_ASSERT(vid < BLOCKSZ);
54  size_type id = vid + first_unfilled[n]*BLOCKSZ;
55  SVEC_ASSERT(b.refcnt(b.first_unused_chunk)==0);
56  b.refcnt(vid) = 1; b.count_unused_chunk--;
57  if (b.count_unused_chunk) {
58  do b.first_unused_chunk++; while (b.refcnt(b.first_unused_chunk));
59  } else {
60  b.first_unused_chunk = BLOCKSZ;
61  remove_block_from_unfilled(first_unfilled[n]);
62  }
63  //cout << "allocated " << first_unfilled[n] << ", " << vid << " @" << obj_data(id) << "\n";
64  SVEC_ASSERT(obj_data(id));
65  memset(obj_data(id), 0, n);
66  //SVEC_ASSERT(refcnt(id) == 0);
67  return id;
68  }
69  void block_allocator::deallocate(block_allocator::node_id nid) {
70  if (nid == 0) return;
71  size_type bid = nid / BLOCKSZ;
72  size_type vid = nid % BLOCKSZ;
73  block &b = blocks[bid];
74  //cout << "deallocate " << bid << "/dim=" << b.dim << ", " << vid << ", unused=" << b.unused << "\n";
75  SVEC_ASSERT(b.refcnt(vid) == 1);
76  b.refcnt(vid) = 0;
77  if (b.count_unused_chunk++ == 0) {
78  insert_block_into_unfilled(bid);
79  b.first_unused_chunk = gmm::uint16_type(vid);
80  } else {
81  b.first_unused_chunk = std::min(b.first_unused_chunk,
82  gmm::uint16_type(vid));
83  if (b.count_unused_chunk == BLOCKSZ) b.clear();
84  }
85  }
86  void block_allocator::memstats() {
87  cout << "block_allocator memory statistics:\ntotal number of blocks: "
88  << blocks.size() << ", each blocks stores " << BLOCKSZ
89  << " chuncks; size of a block header is " << sizeof(block) << " bytes\n";
90  for (size_type d = 0; d < OBJ_SIZE_LIMIT; ++d) {
91  size_type total_cnt=0, used_cnt=0, mem_total = 0, bcnt = 0;
92  for (size_type i=0; i < blocks.size(); ++i) {
93  if (blocks[i].objsz != d) continue; else bcnt++;
94  if (!blocks[i].empty()) {
95  total_cnt += BLOCKSZ;
96  used_cnt += BLOCKSZ - blocks[i].count_unused_chunk;
97  mem_total += (BLOCKSZ+1)*blocks[i].objsz;
98  }
99  mem_total = gmm::uint32_type(mem_total + sizeof(block));
100  }
101  if (mem_total)
102  cout << " sz " << d << ", memory used = " << mem_total << " bytes for "
103  << total_cnt << " nodes, unused space = "
104  << (total_cnt == 0 ? 100. : 100. - 100.* used_cnt / total_cnt)
105  << "%, bcnt=" << bcnt << "\n";
106  }
107  }
108  void block_allocator::insert_block_into_unfilled(block_allocator::size_type bid) {
109  SVEC_ASSERT(bid < blocks.size());
110  dim_type dim = dim_type(blocks[bid].objsz);
111  SVEC_ASSERT(bid != first_unfilled[dim]);
112  SVEC_ASSERT(blocks[bid].prev_unfilled+1 == 0);
113  SVEC_ASSERT(blocks[bid].next_unfilled+1 == 0);
114  blocks[bid].prev_unfilled = size_type(-1);
115  blocks[bid].next_unfilled = first_unfilled[dim];
116  if (first_unfilled[dim] != size_type(-1)) {
117  SVEC_ASSERT(blocks[first_unfilled[dim]].prev_unfilled+1 == 0);
118  blocks[first_unfilled[dim]].prev_unfilled = bid;
119  }
120  first_unfilled[dim] = bid;
121  //cout << "** bloc " << bid << " has been INSERTED in unfilled list, which is now"; show_unfilled(bid);
122  }
123  void block_allocator::remove_block_from_unfilled(block_allocator::size_type bid) {
124  SVEC_ASSERT(bid < blocks.size());
125  dim_type dim = dim_type(blocks[bid].objsz);
126  //cout << "** bloc " << bid << " is going to be REMOVE unfilled list, which is now"; show_unfilled(bid);
127  size_type p = blocks[bid].prev_unfilled; blocks[bid].prev_unfilled = size_type(-1);
128  size_type n = blocks[bid].next_unfilled; blocks[bid].next_unfilled = size_type(-1);
129  if (p != size_type(-1)) { blocks[p].next_unfilled = n; }
130  if (n != size_type(-1)) { blocks[n].prev_unfilled = p; }
131  if (first_unfilled[dim] == bid) { SVEC_ASSERT(p+1==0); first_unfilled[dim] = n; }
132  //cout << "** bloc " << bid << " has been REMOVED in unfilled list, which is now"; show_unfilled(bid);
133  }
134 }
bgeot::size_type
size_t size_type
used as the common size type in the library
Definition: bgeot_poly.h:49
bgeot_small_vector.h
Small (dim < 8) vectors.
bgeot
Basic Geometric Tools.
Definition: bgeot_convex_ref.cc:27