Start of an implementation using doubly-linked lists and virtual
[people/xl0/gpxe.git] / src / core / buffer.c
1 /*
2  * Routines for filling a buffer with data received piecemeal, where
3  * the size of the data is not necessarily known in advance.
4  *
5  * Some protocols do not provide a mechanism for us to know the size
6  * of the file before we happen to receive a particular block
7  * (e.g. the final block in an MTFTP transfer).  In addition, some
8  * protocols (all the multicast protocols plus any TCP-based protocol)
9  * can, in theory, provide the data in any order.
10  *
11  * Rather than requiring each protocol to implement its own equivalent
12  * of "dd" to arrange the data into well-sized pieces before handing
13  * off to the image loader, we provide these generic buffer functions
14  * which assemble a file into a single contiguous block.  The whole
15  * block is then passed to the image loader.
16  *
17  */
18
19 #include "stddef.h"
20 #include "string.h"
21 #include "buffer.h"
22
23 /*
24  * Split a free block at the specified address, to produce two
25  * consecutive free blocks.  If the address is not within the free
26  * block, do nothing and return success.  If one of the resulting free
27  * blocks would be too small to contain the free block descriptor,
28  * return failure.
29  *
30  */
31 static int split_free_block ( struct buffer_free_block *block, void *split ) {
32         struct buffer_free_block *new_block = split;
33
34         if ( ( split <= ( void * ) block ) || ( split >= block->end ) ) {
35                 /* Split is outside block; nothing to do */
36                 return 1;
37         }
38         
39         if ( ( ( block + 1 ) > new_block ) ||
40              ( ( ( void * ) ( new_block + 1 ) ) > block->end ) ) {
41                 /* Split block would be too small; fail */
42                 return 0;
43         }
44
45         /* Create new block, link into free list */
46         new_block->next         = block->next;
47         new_block->next->prev   = new_block;
48         new_block->prev         = block->prev;
49         new_block->end          = block->end;
50         block->next             = new_block;
51         block->end              = new_block;
52         return 1;
53 }
54
55 /*
56  * Remove a block from the free list.
57  *
58  * Note that this leaves block->next intact.
59  *
60  */
61 static inline void unfree_block ( struct buffer_free_block *block ) {
62         block->prev->next = block->next;
63         block->next->prev = block->prev;
64 }
65
66 /*
67  * Mark a stretch of memory within a buffer as allocated.
68  *
69  */
70 static inline int mark_allocated ( struct buffer *buffer,
71                                    void *start, void *end ) {
72         struct buffer_free_block *block = buffer->free_blocks.next;
73
74         while ( block != &buffer->free_blocks ) {
75                 if ( ! ( split_free_block ( block, start ) &&
76                          split_free_block ( block, end ) ) ) {
77                         /* Block split failure; fail */
78                         return 0;
79                 }
80                 /* At this point, block can be entirely contained
81                  * within [start,end), but it can't overlap.
82                  */
83                 if ( ( ( ( void * ) block ) >= start ) &&
84                      ( ( ( void * ) block ) < end ) ) {
85                         unfree_block ( block );
86                 }
87                 block = block->next;
88         }
89
90         return 1;
91 }
92
93 /*
94  * Place data into a buffer
95  *
96  */
97 int fill_buffer ( struct buffer *buffer, void *data,
98                   off_t offset, size_t len ) {
99         void *start = buffer->start + offset;
100         void *end = start + len;
101
102         if ( ! mark_allocated ( buffer, start, end ) ) {
103                 /* Allocation failure; fail */
104                 return 0;
105         }
106         memcpy ( start, data, len );
107         return 1;
108 }
109
110 /*
111  * Initialise a buffer
112  *
113  */
114 static void init_buffer ( struct buffer *buffer, void *start, size_t len ) {
115         struct buffer_free_block *block;
116
117         block = start;
118         block->next = &buffer->free_blocks;
119         block->prev = &buffer->free_blocks;
120         block->end = start + len;
121
122         buffer->free_blocks.next = block;
123         buffer->free_blocks.prev = block;
124         buffer->start = start;
125         buffer->end = start + len;
126 }
127
128 /*
129  * Move a buffer
130  *
131  */