13566673611

Committed 27 Feb 2025 12:42PM CUT coverage: 99.33% (+0.001%) from 99.329%

Build # 13566673611

Build Type

push

github

Committed by

bblanchon

Commit Message

Fix overflowed()

Run Details

2 of 2 new or added lines in 1 file covered. (100.0%)

3 existing lines in 1 file now uncovered.

4005 of 4032 relevant lines covered (99.33%)

10853.67 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

98.2

/src/ArduinoJson/Memory/MemoryPoolList.hpp

// ArduinoJson - https://arduinojson.org
// Copyright © 2014-2025, Benoit BLANCHON
// MIT License

#pragma once

#include <ArduinoJson/Memory/MemoryPool.hpp>
#include <ArduinoJson/Polyfills/assert.hpp>
#include <ArduinoJson/Polyfills/utility.hpp>

#include <string.h>  // memcpy

ARDUINOJSON_BEGIN_PRIVATE_NAMESPACE

using PoolCount = SlotId;

template <typename T>
class MemoryPoolList {
  struct FreeSlot {
    SlotId next;
  };

  static_assert(sizeof(FreeSlot) <= sizeof(T), "T is too small");

 public:
  using Pool = MemoryPool<T>;

  MemoryPoolList() = default;

  ~MemoryPoolList() {
    ARDUINOJSON_ASSERT(count_ == 0);
  }

  friend void swap(MemoryPoolList& a, MemoryPoolList& b) {
    bool aUsedPreallocated = a.pools_ == a.preallocatedPools_;
    bool bUsedPreallocated = b.pools_ == b.preallocatedPools_;

    // Who is using preallocated pools?
    if (aUsedPreallocated && bUsedPreallocated) {
      // both of us => swap preallocated pools
      for (PoolCount i = 0; i < ARDUINOJSON_INITIAL_POOL_COUNT; i++)
        swap_(a.preallocatedPools_[i], b.preallocatedPools_[i]);
    } else if (bUsedPreallocated) {
      // only b => copy b's preallocated pools and give him a's pointer
      for (PoolCount i = 0; i < b.count_; i++)
        a.preallocatedPools_[i] = b.preallocatedPools_[i];
      b.pools_ = a.pools_;
      a.pools_ = a.preallocatedPools_;
    } else if (aUsedPreallocated) {
      // only a => copy a's preallocated pools and give him b's pointer
      for (PoolCount i = 0; i < a.count_; i++)
        b.preallocatedPools_[i] = a.preallocatedPools_[i];
      a.pools_ = b.pools_;
      b.pools_ = b.preallocatedPools_;
    } else {
      // neither => swap pointers
      swap_(a.pools_, b.pools_);
    }

    swap_(a.count_, b.count_);
    swap_(a.capacity_, b.capacity_);
    swap_(a.freeList_, b.freeList_);
  }

  MemoryPoolList& operator=(MemoryPoolList&& src) {
    ARDUINOJSON_ASSERT(count_ == 0);
    if (src.pools_ == src.preallocatedPools_) {
      memcpy(preallocatedPools_, src.preallocatedPools_,
             sizeof(preallocatedPools_));
      pools_ = preallocatedPools_;
    } else {
      pools_ = src.pools_;
      src.pools_ = nullptr;
    }
    count_ = src.count_;
    capacity_ = src.capacity_;
    src.count_ = 0;
    src.capacity_ = 0;
    return *this;
  }

  Slot<T> allocSlot(Allocator* allocator) {
    // try to allocate from free list
    if (freeList_ != NULL_SLOT) {
      return allocFromFreeList();
    }

    // try to allocate from last pool (other pools are full)
    if (count_) {
      auto slot = allocFromLastPool();
      if (slot)
        return slot;
    }

    // create a new pool and try again
    auto pool = addPool(allocator);
    if (!pool)
      return {};

    return allocFromLastPool();
  }

  void freeSlot(Slot<T> slot) {
    reinterpret_cast<FreeSlot*>(slot.ptr())->next = freeList_;
    freeList_ = slot.id();
  }

  T* getSlot(SlotId id) const {
    if (id == NULL_SLOT)
      return nullptr;
    auto poolIndex = SlotId(id / ARDUINOJSON_POOL_CAPACITY);
    auto indexInPool = SlotId(id % ARDUINOJSON_POOL_CAPACITY);
    ARDUINOJSON_ASSERT(poolIndex < count_);
    return pools_[poolIndex].getSlot(indexInPool);
  }

