Linked List and EEPROM approach

I am working on a project similar to this one: [Advice needed] midi controller - EEPROM presets structure - Project Guidance - Arduino Forum

I am using an Arduino Nano.

Namely, I effectively have a 36-switch MIDI controller. Each switch triggers one or more MIDI commands and other commands such as changing graphics on a display. The number of commands can vary with each switch and the user can add, remove, and edit the commands during run-time. These changes should persist through resets and power cycles of the Arduino.

My proposed approach is to have 36 linked list with each element of the list consisting of one command. The initial node of each list is saved in sequential order in the first 36 location of EEPROM with the rest of the linked list data saved in the remaining available EEPROM space and managed by a linked list library.

EEPROM
LOCATION          DATA
    0             [1st NODE OF BUTTON 1 LINKED LIST]
    1             [1st NODE OF BUTTON 2 LINKED LIST]
    .                .
    .                .
    .                .
    35            [1st NODE OF BUTTON 36 LINKED LIST]
    36-END        [ REST OF LINKED LISTS NODES]

Use case example:

  1. Click button 12
  2. Linked list 12 is accessed at EEPROM location 11
  3. Node 1 contents are parsed and MIDI CC command is executed
  4. Node 2 contents are parsed and display text change command is executed
  5. End of linked list reached
  6. Action complete

Are there better ways to do this or pitfalls to avoid?

In particular I'm interested in libraries/methods for managing linked list on EEPROM.

iyDrJUk:
I am working on a project similar to this one: [Advice needed] midi controller - EEPROM presets structure - Project Guidance - Arduino Forum

I am using an Arduino Nano.

Namely, I effectively have a 36-switch MIDI controller. Each switch triggers one or more MIDI commands and other commands such as changing graphics on a display. The number of commands can vary with each switch and the user can add, remove, and edit the commands during run-time. These changes should persist through resets and power cycles of the Arduino.

My proposed approach is to have 36 linked list with each element of the list consisting of one command. The initial node of each list is saved in sequential order in the first 36 location of EEPROM with the rest of the linked list data saved in the remaining available EEPROM space and managed by a linked list library.

EEPROM

LOCATION          DATA
    0            [1st NODE OF BUTTON 1 LINKED LIST]
    1            [1st NODE OF BUTTON 2 LINKED LIST]
    .                .
    .                .
    .                .
    35            [1st NODE OF BUTTON 36 LINKED LIST]
    36-END        [ REST OF LINKED LISTS NODES]




Use case example:
1) Click button 12
2) Linked list 12 is accessed at EEPROM location 11
3) Node 1 contents are parsed and MIDI CC command is executed
4) Node 2 contents are parsed and display text change command is executed
5) End of linked list reached
6) Action complete

Are there better ways to do this or pitfalls to avoid?

In particular I'm interested in libraries/methods for managing linked list on EEPROM.

Welcome to the Arduino forum. I hope you have some experience in programming.

If you have each set of the 36 commands have the maximum number of subcommands, there is no need for a linked list. The subcommands not used can be "nops". Then your index based on the switch number times the array entry length will point you to the beginning of the proper set of commands.

Paul

Unfortunately reserving the maximum amount of sub commands for each switch will exceed available memory. The median size of each command list is likely 1 or 2, but the max will be 15+ and the command data structure will be on the order of 10 bytes each. 15 entries/switch x 10 bytes/entry x 36 switches = 5,400 bytes. :slightly_frowning_face:

I have considered using a 256KB I2C EEPROM to alleviate this limitation but have a bit more to look into around using a serial memory module along with the TCA9548A and 8 i2c OLE displays.

iyDrJUk:
Unfortunately reserving the maximum amount of sub commands for each switch will exceed available memory. The median size of each command list is likely 1 or 2, but the max will be 15+ and the command data structure will be on the order of 10 bytes each. 15 entries/switch x 10 bytes/entry x 36 switches = 5,400 bytes. :slightly_frowning_face:

I have considered using a 256KB I2C EEPROM to alleviate this limitation but have a bit more to look into around using a serial memory module along with the TCA9548A and 8 i2c OLE displays.

Ok, understand.

But you still don't have a "linked list". You have a single dimension array with the 36 initial entries pointing to the start of sub-entries for that group. I guess the last group sub entry will have some identification as it is the last entry for that group.

Paul

A linked list is a sequence of data of indeterminate length. The first element of this data structure is a link to the next structure, that is how many bytes you need to skip before you get to the next data structure.

If you want to extend or reduce the number of elements any of these structures, you move the data structure to the end of the linked list, and then close up the gap you left by moving the whole thing down to cover the missing structure. Only then can you change the data in the linked list.

I once used a linked list to implement a PCB layout program ( 1992 ). It had two types of data, pad shapes and tracks. The tracks consisted of a number of coordinates that you draw a line between. This is a variable length structure as there can be two or more points points defining a track. So the whole PCB could be defined by these two data types in a linked list. It could drag an arbitrary section of pads and tracks to a new location. By drawing this area you could moved all the components fully enclosed in the area without change and yet still have the tracks that started outside the area and finished inside the area rubber band to keep everything connected. Something you still can't do in the majority of affordable PCB layout packages.

For the record this was all done in 40K of Forth code.

Think about your list node data structure. How do you refer to the next node? How do you distinguish MIDI and display commands? How do you manage free space?

DrDiettrich:
Think about your list node data structure. How do you refer to the next node? How do you distinguish MIDI and display commands? How do you manage free space?

By definition each node in the list is linked from at least it's preceding node.

I haven't completely worked out the design of the node data structures to differentiate between various types of commands, but my inclination is to use a different data structure for each command type and wrap this in the data structure for linked list nodes.

I'm hoping a linked list library exist that efficiently manages free memory. If not, I'll have to add some housekeeping functionality. Since EEPROM will only be used for these 36 linked list and nothing else, I suspect the is some memory-friendly O(n) it O(nlogn) time algorithm that can keep track of the available EPROM addresses. Again, this is just a hunch at this point and I'm open to ideas.

With equally sized nodes you only have to maintain a free list and the free memory address.