jcs
/subtext
/amendments
/115
bile: Sync with other projects, drop bubble sort in bile_alloc
jcs made amendment 115 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;
- }
- }
- }
-}
+}