media: use table instead of linked list for media

For consistency with equipment, use our table macros for pictures.
Generally tables (arrays) are preferred over linked lists, because
they allow random access.

This is mostly copy & paste of the equipment code.

Sadly, our table macros are quite messy and need some revamping.
Therefore, the resulting code is likewise somewhat messy.

Signed-off-by: Berthold Stoeger <bstoeger@mail.tuwien.ac.at>

12 files changed, 127 insertions, 95 deletions

diff --git a/core/dive.c b/core/dive.c
index defead0a1..abfff2bc5 100644
--- a/core/dive.c
+++ b/core/dive.c
@@ -415,13 +415,6 @@ static void copy_dc_renumber(struct dive *d, const struct divecomputer *sdc, str
 	ddc->next = NULL;
 }
 
-/* copy an element in a list of pictures */
-static void copy_pl(struct picture *sp, struct picture *dp)
-{
-	*dp = *sp;
-	dp->filename = copy_string(sp->filename);
-}
-
 /* The first divecomputer is embedded in the dive structure. Free its data but not
  * the structure itself. For all remainding dcs in the list, free data *and* structures. */
 void free_dive_dcs(struct divecomputer *dc)
@@ -443,11 +436,12 @@ static void free_dive_structures(struct dive *d)
 	/* free tags, additional dive computers, and pictures */
 	taglist_free(d->tag_list);
 	free_dive_dcs(&d->dc);
-	STRUCTURED_LIST_FREE(struct picture, d->picture_list, free_picture);
 	clear_cylinder_table(&d->cylinders);
 	free(d->cylinders.cylinders);
 	clear_weightsystem_table(&d->weightsystems);
 	free(d->weightsystems.weightsystems);
+	clear_picture_table(&d->pictures);
+	free(d->pictures.pictures);
 }
 
 void free_dive(struct dive *d)
@@ -480,6 +474,7 @@ static void copy_dive_nodc(const struct dive *s, struct dive *d)
 	*d = *s;
 	memset(&d->cylinders, 0, sizeof(d->cylinders));
 	memset(&d->weightsystems, 0, sizeof(d->weightsystems));
+	memset(&d->pictures, 0, sizeof(d->pictures));
 	d->full_text = NULL;
 	invalidate_dive_cache(d);
 	d->buddy = copy_string(s->buddy);
@@ -488,7 +483,7 @@ static void copy_dive_nodc(const struct dive *s, struct dive *d)
 	d->suit = copy_string(s->suit);
 	copy_cylinders(&s->cylinders, &d->cylinders);
 	copy_weights(&s->weightsystems, &d->weightsystems);
-	STRUCTURED_LIST_COPY(struct picture, s->picture_list, d->picture_list, copy_pl);
+	copy_pictures(&s->pictures, &d->pictures);
 	d->tag_list = taglist_copy(s->tag_list);
 }
 
@@ -3062,7 +3057,7 @@ struct dive *merge_dives(const struct dive *a, const struct dive *b, int offset,
 	MERGE_MAX(res, a, b, number);
 	MERGE_NONZERO(res, a, b, cns);
 	MERGE_NONZERO(res, a, b, visibility);
-	STRUCTURED_LIST_COPY(struct picture, a->picture_list ? a->picture_list : b->picture_list, res->picture_list, copy_pl);
+	copy_pictures(a->pictures.nr ? &a->pictures : &b->pictures, &res->pictures);
 	taglist_merge(&res->tag_list, a->tag_list, b->tag_list);
 	cylinders_map_a = malloc(a->cylinders.nr * sizeof(*cylinders_map_a));
 	cylinders_map_b = malloc(b->cylinders.nr * sizeof(*cylinders_map_b));
@@ -3601,43 +3596,16 @@ void create_picture(const char *filename, int shift_time, bool match_all)
 	if (!match_all && !dive_check_picture_time(dive, timestamp))
 		return;
 
-	struct picture *picture = alloc_picture();
-	picture->filename = strdup(filename);
-	picture->offset.seconds = metadata.timestamp - dive->when + shift_time;
-	picture->location = metadata.location;
+	struct picture picture;
+	picture.filename = strdup(filename);
+	picture.offset.seconds = metadata.timestamp - dive->when + shift_time;
+	picture.location = metadata.location;
 
-	dive_add_picture(dive, picture);
-	dive_set_geodata_from_picture(dive, picture, &dive_site_table);
+	add_picture(&dive->pictures, picture);
+	dive_set_geodata_from_picture(dive, &picture, &dive_site_table);
 	invalidate_dive_cache(dive);
 }
 
