I have an array of structs. Its dimension is fixed:

#define ARRAY_SIZE 200
struct mystruct array[ARRAY_SIZE];

This array is saved into a binary file with fwrite() and loaded in RAM
at startup.

During its run, the application could save a new entry in the array,
starting from index 0. When the array is full, the new entry will be
written to index 0 again, overwriting oldest entry. From this moment on,
the number of entries in the array remains constant at ARRAY_SIZE.

The application can be closed and restarted at any moment and, at
startup, the last situation must be restored from the saved file.

In order to understand what is the next position for the new entry, how
many entries are stored in the array and so on, the struct has two
members: a 16 bits unsigned integer ID and boolean valid flag.

struct mystruct {
bool valid;
uint16_t id;
struct myentry entry;
}

Initially the array is initialized with valid members to false.

Now, I'm trying to write the startup function that, after loading the
array from file to RAM, should detect what is the next entry position,
how many entries are stored in the array and so on.

It's very simple if less than 65536 entries have been added to the
array. It's sufficient to search the entry with the maximum ID.
What happens if one more entry is added? The new entry ID will be zero,
that is the lowest ID in the array, but it's the newest entry in the array.

Any help? I suspect the solution is in the difference of unsigned integers.

pozz <pozzugno@gmail.com> writes:
>I have an array of structs. Its dimension is fixed:
>
> #define ARRAY_SIZE 200
> struct mystruct array[ARRAY_SIZE];
>
>This array is saved into a binary file with fwrite() and loaded in RAM
>at startup.
>
>During its run, the application could save a new entry in the array,
>starting from index 0. When the array is full, the new entry will be
>written to index 0 again, overwriting oldest entry. From this moment on,
>the number of entries in the array remains constant at ARRAY_SIZE.

Generally known as a ring buffer.

https://en.wikipedia.org/wiki/Circular_buffer

Which requires metadata (head and tail pointers, generally
when the producer and consumer are distinct).

Use 'mmap' instead of fwrite() [on posix systems] and include
a fixed header before the ring buffer containing metadata
like the head/tail pointers, capacity, etc.

On 06/11/2023 18:07, pozz wrote:
> I have an array of structs. Its dimension is fixed:
>
>   #define ARRAY_SIZE            200
>   struct mystruct array[ARRAY_SIZE];
>
> This array is saved into a binary file with fwrite() and loaded in RAM
> at startup.
>
> During its run, the application could save a new entry in the array,
> starting from index 0. When the array is full, the new entry will be
> written to index 0 again, overwriting oldest entry. From this moment on,
> the number of entries in the array remains constant at ARRAY_SIZE.
>
> The application can be closed and restarted at any moment and, at
> startup, the last situation must be restored from the saved file.
>
> In order to understand what is the next position for the new entry, how
> many entries are stored in the array and so on, the struct has two
> members: a 16 bits unsigned integer ID and boolean valid flag.
>
>   struct mystruct {
>     bool valid;
>     uint16_t id;
>     struct myentry entry;
>   }
>
> Initially the array is initialized with valid members to false.
>
> Now, I'm trying to write the startup function that, after loading the
> array from file to RAM, should detect what is the next entry position,
> how many entries are stored in the array and so on.
>
> It's very simple if less than 65536 entries have been added to the
> array. It's sufficient to search the entry with the maximum ID.
> What happens if one more entry is added? The new entry ID will be zero,
> that is the lowest ID in the array, but it's the newest entry in the array.
>
> Any help? I suspect the solution is in the difference of unsigned integers.

I'm not sure I follow the exact requirements here. But I'd start by
thinking about a maximum number of element additions that is feasible
for the application - clearly 2 ^ 16 is not enough, but 2 ^ 32 might be,
and 2 ^ 64 certainly will be. Replace the "bool valid; uint16_t id;"
with either "uint32_t id;" or "uint64_t id;", where id 0 is used for
"not valid". (The stored id will thus be one more than the index.)
There's no possibility of overflow, solving that problem.

On 2023-11-06, pozz <pozzugno@gmail.com> wrote:
> Any help? I suspect the solution is in the difference of unsigned integers.

The entry IDs are normally consecutive integers. When they wrap, they
jump to zero. Whenever the wraparound happens, the buffer contains
nothing but IDs that are in the range 65336-65535. The 65336 is the
least recent ID, which will be the victim, overwritten by 0.

Thus, when we scan the buffer, we can divide the situation into these
exhaustive cases:

1. there are entries with IDs in the range range 65337 to 65535
a) there are entries present from the ID range 0 to 198
b) no such entries.

2. there aren't.

In case 1 (a), we know we are in the wrapped situation, and and we
must find the highest ID among the 0 to 198 range.

In the other cases, we look for the highest absolute ID.

In case 1 (b), IDs in the 65537+ range are occurring already, but
wrap around has not yet taken place, so there are no 0 to 198 IDs.
Only high ones below 65537.

In case 2, we are near wraparound yet. The initial state falls into
this camp. (The buffer should be initialized so that the IDs are all
zero.)

I suspect this can be done in one pass. Make a pass through the
array, and collect this information:

