mojoshader_common.c
changeset 946 16fec3a3f687
parent 945 f00ea3986db8
child 956 7888858a6777
--- a/mojoshader_common.c	Tue Nov 09 05:05:41 2010 -0500
+++ b/mojoshader_common.c	Wed Nov 10 00:52:01 2010 -0500
@@ -558,7 +558,7 @@
 
 typedef struct BufferBlock
 {
-    char *data;
+    uint8 *data;
     size_t bytes;
     struct BufferBlock *next;
 } BufferBlock;
@@ -589,13 +589,59 @@
     return buffer;
 } // buffer_create
 
-int buffer_append(Buffer *buffer, const char *data, size_t len)
+void *buffer_reserve(Buffer *buffer, const size_t len)
 {
     // note that we make the blocks bigger than blocksize when we have enough
     //  data to overfill a fresh block, to reduce allocations.
     const size_t blocksize = buffer->block_size;
 
     if (len == 0)
+        return NULL;
+
+    if (buffer->tail != NULL)
+    {
+        const size_t tailbytes = buffer->tail->bytes;
+        const size_t avail = (tailbytes >= blocksize) ? 0 : blocksize - tailbytes;
+        if (len <= avail)
+        {
+            buffer->tail->bytes += len;
+            buffer->total_bytes += len;
+            assert(buffer->tail->bytes <= blocksize);
+            return buffer->tail->data + tailbytes;
+        } // if
+    } // if
+
+    // need to allocate a new block (even if a previous block wasn't filled,
+    //  so this buffer is contiguous).
+    const size_t bytecount = len > blocksize ? len : blocksize;
+    const size_t malloc_len = sizeof (BufferBlock) + bytecount;
+    BufferBlock *item = (BufferBlock *) buffer->m(malloc_len, buffer->d);
+    if (item == NULL)
+        return NULL;
+
+    item->data = ((uint8 *) item) + sizeof (BufferBlock);
+    item->bytes = len;
+    item->next = NULL;
+    if (buffer->tail != NULL)
+        buffer->tail->next = item;
+    else
+        buffer->head = item;
+    buffer->tail = item;
+
+    buffer->total_bytes += len;
+
+    return item->data;
+} // buffer_reserve
+
+int buffer_append(Buffer *buffer, const void *_data, size_t len)
+{
+    const uint8 *data = (const uint8 *) _data;
+
+    // note that we make the blocks bigger than blocksize when we have enough
+    //  data to overfill a fresh block, to reduce allocations.
+    const size_t blocksize = buffer->block_size;
+
+    if (len == 0)
         return 1;
 
     if (buffer->tail != NULL)
@@ -623,7 +669,7 @@
         if (item == NULL)
             return 0;
 
-        item->data = ((char *) item) + sizeof (BufferBlock);
+        item->data = ((uint8 *) item) + sizeof (BufferBlock);
         item->bytes = len;
         item->next = NULL;
         if (buffer->tail != NULL)
@@ -693,7 +739,7 @@
     buffer->total_bytes = 0;
 } // buffer_empty
 
-char *buffer_flatten(Buffer *buffer)
+void *buffer_flatten(Buffer *buffer)
 {
     char *retval = (char *) buffer->m(buffer->total_bytes + 1, buffer->d);
     if (retval == NULL)
@@ -718,7 +764,7 @@
     return retval;
 } // buffer_flatten
 
-char *buffer_merge(Buffer **buffers, const size_t n, size_t *_len)
+void *buffer_merge(Buffer **buffers, const size_t n, size_t *_len)
 {
     Buffer *first = NULL;
     size_t len = 0;
@@ -778,5 +824,99 @@
     } // if
 } // buffer_destroy
 
+static int blockscmp(BufferBlock *item, const uint8 *data, size_t len)
+{
+    if (len == 0)
+        return 1;  // "match"
+
+    while (item != NULL)
+    {
+        const size_t itemremain = item->bytes;
+        const size_t avail = len < itemremain ? len : itemremain;
+        if (memcmp(item->data, data, avail) != 0)
+            return 0;  // not a match.
+
+        if (len == avail)
+            return 1;   // complete match!
+
+        len -= avail;
+        data += avail;
+        item = item->next;
+    } // while
+
+    return 0;  // not a complete match.
+} // blockscmp
+
+ssize_t buffer_find(Buffer *buffer, const size_t start,
+                    const void *_data, const size_t len)
+{
+    if (len == 0)
+        return 0;  // I guess that's right.
+
+    if (start >= buffer->total_bytes)
+        return -1;  // definitely can't match.
+
+    if (len > (buffer->total_bytes - start))
+        return -1;  // definitely can't match.
+
+    // Find the start point somewhere in the center of a buffer.
+    BufferBlock *item = buffer->head;
+    const uint8 *ptr = item->data;
+    size_t pos = 0;
+    if (start > 0)
+    {
+        while (1)
+        {
+            assert(item != NULL);
+            if ((pos + item->bytes) > start)  // start is in this block.
+            {
+                ptr = item->data + (start - pos);
+                break;
+            } // if
+
+            pos += item->bytes;
+            item = item->next;
+        } // while
+    } // if
+
+    // okay, we're at the origin of the search.
+    assert(item != NULL);
+    assert(ptr != NULL);
+
+    const uint8 *data = (const uint8 *) _data;
+    const uint8 first = *data;
+    while (item != NULL)
+    {
+        const size_t itemremain = item->bytes - ((size_t)(ptr-item->data));
+        ptr = (uint8 *) memchr(ptr, first, itemremain);
+        while (ptr != NULL)
+        {
+            const size_t retval = pos + ((size_t) (ptr - item->data));
+            if (len == 1)
+                return retval;  // we're done, here it is!
+
+            const size_t itemremain = item->bytes - ((size_t)(ptr-item->data));
+            const size_t avail = len < itemremain ? len : itemremain;
+            if ((avail == 0) || (memcmp(ptr, data, avail) == 0))
+            {
+                // okay, we've got a (sub)string match! Move to the next block.
+                // check all blocks until we get a complete match or a failure.
+                if (blockscmp(item->next, data+avail, len-avail))
+                    return (ssize_t) retval;
+            } // if
+
+            // try again, further in this block.
+            ptr = (uint8 *) memchr(ptr + 1, first, itemremain - 1);
+        } // while
+
+        pos += item->bytes;
+        item = item->next;
+        if (item != NULL)
+            ptr = item->data;
+    } // while
+
+    return -1;  // no match found.
+} // buffer_find
+
 // end of mojoshader_common.c ...