diff options
Diffstat (limited to 'src/util')
47 files changed, 2695 insertions, 1566 deletions
diff --git a/src/util/Alloc.cxx b/src/util/Alloc.cxx new file mode 100644 index 000000000..006e09701 --- /dev/null +++ b/src/util/Alloc.cxx @@ -0,0 +1,77 @@ +/* + * Copyright (C) 2003-2014 The Music Player Daemon Project + * http://www.musicpd.org + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include "config.h" +#include "Alloc.hxx" + +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +gcc_noreturn +static void +oom() +{ + (void)write(STDERR_FILENO, "Out of memory\n", 14); + _exit(1); +} + +void * +xalloc(size_t size) +{ + void *p = malloc(size); + if (gcc_unlikely(p == nullptr)) + oom(); + + return p; +} + +void * +xmemdup(const void *s, size_t size) +{ + void *p = xalloc(size); + memcpy(p, s, size); + return p; +} + +char * +xstrdup(const char *s) +{ + char *p = strdup(s); + if (gcc_unlikely(p == nullptr)) + oom(); + + return p; +} + +char * +xstrndup(const char *s, size_t n) +{ +#ifdef HAVE_STRNDUP + char *p = strndup(s, n); + if (gcc_unlikely(p == nullptr)) + oom(); +#else + char *p = (char *)xalloc(n + 1); + memcpy(p, s, n); + p[n] = 0; +#endif + + return p; +} diff --git a/src/util/Alloc.hxx b/src/util/Alloc.hxx new file mode 100644 index 000000000..15c123b7a --- /dev/null +++ b/src/util/Alloc.hxx @@ -0,0 +1,67 @@ +/* + * Copyright (C) 2003-2014 The Music Player Daemon Project + * http://www.musicpd.org + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#ifndef MPD_ALLOC_HXX +#define MPD_ALLOC_HXX + +#include "Compiler.h" + +#include <stddef.h> + +/** + * Allocate memory. Use free() to free it. + * + * This function never fails; in out-of-memory situations, it aborts + * the process. + */ +gcc_malloc +void * +xalloc(size_t size); + +/** + * Duplicate memory. Use free() to free it. + * + * This function never fails; in out-of-memory situations, it aborts + * the process. + */ +gcc_malloc gcc_nonnull_all +void * +xmemdup(const void *s, size_t size); + +/** + * Duplicate a string. Use free() to free it. + * + * This function never fails; in out-of-memory situations, it aborts + * the process. + */ +gcc_malloc gcc_nonnull_all +char * +xstrdup(const char *s); + +/** + * Duplicate a string. Use free() to free it. + * + * This function never fails; in out-of-memory situations, it aborts + * the process. + */ +gcc_malloc gcc_nonnull_all +char * +xstrndup(const char *s, size_t n); + +#endif diff --git a/src/util/ByteReverse.cxx b/src/util/ByteReverse.cxx index 910c1e2a5..5cc8692a7 100644 --- a/src/util/ByteReverse.cxx +++ b/src/util/ByteReverse.cxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify diff --git a/src/util/ByteReverse.hxx b/src/util/ByteReverse.hxx index d6380213a..0c060c0cb 100644 --- a/src/util/ByteReverse.hxx +++ b/src/util/ByteReverse.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify diff --git a/src/util/Cast.hxx b/src/util/Cast.hxx new file mode 100644 index 000000000..887137da4 --- /dev/null +++ b/src/util/Cast.hxx @@ -0,0 +1,109 @@ +/* + * Copyright (C) 2013-2014 Max Kellermann <max@duempel.org> + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. + */ + +#ifndef CAST_HXX +#define CAST_HXX + +#include "Compiler.h" + +#include <stddef.h> + +/** + * Offset the given pointer by the specified number of bytes. + */ +static inline constexpr void * +OffsetPointer(void *p, ptrdiff_t offset) +{ + return (char *)p + offset; +} + +/** + * Offset the given pointer by the specified number of bytes. + */ +static inline constexpr const void * +OffsetPointer(const void *p, ptrdiff_t offset) +{ + return (const char *)p + offset; +} + +template<typename T, typename U> +static inline constexpr T * +OffsetCast(U *p, ptrdiff_t offset) +{ + return reinterpret_cast<T *>(OffsetPointer(p, offset)); +} + +template<typename T, typename U> +static inline constexpr T * +OffsetCast(const U *p, ptrdiff_t offset) +{ + return reinterpret_cast<const T *>(OffsetPointer(p, offset)); +} + +template<class C, class A> +static constexpr inline ptrdiff_t +ContainerAttributeOffset(const C *null_c, const A C::*p) +{ + return ptrdiff_t((const char *)null_c - (const char *)&(null_c->*p)); +} + +template<class C, class A> +static constexpr inline ptrdiff_t +ContainerAttributeOffset(const A C::*p) +{ + return ContainerAttributeOffset<C, A>(nullptr, p); +} + +/** + * Cast the given pointer to a struct member to its parent structure. + */ +template<class C, class A> +#if defined(__clang__) || GCC_CHECK_VERSION(4,7) +constexpr +#endif +static inline C & +ContainerCast(A &a, A C::*member) +{ + return *OffsetCast<C, A>(&a, ContainerAttributeOffset<C, A>(member)); +} + +/** + * Cast the given pointer to a struct member to its parent structure. + */ +template<class C, class A> +#if defined(__clang__) || GCC_CHECK_VERSION(4,7) +constexpr +#endif +static inline const C & +ContainerCast(const A &a, A C::*member) +{ + return *OffsetCast<const C, const A>(&a, ContainerAttributeOffset<C, A>(member)); +} + +#endif diff --git a/src/util/CharUtil.hxx b/src/util/CharUtil.hxx index dd964f9c3..84a88a94e 100644 --- a/src/util/CharUtil.hxx +++ b/src/util/CharUtil.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2011-2013 Max Kellermann <max@duempel.org> + * Copyright (C) 2011-2014 Max Kellermann <max@duempel.org> * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -27,75 +27,90 @@ * OF THE POSSIBILITY OF SUCH DAMAGE. */ -#ifndef CHAR_UTIL_HPP -#define CHAR_UTIL_HPP +#ifndef CHAR_UTIL_HXX +#define CHAR_UTIL_HXX constexpr static inline bool IsASCII(const unsigned char ch) { - return ch < 0x80; + return ch < 0x80; } constexpr static inline bool IsASCII(const char ch) { - return IsASCII((unsigned char)ch); + return IsASCII((unsigned char)ch); } +constexpr static inline bool IsWhitespaceOrNull(const char ch) { - return (unsigned char)ch <= 0x20; + return (unsigned char)ch <= 0x20; } +constexpr static inline bool IsWhitespaceNotNull(const char ch) { - return ch > 0 && ch <= 0x20; + return ch > 0 && ch <= 0x20; +} + +/** + * Is the given character whitespace? This calls the faster one of + * IsWhitespaceOrNull() or IsWhitespaceNotNull(). Use this if you + * want the fastest implementation, and you don't care if a null byte + * matches. + */ +constexpr +static inline bool +IsWhitespaceFast(const char ch) +{ + return IsWhitespaceOrNull(ch); } constexpr static inline bool IsPrintableASCII(char ch) { - return (signed char)ch >= 0x20; + return (signed char)ch >= 0x20; } constexpr static inline bool IsDigitASCII(char ch) { - return ch >= '0' && ch <= '9'; + return ch >= '0' && ch <= '9'; } constexpr static inline bool IsUpperAlphaASCII(char ch) { - return ch >= 'A' && ch <= 'Z'; + return ch >= 'A' && ch <= 'Z'; } constexpr static inline bool IsLowerAlphaASCII(char ch) { - return ch >= 'a' && ch <= 'z'; + return ch >= 'a' && ch <= 'z'; } constexpr static inline bool IsAlphaASCII(char ch) { - return IsUpperAlphaASCII(ch) || IsLowerAlphaASCII(ch); + return IsUpperAlphaASCII(ch) || IsLowerAlphaASCII(ch); } constexpr static inline bool IsAlphaNumericASCII(char ch) { - return IsAlphaASCII(ch) || IsDigitASCII(ch); + return IsAlphaASCII(ch) || IsDigitASCII(ch); } /** @@ -106,9 +121,22 @@ constexpr static inline char ToUpperASCII(char ch) { - return ch >= 'a' && ch <= 'z' - ? (ch - ('a' - 'A')) - : ch; + return ch >= 'a' && ch <= 'z' + ? (ch - ('a' - 'A')) + : ch; +} + +/** + * Convert the specified ASCII character (0x00..0x7f) to lower case. + * Unlike toupper(), it ignores the system locale. + */ +constexpr +static inline char +ToLowerASCII(char ch) +{ + return ch >= 'A' && ch <= 'Z' + ? (ch + ('a' - 'A')) + : ch; } #endif diff --git a/src/util/CircularBuffer.hxx b/src/util/CircularBuffer.hxx new file mode 100644 index 000000000..da6f412a5 --- /dev/null +++ b/src/util/CircularBuffer.hxx @@ -0,0 +1,186 @@ +/* + * Copyright (C) 2014 Max Kellermann <max@duempel.org> + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. + */ + +#ifndef CIRCULAR_BUFFER_HPP +#define CIRCULAR_BUFFER_HPP + +#include "WritableBuffer.hxx" + +#include <assert.h> +#include <stddef.h> + +/** + * A circular buffer. + * + * This class does not manage buffer memory. It will not allocate or + * free any memory, it only manages the contents of an existing + * buffer given to the constructor. + * + * Everything between #head and #tail is valid data (may wrap around). + * If both are equal, then the buffer is empty. Due to this + * implementation detail, the buffer is empty when #size-1 items are + * stored; the last buffer cell cannot be used. + */ +template<typename T> +class CircularBuffer { +public: + typedef WritableBuffer<T> Range; + typedef typename Range::pointer_type pointer_type; + typedef typename Range::size_type size_type; + +protected: + /** + * The next index to be read. + */ + size_type head; + + /** + * The next index to be written to. + */ + size_type tail; + + const size_type capacity; + const pointer_type data; + +public: + constexpr CircularBuffer(pointer_type _data, size_type _capacity) + :head(0), tail(0), capacity(_capacity), data(_data) {} + + CircularBuffer(const CircularBuffer &other) = delete; + +protected: + constexpr size_type Next(size_type i) const { + return i + 1 == capacity + ? 0 + : i + 1; + } + +public: + void Clear() { + head = tail = 0; + } + + constexpr size_type GetCapacity() const { + return capacity; + } + + constexpr bool IsEmpty() const { + return head == tail; + } + + constexpr bool IsFull() const { + return Next(tail) == head; + } + + /** + * Returns the number of elements stored in this buffer. + */ + constexpr size_type GetSize() const { + return head <= tail + ? tail - head + : capacity - head + tail; + } + + /** + * Returns the number of elements that can be added to this + * buffer. + */ + constexpr size_type GetSpace() const { + /* space = capacity - size - 1 */ + return (head <= tail + ? capacity - tail + head + : head - tail) + - 1; + } + + /** + * Prepares writing. Returns a buffer range which may be written. + * When you are finished, call Append(). + */ + Range Write() { + assert(head < capacity); + assert(tail < capacity); + + size_type end = tail < head + ? head - 1 + /* the "head==0" is there so we don't write + the last cell, as this situation cannot be + represented by head/tail */ + : capacity - (head == 0); + + return Range(data + tail, end - tail); + } + + /** + * Expands the tail of the buffer, after data has been written + * to the buffer returned by Write(). + */ + void Append(size_type n) { + assert(head < capacity); + assert(tail < capacity); + assert(n < capacity); + assert(tail + n <= capacity); + assert(head <= tail || tail + n < head); + + tail += n; + + if (tail == capacity) { + assert(head > 0); + tail = 0; + } + } + + /** + * Return a buffer range which may be read. The buffer pointer is + * writable, to allow modifications while parsing. + */ + Range Read() { + assert(head < capacity); + assert(tail < capacity); + + return Range(data + head, (tail < head ? capacity : tail) - head); + } + + /** + * Marks a chunk as consumed. + */ + void Consume(size_type n) { + assert(head < capacity); + assert(tail < capacity); + assert(n < capacity); + assert(head + n <= capacity); + assert(tail < head || head + n <= tail); + + head += n; + if (head == capacity) + head = 0; + } +}; + +#endif diff --git a/src/util/growing_fifo.h b/src/util/Clamp.hxx index 723c3b3ff..3217ef9f7 100644 --- a/src/util/growing_fifo.h +++ b/src/util/Clamp.hxx @@ -1,6 +1,5 @@ /* - * Copyright (C) 2003-2011 The Music Player Daemon Project - * http://www.musicpd.org + * Copyright (C) 2012 Max Kellermann <max@duempel.org> * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -28,46 +27,23 @@ * OF THE POSSIBILITY OF SUCH DAMAGE. */ -/** \file - * - * Helper functions for our FIFO buffer library (fifo_buffer.h) that - * allows growing the buffer on demand. - * - * This library is not thread safe. - */ - -#ifndef MPD_GROWING_FIFO_H -#define MPD_GROWING_FIFO_H +#ifndef CLAMP_HPP +#define CLAMP_HPP -#include <stddef.h> - -struct fifo_buffer; - -/** - * Allocate a new #fifo_buffer with the default size. - */ -struct fifo_buffer * -growing_fifo_new(void); - -/** - * Prepares writing to the buffer, see fifo_buffer_write() for - * details. The difference is that this function will automatically - * grow the buffer if it is too small. - * - * The caller is responsible for limiting the capacity of the buffer. - * - * @param length the number of bytes that will be written - * @return a pointer to the end of the buffer (will not be NULL) - */ -void * -growing_fifo_write(struct fifo_buffer **buffer_p, size_t length); +#include "Compiler.h" /** - * A helper function that combines growing_fifo_write(), memcpy(), - * fifo_buffer_append(). + * Clamps the specified value in a range. Returns #min or #max if the + * value is outside. */ -void -growing_fifo_append(struct fifo_buffer **buffer_p, - const void *data, size_t length); +template<typename T> +static inline constexpr const T & +Clamp(const T &value, const T &min, const T &max) +{ + return gcc_unlikely(value < min) + ? min + : (gcc_unlikely(value > max) + ? max : value); +} #endif diff --git a/src/util/ConstBuffer.hxx b/src/util/ConstBuffer.hxx new file mode 100644 index 000000000..4d0a49e98 --- /dev/null +++ b/src/util/ConstBuffer.hxx @@ -0,0 +1,251 @@ +/* + * Copyright (C) 2013-2014 Max Kellermann <max@duempel.org> + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. + */ + +#ifndef CONST_BUFFER_HPP +#define CONST_BUFFER_HPP + +#include "Compiler.h" + +#include <cstddef> + +#ifndef NDEBUG +#include <assert.h> +#endif + +template<typename T> +struct ConstBuffer; + +template<> +struct ConstBuffer<void> { + typedef size_t size_type; + typedef const void *pointer_type; + typedef pointer_type const_pointer_type; + typedef pointer_type iterator; + typedef pointer_type const_iterator; + + pointer_type data; + size_type size; + + ConstBuffer() = default; + + constexpr ConstBuffer(std::nullptr_t):data(nullptr), size(0) {} + + constexpr ConstBuffer(pointer_type _data, size_type _size) + :data(_data), size(_size) {} + + constexpr static ConstBuffer Null() { + return ConstBuffer(nullptr, 0); + } + + constexpr static ConstBuffer<void> FromVoid(ConstBuffer<void> other) { + return other; + } + + constexpr ConstBuffer<void> ToVoid() const { + return *this; + } + + constexpr bool IsNull() const { + return data == nullptr; + } + + constexpr bool IsEmpty() const { + return size == 0; + } +}; + +/** + * A reference to a memory area that is read-only. + */ +template<typename T> +struct ConstBuffer { + typedef size_t size_type; + typedef const T &reference_type; + typedef reference_type const_reference_type; + typedef const T *pointer_type; + typedef pointer_type const_pointer_type; + typedef pointer_type iterator; + typedef pointer_type const_iterator; + + pointer_type data; + size_type size; + + ConstBuffer() = default; + + constexpr ConstBuffer(std::nullptr_t):data(nullptr), size(0) {} + + constexpr ConstBuffer(pointer_type _data, size_type _size) + :data(_data), size(_size) {} + + constexpr static ConstBuffer Null() { + return ConstBuffer(nullptr, 0); + } + + /** + * Cast a ConstBuffer<void> to a ConstBuffer<T>. A "void" + * buffer records its size in bytes, and when casting to "T", + * the assertion below ensures that the size is a multiple of + * sizeof(T). + */ +#ifdef NDEBUG + constexpr +#endif + static ConstBuffer<T> FromVoid(ConstBuffer<void> other) { + static_assert(sizeof(T) > 0, "Empty base type"); +#ifndef NDEBUG + assert(other.size % sizeof(T) == 0); +#endif + return ConstBuffer<T>(pointer_type(other.data), + other.size / sizeof(T)); + } + + constexpr ConstBuffer<void> ToVoid() const { + static_assert(sizeof(T) > 0, "Empty base type"); + return ConstBuffer<void>(data, size * sizeof(T)); + } + + constexpr bool IsNull() const { + return data == nullptr; + } + + constexpr bool IsEmpty() const { + return size == 0; + } + + template<typename U> + gcc_pure + bool Contains(U &&u) const { + for (const auto &i : *this) + if (u == i) + return true; + + return false; + } + + constexpr iterator begin() const { + return data; + } + + constexpr iterator end() const { + return data + size; + } + + constexpr const_iterator cbegin() const { + return data; + } + + constexpr const_iterator cend() const { + return data + size; + } + +#ifdef NDEBUG + constexpr +#endif + reference_type operator[](size_type i) const { +#ifndef NDEBUG + assert(i < size); +#endif + + return data[i]; + } + + /** + * Returns a reference to the first element. Buffer must not + * be empty. + */ +#ifdef NDEBUG + constexpr +#endif + reference_type front() const { +#ifndef NDEBUG + assert(!IsEmpty()); +#endif + return data[0]; + } + + /** + * Returns a reference to the last element. Buffer must not + * be empty. + */ +#ifdef NDEBUG + constexpr +#endif + reference_type back() const { +#ifndef NDEBUG + assert(!IsEmpty()); +#endif + return data[size - 1]; + } + + /** + * Remove the first element (by moving the head pointer, does + * not actually modify the buffer). Buffer must not be empty. + */ + void pop_front() { +#ifndef NDEBUG + assert(!IsEmpty()); +#endif + + ++data; + --size; + } + + /** + * Remove the last element (by moving the tail pointer, does + * not actually modify the buffer). Buffer must not be empty. + */ + void pop_back() { +#ifndef NDEBUG + assert(!IsEmpty()); +#endif + + --size; + } + + /** + * Remove the first element and return a reference to it. + * Buffer must not be empty. + */ + reference_type shift() { + reference_type result = front(); + pop_front(); + return result; + } + + void skip_front(size_type n) { +#ifndef NDEBUG + assert(size >= n); +#endif + + data += n; + size -= n; + } +}; + +#endif diff --git a/src/util/Domain.hxx b/src/util/Domain.hxx index bbdbf8371..6dce7b731 100644 --- a/src/util/Domain.hxx +++ b/src/util/Domain.hxx @@ -1,24 +1,34 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project - * http://www.musicpd.org + * Copyright (C) 2013 Max Kellermann <max@duempel.org> * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * - 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. */ -#ifndef MPD_DOMAIN_HXX -#define MPD_DOMAIN_HXX +#ifndef DOMAIN_HXX +#define DOMAIN_HXX class Domain { const char *const name; diff --git a/src/util/DynamicFifoBuffer.hxx b/src/util/DynamicFifoBuffer.hxx new file mode 100644 index 000000000..c1e5d1b94 --- /dev/null +++ b/src/util/DynamicFifoBuffer.hxx @@ -0,0 +1,111 @@ +/* + * Copyright (C) 2003-2013 Max Kellermann <max@duempel.org> + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. + */ + +#ifndef FIFO_BUFFER_HPP +#define FIFO_BUFFER_HPP + +#include "ForeignFifoBuffer.hxx" + +/** + * A first-in-first-out buffer: you can append data at the end, and + * read data from the beginning. This class automatically shifts the + * buffer as needed. It is not thread safe. + */ +template<typename T> +class DynamicFifoBuffer : protected ForeignFifoBuffer<T> { +public: + typedef typename ForeignFifoBuffer<T>::size_type size_type; + typedef typename ForeignFifoBuffer<T>::pointer_type pointer_type; + typedef typename ForeignFifoBuffer<T>::const_pointer_type const_pointer_type; + typedef typename ForeignFifoBuffer<T>::Range Range; + + explicit DynamicFifoBuffer(size_type _capacity) + :ForeignFifoBuffer<T>(new T[_capacity], _capacity) {} + ~DynamicFifoBuffer() { + delete[] GetBuffer(); + } + + DynamicFifoBuffer(const DynamicFifoBuffer &) = delete; + + using ForeignFifoBuffer<T>::GetCapacity; + using ForeignFifoBuffer<T>::Clear; + using ForeignFifoBuffer<T>::IsEmpty; + using ForeignFifoBuffer<T>::IsFull; + using ForeignFifoBuffer<T>::GetAvailable; + using ForeignFifoBuffer<T>::Read; + using ForeignFifoBuffer<T>::Consume; + using ForeignFifoBuffer<T>::Write; + using ForeignFifoBuffer<T>::Append; + + void Grow(size_type new_capacity) { + assert(new_capacity > GetCapacity()); + + T *old_data = GetBuffer(); + T *new_data = new T[new_capacity]; + ForeignFifoBuffer<T>::MoveBuffer(new_data, new_capacity); + delete[] old_data; + } + + void WantWrite(size_type n) { + if (ForeignFifoBuffer<T>::WantWrite(n)) + /* we already have enough space */ + return; + + const size_type in_use = GetAvailable(); + const size_type required_capacity = in_use + n; + size_type new_capacity = GetCapacity(); + do { + new_capacity <<= 1; + } while (new_capacity < required_capacity); + + Grow(new_capacity); + } + + /** + * Write data to the buffer, growing it as needed. Returns a + * writable pointer. + */ + pointer_type Write(size_type n) { + WantWrite(n); + return Write().data; + } + + /** + * Append data to the buffer, growing it as needed. + */ + void Append(const_pointer_type p, size_type n) { + std::copy_n(p, n, Write(n)); + Append(n); + } + +protected: + using ForeignFifoBuffer<T>::GetBuffer; +}; + +#endif diff --git a/src/util/Error.cxx b/src/util/Error.cxx index 5675f4d81..92b2cc5d0 100644 --- a/src/util/Error.cxx +++ b/src/util/Error.cxx @@ -1,31 +1,44 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project - * http://www.musicpd.org + * Copyright (C) 2013 Max Kellermann <max@duempel.org> * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * - 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. */ #include "config.h" #include "Error.hxx" #include "Domain.hxx" +#ifdef WIN32 #include <glib.h> +#endif #include <errno.h> #include <stdarg.h> #include <stdio.h> +#include <string.h> const Domain errno_domain("errno"); @@ -70,7 +83,7 @@ Error::FormatPrefix(const char *fmt, ...) void Error::SetErrno(int e) { - Set(errno_domain, e, g_strerror(e)); + Set(errno_domain, e, strerror(e)); } void @@ -82,7 +95,7 @@ Error::SetErrno() void Error::SetErrno(int e, const char *prefix) { - Format(errno_domain, e, "%s: %s", prefix, g_strerror(e)); + Format(errno_domain, e, "%s: %s", prefix, strerror(e)); } void @@ -120,11 +133,42 @@ Error::FormatErrno(const char *fmt, ...) #ifdef WIN32 void -Error::SetLastError(const char *prefix) +Error::SetLastError(DWORD _code, const char *prefix) { - DWORD _code = GetLastError(); const char *msg = g_win32_error_message(_code); Format(win32_domain, int(_code), "%s: %s", prefix, msg); } +void +Error::SetLastError(const char *prefix) +{ + SetLastError(GetLastError(), prefix); +} + +void +Error::FormatLastError(DWORD _code, const char *fmt, ...) +{ + char buffer[1024]; + va_list ap; + va_start(ap, fmt); + vsnprintf(buffer, sizeof(buffer), fmt, ap); + va_end(ap); + + SetLastError(_code, buffer); +} + +void +Error::FormatLastError(const char *fmt, ...) +{ + DWORD _code = GetLastError(); + + char buffer[1024]; + va_list ap; + va_start(ap, fmt); + vsnprintf(buffer, sizeof(buffer), fmt, ap); + va_end(ap); + + SetLastError(_code, buffer); +} + #endif diff --git a/src/util/Error.hxx b/src/util/Error.hxx index ec8867c6c..ab66ae5cb 100644 --- a/src/util/Error.hxx +++ b/src/util/Error.hxx @@ -1,30 +1,40 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project - * http://www.musicpd.org + * Copyright (C) 2013 Max Kellermann <max@duempel.org> * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * - 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. */ -#ifndef MPD_ERROR_HXX -#define MPD_ERROR_HXX +#ifndef ERROR_HXX +#define ERROR_HXX #include "check.h" #include "Compiler.h" #include <string> -#include <algorithm> +#include <utility> #include <assert.h> @@ -141,17 +151,29 @@ public: message.insert(0, prefix); } + gcc_printf(2,3) void FormatPrefix(const char *fmt, ...); void SetErrno(int e); void SetErrno(); void SetErrno(int e, const char *prefix); void SetErrno(const char *prefix); + + gcc_printf(2,3) void FormatErrno(const char *prefix, ...); + + gcc_printf(3,4) void FormatErrno(int e, const char *prefix, ...); #ifdef WIN32 + void SetLastError(DWORD _code, const char *prefix); void SetLastError(const char *prefix); + + gcc_printf(3,4) + void FormatLastError(DWORD code, const char *fmt, ...); + + gcc_printf(2,3) + void FormatLastError(const char *fmt, ...); #endif }; diff --git a/src/util/ForeignFifoBuffer.hxx b/src/util/ForeignFifoBuffer.hxx new file mode 100644 index 000000000..b829fb030 --- /dev/null +++ b/src/util/ForeignFifoBuffer.hxx @@ -0,0 +1,250 @@ +/* + * Copyright (C) 2003-2014 Max Kellermann <max@duempel.org> + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. + */ + +#ifndef FOREIGN_FIFO_BUFFER_HXX +#define FOREIGN_FIFO_BUFFER_HXX + +#include "WritableBuffer.hxx" + +#include <utility> +#include <algorithm> + +#include <cstddef> + +#include <assert.h> + +/** + * A first-in-first-out buffer: you can append data at the end, and + * read data from the beginning. This class automatically shifts the + * buffer as needed. It is not thread safe. + * + * This class does not manage buffer memory. It will not allocate or + * free any memory, it only manages the contents of an existing buffer + * given to the constructor. + */ +template<typename T> +class ForeignFifoBuffer { +public: + typedef size_t size_type; + typedef WritableBuffer<T> Range; + typedef typename Range::pointer_type pointer_type; + typedef typename Range::const_pointer_type const_pointer_type; + +protected: + size_type head, tail, capacity; + T *data; + +public: + explicit constexpr ForeignFifoBuffer(std::nullptr_t n) + :head(0), tail(0), capacity(0), data(n) {} + + constexpr ForeignFifoBuffer(T *_data, size_type _capacity) + :head(0), tail(0), capacity(_capacity), data(_data) {} + + ForeignFifoBuffer(ForeignFifoBuffer &&src) + :head(src.head), tail(src.tail), + capacity(src.capacity), data(src.data) { + src.SetNull(); + } + + ForeignFifoBuffer &operator=(ForeignFifoBuffer &&src) { + head = src.head; + tail = src.tail; + capacity = src.capacity; + data = src.data; + src.SetNull(); + return *this; + } + + void Swap(ForeignFifoBuffer<T> &other) { + std::swap(head, other.head); + std::swap(tail, other.tail); + std::swap(capacity, other.capacity); + std::swap(data, other.data); + } + + constexpr bool IsNull() const { + return data == nullptr; + } + + constexpr bool IsDefined() const { + return !IsNull(); + } + + T *GetBuffer() { + return data; + } + + constexpr size_type GetCapacity() const { + return capacity; + } + + void SetNull() { + head = tail = 0; + capacity = 0; + data = nullptr; + } + + void SetBuffer(T *_data, size_type _capacity) { + assert(_data != nullptr); + assert(_capacity > 0); + + head = tail = 0; + capacity = _capacity; + data = _data; + } + + void MoveBuffer(T *new_data, size_type new_capacity) { + assert(new_capacity >= tail - head); + + std::move(data + head, data + tail, new_data); + data = new_data; + capacity = new_capacity; + tail -= head; + head = 0; + } + + void Clear() { + head = tail = 0; + } + + constexpr bool IsEmpty() const { + return head == tail; + } + + constexpr bool IsFull() const { + return head == 0 && tail == capacity; + } + + /** + * Prepares writing. Returns a buffer range which may be written. + * When you are finished, call append(). + */ + Range Write() { + if (IsEmpty()) + Clear(); + else if (tail == capacity) + Shift(); + + return Range(data + tail, capacity - tail); + } + + bool WantWrite(size_type n) { + if (tail + n <= capacity) + /* enough space after the tail */ + return true; + + const size_type in_use = tail - head; + const size_type required_capacity = in_use + n; + if (required_capacity > capacity) + return false; + + Shift(); + assert(tail + n <= capacity); + return true; + } + + /** + * Expands the tail of the buffer, after data has been written to + * the buffer returned by write(). + */ + void Append(size_type n) { + assert(tail <= capacity); + assert(n <= capacity); + assert(tail + n <= capacity); + + tail += n; + } + + constexpr size_type GetAvailable() const { + return tail - head; + } + + /** + * Return a buffer range which may be read. The buffer pointer is + * writable, to allow modifications while parsing. + */ + constexpr Range Read() const { + return Range(data + head, tail - head); + } + + /** + * Marks a chunk as consumed. + */ + void Consume(size_type n) { + assert(tail <= capacity); + assert(head <= tail); + assert(n <= tail); + assert(head + n <= tail); + + head += n; + } + + size_type Read(pointer_type p, size_type n) { + auto range = Read(); + if (n > range.size) + n = range.size; + std::copy_n(range.data, n, p); + Consume(n); + return n; + } + + /** + * Move as much data as possible from the specified buffer. + * + * @return the number of items moved + */ + size_type MoveFrom(ForeignFifoBuffer<T> &src) { + auto r = src.Read(); + auto w = Write(); + size_t n = std::min(r.size, w.size); + + std::move(r.data, r.data + n, w.data); + Append(n); + src.Consume(n); + return n; + } + +protected: + void Shift() { + if (head == 0) + return; + + assert(head <= capacity); + assert(tail <= capacity); + assert(tail >= head); + + std::move(data + head, data + tail, data); + + tail -= head; + head = 0; + } +}; + +#endif diff --git a/src/util/FormatString.cxx b/src/util/FormatString.cxx index c13d0fb52..d222a505c 100644 --- a/src/util/FormatString.cxx +++ b/src/util/FormatString.cxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify @@ -19,10 +19,13 @@ #include "FormatString.hxx" -#include <string.h> #include <stdio.h> #include <stdlib.h> +#ifdef WIN32 +#include <string.h> +#endif + char * FormatNewV(const char *fmt, va_list args) { diff --git a/src/util/FormatString.hxx b/src/util/FormatString.hxx index bb4263107..dc1ac3c67 100644 --- a/src/util/FormatString.hxx +++ b/src/util/FormatString.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify diff --git a/src/util/HugeAllocator.cxx b/src/util/HugeAllocator.cxx index d1c55c965..1da049f2f 100644 --- a/src/util/HugeAllocator.cxx +++ b/src/util/HugeAllocator.cxx @@ -1,20 +1,30 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project - * http://www.musicpd.org + * Copyright (C) 2013 Max Kellermann <max@duempel.org> * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * - 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. */ #include "HugeAllocator.hxx" diff --git a/src/util/HugeAllocator.hxx b/src/util/HugeAllocator.hxx index f44a6e3b8..fa45e5610 100644 --- a/src/util/HugeAllocator.hxx +++ b/src/util/HugeAllocator.hxx @@ -1,24 +1,34 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project - * http://www.musicpd.org + * Copyright (C) 2013 Max Kellermann <max@duempel.org> * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * - 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. */ -#ifndef MPD_HUGE_ALLOCATOR_HXX -#define MPD_HUGE_ALLOCATOR_HXX +#ifndef HUGE_ALLOCATOR_HXX +#define HUGE_ALLOCATOR_HXX #include "Compiler.h" @@ -53,6 +63,31 @@ HugeFree(void *p, size_t size); void HugeDiscard(void *p, size_t size); +#elif defined(WIN32) +#include <windows.h> + +gcc_malloc +static inline void * +HugeAllocate(size_t size) +{ + // TODO: use MEM_LARGE_PAGES + return VirtualAlloc(nullptr, size, + MEM_COMMIT|MEM_RESERVE, + PAGE_READWRITE); +} + +static inline void +HugeFree(void *p, gcc_unused size_t size) +{ + VirtualFree(p, 0, MEM_RELEASE); +} + +static inline void +HugeDiscard(void *p, size_t size) +{ + VirtualAlloc(p, size, MEM_RESET, PAGE_NOACCESS); +} + #else /* not Linux: fall back to standard C calls */ diff --git a/src/util/LazyRandomEngine.cxx b/src/util/LazyRandomEngine.cxx index 0f90ebb2e..b0aac913c 100644 --- a/src/util/LazyRandomEngine.cxx +++ b/src/util/LazyRandomEngine.cxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify diff --git a/src/util/LazyRandomEngine.hxx b/src/util/LazyRandomEngine.hxx index bfe4bb60c..4156b3bb1 100644 --- a/src/util/LazyRandomEngine.hxx +++ b/src/util/LazyRandomEngine.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify diff --git a/src/util/OptionDef.hxx b/src/util/OptionDef.hxx new file mode 100644 index 000000000..dd82154c4 --- /dev/null +++ b/src/util/OptionDef.hxx @@ -0,0 +1,63 @@ +/* + * Copyright (C) 2003-2014 The Music Player Daemon Project + * http://www.musicpd.org + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#ifndef MPD_UTIL_OPTIONDEF_HXX +#define MPD_UTIL_OPTIONDEF_HXX + +/** + * Command line option definition. + */ +class OptionDef +{ + const char *long_option; + char short_option; + const char *desc; +public: + constexpr OptionDef(const char *_long_option, const char *_desc) + : long_option(_long_option), + short_option(0), + desc(_desc) { } + + constexpr OptionDef(const char *_long_option, + char _short_option, const char *_desc) + : long_option(_long_option), + short_option(_short_option), + desc(_desc) { } + + bool HasLongOption() const { return long_option != nullptr; } + bool HasShortOption() const { return short_option != 0; } + bool HasDescription() const { return desc != nullptr; } + + const char *GetLongOption() const { + assert(HasLongOption()); + return long_option; + } + + char GetShortOption() const { + assert(HasShortOption()); + return short_option; + } + + const char *GetDescription() const { + assert(HasDescription()); + return desc; + } +}; + +#endif diff --git a/src/util/OptionParser.cxx b/src/util/OptionParser.cxx new file mode 100644 index 000000000..b10008527 --- /dev/null +++ b/src/util/OptionParser.cxx @@ -0,0 +1,59 @@ +/* + * Copyright (C) 2003-2014 The Music Player Daemon Project + * http://www.musicpd.org + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#include "OptionParser.hxx" +#include "OptionDef.hxx" + +#include <string.h> + +bool OptionParser::CheckOption(const OptionDef &opt) +{ + assert(option != nullptr); + + if (is_long) + return opt.HasLongOption() && + strcmp(option, opt.GetLongOption()) == 0; + + return opt.HasShortOption() && + option[0] == opt.GetShortOption() && + option[1] == '\0'; +} + +bool OptionParser::ParseNext() +{ + assert(HasEntries()); + char *arg = *argv; + ++argv; + --argc; + if (arg[0] == '-') { + if (arg[1] == '-') { + option = arg + 2; + is_long = true; + } + else { + option = arg + 1; + is_long = false; + } + option_raw = arg; + return true; + } + option = nullptr; + option_raw = nullptr; + return false; +} diff --git a/src/util/OptionParser.hxx b/src/util/OptionParser.hxx new file mode 100644 index 000000000..b9d34adbb --- /dev/null +++ b/src/util/OptionParser.hxx @@ -0,0 +1,88 @@ +/* + * Copyright (C) 2003-2014 The Music Player Daemon Project + * http://www.musicpd.org + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#ifndef MPD_UTIL_OPTIONPARSER_HXX +#define MPD_UTIL_OPTIONPARSER_HXX + +#include <assert.h> + +class OptionDef; + +/** + * Command line option parser. + */ +class OptionParser +{ + int argc; + char **argv; + char *option; + char *option_raw; + bool is_long; +public: + /** + * Constructs #OptionParser. + */ + OptionParser(int _argc, char **_argv) + : argc(_argc - 1), argv(_argv + 1), + option(nullptr), option_raw(nullptr), is_long(false) { } + + /** + * Checks if there are command line entries to process. + */ + bool HasEntries() const { return argc > 0; } + + /** + * Gets the last parsed option. + */ + char *GetOption() { + assert(option_raw != nullptr); + return option_raw; + } + + /** + * Checks if current option is a specified option. + */ + bool CheckOption(const OptionDef& opt); + + /** + * Checks if current option is a specified option + * or specified alternative option. + */ + bool CheckOption(const OptionDef& opt, const OptionDef &alt_opt) { + return CheckOption(opt) || CheckOption(alt_opt); + } + + /** + * Parses current command line entry. + * Returns true on success, false otherwise. + * Regardless of result, advances current position to the next + * command line entry. + */ + bool ParseNext(); + + /** + * Checks if specified string is a command line option. + */ + static bool IsOption(const char *s) { + assert(s != nullptr); + return s[0] == '-'; + } +}; + +#endif diff --git a/src/util/PeakBuffer.cxx b/src/util/PeakBuffer.cxx index d9b193dd1..e4624bbec 100644 --- a/src/util/PeakBuffer.cxx +++ b/src/util/PeakBuffer.cxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify @@ -18,46 +18,39 @@ */ #include "PeakBuffer.hxx" -#include "HugeAllocator.hxx" -#include "fifo_buffer.h" +#include "DynamicFifoBuffer.hxx" #include <algorithm> #include <assert.h> -#include <stdint.h> #include <string.h> PeakBuffer::~PeakBuffer() { - if (normal_buffer != nullptr) - fifo_buffer_free(normal_buffer); - - if (peak_buffer != nullptr) - HugeFree(peak_buffer, peak_size); + delete normal_buffer; + delete peak_buffer; } bool PeakBuffer::IsEmpty() const { - return (normal_buffer == nullptr || - fifo_buffer_is_empty(normal_buffer)) && - (peak_buffer == nullptr || - fifo_buffer_is_empty(peak_buffer)); + return (normal_buffer == nullptr || normal_buffer->IsEmpty()) && + (peak_buffer == nullptr || peak_buffer->IsEmpty()); } -const void * -PeakBuffer::Read(size_t *length_r) const +WritableBuffer<void> +PeakBuffer::Read() const { if (normal_buffer != nullptr) { - const void *p = fifo_buffer_read(normal_buffer, length_r); - if (p != nullptr) - return p; + const auto p = normal_buffer->Read(); + if (!p.IsEmpty()) + return p.ToVoid(); } if (peak_buffer != nullptr) { - const void *p = fifo_buffer_read(peak_buffer, length_r); - if (p != nullptr) - return p; + const auto p = peak_buffer->Read(); + if (!p.IsEmpty()) + return p.ToVoid(); } return nullptr; @@ -66,15 +59,15 @@ PeakBuffer::Read(size_t *length_r) const void PeakBuffer::Consume(size_t length) { - if (normal_buffer != nullptr && !fifo_buffer_is_empty(normal_buffer)) { - fifo_buffer_consume(normal_buffer, length); + if (normal_buffer != nullptr && !normal_buffer->IsEmpty()) { + normal_buffer->Consume(length); return; } - if (peak_buffer != nullptr && !fifo_buffer_is_empty(peak_buffer)) { - fifo_buffer_consume(peak_buffer, length); - if (fifo_buffer_is_empty(peak_buffer)) { - HugeFree(peak_buffer, peak_size); + if (peak_buffer != nullptr && !peak_buffer->IsEmpty()) { + peak_buffer->Consume(length); + if (peak_buffer->IsEmpty()) { + delete peak_buffer; peak_buffer = nullptr; } @@ -83,7 +76,7 @@ PeakBuffer::Consume(size_t length) } static size_t -AppendTo(fifo_buffer *buffer, const void *data, size_t length) +AppendTo(DynamicFifoBuffer<uint8_t> &buffer, const void *data, size_t length) { assert(data != nullptr); assert(length > 0); @@ -91,14 +84,13 @@ AppendTo(fifo_buffer *buffer, const void *data, size_t length) size_t total = 0; do { - size_t max_length; - void *p = fifo_buffer_write(buffer, &max_length); - if (p == nullptr) + const auto p = buffer.Write(); + if (p.IsEmpty()) break; - const size_t nbytes = std::min(length, max_length); - memcpy(p, data, nbytes); - fifo_buffer_append(buffer, nbytes); + const size_t nbytes = std::min(length, p.size); + memcpy(p.data, data, nbytes); + buffer.Append(nbytes); data = (const uint8_t *)data + nbytes; length -= nbytes; @@ -114,15 +106,15 @@ PeakBuffer::Append(const void *data, size_t length) if (length == 0) return true; - if (peak_buffer != nullptr && !fifo_buffer_is_empty(peak_buffer)) { - size_t nbytes = AppendTo(peak_buffer, data, length); + if (peak_buffer != nullptr && !peak_buffer->IsEmpty()) { + size_t nbytes = AppendTo(*peak_buffer, data, length); return nbytes == length; } if (normal_buffer == nullptr) - normal_buffer = fifo_buffer_new(normal_size); + normal_buffer = new DynamicFifoBuffer<uint8_t>(normal_size); - size_t nbytes = AppendTo(normal_buffer, data, length); + size_t nbytes = AppendTo(*normal_buffer, data, length); if (nbytes > 0) { data = (const uint8_t *)data + nbytes; length -= nbytes; @@ -132,13 +124,11 @@ PeakBuffer::Append(const void *data, size_t length) if (peak_buffer == nullptr) { if (peak_size > 0) - peak_buffer = (fifo_buffer *)HugeAllocate(peak_size); + peak_buffer = new DynamicFifoBuffer<uint8_t>(peak_size); if (peak_buffer == nullptr) return false; - - fifo_buffer_init(peak_buffer, peak_size); } - nbytes = AppendTo(peak_buffer, data, length); + nbytes = AppendTo(*peak_buffer, data, length); return nbytes == length; } diff --git a/src/util/PeakBuffer.hxx b/src/util/PeakBuffer.hxx index a3f385e3e..702a3dee0 100644 --- a/src/util/PeakBuffer.hxx +++ b/src/util/PeakBuffer.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify @@ -20,11 +20,14 @@ #ifndef MPD_PEAK_BUFFER_HXX #define MPD_PEAK_BUFFER_HXX +#include "WritableBuffer.hxx" #include "Compiler.h" #include <stddef.h> +#include <stdint.h> -struct fifo_buffer; +template<typename T> struct WritableBuffer; +template<typename T> class DynamicFifoBuffer; /** * A FIFO-like buffer that will allocate more memory on demand to @@ -34,7 +37,7 @@ struct fifo_buffer; class PeakBuffer { size_t normal_size, peak_size; - fifo_buffer *normal_buffer, *peak_buffer; + DynamicFifoBuffer<uint8_t> *normal_buffer, *peak_buffer; public: PeakBuffer(size_t _normal_size, size_t _peak_size) @@ -57,7 +60,9 @@ public: gcc_pure bool IsEmpty() const; - const void *Read(size_t *length_r) const; + gcc_pure + WritableBuffer<void> Read() const; + void Consume(size_t length); bool Append(const void *data, size_t length); diff --git a/src/util/RefCount.hxx b/src/util/RefCount.hxx index dff850036..02ef8818c 100644 --- a/src/util/RefCount.hxx +++ b/src/util/RefCount.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * Redistribution and use in source and binary forms, with or without diff --git a/src/util/SliceBuffer.hxx b/src/util/SliceBuffer.hxx index 6cde75f34..63ca087ae 100644 --- a/src/util/SliceBuffer.hxx +++ b/src/util/SliceBuffer.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify diff --git a/src/util/list_sort.h b/src/util/SplitString.cxx index 7a65020b9..75e799279 100644 --- a/src/util/list_sort.h +++ b/src/util/SplitString.cxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2012 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify @@ -17,17 +17,21 @@ * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ -/* - * This code was imported from the Linux kernel. - * - */ +#include "SplitString.hxx" + +#include <string.h> -#ifndef _LINUX_LIST_SORT_H -#define _LINUX_LIST_SORT_H +SplitString::SplitString(const char *s, char separator) + :first(nullptr) +{ + const char *x = strchr(s, separator); + if (x == nullptr) + return; -struct list_head; + size_t length = x - s; + second = x + 1; -void list_sort(void *priv, struct list_head *head, - int (*cmp)(void *priv, struct list_head *a, - struct list_head *b)); -#endif + first = new char[length + 1]; + memcpy(first, s, length); + first[length] = 0; +} diff --git a/src/util/SplitString.hxx b/src/util/SplitString.hxx new file mode 100644 index 000000000..96ffb21ec --- /dev/null +++ b/src/util/SplitString.hxx @@ -0,0 +1,71 @@ +/* + * Copyright (C) 2003-2014 The Music Player Daemon Project + * http://www.musicpd.org + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ + +#ifndef MPD_SPLIT_STRING_HXX +#define MPD_SPLIT_STRING_HXX + +#include "Compiler.h" + +#include <assert.h> + +/** + * Split a given constant string at a separator character. Duplicates + * the first part to be able to null-terminate it. + */ +class SplitString { + char *first; + const char *second; + +public: + SplitString(const char *s, char separator); + + ~SplitString() { + delete[] first; + } + + /** + * Was the separator found? + */ + bool IsDefined() const { + return first != nullptr; + } + + /** + * Is the first part empty? + */ + bool IsEmpty() const { + assert(IsDefined()); + + return *first == 0; + } + + const char *GetFirst() const { + assert(IsDefined()); + + return first; + } + + const char *GetSecond() const { + assert(IsDefined()); + + return second; + } +}; + +#endif diff --git a/src/util/FifoBuffer.hxx b/src/util/StaticFifoBuffer.hxx index 75d2d2ef2..40668d152 100644 --- a/src/util/FifoBuffer.hxx +++ b/src/util/StaticFifoBuffer.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2010 Max Kellermann <max@duempel.org> + * Copyright (C) 2003-2014 Max Kellermann <max@duempel.org> * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -27,8 +27,8 @@ * OF THE POSSIBILITY OF SUCH DAMAGE. */ -#ifndef FIFO_BUFFER_HPP -#define FIFO_BUFFER_HPP +#ifndef STATIC_FIFO_BUFFER_HPP +#define STATIC_FIFO_BUFFER_HPP #include "WritableBuffer.hxx" @@ -44,89 +44,91 @@ * buffer as needed. It is not thread safe. */ template<class T, size_t size> -class FifoBuffer { +class StaticFifoBuffer { public: - typedef size_t size_type; + typedef size_t size_type; public: - typedef WritableBuffer<T> Range; + typedef WritableBuffer<T> Range; protected: - size_type head, tail; - T data[size]; + size_type head, tail; + T data[size]; public: - constexpr - FifoBuffer():head(0), tail(0) {} - -protected: - void Shift() { - if (head == 0) - return; - - assert(head <= size); - assert(tail <= size); - assert(tail >= head); - - std::move(data + head, data + tail, data); - - tail -= head; - head = 0; - } - -public: - void Clear() { - head = tail = 0; - } - - bool IsEmpty() const { - return head == tail; - } - - bool IsFull() const { - return head == 0 && tail == size; - } - - /** - * Prepares writing. Returns a buffer range which may be written. - * When you are finished, call append(). - */ - Range Write() { - Shift(); - return Range(data + tail, size - tail); - } - - /** - * Expands the tail of the buffer, after data has been written to - * the buffer returned by write(). - */ - void Append(size_type n) { - assert(tail <= size); - assert(n <= size); - assert(tail + n <= size); - - tail += n; - } - - /** - * Return a buffer range which may be read. The buffer pointer is - * writable, to allow modifications while parsing. - */ - Range Read() { - return Range(data + head, tail - head); - } - - /** - * Marks a chunk as consumed. - */ - void Consume(size_type n) { - assert(tail <= size); - assert(head <= tail); - assert(n <= tail); - assert(head + n <= tail); - - head += n; - } + constexpr + StaticFifoBuffer():head(0), tail(0) {} + + void Shift() { + if (head == 0) + return; + + assert(head <= size); + assert(tail <= size); + assert(tail >= head); + + std::move(data + head, data + tail, data); + + tail -= head; + head = 0; + } + + void Clear() { + head = tail = 0; + } + + bool IsEmpty() const { + return head == tail; + } + + bool IsFull() const { + return head == 0 && tail == size; + } + + /** + * Prepares writing. Returns a buffer range which may be written. + * When you are finished, call append(). + */ + Range Write() { + if (IsEmpty()) + Clear(); + else if (tail == size) + Shift(); + + return Range(data + tail, size - tail); + } + + /** + * Expands the tail of the buffer, after data has been written to + * the buffer returned by write(). + */ + void Append(size_type n) { + assert(tail <= size); + assert(n <= size); + assert(tail + n <= size); + + tail += n; + } + + /** + * Return a buffer range which may be read. The buffer pointer is + * writable, to allow modifications while parsing. + */ + Range Read() { + return Range(data + head, tail - head); + } + + /** + * Marks a chunk as consumed. + */ + void Consume(size_type n) { + assert(tail <= size); + assert(head <= tail); + assert(n <= tail); + assert(head + n <= tail); + + head += n; + } }; #endif diff --git a/src/util/StringUtil.cxx b/src/util/StringUtil.cxx index 7e295bf90..bcade2b3b 100644 --- a/src/util/StringUtil.cxx +++ b/src/util/StringUtil.cxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify @@ -21,10 +21,13 @@ #include "CharUtil.hxx" #include "ASCII.hxx" +#include <algorithm> + #include <assert.h> +#include <string.h> const char * -strchug_fast(const char *p) +StripLeft(const char *p) { while (IsWhitespaceNotNull(*p)) ++p; @@ -32,6 +35,79 @@ strchug_fast(const char *p) return p; } +const char * +StripLeft(const char *p, const char *end) +{ + while (p < end && IsWhitespaceOrNull(*p)) + ++p; + + return p; +} + +const char * +StripRight(const char *p, const char *end) +{ + while (end > p && IsWhitespaceOrNull(end[-1])) + --end; + + return end; +} + +size_t +StripRight(const char *p, size_t length) +{ + while (length > 0 && IsWhitespaceOrNull(p[length - 1])) + --length; + + return length; +} + +void +StripRight(char *p) +{ + size_t old_length = strlen(p); + size_t new_length = StripRight(p, old_length); + p[new_length] = 0; +} + +char * +Strip(char *p) +{ + p = StripLeft(p); + StripRight(p); + return p; +} + +bool +StringStartsWith(const char *haystack, const char *needle) +{ + const size_t length = strlen(needle); + return memcmp(haystack, needle, length) == 0; +} + +bool +StringEndsWith(const char *haystack, const char *needle) +{ + const size_t haystack_length = strlen(haystack); + const size_t needle_length = strlen(needle); + + return haystack_length >= needle_length && + memcmp(haystack + haystack_length - needle_length, + needle, needle_length) == 0; +} + +char * +CopyString(char *gcc_restrict dest, const char *gcc_restrict src, size_t size) +{ + size_t length = strlen(src); + if (length >= size) + length = size - 1; + + char *p = std::copy(src, src + length, dest); + *p = '\0'; + return p; +} + bool string_array_contains(const char *const* haystack, const char *needle) { diff --git a/src/util/StringUtil.hxx b/src/util/StringUtil.hxx index 1c67910a9..9beda5441 100644 --- a/src/util/StringUtil.hxx +++ b/src/util/StringUtil.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify @@ -22,24 +22,86 @@ #include "Compiler.h" +#include <stddef.h> + /** * Returns a pointer to the first non-whitespace character in the * string, or to the end of the string. - * - * This is a faster version of g_strchug(), because it does not move - * data. */ gcc_pure const char * -strchug_fast(const char *p); +StripLeft(const char *p); gcc_pure static inline char * -strchug_fast(char *p) +StripLeft(char *p) { - return const_cast<char *>(strchug_fast((const char *)p)); + return const_cast<char *>(StripLeft((const char *)p)); } +gcc_pure +const char * +StripLeft(const char *p, const char *end); + +/** + * Determine the string's end as if it was stripped on the right side. + */ +gcc_pure +const char * +StripRight(const char *p, const char *end); + +/** + * Determine the string's end as if it was stripped on the right side. + */ +gcc_pure +static inline char * +StripRight(char *p, char *end) +{ + return const_cast<char *>(StripRight((const char *)p, + (const char *)end)); +} + +/** + * Determine the string's length as if it was stripped on the right + * side. + */ +gcc_pure +size_t +StripRight(const char *p, size_t length); + +/** + * Strip trailing whitespace by null-terminating the string. + */ +void +StripRight(char *p); + +/** + * Skip whitespace at the beginning and terminate the string after the + * last non-whitespace character. + */ +char * +Strip(char *p); + +gcc_pure +bool +StringStartsWith(const char *haystack, const char *needle); + +gcc_pure +bool +StringEndsWith(const char *haystack, const char *needle); + +/** + * Copy a string. If the buffer is too small, then the string is + * truncated. This is a safer version of strncpy(). + * + * @param size the size of the destination buffer (including the null + * terminator) + * @return a pointer to the null terminator + */ +gcc_nonnull_all +char * +CopyString(char *dest, const char *src, size_t size); + /** * Checks whether a string array contains the specified string. * diff --git a/src/util/TextFile.hxx b/src/util/TextFile.hxx new file mode 100644 index 000000000..3d7d2d0df --- /dev/null +++ b/src/util/TextFile.hxx @@ -0,0 +1,52 @@ +/* + * Copyright (C) 2008-2014 Max Kellermann <max@duempel.org> + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. + */ + +#ifndef TEXT_FILE_HXX +#define TEXT_FILE_HXX + +#include <string.h> + +template<typename B> +char * +ReadBufferedLine(B &buffer) +{ + auto r = buffer.Read(); + char *newline = reinterpret_cast<char*>(memchr(r.data, '\n', r.size)); + if (newline == nullptr) + return nullptr; + + buffer.Consume(newline + 1 - r.data); + + if (newline > r.data && newline[-1] == '\r') + --newline; + *newline = 0; + return r.data; +} + +#endif diff --git a/src/util/Tokenizer.cxx b/src/util/Tokenizer.cxx index 1c8af23fd..19322b70d 100644 --- a/src/util/Tokenizer.cxx +++ b/src/util/Tokenizer.cxx @@ -1,20 +1,30 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project - * http://www.musicpd.org + * Copyright (C) 2009-2014 Max Kellermann <max@duempel.org> * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * - 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. */ #include "config.h" @@ -24,11 +34,6 @@ #include "Error.hxx" #include "Domain.hxx" -#include <glib.h> - -#include <assert.h> -#include <string.h> - static constexpr Domain tokenizer_domain("tokenizer"); static inline bool @@ -62,11 +67,11 @@ Tokenizer::NextWord(Error &error) whitespace or end-of-string */ while (*++input != 0) { - if (IsWhitespaceOrNull(*input)) { + if (IsWhitespaceFast(*input)) { /* a whitespace: the word ends here */ *input = 0; /* skip all following spaces, too */ - input = strchug_fast(input + 1); + input = StripLeft(input + 1); break; } @@ -107,11 +112,11 @@ Tokenizer::NextUnquoted(Error &error) whitespace or end-of-string */ while (*++input != 0) { - if (IsWhitespaceOrNull(*input)) { + if (IsWhitespaceFast(*input)) { /* a whitespace: the word ends here */ *input = 0; /* skip all following spaces, too */ - input = strchug_fast(input + 1); + input = StripLeft(input + 1); break; } @@ -171,7 +176,7 @@ Tokenizer::NextString(Error &error) line) */ ++input; - if (!IsWhitespaceOrNull(*input)) { + if (!IsWhitespaceFast(*input)) { error.Set(tokenizer_domain, "Space expected after closing '\"'"); return nullptr; @@ -180,7 +185,7 @@ Tokenizer::NextString(Error &error) /* finish the string and return it */ *dest = 0; - input = strchug_fast(input); + input = StripLeft(input); return word; } diff --git a/src/util/Tokenizer.hxx b/src/util/Tokenizer.hxx index a689dc31d..dc2646589 100644 --- a/src/util/Tokenizer.hxx +++ b/src/util/Tokenizer.hxx @@ -1,24 +1,34 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project - * http://www.musicpd.org + * Copyright (C) 2009-2014 Max Kellermann <max@duempel.org> * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + * - 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. */ -#ifndef MPD_TOKENIZER_HXX -#define MPD_TOKENIZER_HXX +#ifndef TOKENIZER_HXX +#define TOKENIZER_HXX class Error; diff --git a/src/util/UTF8.cxx b/src/util/UTF8.cxx new file mode 100644 index 000000000..50ff19e88 --- /dev/null +++ b/src/util/UTF8.cxx @@ -0,0 +1,345 @@ +/* + * Copyright (C) 2011-2014 Max Kellermann <max@duempel.org> + * http://www.musicpd.org + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. + */ + +#include "UTF8.hxx" +#include "CharUtil.hxx" + +#include <algorithm> + +/** + * Is this a leading byte that is followed by 1 continuation byte? + */ +static constexpr bool +IsLeading1(unsigned char ch) +{ + return (ch & 0xe0) == 0xc0; +} + +static constexpr unsigned char +MakeLeading1(unsigned char value) +{ + return 0xc0 | value; +} + +/** + * Is this a leading byte that is followed by 2 continuation byte? + */ +static constexpr bool +IsLeading2(unsigned char ch) +{ + return (ch & 0xf0) == 0xe0; +} + +static constexpr unsigned char +MakeLeading2(unsigned char value) +{ + return 0xe0 | value; +} + +/** + * Is this a leading byte that is followed by 3 continuation byte? + */ +static constexpr bool +IsLeading3(unsigned char ch) +{ + return (ch & 0xf8) == 0xf0; +} + +static constexpr unsigned char +MakeLeading3(unsigned char value) +{ + return 0xf0 | value; +} + +/** + * Is this a leading byte that is followed by 4 continuation byte? + */ +static constexpr bool +IsLeading4(unsigned char ch) +{ + return (ch & 0xfc) == 0xf8; +} + +static constexpr unsigned char +MakeLeading4(unsigned char value) +{ + return 0xf8 | value; +} + +/** + * Is this a leading byte that is followed by 5 continuation byte? + */ +static constexpr bool +IsLeading5(unsigned char ch) +{ + return (ch & 0xfe) == 0xfc; +} + +static constexpr unsigned char +MakeLeading5(unsigned char value) +{ + return 0xfc | value; +} + +static constexpr bool +IsContinuation(unsigned char ch) +{ + return (ch & 0xc0) == 0x80; +} + +/** + * Generate a continuation byte of the low 6 bit. + */ +static constexpr unsigned char +MakeContinuation(unsigned char value) +{ + return 0x80 | (value & 0x3f); +} + +bool +ValidateUTF8(const char *p) +{ + for (; *p != 0; ++p) { + unsigned char ch = *p; + if (IsASCII(ch)) + continue; + + if (IsContinuation(ch)) + /* continuation without a prefix */ + return false; + + if (IsLeading1(ch)) { + /* 1 continuation */ + if (!IsContinuation(*++p)) + return false; + } else if (IsLeading2(ch)) { + /* 2 continuations */ + if (!IsContinuation(*++p) || !IsContinuation(*++p)) + return false; + } else if (IsLeading3(ch)) { + /* 3 continuations */ + if (!IsContinuation(*++p) || !IsContinuation(*++p) || + !IsContinuation(*++p)) + return false; + } else if (IsLeading4(ch)) { + /* 4 continuations */ + if (!IsContinuation(*++p) || !IsContinuation(*++p) || + !IsContinuation(*++p) || !IsContinuation(*++p)) + return false; + } else if (IsLeading5(ch)) { + /* 5 continuations */ + if (!IsContinuation(*++p) || !IsContinuation(*++p) || + !IsContinuation(*++p) || !IsContinuation(*++p) || + !IsContinuation(*++p)) + return false; + } else + return false; + } + + return true; +} + +size_t +SequenceLengthUTF8(char ch) +{ + if (IsASCII(ch)) + return 1; + else if (IsLeading1(ch)) + /* 1 continuation */ + return 2; + else if (IsLeading2(ch)) + /* 2 continuations */ + return 3; + else if (IsLeading3(ch)) + /* 3 continuations */ + return 4; + else if (IsLeading4(ch)) + /* 4 continuations */ + return 5; + else if (IsLeading5(ch)) + /* 5 continuations */ + return 6; + else + /* continuation without a prefix or some other illegal + start byte */ + return 0; + +} + +template<size_t L> +struct CheckSequenceUTF8 { + gcc_pure + bool operator()(const char *p) const { + return IsContinuation(*p) && CheckSequenceUTF8<L-1>()(p + 1); + } +}; + +template<> +struct CheckSequenceUTF8<0u> { + constexpr bool operator()(gcc_unused const char *p) const { + return true; + } +}; + +template<size_t L> +gcc_pure +static size_t +InnerSequenceLengthUTF8(const char *p) +{ + return CheckSequenceUTF8<L>()(p) + ? L + 1 + : 0u; +} + +size_t +SequenceLengthUTF8(const char *p) +{ + const unsigned char ch = *p++; + + if (IsASCII(ch)) + return 1; + else if (IsLeading1(ch)) + /* 1 continuation */ + return InnerSequenceLengthUTF8<1>(p); + else if (IsLeading2(ch)) + /* 2 continuations */ + return InnerSequenceLengthUTF8<2>(p); + else if (IsLeading3(ch)) + /* 3 continuations */ + return InnerSequenceLengthUTF8<3>(p); + else if (IsLeading4(ch)) + /* 4 continuations */ + return InnerSequenceLengthUTF8<4>(p); + else if (IsLeading5(ch)) + /* 5 continuations */ + return InnerSequenceLengthUTF8<5>(p); + else + /* continuation without a prefix or some other illegal + start byte */ + return 0; +} + +static const char * +FindNonASCIIOrZero(const char *p) +{ + while (*p != 0 && IsASCII(*p)) + ++p; + return p; +} + +const char * +Latin1ToUTF8(const char *gcc_restrict src, char *gcc_restrict buffer, + size_t buffer_size) +{ + const char *p = FindNonASCIIOrZero(src); + if (*p == 0) + /* everything is plain ASCII, we don't need to convert anything */ + return src; + + if ((size_t)(p - src) >= buffer_size) + /* buffer too small */ + return nullptr; + + const char *const end = buffer + buffer_size; + char *q = std::copy(src, p, buffer); + + while (*p != 0) { + unsigned char ch = *p++; + + if (IsASCII(ch)) { + *q++ = ch; + + if (q >= end) + /* buffer too small */ + return nullptr; + } else { + if (q + 2 >= end) + /* buffer too small */ + return nullptr; + + *q++ = MakeLeading1(ch >> 6); + *q++ = MakeContinuation(ch); + } + } + + *q = 0; + return buffer; +} + +char * +UnicodeToUTF8(unsigned ch, char *q) +{ + if (gcc_likely(ch < 0x80)) { + *q++ = (char)ch; + } else if (gcc_likely(ch < 0x800)) { + *q++ = MakeLeading1(ch >> 6); + *q++ = MakeContinuation(ch); + } else if (ch < 0x10000) { + *q++ = MakeLeading2(ch >> 12); + *q++ = MakeContinuation(ch >> 6); + *q++ = MakeContinuation(ch); + } else if (ch < 0x200000) { + *q++ = MakeLeading3(ch >> 18); + *q++ = MakeContinuation(ch >> 12); + *q++ = MakeContinuation(ch >> 6); + *q++ = MakeContinuation(ch); + } else if (ch < 0x4000000) { + *q++ = MakeLeading4(ch >> 24); + *q++ = MakeContinuation(ch >> 18); + *q++ = MakeContinuation(ch >> 12); + *q++ = MakeContinuation(ch >> 6); + *q++ = MakeContinuation(ch); + } else if (ch < 0x80000000) { + *q++ = MakeLeading5(ch >> 30); + *q++ = MakeContinuation(ch >> 24); + *q++ = MakeContinuation(ch >> 18); + *q++ = MakeContinuation(ch >> 12); + *q++ = MakeContinuation(ch >> 6); + *q++ = MakeContinuation(ch); + } else { + // error + } + + return q; +} + +size_t +LengthUTF8(const char *p) +{ + /* this is a very naive implementation: it does not do any + verification, it just counts the bytes that are not a UTF-8 + continuation */ + + size_t n = 0; + for (; *p != 0; ++p) + if (!IsContinuation(*p)) + ++n; + return n; +} diff --git a/src/util/growing_fifo.c b/src/util/UTF8.hxx index 88431f60e..82d324f3e 100644 --- a/src/util/growing_fifo.c +++ b/src/util/UTF8.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2011 The Music Player Daemon Project + * Copyright (C) 2011-2014 Max Kellermann <max@duempel.org> * http://www.musicpd.org * * Redistribution and use in source and binary forms, with or without @@ -28,63 +28,63 @@ * OF THE POSSIBILITY OF SUCH DAMAGE. */ -#include "growing_fifo.h" -#include "fifo_buffer.h" +#ifndef UTF8_HXX +#define UTF8_HXX -#include <assert.h> -#include <string.h> +#include "Compiler.h" + +#include <stddef.h> /** - * Align buffer sizes at 8 kB boundaries. Must be a power of two. + * Is this a valid UTF-8 string? */ -static const size_t GROWING_FIFO_ALIGN = 8192; +gcc_pure gcc_nonnull_all +bool +ValidateUTF8(const char *p); /** - * Align the specified size to the next #GROWING_FIFO_ALIGN boundary. + * @return the number of the sequence beginning with the given + * character, or 0 if the character is not a valid start byte */ -static size_t -align(size_t size) -{ - return ((size - 1) | (GROWING_FIFO_ALIGN - 1)) + 1; -} - -struct fifo_buffer * -growing_fifo_new(void) -{ - return fifo_buffer_new(GROWING_FIFO_ALIGN); -} - -void * -growing_fifo_write(struct fifo_buffer **buffer_p, size_t length) -{ - assert(buffer_p != NULL); - - struct fifo_buffer *buffer = *buffer_p; - assert(buffer != NULL); +gcc_const +size_t +SequenceLengthUTF8(char ch); - size_t max_length; - void *p = fifo_buffer_write(buffer, &max_length); - if (p != NULL && max_length >= length) - return p; +/** + * @return the number of the first sequence in the given string, or 0 + * if the sequence is malformed + */ +gcc_pure +size_t +SequenceLengthUTF8(const char *p); - /* grow */ - size_t new_size = fifo_buffer_available(buffer) + length; - assert(new_size > fifo_buffer_capacity(buffer)); - *buffer_p = buffer = fifo_buffer_realloc(buffer, align(new_size)); +/** + * Convert the specified string from ISO-8859-1 to UTF-8. + * + * @return the UTF-8 version of the source string; may return #src if + * there are no non-ASCII characters; returns nullptr if the destination + * buffer is too small + */ +gcc_pure gcc_nonnull_all +const char * +Latin1ToUTF8(const char *src, char *buffer, size_t buffer_size); - /* try again */ - p = fifo_buffer_write(buffer, &max_length); - assert(p != NULL); - assert(max_length >= length); +/** + * Convert the specified Unicode character to UTF-8 and write it to + * the buffer. buffer must have a length of at least 6! + * + * @return a pointer to the buffer plus the added bytes(s) + */ +gcc_nonnull_all +char * +UnicodeToUTF8(unsigned ch, char *buffer); - return p; -} +/** + * Returns the number of characters in the string. This is different + * from strlen(), which counts the number of bytes. + */ +gcc_pure gcc_nonnull_all +size_t +LengthUTF8(const char *p); -void -growing_fifo_append(struct fifo_buffer **buffer_p, - const void *data, size_t length) -{ - void *p = growing_fifo_write(buffer_p, length); - memcpy(p, data, length); - fifo_buffer_append(*buffer_p, length); -} +#endif diff --git a/src/util/UriUtil.cxx b/src/util/UriUtil.cxx index 6dd5a42e1..54d0ded77 100644 --- a/src/util/UriUtil.cxx +++ b/src/util/UriUtil.cxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify @@ -27,6 +27,16 @@ bool uri_has_scheme(const char *uri) return strstr(uri, "://") != nullptr; } +std::string +uri_get_scheme(const char *uri) +{ + const char *end = strstr(uri, "://"); + if (end == nullptr) + end = uri; + + return std::string(uri, end); +} + /* suffixes should be ascii only characters */ const char * uri_get_suffix(const char *uri) @@ -105,6 +115,8 @@ uri_remove_auth(const char *uri) auth = uri + 7; else if (memcmp(uri, "https://", 8) == 0) auth = uri + 8; + else if (memcmp(uri, "ftp://", 6) == 0) + auth = uri + 6; else /* unrecognized URI */ return std::string(); @@ -145,3 +157,31 @@ uri_is_child_or_same(const char *parent, const char *child) { return strcmp(parent, child) == 0 || uri_is_child(parent, child); } + +std::string +uri_apply_base(const std::string &uri, const std::string &base) +{ + if (uri.front() == '/') { + /* absolute path: replace the whole URI path in base */ + + auto i = base.find("://"); + if (i == base.npos) + /* no scheme: override base completely */ + return uri; + + /* find the first slash after the host part */ + i = base.find('/', i + 3); + if (i == base.npos) + /* there's no URI path - simply append uri */ + i = base.length(); + + return base.substr(0, i) + uri; + } + + std::string out(base); + if (out.back() != '/') + out.push_back('/'); + + out += uri; + return out; +} diff --git a/src/util/UriUtil.hxx b/src/util/UriUtil.hxx index 1c6bce3ff..d478d5b92 100644 --- a/src/util/UriUtil.hxx +++ b/src/util/UriUtil.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2013 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify @@ -31,6 +31,13 @@ gcc_pure bool uri_has_scheme(const char *uri); +/** + * Returns the scheme name of the specified URI, or an empty string. + */ +gcc_pure +std::string +uri_get_scheme(const char *uri); + gcc_pure const char * uri_get_suffix(const char *uri); @@ -81,4 +88,12 @@ gcc_pure gcc_nonnull_all bool uri_is_child_or_same(const char *parent, const char *child); +/** + * Translate the given URI in the context of #base. For example, + * uri_apply_base("foo", "http://bar/a/")=="http://bar/a/foo". + */ +gcc_pure +std::string +uri_apply_base(const std::string &uri, const std::string &base); + #endif diff --git a/src/util/VarSize.hxx b/src/util/VarSize.hxx new file mode 100644 index 000000000..04f1bf580 --- /dev/null +++ b/src/util/VarSize.hxx @@ -0,0 +1,83 @@ +/* + * Copyright (C) 2008-2014 Max Kellermann <max@duempel.org> + * + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``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 + * FOUNDATION OR CONTRIBUTORS 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. + */ + +#ifndef MPD_VAR_SIZE_HXX +#define MPD_VAR_SIZE_HXX + +#include "Alloc.hxx" +#include "Compiler.h" + +#include <type_traits> +#include <utility> +#include <new> + +/** + * Allocate and construct a variable-size object. That is useful for + * example when you want to store a variable-length string as the last + * attribute without the overhead of a second allocation. + * + * @param T a struct/class with a variable-size last attribute + * @param declared_tail_size the declared size of the last element in + * #T + * @param real_tail_size the real required size of the last element in + * #T + */ +template<class T, typename... Args> +gcc_malloc +T * +NewVarSize(size_t declared_tail_size, size_t real_tail_size, Args&&... args) +{ + static_assert(std::is_standard_layout<T>::value, + "Not standard-layout"); + + /* determine the total size of this instance */ + size_t size = sizeof(T) - declared_tail_size + real_tail_size; + + /* allocate memory */ + T *instance = (T *)xalloc(size); + + /* call the constructor */ + new(instance) T(std::forward<Args>(args)...); + + return instance; +} + +template<typename T> +gcc_nonnull_all +void +DeleteVarSize(T *instance) +{ + /* call the destructor */ + instance->T::~T(); + + /* free memory */ + free(instance); +} + +#endif diff --git a/src/util/WritableBuffer.hxx b/src/util/WritableBuffer.hxx index 4e529cfad..f9e6d4a96 100644 --- a/src/util/WritableBuffer.hxx +++ b/src/util/WritableBuffer.hxx @@ -1,5 +1,5 @@ /* - * Copyright (C) 2013 Max Kellermann <max@duempel.org> + * Copyright (C) 2013-2014 Max Kellermann <max@duempel.org> * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -32,7 +32,45 @@ #include "Compiler.h" -#include <stddef.h> +#include <cstddef> + +#ifndef NDEBUG +#include <assert.h> +#endif + +template<typename T> +struct WritableBuffer; + +template<> +struct WritableBuffer<void> { + typedef size_t size_type; + typedef void *pointer_type; + typedef const void *const_pointer_type; + typedef pointer_type iterator; + typedef const_pointer_type const_iterator; + + pointer_type data; + size_type size; + + WritableBuffer() = default; + + constexpr WritableBuffer(std::nullptr_t):data(nullptr), size(0) {} + + constexpr WritableBuffer(pointer_type _data, size_type _size) + :data(_data), size(_size) {} + + constexpr static WritableBuffer Null() { + return { nullptr, 0 }; + } + + constexpr bool IsNull() const { + return data == nullptr; + } + + constexpr bool IsEmpty() const { + return size == 0; + } +}; /** * A reference to a memory area that is writable. @@ -41,47 +79,144 @@ */ template<typename T> struct WritableBuffer { - typedef size_t size_type; - typedef T *pointer_type; - typedef const T *const_pointer_type; - typedef pointer_type iterator; - typedef const_pointer_type const_iterator; + typedef size_t size_type; + typedef T &reference_type; + typedef const T &const_reference_type; + typedef T *pointer_type; + typedef const T *const_pointer_type; + typedef pointer_type iterator; + typedef const_pointer_type const_iterator; - pointer_type data; - size_type size; + pointer_type data; + size_type size; - WritableBuffer() = default; + WritableBuffer() = default; - constexpr WritableBuffer(pointer_type _data, size_type _size) - :data(_data), size(_size) {} + constexpr WritableBuffer(std::nullptr_t):data(nullptr), size(0) {} - constexpr static WritableBuffer Null() { - return { nullptr, 0 }; - } + constexpr WritableBuffer(pointer_type _data, size_type _size) + :data(_data), size(_size) {} + + constexpr static WritableBuffer Null() { + return { nullptr, 0 }; + } + + /** + * Cast a WritableBuffer<void> to a WritableBuffer<T>. A "void" + * buffer records its size in bytes, and when casting to "T", + * the assertion below ensures that the size is a multiple of + * sizeof(T). + */ +#ifdef NDEBUG + constexpr +#endif + static WritableBuffer<T> FromVoid(WritableBuffer<void> other) { + static_assert(sizeof(T) > 0, "Empty base type"); +#ifndef NDEBUG + assert(other.size % sizeof(T) == 0); +#endif + return WritableBuffer<T>(pointer_type(other.data), + other.size / sizeof(T)); + } - constexpr bool IsNull() const { - return data == nullptr; - } + constexpr WritableBuffer<void> ToVoid() const { + static_assert(sizeof(T) > 0, "Empty base type"); + return WritableBuffer<void>(data, size * sizeof(T)); + } + + constexpr bool IsNull() const { + return data == nullptr; + } + + constexpr bool IsEmpty() const { + return size == 0; + } + + constexpr iterator begin() const { + return data; + } + + constexpr iterator end() const { + return data + size; + } + + constexpr const_iterator cbegin() const { + return data; + } + + constexpr const_iterator cend() const { + return data + size; + } + +#ifdef NDEBUG + constexpr +#endif + reference_type operator[](size_type i) const { +#ifndef NDEBUG + assert(i < size); +#endif + + return data[i]; + } + + /** + * Returns a reference to the first element. Buffer must not + * be empty. + */ +#ifdef NDEBUG + constexpr +#endif + reference_type front() const { +#ifndef NDEBUG + assert(!IsEmpty()); +#endif + return data[0]; + } + + /** + * Returns a reference to the last element. Buffer must not + * be empty. + */ +#ifdef NDEBUG + constexpr +#endif + reference_type back() const { +#ifndef NDEBUG + assert(!IsEmpty()); +#endif + return data[size - 1]; + } - constexpr bool IsEmpty() const { - return size == 0; - } + /** + * Remove the first element (by moving the head pointer, does + * not actually modify the buffer). Buffer must not be empty. + */ + void pop_front() { + assert(!IsEmpty()); - constexpr iterator begin() const { - return data; - } + ++data; + --size; + } - constexpr iterator end() const { - return data + size; - } + /** + * Remove the last element (by moving the tail pointer, does + * not actually modify the buffer). Buffer must not be empty. + */ + void pop_back() { + assert(!IsEmpty()); - constexpr const_iterator cbegin() const { - return data; - } + --size; + } - constexpr const_iterator cend() const { - return data + size; - } + /** + * Remove the first element and return a reference to it. + * Buffer must not be empty. + */ + reference_type shift() { + reference_type result = front(); + pop_front(); + return result; + } }; #endif diff --git a/src/util/bit_reverse.c b/src/util/bit_reverse.c index ba8a23ef1..9226c4261 100644 --- a/src/util/bit_reverse.c +++ b/src/util/bit_reverse.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2012 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify diff --git a/src/util/bit_reverse.h b/src/util/bit_reverse.h index a02f01b3f..b39b02e92 100644 --- a/src/util/bit_reverse.h +++ b/src/util/bit_reverse.h @@ -1,5 +1,5 @@ /* - * Copyright (C) 2003-2012 The Music Player Daemon Project + * Copyright (C) 2003-2014 The Music Player Daemon Project * http://www.musicpd.org * * This program is free software; you can redistribute it and/or modify diff --git a/src/util/fifo_buffer.c b/src/util/fifo_buffer.c deleted file mode 100644 index 162ddf946..000000000 --- a/src/util/fifo_buffer.c +++ /dev/null @@ -1,218 +0,0 @@ -/* - * Copyright (C) 2003-2011 The Music Player Daemon Project - * http://www.musicpd.org - * - * 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. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * ``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 - * FOUNDATION OR CONTRIBUTORS 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. - */ - -#include "config.h" -#include "fifo_buffer.h" - -#include <glib.h> - -#include <assert.h> -#include <string.h> - -struct fifo_buffer { - size_t size, start, end; - unsigned char buffer[sizeof(size_t)]; -}; - -struct fifo_buffer * -fifo_buffer_new(size_t size) -{ - struct fifo_buffer *buffer; - - assert(size > 0); - - buffer = (struct fifo_buffer *)g_malloc(sizeof(*buffer) - - sizeof(buffer->buffer) + size); - - buffer->size = size; - buffer->start = 0; - buffer->end = 0; - - return buffer; -} - -void -fifo_buffer_init(struct fifo_buffer *buffer, size_t size) -{ - buffer->size = size - (sizeof(*buffer) - sizeof(buffer->buffer)); - buffer->start = 0; - buffer->end = 0; -} - -static void -fifo_buffer_move(struct fifo_buffer *buffer); - -struct fifo_buffer * -fifo_buffer_realloc(struct fifo_buffer *buffer, size_t new_size) -{ - if (buffer == NULL) - return new_size > 0 - ? fifo_buffer_new(new_size) - : NULL; - - /* existing data must fit in new size */ - assert(new_size >= buffer->end - buffer->start); - - if (new_size == 0) { - fifo_buffer_free(buffer); - return NULL; - } - - /* compress the buffer when we're shrinking and the tail of - the buffer would exceed the new size */ - if (buffer->end > new_size) - fifo_buffer_move(buffer); - - /* existing data must fit in new size: second check */ - assert(buffer->end <= new_size); - - buffer = g_realloc(buffer, sizeof(*buffer) - sizeof(buffer->buffer) + - new_size); - buffer->size = new_size; - return buffer; -} - -void -fifo_buffer_free(struct fifo_buffer *buffer) -{ - assert(buffer != NULL); - - g_free(buffer); -} - -size_t -fifo_buffer_capacity(const struct fifo_buffer *buffer) -{ - assert(buffer != NULL); - - return buffer->size; -} - -size_t -fifo_buffer_available(const struct fifo_buffer *buffer) -{ - assert(buffer != NULL); - - return buffer->end - buffer->start; -} - -void -fifo_buffer_clear(struct fifo_buffer *buffer) -{ - assert(buffer != NULL); - - buffer->start = 0; - buffer->end = 0; -} - -const void * -fifo_buffer_read(const struct fifo_buffer *buffer, size_t *length_r) -{ - assert(buffer != NULL); - assert(buffer->end >= buffer->start); - assert(length_r != NULL); - - if (buffer->start == buffer->end) - /* the buffer is empty */ - return NULL; - - *length_r = buffer->end - buffer->start; - return buffer->buffer + buffer->start; -} - -void -fifo_buffer_consume(struct fifo_buffer *buffer, size_t length) -{ - assert(buffer != NULL); - assert(buffer->end >= buffer->start); - assert(buffer->start + length <= buffer->end); - - buffer->start += length; -} - -/** - * Move data to the beginning of the buffer, to make room at the end. - */ -static void -fifo_buffer_move(struct fifo_buffer *buffer) -{ - if (buffer->start == 0) - return; - - if (buffer->end > buffer->start) - memmove(buffer->buffer, - buffer->buffer + buffer->start, - buffer->end - buffer->start); - - buffer->end -= buffer->start; - buffer->start = 0; -} - -void * -fifo_buffer_write(struct fifo_buffer *buffer, size_t *max_length_r) -{ - assert(buffer != NULL); - assert(buffer->end <= buffer->size); - assert(max_length_r != NULL); - - if (buffer->end == buffer->size) { - fifo_buffer_move(buffer); - if (buffer->end == buffer->size) - return NULL; - } else if (buffer->start > 0 && buffer->start == buffer->end) { - buffer->start = 0; - buffer->end = 0; - } - - *max_length_r = buffer->size - buffer->end; - return buffer->buffer + buffer->end; -} - -void -fifo_buffer_append(struct fifo_buffer *buffer, size_t length) -{ - assert(buffer != NULL); - assert(buffer->end >= buffer->start); - assert(buffer->end + length <= buffer->size); - - buffer->end += length; -} - -bool -fifo_buffer_is_empty(struct fifo_buffer *buffer) -{ - return buffer->start == buffer->end; -} - -bool -fifo_buffer_is_full(struct fifo_buffer *buffer) -{ - return buffer->start == 0 && buffer->end == buffer->size; -} diff --git a/src/util/fifo_buffer.h b/src/util/fifo_buffer.h deleted file mode 100644 index ccea97d86..000000000 --- a/src/util/fifo_buffer.h +++ /dev/null @@ -1,164 +0,0 @@ -/* - * Copyright (C) 2003-2011 The Music Player Daemon Project - * http://www.musicpd.org - * - * 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. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * ``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 - * FOUNDATION OR CONTRIBUTORS 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. - */ - -/** \file - * - * This is a general purpose FIFO buffer library. You may append data - * at the end, while another instance reads data from the beginning. - * It is optimized for zero-copy usage: you get pointers to the real - * buffer, where you may operate on. - * - * This library is not thread safe. - */ - -#ifndef MPD_FIFO_BUFFER_H -#define MPD_FIFO_BUFFER_H - -#include <stdbool.h> -#include <stddef.h> - -struct fifo_buffer; - -#ifdef __cplusplus -extern "C" { -#endif - -/** - * Creates a new #fifo_buffer object. Free this object with - * fifo_buffer_free(). - * - * @param size the size of the buffer in bytes - * @return the new #fifo_buffer object - */ -struct fifo_buffer * -fifo_buffer_new(size_t size); - -void -fifo_buffer_init(struct fifo_buffer *buffer, size_t size); - -/** - * Change the capacity of the #fifo_buffer, while preserving existing - * data. - * - * @param buffer the old buffer, may be NULL - * @param new_size the requested new size of the #fifo_buffer; must - * not be smaller than the data which is stored in the old buffer - * @return the new buffer, may be NULL if the requested new size is 0 - */ -struct fifo_buffer * -fifo_buffer_realloc(struct fifo_buffer *buffer, size_t new_size); - -/** - * Frees the resources consumed by this #fifo_buffer object. - */ -void -fifo_buffer_free(struct fifo_buffer *buffer); - -/** - * Return the capacity of the buffer, i.e. the size that was passed to - * fifo_buffer_new(). - */ -size_t -fifo_buffer_capacity(const struct fifo_buffer *buffer); - -/** - * Return the number of bytes currently stored in the buffer. - */ -size_t -fifo_buffer_available(const struct fifo_buffer *buffer); - -/** - * Clears all data currently in this #fifo_buffer object. This does - * not overwrite the actuall buffer; it just resets the internal - * pointers. - */ -void -fifo_buffer_clear(struct fifo_buffer *buffer); - -/** - * Reads from the beginning of the buffer. To remove consumed data - * from the buffer, call fifo_buffer_consume(). - * - * @param buffer the #fifo_buffer object - * @param length_r the maximum amount to read is returned here - * @return a pointer to the beginning of the buffer, or NULL if the - * buffer is empty - */ -const void * -fifo_buffer_read(const struct fifo_buffer *buffer, size_t *length_r); - -/** - * Marks data at the beginning of the buffer as "consumed". - * - * @param buffer the #fifo_buffer object - * @param length the number of bytes which were consumed - */ -void -fifo_buffer_consume(struct fifo_buffer *buffer, size_t length); - -/** - * Prepares writing to the buffer. This returns a buffer which you - * can write to. To commit the write operation, call - * fifo_buffer_append(). - * - * @param buffer the #fifo_buffer object - * @param max_length_r the maximum amount to write is returned here - * @return a pointer to the end of the buffer, or NULL if the buffer - * is already full - */ -void * -fifo_buffer_write(struct fifo_buffer *buffer, size_t *max_length_r); - -/** - * Commits the write operation initiated by fifo_buffer_write(). - * - * @param buffer the #fifo_buffer object - * @param length the number of bytes which were written - */ -void -fifo_buffer_append(struct fifo_buffer *buffer, size_t length); - -/** - * Checks if the buffer is empty. - */ -bool -fifo_buffer_is_empty(struct fifo_buffer *buffer); - -/** - * Checks if the buffer is full. - */ -bool -fifo_buffer_is_full(struct fifo_buffer *buffer); - -#ifdef __cplusplus -} -#endif - -#endif diff --git a/src/util/list.h b/src/util/list.h deleted file mode 100644 index c07565cb7..000000000 --- a/src/util/list.h +++ /dev/null @@ -1,611 +0,0 @@ -/* - * Copyright (C) 2003-2012 The Music Player Daemon Project - * http://www.musicpd.org - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - */ - -/* - * This code was imported from the Linux kernel. - * - */ - -#ifndef _LINUX_LIST_H -#define _LINUX_LIST_H - -#ifdef __clang__ -/* allow typeof() */ -#pragma GCC diagnostic ignored "-Wlanguage-extension-token" -#endif - -#if defined(__GNUC__) && __GNUC__ >= 5 -#pragma GCC diagnostic ignored "-Winvalid-offsetof" -#endif - -/** - * container_of - cast a member of a structure out to the containing structure - * @ptr: the pointer to the member. - * @type: the type of the container struct this is embedded in. - * @member: the name of the member within the struct. - * - */ -#define container_of(ptr, type, member) \ - ((type *)((uint8_t *)ptr - offsetof(type, member))) - -/* - * These are non-NULL pointers that will result in page faults - * under normal circumstances, used to verify that nobody uses - * non-initialized list entries. - */ -#define LIST_POISON1 ((struct list_head *)(void *) 0x00100100) -#define LIST_POISON2 ((struct list_head *)(void *) 0x00200200) - -/* - * Simple doubly linked list implementation. - * - * Some of the internal functions ("__xxx") are useful when - * manipulating whole lists rather than single entries, as - * sometimes we already know the next/prev entries and we can - * generate better code by using them directly rather than - * using the generic single-entry routines. - */ - -struct list_head { - struct list_head *next, *prev; -}; - -#define LIST_HEAD_INIT(name) { &(name), &(name) } - -#define LIST_HEAD(name) \ - struct list_head name = LIST_HEAD_INIT(name) - -static inline void INIT_LIST_HEAD(struct list_head *list) -{ - list->next = list; - list->prev = list; -} - -/* - * Insert a new entry between two known consecutive entries. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -#ifndef CONFIG_DEBUG_LIST -static inline void __list_add(struct list_head *new_item, - struct list_head *prev, - struct list_head *next) -{ - next->prev = new_item; - new_item->next = next; - new_item->prev = prev; - prev->next = new_item; -} -#else -extern void __list_add(struct list_head *new_item, - struct list_head *prev, - struct list_head *next); -#endif - -/** - * list_add - add a new entry - * @new_item: new entry to be added - * @head: list head to add it after - * - * Insert a new entry after the specified head. - * This is good for implementing stacks. - */ -static inline void list_add(struct list_head *new_item, struct list_head *head) -{ - __list_add(new_item, head, head->next); -} - - -/** - * list_add_tail - add a new entry - * @new_item: new entry to be added - * @head: list head to add it before - * - * Insert a new entry before the specified head. - * This is useful for implementing queues. - */ -static inline void -list_add_tail(struct list_head *new_item, struct list_head *head) -{ - __list_add(new_item, head->prev, head); -} - -/* - * Delete a list entry by making the prev/next entries - * point to each other. - * - * This is only for internal list manipulation where we know - * the prev/next entries already! - */ -static inline void __list_del(struct list_head * prev, struct list_head * next) -{ - next->prev = prev; - prev->next = next; -} - -/** - * list_del - deletes entry from list. - * @entry: the element to delete from the list. - * Note: list_empty() on entry does not return true after this, the entry is - * in an undefined state. - */ -#ifndef CONFIG_DEBUG_LIST -static inline void __list_del_entry(struct list_head *entry) -{ - __list_del(entry->prev, entry->next); -} - -static inline void list_del(struct list_head *entry) -{ - __list_del(entry->prev, entry->next); - entry->next = LIST_POISON1; - entry->prev = LIST_POISON2; -} -#else -extern void __list_del_entry(struct list_head *entry); -extern void list_del(struct list_head *entry); -#endif - -/** - * list_replace - replace old entry by new one - * @old : the element to be replaced - * @new_item : the new element to insert - * - * If @old was empty, it will be overwritten. - */ -static inline void list_replace(struct list_head *old, - struct list_head *new_item) -{ - new_item->next = old->next; - new_item->next->prev = new_item; - new_item->prev = old->prev; - new_item->prev->next = new_item; -} - -static inline void list_replace_init(struct list_head *old, - struct list_head *new_item) -{ - list_replace(old, new_item); - INIT_LIST_HEAD(old); -} - -/** - * list_del_init - deletes entry from list and reinitialize it. - * @entry: the element to delete from the list. - */ -static inline void list_del_init(struct list_head *entry) -{ - __list_del_entry(entry); - INIT_LIST_HEAD(entry); -} - -/** - * list_move - delete from one list and add as another's head - * @list: the entry to move - * @head: the head that will precede our entry - */ -static inline void list_move(struct list_head *list, struct list_head *head) -{ - __list_del_entry(list); - list_add(list, head); -} - -/** - * list_move_tail - delete from one list and add as another's tail - * @list: the entry to move - * @head: the head that will follow our entry - */ -static inline void list_move_tail(struct list_head *list, - struct list_head *head) -{ - __list_del_entry(list); - list_add_tail(list, head); -} - -/** - * list_is_last - tests whether @list is the last entry in list @head - * @list: the entry to test - * @head: the head of the list - */ -static inline int list_is_last(const struct list_head *list, - const struct list_head *head) -{ - return list->next == head; -} - -/** - * list_empty - tests whether a list is empty - * @head: the list to test. - */ -static inline int list_empty(const struct list_head *head) -{ - return head->next == head; -} - -/** - * list_empty_careful - tests whether a list is empty and not being modified - * @head: the list to test - * - * Description: - * tests whether a list is empty _and_ checks that no other CPU might be - * in the process of modifying either member (next or prev) - * - * NOTE: using list_empty_careful() without synchronization - * can only be safe if the only activity that can happen - * to the list entry is list_del_init(). Eg. it cannot be used - * if another CPU could re-list_add() it. - */ -static inline int list_empty_careful(const struct list_head *head) -{ - struct list_head *next = head->next; - return (next == head) && (next == head->prev); -} - -/** - * list_rotate_left - rotate the list to the left - * @head: the head of the list - */ -static inline void list_rotate_left(struct list_head *head) -{ - struct list_head *first; - - if (!list_empty(head)) { - first = head->next; - list_move_tail(first, head); - } -} - -/** - * list_is_singular - tests whether a list has just one entry. - * @head: the list to test. - */ -static inline int list_is_singular(const struct list_head *head) -{ - return !list_empty(head) && (head->next == head->prev); -} - -static inline void __list_cut_position(struct list_head *list, - struct list_head *head, struct list_head *entry) -{ - struct list_head *new_first = entry->next; - list->next = head->next; - list->next->prev = list; - list->prev = entry; - entry->next = list; - head->next = new_first; - new_first->prev = head; -} - -/** - * list_cut_position - cut a list into two - * @list: a new list to add all removed entries - * @head: a list with entries - * @entry: an entry within head, could be the head itself - * and if so we won't cut the list - * - * This helper moves the initial part of @head, up to and - * including @entry, from @head to @list. You should - * pass on @entry an element you know is on @head. @list - * should be an empty list or a list you do not care about - * losing its data. - * - */ -static inline void list_cut_position(struct list_head *list, - struct list_head *head, struct list_head *entry) -{ - if (list_empty(head)) - return; - if (list_is_singular(head) && - (head->next != entry && head != entry)) - return; - if (entry == head) - INIT_LIST_HEAD(list); - else - __list_cut_position(list, head, entry); -} - -static inline void __list_splice(const struct list_head *list, - struct list_head *prev, - struct list_head *next) -{ - struct list_head *first = list->next; - struct list_head *last = list->prev; - - first->prev = prev; - prev->next = first; - - last->next = next; - next->prev = last; -} - -/** - * list_splice - join two lists, this is designed for stacks - * @list: the new list to add. - * @head: the place to add it in the first list. - */ -static inline void list_splice(const struct list_head *list, - struct list_head *head) -{ - if (!list_empty(list)) - __list_splice(list, head, head->next); -} - -/** - * list_splice_tail - join two lists, each list being a queue - * @list: the new list to add. - * @head: the place to add it in the first list. - */ -static inline void list_splice_tail(struct list_head *list, - struct list_head *head) -{ - if (!list_empty(list)) - __list_splice(list, head->prev, head); -} - -/** - * list_splice_init - join two lists and reinitialise the emptied list. - * @list: the new list to add. - * @head: the place to add it in the first list. - * - * The list at @list is reinitialised - */ -static inline void list_splice_init(struct list_head *list, - struct list_head *head) -{ - if (!list_empty(list)) { - __list_splice(list, head, head->next); - INIT_LIST_HEAD(list); - } -} - -/** - * list_splice_tail_init - join two lists and reinitialise the emptied list - * @list: the new list to add. - * @head: the place to add it in the first list. - * - * Each of the lists is a queue. - * The list at @list is reinitialised - */ -static inline void list_splice_tail_init(struct list_head *list, - struct list_head *head) -{ - if (!list_empty(list)) { - __list_splice(list, head->prev, head); - INIT_LIST_HEAD(list); - } -} - -/** - * list_entry - get the struct for this entry - * @ptr: the &struct list_head pointer. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_struct within the struct. - */ -#define list_entry(ptr, type, member) \ - container_of(ptr, type, member) - -/** - * list_first_entry - get the first element from a list - * @ptr: the list head to take the element from. - * @type: the type of the struct this is embedded in. - * @member: the name of the list_struct within the struct. - * - * Note, that list is expected to be not empty. - */ -#define list_first_entry(ptr, type, member) \ - list_entry((ptr)->next, type, member) - -/** - * list_for_each - iterate over a list - * @pos: the &struct list_head to use as a loop cursor. - * @head: the head for your list. - */ -#define list_for_each(pos, head) \ - for (pos = (head)->next; pos != (head); pos = pos->next) - -/** - * __list_for_each - iterate over a list - * @pos: the &struct list_head to use as a loop cursor. - * @head: the head for your list. - * - * This variant doesn't differ from list_for_each() any more. - * We don't do prefetching in either case. - */ -#define __list_for_each(pos, head) \ - for (pos = (head)->next; pos != (head); pos = pos->next) - -/** - * list_for_each_prev - iterate over a list backwards - * @pos: the &struct list_head to use as a loop cursor. - * @head: the head for your list. - */ -#define list_for_each_prev(pos, head) \ - for (pos = (head)->prev; pos != (head); pos = pos->prev) - -/** - * list_for_each_safe - iterate over a list safe against removal of list entry - * @pos: the &struct list_head to use as a loop cursor. - * @n: another &struct list_head to use as temporary storage - * @head: the head for your list. - */ -#define list_for_each_safe(pos, n, head) \ - for (pos = (head)->next, n = pos->next; pos != (head); \ - pos = n, n = pos->next) - -/** - * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry - * @pos: the &struct list_head to use as a loop cursor. - * @n: another &struct list_head to use as temporary storage - * @head: the head for your list. - */ -#define list_for_each_prev_safe(pos, n, head) \ - for (pos = (head)->prev, n = pos->prev; \ - pos != (head); \ - pos = n, n = pos->prev) - -/** - * list_for_each_entry - iterate over list of given type - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry(pos, head, member) \ - for (pos = list_entry((head)->next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = list_entry(pos->member.next, typeof(*pos), member)) - -/** - * list_for_each_entry_reverse - iterate backwards over list of given type. - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry_reverse(pos, head, member) \ - for (pos = list_entry((head)->prev, typeof(*pos), member); \ - &pos->member != (head); \ - pos = list_entry(pos->member.prev, typeof(*pos), member)) - -/** - * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue() - * @pos: the type * to use as a start point - * @head: the head of the list - * @member: the name of the list_struct within the struct. - * - * Prepares a pos entry for use as a start point in list_for_each_entry_continue(). - */ -#define list_prepare_entry(pos, head, member) \ - ((pos) ? : list_entry(head, typeof(*pos), member)) - -/** - * list_for_each_entry_continue - continue iteration over list of given type - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Continue to iterate over list of given type, continuing after - * the current position. - */ -#define list_for_each_entry_continue(pos, head, member) \ - for (pos = list_entry(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = list_entry(pos->member.next, typeof(*pos), member)) - -/** - * list_for_each_entry_continue_reverse - iterate backwards from the given point - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Start to iterate over list of given type backwards, continuing after - * the current position. - */ -#define list_for_each_entry_continue_reverse(pos, head, member) \ - for (pos = list_entry(pos->member.prev, typeof(*pos), member); \ - &pos->member != (head); \ - pos = list_entry(pos->member.prev, typeof(*pos), member)) - -/** - * list_for_each_entry_from - iterate over list of given type from the current point - * @pos: the type * to use as a loop cursor. - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Iterate over list of given type, continuing from current position. - */ -#define list_for_each_entry_from(pos, head, member) \ - for (; &pos->member != (head); \ - pos = list_entry(pos->member.next, typeof(*pos), member)) - -/** - * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry - * @pos: the type * to use as a loop cursor. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - */ -#define list_for_each_entry_safe(pos, n, head, member) \ - for (pos = list_entry((head)->next, typeof(*pos), member), \ - n = list_entry(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.next, typeof(*n), member)) - -/** - * list_for_each_entry_safe_continue - continue list iteration safe against removal - * @pos: the type * to use as a loop cursor. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Iterate over list of given type, continuing after current point, - * safe against removal of list entry. - */ -#define list_for_each_entry_safe_continue(pos, n, head, member) \ - for (pos = list_entry(pos->member.next, typeof(*pos), member), \ - n = list_entry(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.next, typeof(*n), member)) - -/** - * list_for_each_entry_safe_from - iterate over list from current point safe against removal - * @pos: the type * to use as a loop cursor. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Iterate over list of given type from current point, safe against - * removal of list entry. - */ -#define list_for_each_entry_safe_from(pos, n, head, member) \ - for (n = list_entry(pos->member.next, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.next, typeof(*n), member)) - -/** - * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal - * @pos: the type * to use as a loop cursor. - * @n: another type * to use as temporary storage - * @head: the head for your list. - * @member: the name of the list_struct within the struct. - * - * Iterate backwards over list of given type, safe against removal - * of list entry. - */ -#define list_for_each_entry_safe_reverse(pos, n, head, member) \ - for (pos = list_entry((head)->prev, typeof(*pos), member), \ - n = list_entry(pos->member.prev, typeof(*pos), member); \ - &pos->member != (head); \ - pos = n, n = list_entry(n->member.prev, typeof(*n), member)) - -/** - * list_safe_reset_next - reset a stale list_for_each_entry_safe loop - * @pos: the loop cursor used in the list_for_each_entry_safe loop - * @n: temporary storage used in list_for_each_entry_safe - * @member: the name of the list_struct within the struct. - * - * list_safe_reset_next is not safe to use in general if the list may be - * modified concurrently (eg. the lock is dropped in the loop body). An - * exception to this is if the cursor element (pos) is pinned in the list, - * and list_safe_reset_next is called after re-taking the lock and before - * completing the current iteration of the loop body. - */ -#define list_safe_reset_next(pos, n, member) \ - n = list_entry(pos->member.next, typeof(*pos), member) - -#endif diff --git a/src/util/list_sort.c b/src/util/list_sort.c deleted file mode 100644 index 8534f3360..000000000 --- a/src/util/list_sort.c +++ /dev/null @@ -1,162 +0,0 @@ -/* - * Copyright (C) 2003-2012 The Music Player Daemon Project - * http://www.musicpd.org - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License along - * with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - */ - -/* - * This code was imported from the Linux kernel. - * - */ - -#include "list_sort.h" -#include "list.h" -#include "Macros.hxx" -#include "Compiler.h" - -#include <string.h> - -#define unlikely gcc_unlikely - -#define MAX_LIST_LENGTH_BITS 20 - -/* - * Returns a list organized in an intermediate format suited - * to chaining of merge() calls: null-terminated, no reserved or - * sentinel head node, "prev" links not maintained. - */ -static struct list_head *merge(void *priv, - int (*cmp)(void *priv, struct list_head *a, - struct list_head *b), - struct list_head *a, struct list_head *b) -{ - struct list_head head, *tail = &head; - - while (a && b) { - /* if equal, take 'a' -- important for sort stability */ - if ((*cmp)(priv, a, b) <= 0) { - tail->next = a; - a = a->next; - } else { - tail->next = b; - b = b->next; - } - tail = tail->next; - } - tail->next = a?a:b; - return head.next; -} - -/* - * Combine final list merge with restoration of standard doubly-linked - * list structure. This approach duplicates code from merge(), but - * runs faster than the tidier alternatives of either a separate final - * prev-link restoration pass, or maintaining the prev links - * throughout. - */ -static void merge_and_restore_back_links(void *priv, - int (*cmp)(void *priv, struct list_head *a, - struct list_head *b), - struct list_head *head, - struct list_head *a, struct list_head *b) -{ - struct list_head *tail = head; - - while (a && b) { - /* if equal, take 'a' -- important for sort stability */ - if ((*cmp)(priv, a, b) <= 0) { - tail->next = a; - a->prev = tail; - a = a->next; - } else { - tail->next = b; - b->prev = tail; - b = b->next; - } - tail = tail->next; - } - tail->next = a ? a : b; - - do { - /* - * In worst cases this loop may run many iterations. - * Continue callbacks to the client even though no - * element comparison is needed, so the client's cmp() - * routine can invoke cond_resched() periodically. - */ - (*cmp)(priv, tail->next, tail->next); - - tail->next->prev = tail; - tail = tail->next; - } while (tail->next); - - tail->next = head; - head->prev = tail; -} - -/** - * list_sort - sort a list - * @priv: private data, opaque to list_sort(), passed to @cmp - * @head: the list to sort - * @cmp: the elements comparison function - * - * This function implements "merge sort", which has O(nlog(n)) - * complexity. - * - * The comparison function @cmp must return a negative value if @a - * should sort before @b, and a positive value if @a should sort after - * @b. If @a and @b are equivalent, and their original relative - * ordering is to be preserved, @cmp must return 0. - */ -void list_sort(void *priv, struct list_head *head, - int (*cmp)(void *priv, struct list_head *a, - struct list_head *b)) -{ - struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists - -- last slot is a sentinel */ - int lev; /* index into part[] */ - int max_lev = 0; - struct list_head *list; - - if (list_empty(head)) - return; - - memset(part, 0, sizeof(part)); - - head->prev->next = NULL; - list = head->next; - - while (list) { - struct list_head *cur = list; - list = list->next; - cur->next = NULL; - - for (lev = 0; part[lev]; lev++) { - cur = merge(priv, cmp, part[lev], cur); - part[lev] = NULL; - } - if (lev > max_lev) { - max_lev = lev; - } - part[lev] = cur; - } - - for (lev = 0; lev < max_lev; lev++) - if (part[lev]) - list = merge(priv, cmp, part[lev], list); - - merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); -} |