A. What is the highest ID, in the range 0 to 198? (Use the value
65535 if it doesn't exist.)

B. What is the absolutely highest ID?

C. Are there IDs in the range 65537+

From that, you have everythign you need. If from (A) you get
a value other than 65535, and (C) indicates yes, then we are in
case 1 (a), and so the value from (A) is the highest ID. Otherwise the
value from (B) is the highest ID. We save the positions as well, in the
same pass.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

pozz <pozzugno@gmail.com> writes:

> I have an array of structs. Its dimension is fixed:
>
> #define ARRAY_SIZE 200
> struct mystruct array[ARRAY_SIZE];
>
> This array is saved into a binary file with fwrite() and loaded in RAM at
> startup.
>
> During its run, the application could save a new entry in the array,
> starting from index 0. When the array is full, the new entry will be
> written to index 0 again, overwriting oldest entry. From this moment on,
> the number of entries in the array remains constant at ARRAY_SIZE.
>
> The application can be closed and restarted at any moment and, at startup,
> the last situation must be restored from the saved file.
>
> In order to understand what is the next position for the new entry, how
> many entries are stored in the array and so on, the struct has two members:
> a 16 bits unsigned integer ID and boolean valid flag.
>
> struct mystruct {
> bool valid;
> uint16_t id;
> struct myentry entry;
> }
>
> Initially the array is initialized with valid members to false.
>
> Now, I'm trying to write the startup function that, after loading the array
> from file to RAM, should detect what is the next entry position, how many
> entries are stored in the array and so on.

You are, fundamentally, storing the wrong data. Save the index of the
next entry as well as the array. And if you are using the IDs only to
find the next entry, remove the id member from the struct.

--
Ben.

scott@slp53.sl.home (Scott Lurndal) writes:
>pozz <pozzugno@gmail.com> writes:
>>I have an array of structs. Its dimension is fixed:
>>
>> #define ARRAY_SIZE 200
>> struct mystruct array[ARRAY_SIZE];
>>
>>This array is saved into a binary file with fwrite() and loaded in RAM
>>at startup.
>>
>>During its run, the application could save a new entry in the array,
>>starting from index 0. When the array is full, the new entry will be
>>written to index 0 again, overwriting oldest entry. From this moment on,
>>the number of entries in the array remains constant at ARRAY_SIZE.
>
>Generally known as a ring buffer.
>
>https://en.wikipedia.org/wiki/Circular_buffer
>
>Which requires metadata (head and tail pointers, generally
>when the producer and consumer are distinct).
>
>Use 'mmap' instead of fwrite() [on posix systems] and include
>a fixed header before the ring buffer containing metadata
>like the head/tail pointers, capacity, etc.
>

A good description of how such a buffer works in a producer/consumer
environment is in the ARM SMMU specification:

IHI0070E_a-System_Memory_Management_Unit_Architecture_Specification.pdf

Which can be downloaded from the ARM website..

See section 3.5 on page 53.

Il 06/11/2023 18:07, pozz ha scritto:
> I have an array of structs.
[...]

I oversimplified my problem. I don't really use fread/fwrite to
load/save the array to the disk. It isn't a disk at all, it's a NOR
Flash in an embedded application.

So the CPU can erase an entire sector (the array), transforming every
byte to 0xFF, or can write whatever value to a location previously erased.

My array is initialized to 0xFF by erasing the Flash sectors where it is
saved in non-volatile way. When a new entry is generated, the struct is
written to the Flash.

pozz ha scritto:
> I have an array of structs. Its dimension is fixed:
>
>   #define ARRAY_SIZE            200
>   struct mystruct array[ARRAY_SIZE];
>
> This array is saved into a binary file with fwrite() and loaded in RAM
> at startup.
>
> During its run, the application could save a new entry in the array,
> starting from index 0. When the array is full, the new entry will be
> written to index 0 again, overwriting oldest entry. From this moment on,
> the number of entries in the array remains constant at ARRAY_SIZE.
>
> The application can be closed and restarted at any moment and, at
> startup, the last situation must be restored from the saved file.
>
> In order to understand what is the next position for the new entry, how
> many entries are stored in the array and so on, the struct has two
> members: a 16 bits unsigned integer ID and boolean valid flag.
>
>   struct mystruct {
>     bool valid;
>     uint16_t id;
>     struct myentry entry;
>   }
>
> Initially the array is initialized with valid members to false.
>
> Now, I'm trying to write the startup function that, after loading the
> array from file to RAM, should detect what is the next entry position,
> how many entries are stored in the array and so on.
>
> It's very simple if less than 65536 entries have been added to the
> array. It's sufficient to search the entry with the maximum ID.
> What happens if one more entry is added? The new entry ID will be zero,
> that is the lowest ID in the array, but it's the newest entry in the array.
>
> Any help? I suspect the solution is in the difference of unsigned integers.

Everything would become simple if you save data starting from the most
recent entry and respecting the circularity. In this way, when
restarting, the first field will also be the most recent. With a
circular beffer it is not important that the data are positioned exactly
as originally.

On 06/11/2023 21:36, pozz wrote:
> Il 06/11/2023 18:07, pozz ha scritto:
>> I have an array of structs.
> [...]
>
> I oversimplified my problem. I don't really use fread/fwrite to
> load/save the array to the disk. It isn't a disk at all, it's a NOR
> Flash in an embedded application.
>
> So the CPU can erase an entire sector (the array), transforming every
> byte to 0xFF, or can write whatever value to a location previously erased.
>
> My array is initialized to 0xFF by erasing the Flash sectors where it is
> saved in non-volatile way. When a new entry is generated, the struct is
> written to the Flash.
>
You might want to consider what would happen if the power went off after
you've erased the sector, but before you've written the new data.

Andy