Index: boot/Makefile.common =================================================================== --- boot/Makefile.common (revision 6eef3c4403b57fc01e6b79237e6cc0a6a6a7d016) +++ boot/Makefile.common (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -149,4 +149,5 @@ RD_APPS_NON_ESSENTIAL = \ + $(USPACE_PATH)/app/bithenge/bithenge \ $(USPACE_PATH)/app/blkdump/blkdump \ $(USPACE_PATH)/app/bnchmark/bnchmark \ Index: uspace/Makefile =================================================================== --- uspace/Makefile (revision 6eef3c4403b57fc01e6b79237e6cc0a6a6a7d016) +++ uspace/Makefile (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -35,4 +35,5 @@ DIRS = \ app/bdsh \ + app/bithenge \ app/blkdump \ app/bnchmark \ Index: uspace/app/bithenge/Makefile =================================================================== --- uspace/app/bithenge/Makefile (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/Makefile (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,42 @@ +# +# Copyright (c) 2012 Sean Bartell +# All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# - Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# - Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution. +# - The name of the author may not be used to endorse or promote products +# derived from this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR +# IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +# OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +# IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, +# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT +# NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF +# THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +# + +USPACE_PREFIX = ../.. +LIBS = $(LIBBLOCK_PREFIX)/libblock.a +EXTRA_CFLAGS = -I$(LIBBLOCK_PREFIX) +BINARY = bithenge + +SOURCES = \ + blob.c \ + block.c \ + file.c \ + print.c \ + test.c \ + tree.c + +include $(USPACE_PREFIX)/Makefile.common Index: uspace/app/bithenge/blob.c =================================================================== --- uspace/app/bithenge/blob.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/blob.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,300 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Raw binary blobs. + */ + +#include +#include +#include +#include +#include +#include +#include "blob.h" +#include "tree.h" + +/** Initialize a random access blob. + * @memberof bithenge_blob_t + * @param[out] blob The blob to initialize. + * @param[in] ops Operations providing random access support. This pointer must + * be valid until the blob is destroyed. + * @return EOK on success or an error code from errno.h. + */ +int bithenge_new_random_access_blob(bithenge_blob_t *blob, + const bithenge_random_access_blob_ops_t *ops) +{ + assert(blob); + assert(ops); + assert(ops->destroy); + assert(ops->read); + assert(ops->size); + + blob->base.type = BITHENGE_NODE_BLOB; + blob->base.blob_ops = ops; + return EOK; +} + +static int sequential_buffer(bithenge_sequential_blob_t *blob, aoff64_t end) +{ + bool need_realloc = false; + while (end > blob->buffer_size) { + blob->buffer_size = max(4096, 2 * blob->buffer_size); + need_realloc = true; + } + if (need_realloc) { + char *buffer = realloc(blob->buffer, blob->buffer_size); + if (!buffer) + return ENOMEM; + blob->buffer = buffer; + } + aoff64_t size = end - blob->data_size; + int rc = blob->ops->read(blob, blob->buffer + blob->data_size, &size); + if (rc != EOK) + return rc; + blob->data_size += size; + return EOK; +} + +static inline bithenge_sequential_blob_t *sequential_from_blob( + bithenge_blob_t *base) +{ + return (bithenge_sequential_blob_t *)base; +} + +static inline bithenge_blob_t *blob_from_sequential( + bithenge_sequential_blob_t *blob) +{ + return &blob->base; +} + +static int sequential_size(bithenge_blob_t *base, aoff64_t *size) +{ + bithenge_sequential_blob_t *blob = sequential_from_blob(base); + int rc; + if (blob->ops->size) { + rc = blob->ops->size(blob, size); + if (rc == EOK) + return EOK; + } + rc = sequential_buffer(blob, blob->buffer_size); + if (rc != EOK) + return rc; + while (blob->data_size == blob->buffer_size) { + rc = sequential_buffer(blob, 2 * blob->buffer_size); + if (rc != EOK) + return rc; + } + *size = blob->data_size; + return EOK; +} + +static int sequential_read(bithenge_blob_t *base, aoff64_t offset, + char *buffer, aoff64_t *size) +{ + bithenge_sequential_blob_t *blob = sequential_from_blob(base); + aoff64_t end = offset + *size; + if (end > blob->data_size) { + int rc = sequential_buffer(blob, end); + if (rc != EOK) + return rc; + } + if (offset > blob->data_size) + return EINVAL; + *size = min(*size, blob->data_size - end); + memcpy(buffer, blob->buffer + offset, *size); + return EOK; +} + +static int sequential_destroy(bithenge_blob_t *base) +{ + bithenge_sequential_blob_t *blob = sequential_from_blob(base); + free(blob->buffer); + return blob->ops->destroy(blob); +} + +static const bithenge_random_access_blob_ops_t sequential_ops = { + .size = sequential_size, + .read = sequential_read, + .destroy = sequential_destroy, +}; + +/** Initialize a sequential blob. + * @memberof bithenge_sequential_blob_t + * @param[out] blob The blob to initialize. + * @param[in] ops Operations providing sequential access support. This pointer + * must be valid until the blob is destroyed. + * @return EOK on success or an error code from errno.h. + */ +int bithenge_new_sequential_blob(bithenge_sequential_blob_t *blob, + const bithenge_sequential_blob_ops_t *ops) +{ + assert(blob); + assert(ops); + assert(ops->destroy); + assert(ops->read); + // ops->size is optional + + int rc = bithenge_new_random_access_blob(blob_from_sequential(blob), + &sequential_ops); + if (rc != EOK) + return rc; + blob->ops = ops; + blob->buffer = NULL; // realloc(NULL, ...) works like malloc + blob->buffer_size = 0; + blob->data_size = 0; + return EOK; +} + +typedef struct { + bithenge_blob_t base; + const char *buffer; + size_t size; + bool needs_free; +} memory_blob_t; + +static inline memory_blob_t *memory_from_blob(bithenge_blob_t *base) +{ + return (memory_blob_t *)base; +} + +static inline bithenge_blob_t *blob_from_memory(memory_blob_t *blob) +{ + return &blob->base; +} + +static int memory_size(bithenge_blob_t *base, aoff64_t *size) +{ + memory_blob_t *blob = memory_from_blob(base); + *size = blob->size; + return EOK; +} + +static int memory_read(bithenge_blob_t *base, aoff64_t offset, char *buffer, + aoff64_t *size) +{ + memory_blob_t *blob = memory_from_blob(base); + if (offset > blob->size) + return ELIMIT; + *size = min(*size, blob->size - offset); + memcpy(buffer, blob->buffer + offset, *size); + return EOK; +} + +static int memory_destroy(bithenge_blob_t *base) +{ + memory_blob_t *blob = memory_from_blob(base); + if (blob->needs_free) + free(blob->buffer); + free(blob); + return EOK; +} + +static const bithenge_random_access_blob_ops_t memory_ops = { + .size = memory_size, + .read = memory_read, + .destroy = memory_destroy, +}; + +/** Create a blob node from data. Unlike with @a + * bithenge_blob_t::bithenge_new_blob_from_buffer, the data is copied into a + * new buffer and the original data can be changed after this call. The blob + * must be freed with @a bithenge_node_t::bithenge_node_destroy after it is + * used. + * @memberof bithenge_blob_t + * @param[out] out Stores the created blob node. + * @param[in] data The data. + * @param len The length of the data. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_blob_from_data(bithenge_node_t **out, const void *data, + size_t len) +{ + int rc; + assert(data || !len); + + memory_blob_t *blob = malloc(sizeof(*blob)); + if (!blob) + return ENOMEM; + rc = bithenge_new_random_access_blob(blob_from_memory(blob), + &memory_ops); + if (rc != EOK) { + free(blob); + return rc; + } + char *buffer = malloc(len); + if (!buffer) { + free(blob); + return rc; + } + memcpy(buffer, data, len); + blob->buffer = buffer; + blob->size = len; + blob->needs_free = true; + *out = bithenge_blob_as_node(blob_from_memory(blob)); + return EOK; +} + +/** Create a blob node from a buffer. The buffer must exist as long as the blob + * does. The blob must be freed with @a bithenge_node_t::bithenge_node_destroy + * after it is used. + * @memberof bithenge_blob_t + * @param[out] out Stores the created blob node. + * @param[in] buffer The buffer, which must not be changed until the blob is + * destroyed. + * @param len The length of the data. + * @param needs_free Whether the buffer should be freed with free() when the + * blob is destroyed. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_blob_from_buffer(bithenge_node_t **out, const void *buffer, + size_t len, bool needs_free) +{ + int rc; + assert(buffer || !len); + + memory_blob_t *blob = malloc(sizeof(*blob)); + if (!blob) + return ENOMEM; + rc = bithenge_new_random_access_blob(blob_from_memory(blob), + &memory_ops); + if (rc != EOK) { + free(blob); + return rc; + } + blob->buffer = buffer; + blob->size = len; + blob->needs_free = needs_free; + *out = bithenge_blob_as_node(blob_from_memory(blob)); + return EOK; +} + +/** @} + */ Index: uspace/app/bithenge/blob.h =================================================================== --- uspace/app/bithenge/blob.h (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/blob.h (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,187 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Raw binary blobs. + */ + +#ifndef BITHENGE_BLOB_H_ +#define BITHENGE_BLOB_H_ + +#include +#include "tree.h" + +/** A blob of raw binary data. + * @implements bithenge_node_t */ +typedef struct { + /** @privatesection */ + struct bithenge_node_t base; +} bithenge_blob_t; + +/** Operations providing random access to binary data. + * @todo Should these be thread-safe? */ +typedef struct bithenge_random_access_blob_ops_t { + /** @copydoc bithenge_blob_t::bithenge_blob_size */ + int (*size)(bithenge_blob_t *blob, aoff64_t *size); + /** @copydoc bithenge_blob_t::bithenge_blob_read */ + int (*read)(bithenge_blob_t *blob, aoff64_t offset, char *buffer, + aoff64_t *size); + /** Destroy the blob. + * @param blob The blob. + * @return EOK on success or an error code from errno.h. */ + int (*destroy)(bithenge_blob_t *blob); +} bithenge_random_access_blob_ops_t; + +/** A blob built from an object that supports only sequential reading. + * @implements bithenge_blob_t */ +typedef struct { + /** @privatesection */ + /** The base random-access blob. */ + bithenge_blob_t base; + /** Operations providing sequential access. */ + const struct bithenge_sequential_blob_ops_t *ops; + /** Buffer containing all data read. */ + char *buffer; + /** Size of buffer. */ + aoff64_t buffer_size; + /** Amount of data actually in buffer. */ + aoff64_t data_size; +} bithenge_sequential_blob_t; + +/** Operations providing sequential access to binary data. + * @memberof bithenge_sequential_blob_t */ +typedef struct bithenge_sequential_blob_ops_t { + + /** Get the total size of the blob. If the total size cannot be + * determined easily, this field may be null or return an error, + * forcing the entire blob to be read to determine its size. + * + * @memberof bithenge_blob_t + * @param blob The blob. + * @param[out] size Total size of the blob. + * @return EOK on success or an error code from errno.h. + */ + int (*size)(bithenge_sequential_blob_t *blob, aoff64_t *size); + + /** Read the next part of the blob. If the requested data extends + * beyond the end of the blob, the data up until the end of the blob + * will be read. + * + * @param blob The blob. + * @param[out] buffer Buffer to read into. If an error occurs, the contents are + * undefined. + * @param[in,out] size Number of bytes to read; may be 0. If not enough + * data is left in the blob, the actual number of bytes read should be + * stored here. If an error occurs, the contents are undefined. + * @return EOK on success or an error code from errno.h. + */ + int (*read)(bithenge_sequential_blob_t *blob, char *buffer, + aoff64_t *size); + + /** Destroy the blob. + * @param blob The blob. + * @return EOK on success or an error code from errno.h. */ + int (*destroy)(bithenge_sequential_blob_t *blob); +} bithenge_sequential_blob_ops_t; + +/** Get the total size of the blob. + * + * @memberof bithenge_blob_t + * @param blob The blob. + * @param[out] size Total size of the blob. + * @return EOK on success or an error code from errno.h. + */ +static inline int bithenge_blob_size(bithenge_blob_t *blob, aoff64_t *size) +{ + assert(blob); + assert(blob->base.blob_ops); + return blob->base.blob_ops->size(blob, size); +} + +/** Read part of the blob. If the requested data extends beyond the end of the + * blob, the data up until the end of the blob will be read. If the offset is + * beyond the end of the blob, even if the size is zero, an error will be + * returned. + * + * @memberof bithenge_blob_t + * @param blob The blob. + * @param offset Byte offset within the blob. + * @param[out] buffer Buffer to read into. If an error occurs, the contents are + * undefined. + * @param[in,out] size Number of bytes to read; may be 0. If the requested + * range extends beyond the end of the blob, the actual number of bytes read + * should be stored here. If an error occurs, the contents are undefined. + * @return EOK on success or an error code from errno.h. + */ +static inline int bithenge_blob_read(bithenge_blob_t *blob, aoff64_t offset, + char *buffer, aoff64_t *size) +{ + assert(blob); + assert(blob->base.blob_ops); + return blob->base.blob_ops->read(blob, offset, buffer, size); +} + +/** Cast a blob node to a generic node. + * @memberof bithenge_blob_t + * @param blob The blob to cast. + * @return The blob node as a generic node. */ +static inline bithenge_node_t *bithenge_blob_as_node(bithenge_blob_t *blob) +{ + return &blob->base; +} + +/** Cast a generic node to a blob node. + * @memberof bithenge_blob_t + * @param node The node to cast, which must be a blob node. + * @return The generic node as a blob node. */ +static inline bithenge_blob_t *bithenge_node_as_blob(bithenge_node_t *node) +{ + assert(node->type == BITHENGE_NODE_BLOB); + return (bithenge_blob_t *)node; +} + +int bithenge_new_random_access_blob(bithenge_blob_t *blob, + const bithenge_random_access_blob_ops_t *ops); + +int bithenge_new_sequential_blob(bithenge_sequential_blob_t *blob, + const bithenge_sequential_blob_ops_t *ops); + +int bithenge_new_blob_from_data(bithenge_node_t **out, const void *data, + size_t len); + +int bithenge_new_blob_from_buffer(bithenge_node_t **out, const void *buffer, + size_t len, bool needs_free); + +#endif + +/** @} + */ Index: uspace/app/bithenge/block.c =================================================================== --- uspace/app/bithenge/block.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/block.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,146 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Access block devices as blobs. + * @todo Provide more information about the block device (block size). + */ + +#include +#include +#include +#include +#include +#include +#include "blob.h" +#include "block.h" + +typedef struct { + bithenge_blob_t base; + service_id_t service_id; + aoff64_t size; +} block_blob_t; + +static inline block_blob_t *block_from_blob(bithenge_blob_t *base) +{ + return (block_blob_t *)base; +} + +static inline bithenge_blob_t *blob_from_block(block_blob_t *blob) +{ + return &blob->base; +} + +static int block_size(bithenge_blob_t *base, aoff64_t *size) +{ + block_blob_t *blob = block_from_blob(base); + *size = blob->size; + return EOK; +} + +static int block_read(bithenge_blob_t *base, aoff64_t offset, char *buffer, + aoff64_t *size) +{ + block_blob_t *blob = block_from_blob(base); + if (offset > blob->size) + return ELIMIT; + *size = min(*size, blob->size - offset); + return block_read_bytes_direct(blob->service_id, offset, *size, buffer); +} + +static int block_destroy(bithenge_blob_t *base) +{ + block_blob_t *blob = block_from_blob(base); + block_fini(blob->service_id); + free(blob); + return EOK; +} + +static const bithenge_random_access_blob_ops_t block_ops = { + .size = block_size, + .read = block_read, + .destroy = block_destroy, +}; + +/** Create a blob for a block device. The blob must be freed with + * @a bithenge_node_t::bithenge_node_destroy after it is used. + * @param[out] out Stores the created blob. + * @param service_id The service ID of the block device. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_block_blob(bithenge_node_t **out, service_id_t service_id) +{ + assert(out); + + // Initialize libblock + int rc; + rc = block_init(EXCHANGE_SERIALIZE, service_id, 2048); + if (rc != EOK) + return rc; + + // Calculate total device size + size_t bsize; + aoff64_t nblocks; + aoff64_t size; + rc = block_get_bsize(service_id, &bsize); + if (rc != EOK) { + block_fini(service_id); + return rc; + } + rc = block_get_nblocks(service_id, &nblocks); + if (rc != EOK) { + block_fini(service_id); + return rc; + } + size = bsize * nblocks; + + // Create blob + block_blob_t *blob = malloc(sizeof(*blob)); + if (!blob) { + block_fini(service_id); + return ENOMEM; + } + rc = bithenge_new_random_access_blob(blob_from_block(blob), + &block_ops); + if (rc != EOK) { + free(blob); + block_fini(service_id); + return rc; + } + blob->service_id = service_id; + blob->size = size; + *out = bithenge_blob_as_node(blob_from_block(blob)); + + return EOK; +} + +/** @} + */ Index: uspace/app/bithenge/block.h =================================================================== --- uspace/app/bithenge/block.h (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/block.h (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Access block devices as blobs. + */ + +#ifndef BITHENGE_BLOCK_H_ +#define BITHENGE_BLOCK_H_ + +#include +#include "blob.h" + +int bithenge_new_block_blob(bithenge_node_t **, service_id_t); + +#endif + +/** @} + */ Index: uspace/app/bithenge/file.c =================================================================== --- uspace/app/bithenge/file.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/file.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,174 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Access files as blobs. + * @todo Provide more information about the file. + */ + +#include +#include +#include +#include +#include +#include +#include +#include "blob.h" +#include "file.h" + +typedef struct { + bithenge_blob_t base; + int fd; + aoff64_t size; // needed by file_read() + bool needs_close; +} file_blob_t; + +static inline file_blob_t *file_from_blob(bithenge_blob_t *base) +{ + return (file_blob_t *)base; +} + +static inline bithenge_blob_t *blob_from_file(file_blob_t *blob) +{ + return &blob->base; +} + +static int file_size(bithenge_blob_t *base, aoff64_t *size) +{ + file_blob_t *blob = file_from_blob(base); + *size = blob->size; + return EOK; +} + +static int file_read(bithenge_blob_t *base, aoff64_t offset, char *buffer, + aoff64_t *size) +{ + file_blob_t *blob = file_from_blob(base); + if (offset > blob->size) + return ELIMIT; + *size = min(*size, blob->size - offset); + int rc = lseek(blob->fd, offset, SEEK_SET); + if (rc != EOK) + return rc; + return read(blob->fd, buffer, *size); +} + +static int file_destroy(bithenge_blob_t *base) +{ + file_blob_t *blob = file_from_blob(base); + close(blob->fd); + free(blob); + return EOK; +} + +static const bithenge_random_access_blob_ops_t file_ops = { + .size = file_size, + .read = file_read, + .destroy = file_destroy, +}; + +static int new_file_blob(bithenge_node_t **out, int fd, bool needs_close) +{ + assert(out); + + struct stat stat; + int rc = fstat(fd, &stat); + if (rc != EOK) { + if (needs_close) + close(fd); + return rc; + } + + // Create blob + file_blob_t *blob = malloc(sizeof(*blob)); + if (!blob) { + if (needs_close) + close(fd); + return ENOMEM; + } + rc = bithenge_new_random_access_blob(blob_from_file(blob), + &file_ops); + if (rc != EOK) { + free(blob); + if (needs_close) + close(fd); + return rc; + } + blob->fd = fd; + blob->size = stat.size; + blob->needs_close = needs_close; + *out = bithenge_blob_as_node(blob_from_file(blob)); + + return EOK; +} + +/** Create a blob for a file. The blob must be freed with @a + * bithenge_node_t::bithenge_node_destroy after it is used. + * @param[out] out Stores the created blob. + * @param filename The name of the file. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_file_blob(bithenge_node_t **out, const char *filename) +{ + assert(filename); + + int fd = open(filename, O_RDONLY); + if (fd < 0) + return fd; + + return new_file_blob(out, fd, true); +} + +/** Create a blob for a file descriptor. The blob must be freed with @a + * bithenge_node_t::bithenge_node_destroy after it is used. + * @param[out] out Stores the created blob. + * @param fd The file descriptor. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_file_blob_from_fd(bithenge_node_t **out, int fd) +{ + return new_file_blob(out, fd, false); +} + +/** Create a blob for a file pointer. The blob must be freed with @a + * bithenge_node_t::bithenge_node_destroy after it is used. + * @param[out] out Stores the created blob. + * @param file The file pointer. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_file_blob_from_file(bithenge_node_t **out, FILE *file) +{ + int fd = fileno(file); + if (fd < 0) + return errno; + return new_file_blob(out, fd, false); +} + +/** @} + */ Index: uspace/app/bithenge/file.h =================================================================== --- uspace/app/bithenge/file.h (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/file.h (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,50 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Access files as blobs. + */ + +#ifndef BITHENGE_FILE_H_ +#define BITHENGE_FILE_H_ + +#include +#include "blob.h" + +int bithenge_new_file_blob(bithenge_node_t **, const char *); +int bithenge_new_file_blob_from_fd(bithenge_node_t **, int); +int bithenge_new_file_blob_from_file(bithenge_node_t **, FILE *); + +#endif + +/** @} + */ Index: uspace/app/bithenge/print.c =================================================================== --- uspace/app/bithenge/print.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/print.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,165 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Write a tree as JSON or other text formats. + */ + +#include +#include +#include "blob.h" +#include "print.h" +#include "tree.h" + +typedef struct { + bithenge_print_type_t type; + bool first; +} print_internal_data_t; + +static int print_internal_func(bithenge_node_t *key, bithenge_node_t *value, void *data_) +{ + print_internal_data_t *data = (print_internal_data_t *)data_; + int rc; + if (!data->first) + printf(", "); + data->first = false; + bool add_quotes = data->type == BITHENGE_PRINT_JSON + && bithenge_node_type(key) != BITHENGE_NODE_STRING; + if (add_quotes) + printf("\""); + rc = bithenge_print_node(data->type, key); + if (rc != EOK) + return rc; + if (add_quotes) + printf("\""); + printf(": "); + rc = bithenge_print_node(data->type, value); + if (rc != EOK) + return rc; + return EOK; +} + +static int print_internal(bithenge_print_type_t type, bithenge_node_t *node) +{ + int rc; + print_internal_data_t data = { type, true }; + printf("{"); + rc = bithenge_node_for_each(node, print_internal_func, &data); + if (rc != EOK) + return rc; + printf("}"); + return EOK; +} + +static int print_boolean(bithenge_print_type_t type, bithenge_node_t *node) +{ + bool value = bithenge_boolean_node_value(node); + switch (type) { + case BITHENGE_PRINT_PYTHON: + printf(value ? "True" : "False"); + break; + case BITHENGE_PRINT_JSON: + printf(value ? "true" : "false"); + break; + } + return EOK; +} + +static int print_integer(bithenge_print_type_t type, bithenge_node_t *node) +{ + bithenge_int_t value = bithenge_integer_node_value(node); + printf("%" BITHENGE_PRId, value); + return EOK; +} + +static int print_string(bithenge_print_type_t type, bithenge_node_t *node) +{ + size_t off = 0; + const char *value = bithenge_string_node_value(node); + wchar_t ch; + printf("\""); + while ((ch = str_decode(value, &off, STR_NO_LIMIT)) != 0) { + if (ch == '"' || ch == '\\') { + printf("\\%lc", (wint_t) ch); + } else if (ch <= 0x1f) { + printf("\\u%04x", (unsigned int) ch); + } else { + printf("%lc", (wint_t) ch); + } + } + printf("\""); + return EOK; +} + +static int print_blob(bithenge_print_type_t type, bithenge_node_t *node) +{ + bithenge_blob_t *blob = bithenge_node_as_blob(node); + aoff64_t pos = 0; + char buffer[1024]; + aoff64_t size = sizeof(buffer); + int rc; + printf(type == BITHENGE_PRINT_PYTHON ? "b\"" : "\""); + do { + rc = bithenge_blob_read(blob, pos, buffer, &size); + if (rc != EOK) + return rc; + for (aoff64_t i = 0; i < size; i++) + printf("\\x%02x", buffer[i]); + pos += size; + } while (size == sizeof(buffer)); + printf("\""); + return EOK; +} + +/** Print a tree as text. + * @param type The format to use. + * @param tree The root node of the tree to print. + * @return EOK on success or an error code from errno.h. */ +int bithenge_print_node(bithenge_print_type_t type, bithenge_node_t *tree) +{ + switch (bithenge_node_type(tree)) { + case BITHENGE_NODE_INTERNAL: + return print_internal(type, tree); + case BITHENGE_NODE_BOOLEAN: + return print_boolean(type, tree); + case BITHENGE_NODE_INTEGER: + return print_integer(type, tree); + case BITHENGE_NODE_STRING: + return print_string(type, tree); + case BITHENGE_NODE_BLOB: + return print_blob(type, tree); + } + return ENOTSUP; +} + +/** @} + */ Index: uspace/app/bithenge/print.h =================================================================== --- uspace/app/bithenge/print.h (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/print.h (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,57 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Write a tree as JSON or other text formats. + */ + +#ifndef BITHENGE_PRINT_H_ +#define BITHENGE_PRINT_H_ + +#include "tree.h" + +/** Specifies the format to be used when printing. */ +typedef enum { + /** Print a Python value. Note that internal nodes will be represented + * as unordered dictionaries. */ + BITHENGE_PRINT_PYTHON, + /** Print JSON. Due to the limitations of JSON, type information may be + * lost. */ + BITHENGE_PRINT_JSON, +} bithenge_print_type_t; + +int bithenge_print_node(bithenge_print_type_t, bithenge_node_t *); + +#endif + +/** @} + */ Index: uspace/app/bithenge/test.c =================================================================== --- uspace/app/bithenge/test.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/test.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,120 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Simple program to test Bithenge. + */ + +#include +#include +#include +#include "blob.h" +#include "block.h" +#include "file.h" +#include "print.h" +#include "tree.h" + +static void +print_data(const char *data, size_t len) +{ + while (len--) + printf("%02x ", (uint8_t)(*data++)); + printf("\n"); +} + +static void +print_blob(bithenge_node_t *node) +{ + bithenge_blob_t *blob = bithenge_node_as_blob(node); + aoff64_t size; + bithenge_blob_size(blob, &size); + printf("Size: %d; ", (int)size); + char buffer[64]; + size = sizeof(buffer); + bithenge_blob_read(blob, 0, buffer, &size); + print_data(buffer, size); +} + +int main(int argc, char *argv[]) +{ + bithenge_node_t *node; + + service_id_t service_id; + loc_service_get_id("bd/initrd", &service_id, 0); + bithenge_new_block_blob(&node, service_id); + printf("Data from block:bd/initrd: "); + print_blob(node); + bithenge_node_destroy(node); + + const char data[] = "'Twas brillig, and the slithy toves"; + bithenge_new_blob_from_data(&node, data, sizeof(data)); + printf("Data from memory (from_data): "); + print_blob(node); + bithenge_node_destroy(node); + + bithenge_new_blob_from_buffer(&node, data, sizeof(data), false); + printf("Data from memory (from_buffer): "); + print_blob(node); + bithenge_node_destroy(node); + + bithenge_new_file_blob(&node, "/textdemo"); + printf("Data from file:/textdemo: "); + print_blob(node); + bithenge_node_destroy(node); + + bithenge_new_file_blob_from_fd(&node, 0); + printf("Data from fd:0: "); + print_blob(node); + bithenge_node_destroy(node); + + // {True: {}, -1351: "\"false\"", "true": False, 0: b"..."} + bithenge_node_t *nodes[8]; + bithenge_new_boolean_node(&nodes[0], true); + bithenge_new_simple_internal_node(&nodes[1], NULL, 0, false); + bithenge_new_integer_node(&nodes[2], -1351); + bithenge_new_string_node(&nodes[3], "\"false\"", false); + bithenge_new_string_node(&nodes[4], "true", false); + bithenge_new_boolean_node(&nodes[5], false); + bithenge_new_integer_node(&nodes[6], 0); + bithenge_new_blob_from_data(&nodes[7], data, sizeof(data)); + bithenge_new_simple_internal_node(&node, nodes, 4, false); + bithenge_print_node(BITHENGE_PRINT_PYTHON, node); + printf("\n"); + bithenge_print_node(BITHENGE_PRINT_JSON, node); + printf("\n"); + bithenge_node_destroy(node); + + return 0; +} + +/** @} + */ Index: uspace/app/bithenge/tree.c =================================================================== --- uspace/app/bithenge/tree.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/tree.c (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,210 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Trees and nodes. + */ + +#include +#include +#include "blob.h" +#include "tree.h" + +static int blob_destroy(bithenge_node_t *base) +{ + bithenge_blob_t *blob = bithenge_node_as_blob(base); + assert(blob->base.blob_ops); + return blob->base.blob_ops->destroy(blob); +} + +/** Destroy a node. + * @memberof bithenge_node_t + * @param node The node to destroy. + * @return EOK on success or an error code from errno.h. */ +int bithenge_node_destroy(bithenge_node_t *node) +{ + switch (bithenge_node_type(node)) { + case BITHENGE_NODE_BLOB: + return blob_destroy(node); + case BITHENGE_NODE_STRING: + if (node->string_value.needs_free) + free(node->string_value.ptr); + break; + case BITHENGE_NODE_INTERNAL: + return node->internal_ops->destroy(node); + case BITHENGE_NODE_BOOLEAN: + return EOK; // the boolean nodes are allocated statically below + case BITHENGE_NODE_INTEGER: /* pass-through */ + break; + } + free(node); + return EOK; +} + +typedef struct +{ + bithenge_node_t base; + bithenge_node_t **nodes; + bithenge_int_t len; + bool needs_free; +} simple_internal_node_t; + +static simple_internal_node_t *node_as_simple(bithenge_node_t *node) +{ + return (simple_internal_node_t *)node; +} + +static int simple_internal_node_for_each(bithenge_node_t *base, + bithenge_for_each_func_t func, void *data) +{ + int rc; + simple_internal_node_t *node = node_as_simple(base); + for (bithenge_int_t i = 0; i < node->len; i++) { + rc = func(node->nodes[2*i+0], node->nodes[2*i+1], data); + if (rc != EOK) + return rc; + } + return EOK; +} + +static int simple_internal_node_destroy(bithenge_node_t *base) +{ + int rc; + simple_internal_node_t *node = node_as_simple(base); + for (bithenge_int_t i = 0; i < node->len; i++) { + rc = bithenge_node_destroy(node->nodes[2*i+0]); + if (rc != EOK) + return rc; + rc = bithenge_node_destroy(node->nodes[2*i+1]); + if (rc != EOK) + return rc; + } + if (node->needs_free) + free(node->nodes); + free(node); + return EOK; +} + +static bithenge_internal_node_ops_t simple_internal_node_ops = { + .for_each = simple_internal_node_for_each, + .destroy = simple_internal_node_destroy, +}; + +static bithenge_node_t *simple_internal_as_node(simple_internal_node_t *node) +{ + return &node->base; +} + +/** Create an internal node from a set of keys and values. The node must be + * freed with @a bithenge_node_t::bithenge_node_destroy after it is used, which + * will also destroy all the key and value nodes. + * @memberof bithenge_node_t + * @param[out] out Stores the created internal node. + * @param nodes The array of key-value pairs. Keys are stored at even indices + * and values are stored at odd indices. + * @param len The number of key-value pairs in the node array. + * @param needs_free If true, when the internal node is destroyed it will free + * the nodes array as well as destroying each node inside it. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_simple_internal_node(bithenge_node_t **out, + bithenge_node_t **nodes, bithenge_int_t len, bool needs_free) +{ + assert(out); + simple_internal_node_t *node = malloc(sizeof(*node)); + if (!node) + return ENOMEM; + node->base.type = BITHENGE_NODE_INTERNAL; + node->base.internal_ops = &simple_internal_node_ops; + node->nodes = nodes; + node->len = len; + node->needs_free = needs_free; + *out = simple_internal_as_node(node); + return EOK; +} + +static bithenge_node_t false_node = { BITHENGE_NODE_BOOLEAN, .boolean_value = false }; +static bithenge_node_t true_node = { BITHENGE_NODE_BOOLEAN, .boolean_value = true }; + +/** Create a boolean node. The node must be freed with @a + * bithenge_node_t::bithenge_node_destroy after it is used. + * @memberof bithenge_node_t + * @param[out] out Stores the created boolean node. + * @param value The value for the node to hold. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_boolean_node(bithenge_node_t **out, bool value) +{ + assert(out); + *out = value ? &true_node : &false_node; + return EOK; +} + +/** Create an integer node. The node must be freed with @a + * bithenge_node_t::bithenge_node_destroy after it is used. + * @memberof bithenge_node_t + * @param[out] out Stores the created integer node. + * @param value The value for the node to hold. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_integer_node(bithenge_node_t **out, bithenge_int_t value) +{ + assert(out); + bithenge_node_t *node = malloc(sizeof(*node)); + if (!node) + return ENOMEM; + node->type = BITHENGE_NODE_INTEGER; + node->integer_value = value; + *out = node; + return EOK; +} + +/** Create a string node. The node must be freed with @a + * bithenge_node_t::bithenge_node_destroy after it is used. + * @memberof bithenge_node_t + * @param[out] out Stores the created string node. + * @param value The value for the node to hold. + * @param needs_free Whether the string should be freed when the node is + * destroyed. + * @return EOK on success or an error code from errno.h. */ +int bithenge_new_string_node(bithenge_node_t **out, const char *value, bool needs_free) +{ + assert(out); + bithenge_node_t *node = malloc(sizeof(*node)); + if (!node) + return ENOMEM; + node->type = BITHENGE_NODE_STRING; + node->string_value.ptr = value; + node->string_value.needs_free = needs_free; + *out = node; + return EOK; +} + +/** @} + */ Index: uspace/app/bithenge/tree.h =================================================================== --- uspace/app/bithenge/tree.h (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) +++ uspace/app/bithenge/tree.h (revision 8b36bf28adc74d3d3510444d9f6fbf2037ba01cd) @@ -0,0 +1,159 @@ +/* + * Copyright (c) 2012 Sean Bartell + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup bithenge + * @{ + */ +/** + * @file + * Trees and nodes. + */ + +#ifndef BITHENGE_TREE_H_ +#define BITHENGE_TREE_H_ + +#include +#include +#include +#include + +#ifdef INTMAX_MAX +typedef intmax_t bithenge_int_t; +#define BITHENGE_PRId PRIdMAX +#else +typedef int64_t bithenge_int_t; +#define BITHENGE_PRId PRId64 +#endif + +/** Indicates the type of a tree node. */ +typedef enum { + /** An internal node with labelled edges to other nodes. */ + BITHENGE_NODE_INTERNAL = 1, + /** A leaf node holding a boolean value. */ + BITHENGE_NODE_BOOLEAN, + /** A leaf node holding an integer. */ + BITHENGE_NODE_INTEGER, + /** A leaf node holding a string. */ + BITHENGE_NODE_STRING, + /** A leaf node holding a binary blob. */ + BITHENGE_NODE_BLOB, +} bithenge_node_type_t; + +typedef struct bithenge_node_t { + /** @privatesection */ + bithenge_node_type_t type; + union { + const struct bithenge_internal_node_ops_t *internal_ops; + bool boolean_value; + bithenge_int_t integer_value; + struct { + const char *ptr; + bool needs_free; + } string_value; + const struct bithenge_random_access_blob_ops_t *blob_ops; + }; +} bithenge_node_t; + +/** A callback function used to iterate over a node's children. + * @memberof bithenge_node_t + * @param key The key. + * @param value The value. + * @param data Data provided to @a bithenge_node_t::bithenge_node_for_each. + * @return EOK on success or an error code from errno.h. */ +typedef int (*bithenge_for_each_func_t)(bithenge_node_t *key, bithenge_node_t *value, void *data); + +/** Operations providing access to an internal node. */ +typedef struct bithenge_internal_node_ops_t { + /** @copydoc bithenge_node_t::bithenge_node_for_each */ + int (*for_each)(bithenge_node_t *node, bithenge_for_each_func_t func, void *data); + /** @copydoc bithenge_node_t::bithenge_node_destroy */ + int (*destroy)(bithenge_node_t *node); +} bithenge_internal_node_ops_t; + +/** Find the type of a node. + * @memberof bithenge_node_t + * @param node The node. + * @return The type of the node. */ +static inline bithenge_node_type_t bithenge_node_type(const bithenge_node_t *node) +{ + return node->type; +} + +/** Iterate over a node's children. + * @memberof bithenge_node_t + * @param node The internal node to iterate over. + * @param func The callback function. + * @param data Data to provide to the callback function. + * @return EOK on success or an error code from errno.h. */ +static inline int bithenge_node_for_each(bithenge_node_t *node, bithenge_for_each_func_t func, void *data) +{ + assert(node->type == BITHENGE_NODE_INTERNAL); + return node->internal_ops->for_each(node, func, data); +} + +/** Get the value of a boolean node. + * @memberof bithenge_node_t + * @param node The boolean node. + * @return The node's value. */ +static inline bool bithenge_boolean_node_value(bithenge_node_t *node) +{ + assert(node->type == BITHENGE_NODE_BOOLEAN); + return node->boolean_value; +} + +/** Get the value of an integer node. + * @memberof bithenge_node_t + * @param node The integer node. + * @return The node's value. */ +static inline bithenge_int_t bithenge_integer_node_value(bithenge_node_t *node) +{ + assert(node->type == BITHENGE_NODE_INTEGER); + return node->integer_value; +} + +/** Get the value of an string node. + * @memberof bithenge_node_t + * @param node The string node. + * @return The node's value. */ +static inline const char *bithenge_string_node_value(bithenge_node_t *node) +{ + assert(node->type == BITHENGE_NODE_STRING); + return node->string_value.ptr; +} + +int bithenge_new_simple_internal_node(bithenge_node_t **, bithenge_node_t **, + bithenge_int_t, bool needs_free); +int bithenge_new_boolean_node(bithenge_node_t **, bool); +int bithenge_new_integer_node(bithenge_node_t **, bithenge_int_t); +int bithenge_new_string_node(bithenge_node_t **, const char *, bool); +int bithenge_node_destroy(bithenge_node_t *); + +#endif + +/** @} + */