  SlotId find(const T& value) const {
    for (PoolCount i = 0; i < count_; i++) {
      SlotId id = pools_[i].find(value);
      if (id != NULL_SLOT)
        return SlotId(i * ARDUINOJSON_POOL_CAPACITY + id);
    }
    return NULL_SLOT;
  }

  void clear(Allocator* allocator) {
    for (PoolCount i = 0; i < count_; i++)
      pools_[i].destroy(allocator);
    count_ = 0;
    freeList_ = NULL_SLOT;
    if (pools_ != preallocatedPools_) {
      allocator->deallocate(pools_);
      pools_ = preallocatedPools_;
      capacity_ = ARDUINOJSON_INITIAL_POOL_COUNT;
    }
  }

  SlotCount usage() const {
    SlotCount total = 0;
    for (PoolCount i = 0; i < count_; i++)
      total = SlotCount(total + pools_[i].usage());
    return total;
  }

  size_t size() const {
    return Pool::slotsToBytes(usage());
  }

  void shrinkToFit(Allocator* allocator) {
    if (count_ > 0)
      pools_[count_ - 1].shrinkToFit(allocator);
    if (pools_ != preallocatedPools_ && count_ != capacity_) {
      pools_ = static_cast<Pool*>(
          allocator->reallocate(pools_, count_ * sizeof(Pool)));
      ARDUINOJSON_ASSERT(pools_ != nullptr);  // realloc to smaller can't fail
      capacity_ = count_;
    }
  }

 private:
  Slot<T> allocFromFreeList() {
    ARDUINOJSON_ASSERT(freeList_ != NULL_SLOT);
    auto id = freeList_;
    auto slot = getSlot(freeList_);
    freeList_ = reinterpret_cast<FreeSlot*>(slot)->next;
    return {slot, id};
  }

  Slot<T> allocFromLastPool() {
    ARDUINOJSON_ASSERT(count_ > 0);
    auto poolIndex = SlotId(count_ - 1);
    auto slot = pools_[poolIndex].allocSlot();
    if (!slot)
      return {};
    return {slot.ptr(),
            SlotId(poolIndex * ARDUINOJSON_POOL_CAPACITY + slot.id())};
  }

  Pool* addPool(Allocator* allocator) {
    if (count_ == capacity_ && !increaseCapacity(allocator))
      return nullptr;
    auto pool = &pools_[count_++];
    SlotCount poolCapacity = ARDUINOJSON_POOL_CAPACITY;
    if (count_ == maxPools)  // last pool is smaller because of NULL_SLOT
      poolCapacity--;
    pool->create(poolCapacity, allocator);
    return pool;
  }

  bool increaseCapacity(Allocator* allocator) {
    if (capacity_ == maxPools)
      return false;
    void* newPools;
    auto newCapacity = PoolCount(capacity_ * 2);

    if (pools_ == preallocatedPools_) {
      newPools = allocator->allocate(newCapacity * sizeof(Pool));
      if (!newPools)
        return false;
      memcpy(newPools, preallocatedPools_, sizeof(preallocatedPools_));
    } else {
      newPools = allocator->reallocate(pools_, newCapacity * sizeof(Pool));
      if (!newPools)
        return false;
    }

    pools_ = static_cast<Pool*>(newPools);
    capacity_ = newCapacity;
    return true;
  }

  Pool preallocatedPools_[ARDUINOJSON_INITIAL_POOL_COUNT];
  Pool* pools_ = preallocatedPools_;
  PoolCount count_ = 0;
  PoolCount capacity_ = ARDUINOJSON_INITIAL_POOL_COUNT;
  SlotId freeList_ = NULL_SLOT;

 public:
  static const PoolCount maxPools =
      PoolCount(NULL_SLOT / ARDUINOJSON_POOL_CAPACITY + 1);
};

ARDUINOJSON_END_PRIVATE_NAMESPACE