-void dive_add_picture(struct dive *dive, struct picture *newpic)
-{
-	struct picture **pic_ptr = &dive->picture_list;
-	/* let's keep the list sorted by time */
-	while (*pic_ptr && (*pic_ptr)->offset.seconds <= newpic->offset.seconds)
-		pic_ptr = &(*pic_ptr)->next;
-	newpic->next = *pic_ptr;
-	*pic_ptr = newpic;
-	return;
-}
-
-// Return true if picture was found and deleted
-bool dive_remove_picture(struct dive *d, const char *filename)
-{
-	struct picture **picture = &d->picture_list;
-	while (*picture && !same_string((*picture)->filename, filename))
-		picture = &(*picture)->next;
-	if (*picture) {
-		struct picture *temp = (*picture)->next;
-		free_picture(*picture);
-		*picture = temp;
-		invalidate_dive_cache(d);
-		return true;
-	}
-	return false;
-}
-
 /* clones a dive and moves given dive computer to front */
 struct dive *make_first_dc(const struct dive *d, int dc_number)
 {
diff --git a/core/dive.h b/core/dive.h
index 12b2a102a..33c7c8b0f 100644
--- a/core/dive.h
+++ b/core/dive.h
@@ -14,6 +14,7 @@
 
 #include "divemode.h"
 #include "equipment.h"
+#include "picture.h"
 
 #ifdef __cplusplus
 extern "C" {
@@ -128,7 +129,6 @@ struct divecomputer {
 	struct divecomputer *next;
 };
 
-struct picture;
 struct dive_site;
 struct dive_site_table;
 struct dive_table;
@@ -160,7 +160,7 @@ struct dive {
 	struct tag_entry *tag_list;
 	struct divecomputer dc;
 	int id; // unique ID for this dive
-	struct picture *picture_list;
+	struct picture_table pictures;
 	unsigned char git_id[20];
 	bool notrip; /* Don't autogroup this dive to a trip */
 	bool selected;
@@ -205,12 +205,12 @@ extern struct event *get_next_divemodechange(const struct event **evd, bool upda
 extern enum divemode_t get_divemode_at_time(const struct divecomputer *dc, int dtime, const struct event **ev_dmc);
 
 /* picture list and methods related to dive picture handling */
-#define FOR_EACH_PICTURE(_dive) \
-	if (_dive)              \
-		for (struct picture *picture = (_dive)->picture_list; picture; picture = picture->next)
+#define FOR_EACH_PICTURE(_dive)								\
+	if ((_dive) && (_dive)->pictures.nr)						\
+		for (struct picture *picture = (_dive)->pictures.pictures;		\
+		     picture < (_dive)->pictures.pictures + (_dive)->pictures.nr;	\
+		     picture++)
 extern void create_picture(const char *filename, int shift_time, bool match_all);
-extern void dive_add_picture(struct dive *d, struct picture *newpic);
-extern bool dive_remove_picture(struct dive *d, const char *filename);
 extern bool picture_check_valid_time(timestamp_t timestamp, int shift_time);
 
 extern bool has_gaschange_event(const struct dive *dive, const struct divecomputer *dc, int idx);
diff --git a/core/equipment.c b/core/equipment.c
index 16d6185c1..05e71cee5 100644
--- a/core/equipment.c
+++ b/core/equipment.c
@@ -132,14 +132,14 @@ weightsystem_t clone_weightsystem(weightsystem_t ws)
 }
 
 /* Add a clone of a weightsystem to the end of a weightsystem table.
- * Cloned in means that the description-string is copied. */
+ * Cloned means that the description-string is copied. */
 void add_cloned_weightsystem(struct weightsystem_table *t, weightsystem_t ws)
 {
 	add_to_weightsystem_table(t, t->nr, clone_weightsystem(ws));
 }
 
 /* Add a clone of a weightsystem to the end of a weightsystem table.
- * Cloned in means that the description-string is copied. */
+ * Cloned means that the description-string is copied. */
 void add_cloned_weightsystem_at(struct weightsystem_table *t, weightsystem_t ws)
 {
 	add_to_weightsystem_table(t, t->nr, clone_weightsystem(ws));
@@ -165,7 +165,7 @@ void add_cylinder(struct cylinder_table *t, int idx, cylinder_t cyl)
 }
 
 /* Add a clone of a cylinder to the end of a cylinder table.
- * Cloned in means that the description-string is copied. */
+ * Cloned means that the description-string is copied. */
 void add_cloned_cylinder(struct cylinder_table *t, cylinder_t cyl)
 {
 	add_cylinder(t, t->nr, clone_cylinder(cyl));
diff --git a/core/load-git.c b/core/load-git.c
index ec922d37b..8d3257d0b 100644
--- a/core/load-git.c
+++ b/core/load-git.c
@@ -34,7 +34,7 @@ struct git_parser_state {
 	struct divecomputer *active_dc;
 	struct dive *active_dive;
 	dive_trip_t *active_trip;
-	struct picture *active_pic;
+	struct picture active_pic;
 	struct dive_site *active_site;
 	struct dive_table *table;
 	struct trip_table *trips;
@@ -1006,13 +1006,13 @@ static void parse_settings_divecomputerid(char *line, struct membuffer *str, str
 static void parse_picture_filename(char *line, struct membuffer *str, struct git_parser_state *state)
 {
 	UNUSED(line);
-	state->active_pic->filename = detach_cstring(str);
+	state->active_pic.filename = detach_cstring(str);
 }
 
 static void parse_picture_gps(char *line, struct membuffer *str, struct git_parser_state *state)
 {
 	UNUSED(str);
-	parse_location(line, &state->active_pic->location);
+	parse_location(line, &state->active_pic.location);
 }
 
 static void parse_picture_hash(char *line, struct membuffer *str, struct git_parser_state *state)
@@ -1615,13 +1615,15 @@ static int parse_picture_entry(struct git_parser_state *state, const git_tree_en
 	if (!blob)
 		return report_error("Unable to read picture file");
 
-	state->active_pic = alloc_picture();
-	state->active_pic->offset.seconds = offset;
+	state->active_pic.offset.seconds = offset;
 
 	for_each_line(blob, picture_parser, state);
-	dive_add_picture(state->active_dive, state->active_pic);
+	add_picture(&state->active_dive->pictures, state->active_pic);
 	git_blob_free(blob);
-	state->active_pic = NULL;
+
+	/* add_picture took ownership of the data -
+	 * clear out our copy just to be sure. */
+	state->active_pic = empty_picture;
 	return 0;
 }
 
diff --git a/core/parse-xml.c b/core/parse-xml.c
index 164b17b83..4aad15bb5 100644
--- a/core/parse-xml.c
+++ b/core/parse-xml.c
@@ -1258,11 +1258,11 @@ static void try_to_fill_dive(struct dive *dive, const char *name, char *buf, str
 	if (match_dc_data_fields(&dive->dc, name, buf, state))
 		return;
 
-	if (MATCH("filename.picture", utf8_string, &state->cur_picture->filename))
+	if (MATCH("filename.picture", utf8_string, &state->cur_picture.filename))
 		return;
-	if (MATCH("offset.picture", offsettime, &state->cur_picture->offset))
+	if (MATCH("offset.picture", offsettime, &state->cur_picture.offset))
 		return;
-	if (MATCH("gps.picture", gps_picture_location, state->cur_picture))
+	if (MATCH("gps.picture", gps_picture_location, &state->cur_picture))
 		return;
 	if (MATCH("hash.picture", utf8_string, &hash)) {
 		/* Legacy -> ignore. */
diff --git a/core/parse.c b/core/parse.c
index be10d65e3..f3b7e0b36 100644
--- a/core/parse.c
+++ b/core/parse.c
@@ -31,7 +31,6 @@ void free_parser_state(struct parser_state *state)
 	free_dive(state->cur_dive);
 	free_trip(state->cur_trip);
 	free_dive_site(state->cur_dive_site);
-	free_picture(state->cur_picture);
 	free((void *)state->cur_extra_data.key);
 	free((void *)state->cur_extra_data.value);
 	free((void *)state->cur_settings.dc.model);
@@ -106,11 +105,11 @@ void event_end(struct parser_state *state)
 {
 	struct divecomputer *dc = get_dc(state);
 	if (state->cur_event.type == 123) {
-		struct picture *pic = alloc_picture();
-		pic->filename = strdup(state->cur_event.name);
+		struct picture pic;
+		pic.filename = strdup(state->cur_event.name);
 		/* theoretically this could fail - but we didn't support multi year offsets */
-		pic->offset.seconds = state->cur_event.time.seconds;
-		dive_add_picture(state->cur_dive, pic);
+		pic.offset.seconds = state->cur_event.time.seconds;
+		add_picture(&state->cur_dive->pictures, pic); /* Takes ownership. */
 	} else {
 		struct event *ev;
 		/* At some point gas change events did not have any type. Thus we need to add
@@ -274,13 +273,13 @@ void trip_end(struct parser_state *state)
 
 void picture_start(struct parser_state *state)
 {
-	state->cur_picture = alloc_picture();
 }
 
 void picture_end(struct parser_state *state)
 {
-	dive_add_picture(state->cur_dive, state->cur_picture);
-	state->cur_picture = NULL;
+	add_picture(&state->cur_dive->pictures, state->cur_picture);
+	/* dive_add_picture took ownership, we can just clear out copy of the data */
+	state->cur_picture = empty_picture;
 }
 
 cylinder_t *cylinder_start(struct parser_state *state)
diff --git a/core/parse.h b/core/parse.h
index 56fbff7b4..8886bcd8d 100644
--- a/core/parse.h
+++ b/core/parse.h
@@ -50,7 +50,7 @@ struct parser_state {
 	location_t cur_location;
 	struct dive_trip *cur_trip;		/* owning */
 	struct sample *cur_sample;		/* non-owning */
-	struct picture *cur_picture;		/* owning */
+	struct picture cur_picture;		/* owning */
 	char *country, *city;			/* owning */
 
 	bool in_settings;
diff --git a/core/picture.c b/core/picture.c
index 3f887efe8..727500afd 100644
--- a/core/picture.c
+++ b/core/picture.c
@@ -1,21 +1,71 @@
 // SPDX-License-Identifier: GPL-2.0
 #include "picture.h"
+#include "table.h"
+#include "subsurface-string.h"
 #include <stdlib.h>
 #include <string.h>
 
-struct picture *alloc_picture()
+static void free_picture(struct picture picture)
 {
-	struct picture *pic = malloc(sizeof(struct picture));
-	if (!pic)
-		exit(1);
-	memset(pic, 0, sizeof(struct picture));
-	return pic;
+	free(picture.filename);
+	picture.filename = NULL;
 }
 
-void free_picture(struct picture *picture)
+static int comp_pictures(struct picture a, struct picture b)
 {
-	if (picture) {
-		free(picture->filename);
-		free(picture);
+	if (a.offset.seconds < b.offset.seconds)
+		return -1;
+	if (a.offset.seconds > b.offset.seconds)
+		return 1;
+	return strcmp(a.filename ?: "", b.filename ?: "");
+}
+
+static bool picture_less_than(struct picture a, struct picture b)
+{
+	return comp_pictures(a, b) < 0;
+}
+
+/* picture table functions */
+//static MAKE_GET_IDX(picture_table, struct picture, pictures)
+static MAKE_GROW_TABLE(picture_table, struct picture, pictures)
+static MAKE_GET_INSERTION_INDEX(picture_table, struct picture, pictures, picture_less_than)
+MAKE_ADD_TO(picture_table, struct picture, pictures)
+static MAKE_REMOVE_FROM(picture_table, pictures)
+//MAKE_SORT(picture_table, struct picture, pictures, comp_pictures)
+//MAKE_REMOVE(picture_table, struct picture, picture)
+MAKE_CLEAR_TABLE(picture_table, pictures, picture)
+
+/* Add a clone of a picture to the end of a picture table.
+ * Cloned means that the filename-string is copied. */
+static void add_cloned_picture(struct picture_table *t, struct picture pic)
+{
+	pic.filename = copy_string(pic.filename);
+	int idx = picture_table_get_insertion_index(t, pic);
+	add_to_picture_table(t, idx, pic);
+}
+
+void copy_pictures(const struct picture_table *s, struct picture_table *d)
+{
+	int i;
+	clear_picture_table(d);
+	for (i = 0; i < s->nr; i++)
+		add_cloned_picture(d, s->pictures[i]);
+}
+
+void add_picture(struct picture_table *t, struct picture newpic)
+{
+	int idx = picture_table_get_insertion_index(t, newpic);
+	add_to_picture_table(t, idx, newpic);
+}
+
+// Return true if picture was found and deleted
+bool remove_picture(struct picture_table *t, const char *filename)
+{
+	for (int i = 0; i < t->nr; ++i) {
+		if (same_string(t->pictures[i].filename, filename)) {
+			remove_from_picture_table(t, i);
+			return true;
+		}
 	}
+	return false;
 }
diff --git a/core/picture.h b/core/picture.h
index 6dd6650dd..da1a42acd 100644
--- a/core/picture.h
+++ b/core/picture.h
@@ -4,6 +4,7 @@
 
 // picture (more precisely media) related strutures and functions
 #include "units.h"
+#include <stddef.h> // For NULL
 
 #ifdef __cplusplus
 extern "C" {
@@ -13,11 +14,26 @@ struct picture {
 	char *filename;
 	offset_t offset;
 	location_t location;
-	struct picture *next;
 };
+static const struct picture empty_picture = { NULL, { 0 }, { { 0 }, { 0 } } };
 
-extern struct picture *alloc_picture();
-extern void free_picture(struct picture *picture);
+/* Table of pictures. Attention: this stores pictures,
+ * *not* pointers to pictures. This has two crucial consequences:
+ * 1) Pointers to pictures are not stable. They may be
+ *    invalidated if the table is reallocated.
+ * 2) add_to_picture_table(), etc. take ownership of the
+ *    picture. Notably of the filename. */
+struct picture_table {
+	int nr, allocated;
+	struct picture *pictures;
+};
+
+/* picture table functions */
+extern void clear_picture_table(struct picture_table *);
+extern void add_to_picture_table(struct picture_table *, int idx, struct picture pic);
+extern void copy_pictures(const struct picture_table *s, struct picture_table *d);
+extern void add_picture(struct picture_table *, struct picture newpic);
+extern bool remove_picture(struct picture_table *, const char *filename);
 
 #ifdef __cplusplus
 }
diff --git a/core/save-git.c b/core/save-git.c
index 01f804006..ec594f131 100644
--- a/core/save-git.c
+++ b/core/save-git.c
@@ -636,7 +636,7 @@ static int save_one_picture(git_repository *repo, struct dir *dir, struct pictur
 
 static int save_pictures(git_repository *repo, struct dir *dir, struct dive *dive)
 {
-	if (dive->picture_list) {
+	if (dive->pictures.nr > 0) {
 		dir = mktree(repo, dir, "Pictures");
 		FOR_EACH_PICTURE(dive) {
 			save_one_picture(repo, dir, picture);
diff --git a/core/save-html.c b/core/save-html.c
index 5a01a6d2e..dd4bde130 100644
--- a/core/save-html.c
+++ b/core/save-html.c
@@ -28,23 +28,20 @@ void write_attribute(struct membuffer *b, const char *att_name, const char *valu
 
 void save_photos(struct membuffer *b, const char *photos_dir, struct dive *dive)
 {
-	struct picture *pic = dive->picture_list;
-
-	if (!pic)
+	if (dive->pictures.nr <= 0)
 		return;
 
 	char *separator = "\"photos\":[";
-	do {
+	FOR_EACH_PICTURE(dive) {
 		put_string(b, separator);
 		separator = ", ";
-		char *fname = get_file_name(local_file_path(pic));
+		char *fname = get_file_name(local_file_path(picture));
 		put_string(b, "{\"filename\":\"");
 		put_quoted(b, fname, 1, 0);
 		put_string(b, "\"}");
-		copy_image_and_overwrite(local_file_path(pic), photos_dir, fname);
+		copy_image_and_overwrite(local_file_path(picture), photos_dir, fname);
 		free(fname);
-		pic = pic->next;
-	} while (pic);
+	}
 	put_string(b, "],");
 }
 
diff --git a/core/structured_list.h b/core/structured_list.h
index cdf76bb8e..e8fc0d9a2 100644
--- a/core/structured_list.h
+++ b/core/structured_list.h
@@ -2,7 +2,7 @@
 #ifndef STRUCTURED_LIST_H
 #define STRUCTURED_LIST_H
 
-/* Clear whole list; this works for taglist, picturelist and dive computers */
+/* Clear whole list; this works for taglist and dive computers */
 #define STRUCTURED_LIST_FREE(_type, _start, _free) \
 	{                                          \
 		_type *_ptr = _start;              \