[v5.1] [Heap Trace Standalone] hash map uses doubly linked list, but single linked would be better (IDFGH-9846)

[chipweinberger]

@SoucheSouche

Again, thanks for your work on this PR.

It looks like the hash map entries are storing a doubly linked list. i.e. TAILQ

/* Define struct: linked list of records */
TAILQ_HEAD(heap_trace_record_list_struct_t, heap_trace_record_t); 
typedef struct heap_trace_record_list_struct_t heap_trace_record_list_t;
static heap_trace_hash_list_t hash_map[(size_t)CONFIG_HEAP_TRACE_HASH_MAP_SIZE]; // Buffer used for hashmap entries

AFAICT, a singly linked list is all we need, and would save 50% of the memory.

SLIST_HEAD(heap_trace_record_list_struct_t, heap_trace_record_t*);

Thanks again.

[chipweinberger]

I edited this issue. Hopefully your internal issue tracker supports edits.

[chipweinberger]

Note, the records themselves are doubly linked because:

• during freeing, we traverse backwards
• during printing, we traverse forwards (chronological)

But the hash map does not need this feature.

Also, because the hash map should be large as possible to avoid collisions, we care more that each entry is as small as possible.