1	// ArduinoJson - https://arduinojson.org
2	// Copyright © 2014-2025, Benoit BLANCHON
3	// MIT License
4
5	#pragma once
6
7	#include <ArduinoJson/Memory/MemoryPool.hpp>
8	#include <ArduinoJson/Polyfills/assert.hpp>
9	#include <ArduinoJson/Polyfills/utility.hpp>
10
11	#include <string.h> // memcpy
12
13	ARDUINOJSON_BEGIN_PRIVATE_NAMESPACE
14
15	using PoolCount = SlotId;
16
17	template <typename T>
18	class MemoryPoolList {
19	struct FreeSlot {
20	SlotId next;
21	};
22
23	static_assert(sizeof(FreeSlot) <= sizeof(T), "T is too small");
24
25	public:
26	using Pool = MemoryPool<T>;
27
28	MemoryPoolList() = default;	4,200✔
29
30	~MemoryPoolList() {	4,200✔
31	ARDUINOJSON_ASSERT(count_ == 0);
32	}	4,200✔
33
34	friend void swap(MemoryPoolList& a, MemoryPoolList& b) {	22✔
35	bool aUsedPreallocated = a.pools_ == a.preallocatedPools_;	22✔
36	bool bUsedPreallocated = b.pools_ == b.preallocatedPools_;	22✔
37
38	// Who is using preallocated pools?
39	if (aUsedPreallocated && bUsedPreallocated) {	22✔
40	// both of us => swap preallocated pools
41	for (PoolCount i = 0; i < ARDUINOJSON_INITIAL_POOL_COUNT; i++)	95✔
42	swap_(a.preallocatedPools_[i], b.preallocatedPools_[i]);	95✔
43	} else if (bUsedPreallocated) {	3✔
44	// only b => copy b's preallocated pools and give him a's pointer
45	for (PoolCount i = 0; i < b.count_; i++)	2✔
46	a.preallocatedPools_[i] = b.preallocatedPools_[i];	1✔
47	b.pools_ = a.pools_;	1✔
48	a.pools_ = a.preallocatedPools_;	1✔
49	} else if (aUsedPreallocated) {	2✔
50	// only a => copy a's preallocated pools and give him b's pointer
51	for (PoolCount i = 0; i < a.count_; i++)	2✔
52	b.preallocatedPools_[i] = a.preallocatedPools_[i];	1✔
53	a.pools_ = b.pools_;	1✔
54	b.pools_ = b.preallocatedPools_;	1✔
55	} else {
56	// neither => swap pointers
57	swap_(a.pools_, b.pools_);	1✔
58	}
59
60	swap_(a.count_, b.count_);	22✔
61	swap_(a.capacity_, b.capacity_);	22✔
62	swap_(a.freeList_, b.freeList_);	22✔
63	}	22✔
64
65	MemoryPoolList& operator=(MemoryPoolList&& src) {
66	ARDUINOJSON_ASSERT(count_ == 0);
67	if (src.pools_ == src.preallocatedPools_) {
68	memcpy(preallocatedPools_, src.preallocatedPools_,
69	sizeof(preallocatedPools_));
70	pools_ = preallocatedPools_;
71	} else {
72	pools_ = src.pools_;
73	src.pools_ = nullptr;
74	}
75	count_ = src.count_;
76	capacity_ = src.capacity_;
77	src.count_ = 0;
78	src.capacity_ = 0;
79	return *this;
80	}
81
82	Slot<T> allocSlot(Allocator* allocator) {	76,007✔
83	// try to allocate from free list
84	if (freeList_ != NULL_SLOT) {	76,007✔
85	return allocFromFreeList();	262✔
86	}
87
88	// try to allocate from last pool (other pools are full)
89	if (count_) {	75,745✔
90	auto slot = allocFromLastPool();	73,922✔
91	if (slot)	73,922✔
92	return slot;	73,614✔
93	}
94
95	// create a new pool and try again
96	auto pool = addPool(allocator);	2,131✔
97	if (!pool)	2,131✔
98	return {};	10✔
99
100	return allocFromLastPool();	2,121✔
101	}
102
103	void freeSlot(Slot<T> slot) {	373✔
104	reinterpret_cast<FreeSlot*>(slot.ptr())->next = freeList_;	373✔
105	freeList_ = slot.id();	373✔
106	}	373✔
107
108	T* getSlot(SlotId id) const {	372,886✔
109	if (id == NULL_SLOT)	372,886✔
110	return nullptr;	4,579✔
111	auto poolIndex = SlotId(id / ARDUINOJSON_POOL_CAPACITY);	368,307✔
112	auto indexInPool = SlotId(id % ARDUINOJSON_POOL_CAPACITY);	368,307✔
113	ARDUINOJSON_ASSERT(poolIndex < count_);
114	return pools_[poolIndex].getSlot(indexInPool);	368,307✔
115	}
116
117	SlotId find(const T& value) const {	1,163✔
118	for (PoolCount i = 0; i < count_; i++) {	1,717✔
119	SlotId id = pools_[i].find(value);	622✔
120	if (id != NULL_SLOT)	622✔
121	return SlotId(i * ARDUINOJSON_POOL_CAPACITY + id);	68✔
122	}
123	return NULL_SLOT;	1,095✔
124	}
125
126	void clear(Allocator* allocator) {	8,094✔
127	for (PoolCount i = 0; i < count_; i++)	10,215✔
128	pools_[i].destroy(allocator);	2,121✔
129	count_ = 0;	8,094✔
130	freeList_ = NULL_SLOT;	8,094✔
131	if (pools_ != preallocatedPools_) {	8,094✔
132	allocator->deallocate(pools_);	7✔
133	pools_ = preallocatedPools_;	7✔
134	capacity_ = ARDUINOJSON_INITIAL_POOL_COUNT;	7✔
135	}
136	}	8,094✔
137
138	SlotCount usage() const {	14✔
139	SlotCount total = 0;	14✔
140	for (PoolCount i = 0; i < count_; i++)	17✔
141	total = SlotCount(total + pools_[i].usage());	3✔
142	return total;	14✔
143	}
144
145	size_t size() const {	14✔
146	return Pool::slotsToBytes(usage());	14✔
147	}
148
149	void shrinkToFit(Allocator* allocator) {	2,700✔
150	if (count_ > 0)	2,700✔
151	pools_[count_ - 1].shrinkToFit(allocator);	531✔
152	if (pools_ != preallocatedPools_ && count_ != capacity_) {	2,700✔
153	pools_ = static_cast<Pool*>(	2✔
154	allocator->reallocate(pools_, count_ * sizeof(Pool)));	1✔
155	ARDUINOJSON_ASSERT(pools_ != nullptr); // realloc to smaller can't fail
156	capacity_ = count_;	1✔
157	}
158	}	2,700✔
159
160	private:
161	Slot<T> allocFromFreeList() {	262✔
162	ARDUINOJSON_ASSERT(freeList_ != NULL_SLOT);
163	auto id = freeList_;	262✔
164	auto slot = getSlot(freeList_);	262✔
165	freeList_ = reinterpret_cast<FreeSlot*>(slot)->next;	262✔
166	return {slot, id};	262✔
167	}
168
169	Slot<T> allocFromLastPool() {	76,043✔
170	ARDUINOJSON_ASSERT(count_ > 0);
171	auto poolIndex = SlotId(count_ - 1);	76,043✔
172	auto slot = pools_[poolIndex].allocSlot();	76,043✔
173	if (!slot)	76,043✔
174	return {};	349✔
175	return {slot.ptr(),
176	SlotId(poolIndex * ARDUINOJSON_POOL_CAPACITY + slot.id())};	75,694✔
177	}
178
179	Pool* addPool(Allocator* allocator) {	2,131✔
180	if (count_ == capacity_ && !increaseCapacity(allocator))	2,131✔
181	return nullptr;	10✔
182	auto pool = &pools_[count_++];	2,121✔
183	SlotCount poolCapacity = ARDUINOJSON_POOL_CAPACITY;	2,121✔
184	if (count_ == maxPools) // last pool is smaller because of NULL_SLOT	2,121✔
185	poolCapacity--;	1✔
186	pool->create(poolCapacity, allocator);	2,121✔
187	return pool;	2,121✔
188	}
189
190	bool increaseCapacity(Allocator* allocator) {	23✔
191	if (capacity_ == maxPools)	23✔
192	return false;	10✔
193	void* newPools;
194	auto newCapacity = PoolCount(capacity_ * 2);	13✔
195
196	if (pools_ == preallocatedPools_) {	13✔
197	newPools = allocator->allocate(newCapacity * sizeof(Pool));	7✔
198	if (!newPools)	7✔
199	return false;	×
200	memcpy(newPools, preallocatedPools_, sizeof(preallocatedPools_));	7✔
201	} else {
202	newPools = allocator->reallocate(pools_, newCapacity * sizeof(Pool));	6✔
203	if (!newPools)	6✔
204	return false;	×
205	}
206
207	pools_ = static_cast<Pool*>(newPools);	13✔
208	capacity_ = newCapacity;	13✔
209	return true;	13✔
210	}
211
212	Pool preallocatedPools_[ARDUINOJSON_INITIAL_POOL_COUNT];
213	Pool* pools_ = preallocatedPools_;
214	PoolCount count_ = 0;
215	PoolCount capacity_ = ARDUINOJSON_INITIAL_POOL_COUNT;
216	SlotId freeList_ = NULL_SLOT;
217
218	public:
219	static const PoolCount maxPools =
220	PoolCount(NULL_SLOT / ARDUINOJSON_POOL_CAPACITY + 1);
221	};
222
223	ARDUINOJSON_END_PRIVATE_NAMESPACE

bblanchon / ArduinoJson / 13566673611

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous