From f2c1beb5c3139238a3570d8f5052635519367d26 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Yaroslav=20de=20la=20Pe=C3=B1a=20Smirnov?= Date: Thu, 13 Oct 2022 01:13:12 +0300 Subject: Switch to vector + qsort instead of bst Doesn't improve perfomance that much (sorting is far from the hotspot), but I realized that I didn't really need a BST for this use-case and I felt dumb for using one :/ --- include/bstree.h | 68 ---------------------------------------------------- include/components.h | 10 ++++---- include/render.h | 3 +-- include/site.h | 4 ++-- 4 files changed, 8 insertions(+), 77 deletions(-) delete mode 100644 include/bstree.h (limited to 'include') diff --git a/include/bstree.h b/include/bstree.h deleted file mode 100644 index 9577b73..0000000 --- a/include/bstree.h +++ /dev/null @@ -1,68 +0,0 @@ -/* - * Copyright 2021 Yaroslav de la Peña Smirnov - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in - * all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ -#ifndef BSTREE_H -#define BSTREE_H - -#include - -/* < 0 means a less than b; 0 means equal; > 0 means a more than b. */ -typedef int (*bst_cmp_fn)(const void *a, const void *b); -typedef void (*bst_free_fn)(void *data); - -struct bstree { - struct bstnode *root; - bst_cmp_fn cmp; - /* It can be NULL, in which case you will have to free the values manually */ - bst_free_fn free; -}; - -struct bstnode { - void *value; - struct bstnode *parent; - struct bstnode *left; - struct bstnode *right; -}; - -typedef bool (*bst_walk_cb)(struct bstnode *, void *data); - -struct bstree *bstree_new(bst_cmp_fn, bst_free_fn); - -struct bstnode *bstree_add(struct bstree *, void *val); - -/* Returns NULL if a node with the value wasn't found */ -struct bstnode *bstree_search(struct bstree *, void *val); - -struct bstnode *bstree_min(struct bstnode *); - -struct bstnode *bstree_max(struct bstnode *); - -struct bstnode *bstree_predecessor(struct bstnode *); - -struct bstnode *bstree_successor(struct bstnode *); - -bool bstree_inorder_walk(struct bstnode *, bst_walk_cb, void *data); - -void bstree_remove(struct bstree *, struct bstnode *); - -void bstree_destroy(struct bstree *); - -#endif diff --git a/include/components.h b/include/components.h index f08d79a..4317187 100644 --- a/include/components.h +++ b/include/components.h @@ -68,11 +68,11 @@ struct album { char year[8]; /* The date of the album is the date of the earliest image */ time_t tstamp; - /* - * Binary search tree with the images of this album sorted by date from + /* + * List/vector with the images of this album to be sorted by from * older to newer. */ - struct bstree *images; + struct vector *images; /* Files/dirs that belong to images and which shouldn't be deleted */ struct hmap *preserved; /* Reference counted hashmap with values to be passed to the template */ @@ -92,7 +92,7 @@ struct image *image_old(struct stat *istat); int image_cmp(const void *a, const void *b); -void image_destroy(void *data); +void image_destroy(struct image *); struct album *album_new(struct album_config *, struct site *, const char *src, const char *rsrc, const struct stat *); @@ -103,6 +103,6 @@ void album_add_image(struct album *, struct image *); void album_set_year(struct album *); -void album_destroy(void *data); +void album_destroy(struct album *); #endif diff --git a/include/render.h b/include/render.h index 9b5e9e2..24c931a 100644 --- a/include/render.h +++ b/include/render.h @@ -1,7 +1,6 @@ #ifndef REVELA_RENDER_H #define REVELA_RENDER_H -#include "bstree.h" #include "config.h" #include "components.h" @@ -86,7 +85,7 @@ bool render_make_image(struct render *r, const char *path, bool render_set_album_vars(struct render *, struct album *); bool render_init(struct render *, const char *path, struct site_config *, - struct bstree *albums); + struct vector *albums); void render_deinit(struct render *); diff --git a/include/site.h b/include/site.h index 43a20d2..0f45667 100644 --- a/include/site.h +++ b/include/site.h @@ -2,7 +2,6 @@ #define REVELA_SITE_H #include "config.h" -#include "bstree.h" #include "render.h" #include "components.h" @@ -29,7 +28,8 @@ struct site { * site_init() */ size_t rel_content_dir; - struct bstree *albums; + /* List/vector with the albums to be sorted from newer to older */ + struct vector *albums; /* Files/dirs that belong to albums and which shouldn't be deleted */ struct hmap *album_dirs; struct render render; -- cgit v1.2.3