jcs
/amend
/amendments
/67
bile_alloc: Replace bubble sort of objects in map
The map is always sorted, so we can avoid burning some CPU by not
iterating through the entire map every time. Find the first place
to stick the new object based on its position and shift everything
else up in one memmove.
Sped up bile regression tests by 16%
jcs made amendment 67 about 1 year ago
--- bile.c Wed Jun 1 16:39:17 2022
+++ bile.c Fri Jun 3 12:47:56 2022
@@ -30,7 +30,6 @@ struct bile_object * bile_object_in_map(struct bile *b
short bile_read_map(struct bile *bile,
struct bile_object *map_ptr);
short bile_write_map(struct bile *bile);
-void bile_sort_by_pos(struct bile *bile);
size_t bile_xwriteat(struct bile *bile, const size_t pos,
const void *data, const size_t len);
@@ -740,18 +739,15 @@ struct bile_object *
bile_alloc(struct bile *bile, const OSType type, const unsigned long id,
const size_t size)
{
- struct bile_object *newo, *o;
+ struct bile_object newo;
size_t last_pos = BILE_HEADER_LEN;
- size_t n;
+ size_t n, map_pos;
if (bile == NULL)
panic("bile_alloc: bogus bile");
_bile_error = bile->last_error = 0;
- bile->map = xreallocarray(bile->map, bile->nobjects + 1,
- BILE_OBJECT_SIZE);
-
/* find a last_pos we can use */
for (n = 0; n < bile->nobjects; n++) {
if (bile->map[n].pos - last_pos >= (size + BILE_OBJECT_SIZE))
@@ -759,23 +755,40 @@ bile_alloc(struct bile *bile, const OSType type, const
last_pos = bile->map[n].pos + BILE_OBJECT_SIZE + bile->map[n].size;
}
- newo = &bile->map[bile->nobjects];
+ /*
+ * The map is always sorted, so walk the map to find out where to
+ * wedge a copy of this new object, then return a pointer to it in
+ * the map.
+ */
+
+ map_pos = bile->nobjects;
+ for (n = 0; n + 1 < bile->nobjects; n++) {
+ if (n == 0 && last_pos < bile->map[n].pos) {
+ map_pos = 0;
+ break;
+ }
+ if (last_pos > bile->map[n].pos &&
+ last_pos < bile->map[n + 1].pos) {
+ map_pos = n + 1;
+ break;
+ }
+ }
+
bile->nobjects++;
- newo->pos = last_pos;
- newo->size = size;
- newo->type = type;
- newo->id = id;
+ bile->map = xreallocarray(bile->map, bile->nobjects, BILE_OBJECT_SIZE);
- bile_sort_by_pos(bile);
-
- /* find our new object pointer after sorting */
- for (n = bile->nobjects; n > 0; n--) {
- o = &bile->map[n - 1];
- if (o->type == type && o->pos == last_pos)
- return o;
+ if (map_pos + 1 < bile->nobjects) {
+ /* shift remaining objects up */
+ memmove(&bile->map[map_pos + 1], &bile->map[map_pos],
+ sizeof(struct bile_object) * (bile->nobjects - map_pos - 1));
}
- panic("bile_alloc: couldn't find newly added object?");
+ bile->map[map_pos].type = type;
+ bile->map[map_pos].id = id;
+ bile->map[map_pos].size = size;
+ bile->map[map_pos].pos = last_pos;
+
+ return &bile->map[map_pos];
}
short
@@ -976,26 +989,4 @@ bile_xwriteat(struct bile *bile, const size_t pos, con
GetFPos(bile->frefnum, &bile->file_size);
return wsize;
-}
-
-void
-bile_sort_by_pos(struct bile *bile)
-{
- ssize_t n, j;
- struct bile_object o;
-
- if (bile == NULL)
- panic("bile_sort_by_pos: bogus bile");
-
- _bile_error = bile->last_error = 0;
-
- for (n = 0; n < bile->nobjects; n++) {
- for (j = 0; j < bile->nobjects - n - 1; j++) {
- if (bile->map[j].pos > bile->map[j + 1].pos) {
- o = bile->map[j];
- bile->map[j] = bile->map[j + 1];
- bile->map[j + 1] = o;
- }
- }
- }
-}
+}