diff options
Diffstat (limited to 'src/system_wrappers/source')
48 files changed, 8433 insertions, 0 deletions
diff --git a/src/system_wrappers/source/Android.mk b/src/system_wrappers/source/Android.mk new file mode 100644 index 0000000000..f8e406f995 --- /dev/null +++ b/src/system_wrappers/source/Android.mk @@ -0,0 +1,67 @@ +# This file is generated by gyp; do not edit. This means you! + +LOCAL_PATH := $(call my-dir) + +include $(CLEAR_VARS) + +LOCAL_ARM_MODE := arm +LOCAL_MODULE := libwebrtc_system_wrappers +LOCAL_MODULE_TAGS := optional +LOCAL_CPP_EXTENSION := .cc +LOCAL_GENERATED_SOURCES := +LOCAL_SRC_FILES := \ + map.cc \ + rw_lock_generic.cc \ + sort.cc \ + aligned_malloc.cc \ + atomic32.cc \ + condition_variable.cc \ + cpu.cc \ + cpu_features.cc \ + critical_section.cc \ + event.cc \ + file_impl.cc \ + list_no_stl.cc \ + rw_lock.cc \ + thread.cc \ + trace_impl.cc \ + condition_variable_linux.cc \ + cpu_linux.cc \ + critical_section_linux.cc \ + event_linux.cc \ + thread_linux.cc \ + trace_linux.cc \ + rw_lock_linux.cc + +# Flags passed to both C and C++ files. +MY_CFLAGS := +MY_CFLAGS_C := +MY_DEFS := '-DNO_TCMALLOC' \ + '-DNO_HEAPCHECKER' \ + '-DWEBRTC_TARGET_PC' \ + '-DWEBRTC_LINUX' \ + '-DWEBRTC_CLOCK_TYPE_REALTIME' \ + '-DWEBRTC_THREAD_RR' \ + '-DWEBRTC_ANDROID' \ + '-DANDROID' +LOCAL_CFLAGS := $(MY_CFLAGS_C) $(MY_CFLAGS) $(MY_DEFS) + +# Include paths placed before CFLAGS/CPPFLAGS +LOCAL_C_INCLUDES := $(LOCAL_PATH)/../.. \ + $(LOCAL_PATH)/spreadsortlib \ + $(LOCAL_PATH)/../interface + +# Flags passed to only C++ (and not C) files. +LOCAL_CPPFLAGS := + +LOCAL_LDFLAGS := + +LOCAL_STATIC_LIBRARIES := + +LOCAL_SHARED_LIBRARIES := libcutils \ + libdl \ + libstlport +LOCAL_ADDITIONAL_DEPENDENCIES := + +include external/stlport/libstlport.mk +include $(BUILD_STATIC_LIBRARY) diff --git a/src/system_wrappers/source/aligned_malloc.cc b/src/system_wrappers/source/aligned_malloc.cc new file mode 100644 index 0000000000..62257533e3 --- /dev/null +++ b/src/system_wrappers/source/aligned_malloc.cc @@ -0,0 +1,121 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "aligned_malloc.h" + +#include <assert.h> +#include <memory.h> + +#ifdef ANDROID +#include <stdlib.h> +#endif + +#if WEBRTC_MAC + #include <malloc/malloc.h> +#else + #include <malloc.h> +#endif + +#if _WIN32 + #include <windows.h> +#else + #include <stdint.h> +#endif + +#include "typedefs.h" + +// Ok reference on memory alignment: +// http://stackoverflow.com/questions/227897/solve-the-memory-alignment-in-c-interview-question-that-stumped-me + +namespace webrtc +{ +// TODO (hellner) better to create just one memory block and +// interpret the first sizeof(AlignedMemory) bytes as +// an AlignedMemory struct. +struct AlignedMemory +{ + void* alignedBuffer; + void* memoryPointer; +}; + +void* AlignedMalloc(size_t size, size_t alignment) +{ + if(alignment == 0) + { + // Don't allow alignment 0 since it's undefined. + return NULL; + } + // Make sure that the alignment is an integer power of two or fail. + if(alignment & (alignment - 1)) + { + return NULL; + } + + AlignedMemory* returnValue = new AlignedMemory(); + if(returnValue == NULL) + { + return NULL; + } + + // The memory is aligned towards the lowest address that so only + // alignment - 1 bytes needs to be allocated. + // A pointer to AlignedMemory must be stored so that it can be retreived for + // deletion, ergo the sizeof(uintptr_t). + returnValue->memoryPointer = malloc(size + sizeof(uintptr_t) + + alignment - 1); + if(returnValue->memoryPointer == NULL) + { + delete returnValue; + return NULL; + } + + // Alligning after the sizeof(header) bytes will leave room for the header + // in the same memory block. + uintptr_t alignStartPos = (uintptr_t)returnValue->memoryPointer; + alignStartPos += sizeof(uintptr_t); + + // The buffer should be aligned with 'alignment' bytes. The - 1 guarantees + // that we align towards the lowest address. + uintptr_t alignedPos = (alignStartPos + alignment - 1) & ~(alignment - 1); + + // alignedPos is the address sought for. + returnValue->alignedBuffer = (void*)alignedPos; + + // Store the address to the AlignedMemory struct in the header so that a + // it's possible to reclaim all memory. + uintptr_t headerPos = alignedPos; + headerPos -= sizeof(uintptr_t); + void* headerPtr = (void*) headerPos; + uintptr_t headerValue = (uintptr_t)returnValue; + memcpy(headerPtr,&headerValue,sizeof(uintptr_t)); + + return returnValue->alignedBuffer; +} + +void AlignedFree(void* memBlock) +{ + if(memBlock == NULL) + { + return; + } + uintptr_t alignedPos = (uintptr_t)memBlock; + uintptr_t headerPos = alignedPos - sizeof(uintptr_t); + + // Read out the address of the AlignedMemory struct from the header. + uintptr_t* headerPtr = (uintptr_t*)headerPos; + AlignedMemory* deleteMemory = (AlignedMemory*) *headerPtr; + + if(deleteMemory->memoryPointer != NULL) + { + free(deleteMemory->memoryPointer); + } + delete deleteMemory; +} +} // namespace webrtc diff --git a/src/system_wrappers/source/atomic32.cc b/src/system_wrappers/source/atomic32.cc new file mode 100644 index 0000000000..3d6849ef25 --- /dev/null +++ b/src/system_wrappers/source/atomic32.cc @@ -0,0 +1,84 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "atomic32_wrapper.h" + +#if defined(_WIN32) + #include "atomic32_windows.h" +#elif defined(WEBRTC_LINUX) + #include "atomic32_linux.h" +#elif defined(WEBRTC_MAC) + #include "atomic32_mac.h" +#else + #error unsupported os! +#endif + +namespace webrtc { +Atomic32Wrapper::Atomic32Wrapper(WebRtc_Word32 initialValue) + : _impl(*new Atomic32Impl(initialValue)) +{ +} + +Atomic32Wrapper::~Atomic32Wrapper() +{ + delete &_impl; +} + +WebRtc_Word32 Atomic32Wrapper::operator++() +{ + return ++_impl; +} + +WebRtc_Word32 Atomic32Wrapper::operator--() +{ + return --_impl; +} + +// Read and write to properly aligned variables are atomic operations. +// Ex reference (for Windows): http://msdn.microsoft.com/en-us/library/ms684122(v=VS.85).aspx +// TODO (hellner) operator= and Atomic32Wrapper::Value() can be fully +// implemented here. +Atomic32Wrapper& Atomic32Wrapper::operator=(const Atomic32Wrapper& rhs) +{ + if(this == &rhs) + { + return *this; + } + _impl = rhs._impl; + return *this; +} + +Atomic32Wrapper& Atomic32Wrapper::operator=(WebRtc_Word32 rhs) +{ + _impl = rhs; + return *this; +} + +WebRtc_Word32 Atomic32Wrapper::operator+=(WebRtc_Word32 rhs) +{ + return _impl += rhs; +} + +WebRtc_Word32 Atomic32Wrapper::operator-=(WebRtc_Word32 rhs) +{ + return _impl -= rhs; +} + +bool Atomic32Wrapper::CompareExchange(WebRtc_Word32 newValue, + WebRtc_Word32 compareValue) +{ + return _impl.CompareExchange(newValue,compareValue); +} + +WebRtc_Word32 Atomic32Wrapper::Value() const +{ + return _impl.Value(); +} +} // namespace webrtc diff --git a/src/system_wrappers/source/atomic32_linux.h b/src/system_wrappers/source/atomic32_linux.h new file mode 100644 index 0000000000..f9f5650f2a --- /dev/null +++ b/src/system_wrappers/source/atomic32_linux.h @@ -0,0 +1,119 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// Atomic system independant 32-bit signed integer. +// Linux implementation. +// Note: Requires gcc 4.1.2 or later. +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_ATOMIC32_LINUX_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_ATOMIC32_LINUX_H_ + +#include <inttypes.h> +#include <malloc.h> + +#include "common_types.h" + +namespace webrtc { +class Atomic32Impl +{ +public: + inline Atomic32Impl(WebRtc_Word32 initialValue); + inline ~Atomic32Impl(); + + inline WebRtc_Word32 operator++(); + inline WebRtc_Word32 operator--(); + + inline Atomic32Impl& operator=(const Atomic32Impl& rhs); + inline Atomic32Impl& operator=(WebRtc_Word32 rhs); + inline WebRtc_Word32 operator+=(WebRtc_Word32 rhs); + inline WebRtc_Word32 operator-=(WebRtc_Word32 rhs); + + inline bool CompareExchange(WebRtc_Word32 newValue, + WebRtc_Word32 compareValue); + + inline WebRtc_Word32 Value() const; +private: + void* _ptrMemory; + // Volatile ensures full memory barriers. + volatile WebRtc_Word32* _value; +}; + +// TODO (hellner) use aligned_malloc instead of doing it manually. +inline Atomic32Impl::Atomic32Impl(WebRtc_Word32 initialValue) + : _ptrMemory(NULL), + _value(NULL) +{ // Align the memory associated with _value on a 32-bit boundary. This is a + // requirement for the used Linux APIs to be atomic. + // Keep _ptrMemory to be able to reclaim memory. + _ptrMemory = malloc(sizeof(WebRtc_Word32)*2); + _value = (WebRtc_Word32*) (((uintptr_t)_ptrMemory+3)&(~0x3)); + *_value = initialValue; +} + +inline Atomic32Impl::~Atomic32Impl() +{ + if(_ptrMemory != NULL) + { + free(_ptrMemory); + } +} + +inline WebRtc_Word32 Atomic32Impl::operator++() +{ + WebRtc_Word32 returnValue = __sync_fetch_and_add(_value,1); + returnValue++; + return returnValue; +} + +inline WebRtc_Word32 Atomic32Impl::operator--() +{ + WebRtc_Word32 returnValue = __sync_fetch_and_sub(_value,1); + returnValue--; + return returnValue; +} + +inline Atomic32Impl& Atomic32Impl::operator=(const Atomic32Impl& rhs) +{ + *_value = *rhs._value; + return *this; +} + +inline Atomic32Impl& Atomic32Impl::operator=(WebRtc_Word32 rhs) +{ + *_value = rhs; + return *this; +} + +inline WebRtc_Word32 Atomic32Impl::operator+=(WebRtc_Word32 rhs) +{ + WebRtc_Word32 returnValue = __sync_fetch_and_add(_value,rhs); + returnValue += rhs; + return returnValue; +} + +inline WebRtc_Word32 Atomic32Impl::operator-=(WebRtc_Word32 rhs) +{ + WebRtc_Word32 returnValue = __sync_fetch_and_sub(_value,rhs); + returnValue -= rhs; + return returnValue; +} + +inline bool Atomic32Impl::CompareExchange(WebRtc_Word32 newValue, + WebRtc_Word32 compareValue) +{ + return __sync_bool_compare_and_swap(_value,compareValue,newValue); +} + +inline WebRtc_Word32 Atomic32Impl::Value() const +{ + return *_value; +} +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_ATOMIC32_LINUX_H_ diff --git a/src/system_wrappers/source/atomic32_mac.h b/src/system_wrappers/source/atomic32_mac.h new file mode 100644 index 0000000000..bf8febcdb5 --- /dev/null +++ b/src/system_wrappers/source/atomic32_mac.h @@ -0,0 +1,117 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// Atomic system independant 32-bit signed integer. +// Mac implementation. +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_ATOMIC32_MAC_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_ATOMIC32_MAC_H_ + +#include <stdlib.h> +#include <libkern/OSAtomic.h> + +#include "common_types.h" + +namespace webrtc { +class Atomic32Impl +{ +public: + inline Atomic32Impl(WebRtc_Word32 initialValue); + inline ~Atomic32Impl(); + + inline WebRtc_Word32 operator++(); + inline WebRtc_Word32 operator--(); + + inline Atomic32Impl& operator=(const Atomic32Impl& rhs); + inline Atomic32Impl& operator=(WebRtc_Word32 rhs); + inline WebRtc_Word32 operator+=(WebRtc_Word32 rhs); + inline WebRtc_Word32 operator-=(WebRtc_Word32 rhs); + + inline bool CompareExchange(WebRtc_Word32 newValue, + WebRtc_Word32 compareValue); + + inline WebRtc_Word32 Value() const; +private: + void* _ptrMemory; + // Volatile ensures full memory barriers. + volatile WebRtc_Word32* _value; +}; + +// TODO (hellner) use aligned_malloc instead of doing it manually. +inline Atomic32Impl::Atomic32Impl(WebRtc_Word32 initialValue) + : + _ptrMemory(NULL), + _value(NULL) +{ // Align the memory associated with _value on a 32-bit boundary. This is a + // requirement for the used Mac APIs to be atomic. + // Keep _ptrMemory to be able to reclaim memory. + _ptrMemory = malloc(sizeof(WebRtc_Word32)*2); + _value = (WebRtc_Word32*) (((uintptr_t)_ptrMemory+3)&(~0x3)); + *_value = initialValue; +} + +inline Atomic32Impl::~Atomic32Impl() +{ + if(_ptrMemory != NULL) + { + free(_ptrMemory); + } +} + +inline WebRtc_Word32 Atomic32Impl::operator++() +{ + return OSAtomicIncrement32Barrier( + reinterpret_cast<volatile int32_t*>(_value)); +} + +inline WebRtc_Word32 Atomic32Impl::operator--() +{ + return OSAtomicDecrement32Barrier( + reinterpret_cast<volatile int32_t*>(_value)); +} + +inline Atomic32Impl& Atomic32Impl::operator=(const Atomic32Impl& rhs) +{ + *_value = *rhs._value; + return *this; +} + +inline Atomic32Impl& Atomic32Impl::operator=(WebRtc_Word32 rhs) +{ + *_value = rhs; + return *this; +} + +inline WebRtc_Word32 Atomic32Impl::operator+=(WebRtc_Word32 rhs) +{ + return OSAtomicAdd32Barrier(rhs, + reinterpret_cast<volatile int32_t*>(_value)); +} + +inline WebRtc_Word32 Atomic32Impl::operator-=(WebRtc_Word32 rhs) +{ + return OSAtomicAdd32Barrier(-rhs, + reinterpret_cast<volatile int32_t*>(_value)); +} + +inline bool Atomic32Impl::CompareExchange(WebRtc_Word32 newValue, + WebRtc_Word32 compareValue) +{ + return OSAtomicCompareAndSwap32Barrier( + compareValue, + newValue, + reinterpret_cast<volatile int32_t*>(_value)); +} + +inline WebRtc_Word32 Atomic32Impl::Value() const +{ + return *_value; +} +} // namespace webrtc +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_ATOMIC32_MAC_H_ diff --git a/src/system_wrappers/source/condition_variable.cc b/src/system_wrappers/source/condition_variable.cc new file mode 100644 index 0000000000..7ca1b567e2 --- /dev/null +++ b/src/system_wrappers/source/condition_variable.cc @@ -0,0 +1,37 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#if defined(_WIN32) + #include <windows.h> + #include "condition_variable_wrapper.h" + #include "condition_variable_windows.h" +#elif defined(WEBRTC_LINUX) + #include <pthread.h> + #include "condition_variable_wrapper.h" + #include "condition_variable_linux.h" +#elif defined(WEBRTC_MAC) || defined(WEBRTC_MAC_INTEL) + #include <pthread.h> + #include "condition_variable_wrapper.h" + #include "condition_variable_linux.h" + #endif + +namespace webrtc { +ConditionVariableWrapper* +ConditionVariableWrapper::CreateConditionVariable() +{ +#if defined(_WIN32) + return new ConditionVariableWindows; +#elif defined(WEBRTC_LINUX) || defined(WEBRTC_MAC) || defined(WEBRTC_MAC_INTEL) + return ConditionVariableLinux::Create(); +#else + return NULL; +#endif +} +} // namespace webrtc diff --git a/src/system_wrappers/source/condition_variable_linux.cc b/src/system_wrappers/source/condition_variable_linux.cc new file mode 100644 index 0000000000..778c2cf715 --- /dev/null +++ b/src/system_wrappers/source/condition_variable_linux.cc @@ -0,0 +1,151 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "condition_variable_linux.h" + +#if defined(WEBRTC_LINUX) +#include <ctime> +#else +#include <sys/time.h> +#endif + +#include <errno.h> + +#include "critical_section_linux.h" + +namespace webrtc { +ConditionVariableWrapper* ConditionVariableLinux::Create() +{ + ConditionVariableLinux* ptr = new ConditionVariableLinux; + if (!ptr) + { + return NULL; + } + + const int error = ptr->Construct(); + if (error) + { + delete ptr; + return NULL; + } + + return ptr; +} + +ConditionVariableLinux::ConditionVariableLinux() +{ +} + +int ConditionVariableLinux::Construct() +{ + int result = 0; +#ifdef WEBRTC_CLOCK_TYPE_REALTIME + result = pthread_cond_init(&_cond, NULL); +#else + pthread_condattr_t condAttr; + result = pthread_condattr_init(&condAttr); + if (result != 0) + { + return -1; + } + result = pthread_condattr_setclock(&condAttr, CLOCK_MONOTONIC); + if (result != 0) + { + return -1; + } + result = pthread_cond_init(&_cond, &condAttr); + if (result != 0) + { + return -1; + } + result = pthread_condattr_destroy(&condAttr); + if (result != 0) + { + return -1; + } +#endif + return 0; +} + +ConditionVariableLinux::~ConditionVariableLinux() +{ + pthread_cond_destroy(&_cond); +} + +void ConditionVariableLinux::SleepCS(CriticalSectionWrapper& critSect) +{ + CriticalSectionLinux* cs = reinterpret_cast<CriticalSectionLinux*>( + &critSect); + pthread_cond_wait(&_cond, &cs->_mutex); +} + + +bool +ConditionVariableLinux::SleepCS( + CriticalSectionWrapper& critSect, + unsigned long maxTimeInMS) +{ + const unsigned long INFINITE = 0xFFFFFFFF; + + const int MILLISECONDS_PER_SECOND = 1000; +#ifndef WEBRTC_LINUX + const int MICROSECONDS_PER_MILLISECOND = 1000; +#endif + const int NANOSECONDS_PER_SECOND = 1000000000; + const int NANOSECONDS_PER_MILLISECOND = 1000000; + + CriticalSectionLinux* cs = reinterpret_cast<CriticalSectionLinux*>( + &critSect); + + if (maxTimeInMS != INFINITE) + { + timespec ts; +#ifndef WEBRTC_MAC +#ifdef WEBRTC_CLOCK_TYPE_REALTIME + clock_gettime(CLOCK_REALTIME, &ts); +#else + clock_gettime(CLOCK_MONOTONIC, &ts); +#endif +#else + struct timeval tv; + gettimeofday(&tv, 0); + ts.tv_sec = tv.tv_sec; + ts.tv_nsec = tv.tv_usec * MICROSECONDS_PER_MILLISECOND; +#endif + + ts.tv_sec += maxTimeInMS / MILLISECONDS_PER_SECOND; + ts.tv_nsec += (maxTimeInMS - ((maxTimeInMS / MILLISECONDS_PER_SECOND)* + MILLISECONDS_PER_SECOND)) * NANOSECONDS_PER_MILLISECOND; + + if (ts.tv_nsec >= NANOSECONDS_PER_SECOND) + { + ts.tv_sec += ts.tv_nsec / NANOSECONDS_PER_SECOND; + ts.tv_nsec %= NANOSECONDS_PER_SECOND; + } + const int res = pthread_cond_timedwait(&_cond, &cs->_mutex, &ts); + return (res == ETIMEDOUT) ? false : true; + } + else + { + pthread_cond_wait(&_cond, &cs->_mutex); + return true; + } +} + +void ConditionVariableLinux::Wake() +{ + pthread_cond_signal(&_cond); +} + +void ConditionVariableLinux::WakeAll() +{ + pthread_cond_broadcast(&_cond); +} +} // namespace webrtc diff --git a/src/system_wrappers/source/condition_variable_linux.h b/src/system_wrappers/source/condition_variable_linux.h new file mode 100644 index 0000000000..0300c5b5af --- /dev/null +++ b/src/system_wrappers/source/condition_variable_linux.h @@ -0,0 +1,39 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_CONDITION_VARIABLE_LINUX_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_CONDITION_VARIABLE_LINUX_H_ + +#include "condition_variable_wrapper.h" + +#include <pthread.h> + +namespace webrtc { +class ConditionVariableLinux : public ConditionVariableWrapper +{ +public: + static ConditionVariableWrapper* Create(); + ~ConditionVariableLinux(); + + void SleepCS(CriticalSectionWrapper& critSect); + bool SleepCS(CriticalSectionWrapper& critSect, unsigned long maxTimeInMS); + void Wake(); + void WakeAll(); + +private: + ConditionVariableLinux(); + int Construct(); + +private: + pthread_cond_t _cond; +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_CONDITION_VARIABLE_LINUX_H_ diff --git a/src/system_wrappers/source/cpu.cc b/src/system_wrappers/source/cpu.cc new file mode 100644 index 0000000000..2285872720 --- /dev/null +++ b/src/system_wrappers/source/cpu.cc @@ -0,0 +1,87 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "cpu_wrapper.h" + +#if defined(_WIN32) + #include <Windows.h> + #include "engine_configurations.h" + #include "cpu_windows.h" +#elif defined(WEBRTC_MAC) + #include <sys/types.h> + #include <sys/sysctl.h> + #include "cpu_mac.h" +#elif defined(WEBRTC_MAC_INTEL) + #include "cpu_mac.h" +#elif defined(ANDROID) + // Not implemented yet, might be possible to use Linux implementation +#else // defined(WEBRTC_LINUX) + #include <sys/sysinfo.h> + #include "cpu_linux.h" +#endif + +#include "trace.h" + +namespace webrtc { +WebRtc_UWord32 CpuWrapper::_numberOfCores = 0; + +WebRtc_UWord32 CpuWrapper::DetectNumberOfCores() +{ + if (!_numberOfCores) + { +#if defined(_WIN32) + SYSTEM_INFO si; + GetSystemInfo(&si); + _numberOfCores = static_cast<WebRtc_UWord32>(si.dwNumberOfProcessors); + WEBRTC_TRACE(kTraceStateInfo, kTraceUtility, -1, + "Available number of cores:%d", _numberOfCores); + +#elif defined(WEBRTC_LINUX) && !defined(ANDROID) + _numberOfCores = get_nprocs(); + WEBRTC_TRACE(kTraceStateInfo, kTraceUtility, -1, + "Available number of cores:%d", _numberOfCores); + +#elif (defined(WEBRTC_MAC) || defined(WEBRTC_MAC_INTEL)) + int name[] = {CTL_HW, HW_AVAILCPU}; + int ncpu; + size_t size = sizeof(ncpu); + if(0 == sysctl(name, 2, &ncpu, &size, NULL, 0)) + { + _numberOfCores = static_cast<WebRtc_UWord32>(ncpu); + WEBRTC_TRACE(kTraceStateInfo, kTraceUtility, -1, + "Available number of cores:%d", _numberOfCores); + } else + { + WEBRTC_TRACE(kTraceError, kTraceUtility, -1, + "Failed to get number of cores"); + _numberOfCores = 1; + } +#else + WEBRTC_TRACE(kTraceWarning, kTraceUtility, -1, + "No function to get number of cores"); + _numberOfCores = 1; +#endif + } + return _numberOfCores; +} + +CpuWrapper* CpuWrapper::CreateCpu() +{ +#if defined(_WIN32) + return new CpuWindows(); +#elif (defined(WEBRTC_MAC) || defined(WEBRTC_MAC_INTEL)) + return new CpuWrapperMac(); +#elif defined(ANDROID) + return 0; +#else + return new CpuLinux(); +#endif +} +} // namespace webrtc diff --git a/src/system_wrappers/source/cpu_features.cc b/src/system_wrappers/source/cpu_features.cc new file mode 100644 index 0000000000..850dc9b038 --- /dev/null +++ b/src/system_wrappers/source/cpu_features.cc @@ -0,0 +1,60 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "cpu_features_wrapper.h" + +// No CPU feature is available => straight C path. +int GetCPUInfoNoASM(CPUFeature feature) { + (void)feature; + return 0; +} + +// Intrinsic for "cpuid". +#if defined(__pic__) && defined(__i386__) +static inline void cpuid(int cpu_info[4], int info_type) { + __asm__ volatile ( + "mov %%ebx, %%edi\n" + "cpuid\n" + "xchg %%edi, %%ebx\n" + : "=a"(cpu_info[0]), "=D"(cpu_info[1]), "=c"(cpu_info[2]), "=d"(cpu_info[3]) + : "a"(info_type)); +} +#elif defined(__i386__) || defined(__x86_64__) +static inline void cpuid(int cpu_info[4], int info_type) { + __asm__ volatile ( + "cpuid\n" + : "=a"(cpu_info[0]), "=b"(cpu_info[1]), "=c"(cpu_info[2]), "=d"(cpu_info[3]) + : "a"(info_type)); +} +#endif + +#if defined(__i386__) || defined(__x86_64__) +// Actual feature detection for x86. +static int GetCPUInfo(CPUFeature feature) { + int cpu_info[4]; + cpuid(cpu_info, 1); + if (feature == kSSE2) { + return 0 != (cpu_info[3] & 0x04000000); + } + if (feature == kSSE3) { + return 0 != (cpu_info[2] & 0x00000001); + } + return 0; +} +#else +// Default to straight C for other platforms. +static int GetCPUInfo(CPUFeature feature) { + (void)feature; + return 0; +} +#endif + +WebRtc_CPUInfo WebRtc_GetCPUInfo = GetCPUInfo; +WebRtc_CPUInfo WebRtc_GetCPUInfoNoASM = GetCPUInfoNoASM; diff --git a/src/system_wrappers/source/cpu_linux.cc b/src/system_wrappers/source/cpu_linux.cc new file mode 100644 index 0000000000..eff9704db9 --- /dev/null +++ b/src/system_wrappers/source/cpu_linux.cc @@ -0,0 +1,172 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "cpu_linux.h" + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +namespace webrtc { +CpuLinux::CpuLinux() +{ + m_oldBusyTime = 0; + m_oldIdleTime = 0; + m_numCores = 0; + m_numCores = GetNumCores(); + m_oldBusyTimeMulti = new long long[m_numCores]; + memset(m_oldBusyTimeMulti, 0, sizeof(long long) * m_numCores); + m_oldIdleTimeMulti = new long long[m_numCores]; + memset(m_oldIdleTimeMulti, 0, sizeof(long long) * m_numCores); + m_idleArray = new long long[m_numCores]; + memset(m_idleArray, 0, sizeof(long long) * m_numCores); + m_busyArray = new long long[m_numCores]; + memset(m_busyArray, 0, sizeof(long long) * m_numCores); + m_resultArray = new WebRtc_UWord32[m_numCores]; + + GetData(m_oldBusyTime, m_oldIdleTime, m_busyArray, m_idleArray); +} + +CpuLinux::~CpuLinux() +{ + delete [] m_oldBusyTimeMulti; + delete [] m_oldIdleTimeMulti; + delete [] m_idleArray; + delete [] m_busyArray; + delete [] m_resultArray; +} + +WebRtc_Word32 CpuLinux::CpuUsage() +{ + WebRtc_UWord32 dummy = 0; + WebRtc_UWord32* dummyArray = NULL; + return CpuUsageMultiCore(dummy, dummyArray); +} + +WebRtc_Word32 CpuLinux::CpuUsageMultiCore(WebRtc_UWord32& numCores, + WebRtc_UWord32*& coreArray) +{ + coreArray = m_resultArray; + numCores = m_numCores; + long long busy = 0; + long long idle = 0; + GetData(busy, idle, m_busyArray, m_idleArray); + + long long deltaBusy = busy - m_oldBusyTime; + long long deltaIdle = idle - m_oldIdleTime; + m_oldBusyTime = busy; + m_oldIdleTime = idle; + + int retVal = -1; + if (deltaBusy + deltaIdle == 0) + { + retVal = 0; + } + else + { + retVal = (int)(100 * (deltaBusy) / (deltaBusy + deltaIdle)); + } + + if (coreArray == NULL) + { + return retVal; + } + + for (WebRtc_UWord32 i = 0; i < m_numCores; i++) + { + deltaBusy = m_busyArray[i] - m_oldBusyTimeMulti[i]; + deltaIdle = m_idleArray[i] - m_oldIdleTimeMulti[i]; + m_oldBusyTimeMulti[i] = m_busyArray[i]; + m_oldIdleTimeMulti[i] = m_idleArray[i]; + if(deltaBusy + deltaIdle == 0) + { + coreArray[i] = 0; + } + else + { + coreArray[i] = (int)(100 * (deltaBusy) / (deltaBusy+deltaIdle)); + } + } + return retVal; +} + + +int CpuLinux::GetData(long long& busy, long long& idle, long long*& busyArray, + long long*& idleArray) +{ + FILE* fp = fopen("/proc/stat", "r"); + if (!fp) + { + return -1; + } + + char line[100]; + char* dummy = fgets(line, 100, fp); + char firstWord[100]; + sscanf(line, "%s ", firstWord); + if(strncmp(firstWord, "cpu", 3)!=0) + { + return -1; + } + char sUser[100]; + char sNice[100]; + char sSystem[100]; + char sIdle[100]; + sscanf(line, "%s %s %s %s %s ", firstWord, sUser, sNice, sSystem, sIdle); + long long luser = atoll(sUser); + long long lnice = atoll(sNice); + long long lsystem = atoll(sSystem); + long long lidle = atoll (sIdle); + + busy = luser + lnice + lsystem; + idle = lidle; + for (WebRtc_UWord32 i = 0; i < m_numCores; i++) + { + dummy = fgets(line, 100, fp); + sscanf(line, "%s %s %s %s %s ", firstWord, sUser, sNice, sSystem, + sIdle); + luser = atoll(sUser); + lnice = atoll(sNice); + lsystem = atoll(sSystem); + lidle = atoll (sIdle); + busyArray[i] = luser + lnice + lsystem; + idleArray[i] = lidle; + } + fclose(fp); + return 0; +} + +int CpuLinux::GetNumCores() +{ + FILE* fp = fopen("/proc/stat", "r"); + if (!fp) + { + return -1; + } + // Skip first line + char line[100]; + char* dummy = fgets(line, 100, fp); + int numCores = -1; + char firstWord[100]; + do + { + numCores++; + if (fgets(line, 100, fp)) + { + sscanf(line, "%s ", firstWord); + } else { + break; + } + } while (strncmp(firstWord, "cpu", 3) == 0); + fclose(fp); + return numCores; +} +} // namespace webrtc diff --git a/src/system_wrappers/source/cpu_linux.h b/src/system_wrappers/source/cpu_linux.h new file mode 100644 index 0000000000..9b22e836e2 --- /dev/null +++ b/src/system_wrappers/source/cpu_linux.h @@ -0,0 +1,51 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_CPU_LINUX_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_CPU_LINUX_H_ + +#include "cpu_wrapper.h" + +namespace webrtc { +class CpuLinux : public CpuWrapper +{ +public: + CpuLinux(); + virtual ~CpuLinux(); + + virtual WebRtc_Word32 CpuUsage(); + virtual WebRtc_Word32 CpuUsage(WebRtc_Word8* /*pProcessName*/, + WebRtc_UWord32 /*length*/) {return 0;} + virtual WebRtc_Word32 CpuUsage(WebRtc_UWord32 /*dwProcessID*/) {return 0;} + + virtual WebRtc_Word32 CpuUsageMultiCore(WebRtc_UWord32& numCores, + WebRtc_UWord32*& array); + + virtual void Reset() {return;} + virtual void Stop() {return;} +private: + int GetData(long long& busy, long long& idle, long long*& busyArray, + long long*& idleArray); + int GetNumCores(); + + long long m_oldBusyTime; + long long m_oldIdleTime; + + long long* m_oldBusyTimeMulti; + long long* m_oldIdleTimeMulti; + + long long* m_idleArray; + long long* m_busyArray; + WebRtc_UWord32* m_resultArray; + WebRtc_UWord32 m_numCores; +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_CPU_LINUX_H_ diff --git a/src/system_wrappers/source/cpu_mac.cc b/src/system_wrappers/source/cpu_mac.cc new file mode 100644 index 0000000000..c2a11e1b6d --- /dev/null +++ b/src/system_wrappers/source/cpu_mac.cc @@ -0,0 +1,132 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "cpu_mac.h" + +#include <iostream> +#include <mach/mach.h> +#include <mach/mach_error.h> + +#include "tick_util.h" + +namespace webrtc { +CpuWrapperMac::CpuWrapperMac() : _cpuUsage(NULL) +{ + natural_t cpuCount; + processor_info_array_t infoArray; + mach_msg_type_number_t infoCount; + + kern_return_t error = host_processor_info(mach_host_self(), + PROCESSOR_CPU_LOAD_INFO, + &cpuCount, + &infoArray, + &infoCount); + if (error) + { + return; + } + + _cpuUsage = new WebRtc_UWord32[cpuCount]; + _lastTickCount = new WebRtc_Word64[cpuCount]; + _lastTime = TickTime::MillisecondTimestamp(); + + processor_cpu_load_info_data_t* cpuLoadInfo = + (processor_cpu_load_info_data_t*) infoArray; + for (unsigned int cpu= 0; cpu < cpuCount; cpu++) + { + WebRtc_Word64 ticks = 0; + for (int state = 0; state < 2; state++) + { + ticks += cpuLoadInfo[cpu].cpu_ticks[state]; + } + _lastTickCount[cpu] = ticks; + } + vm_deallocate(mach_task_self(), (vm_address_t)infoArray, infoCount); +} + +CpuWrapperMac::~CpuWrapperMac() +{ + delete _cpuUsage; + delete _lastTickCount; +} + +WebRtc_Word32 CpuWrapperMac::CpuUsage() +{ + WebRtc_UWord32 numCores; + WebRtc_UWord32* array = NULL; + return CpuUsageMultiCore(numCores, array); +} + +WebRtc_Word32 +CpuWrapperMac::CpuUsageMultiCore(WebRtc_UWord32& numCores, + WebRtc_UWord32*& array) +{ + natural_t cpuCount; + processor_info_array_t infoArray; + mach_msg_type_number_t infoCount; + + // sanity check + if(_cpuUsage == NULL) + { + return -1; + } + WebRtc_Word64 now = TickTime::MillisecondTimestamp(); + WebRtc_Word64 timeDiffMS = now - _lastTime; + // TODO(hellner) why block here? Why not just return the old + // value? Is this behavior consistent across all + // platforms? + // Make sure that at least 500 ms pass between calls. + if(timeDiffMS < 500) + { + usleep((500-timeDiffMS)*1000); + return CpuUsageMultiCore(numCores, array); + } + _lastTime = now; + + kern_return_t error = host_processor_info(mach_host_self(), + PROCESSOR_CPU_LOAD_INFO, + &cpuCount, + &infoArray, + &infoCount); + if (error) + { + return -1; + } + + processor_cpu_load_info_data_t* cpuLoadInfo = + (processor_cpu_load_info_data_t*) infoArray; + + WebRtc_Word32 totalCpuUsage = 0; + for (unsigned int cpu = 0; cpu < cpuCount; cpu++) + { + WebRtc_Word64 ticks = 0; + for (int state = 0; state < 2; state++) + { + ticks += cpuLoadInfo[cpu].cpu_ticks[state]; + } + if(timeDiffMS <= 0) + { + _cpuUsage[cpu] = 0; + }else { + _cpuUsage[cpu] = (WebRtc_UWord32)((1000 * + (ticks - _lastTickCount[cpu])) / + timeDiffMS); + } + _lastTickCount[cpu] = ticks; + totalCpuUsage += _cpuUsage[cpu]; + } + + vm_deallocate(mach_task_self(), (vm_address_t)infoArray, infoCount); + + numCores = cpuCount; + array = _cpuUsage; + return totalCpuUsage/cpuCount; +} +} // namespace webrtc diff --git a/src/system_wrappers/source/cpu_mac.h b/src/system_wrappers/source/cpu_mac.h new file mode 100644 index 0000000000..04cd097be9 --- /dev/null +++ b/src/system_wrappers/source/cpu_mac.h @@ -0,0 +1,44 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_CPU_MAC_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_CPU_MAC_H_ + +#include "cpu_wrapper.h" + +namespace webrtc { +class CpuWrapperMac : public CpuWrapper +{ +public: + CpuWrapperMac(); + virtual ~CpuWrapperMac(); + + virtual WebRtc_Word32 CpuUsage(); + virtual WebRtc_Word32 CpuUsage(WebRtc_Word8* /*pProcessName*/, + WebRtc_UWord32 /*length*/) {return -1;} + virtual WebRtc_Word32 CpuUsage(WebRtc_UWord32 /*dwProcessID*/) {return -1;} + + // Note: this class will block the call and sleep if called too fast + // This function blocks the calling thread if the thread is calling it more + // often than every 500 ms. + virtual WebRtc_Word32 CpuUsageMultiCore(WebRtc_UWord32& numCores, + WebRtc_UWord32*& array); + + virtual void Reset() {} + virtual void Stop() {} + +private: + WebRtc_UWord32* _cpuUsage; + WebRtc_Word64* _lastTickCount; + WebRtc_Word64 _lastTime; +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_CPU_MAC_H_ diff --git a/src/system_wrappers/source/critical_section.cc b/src/system_wrappers/source/critical_section.cc new file mode 100644 index 0000000000..213c352898 --- /dev/null +++ b/src/system_wrappers/source/critical_section.cc @@ -0,0 +1,27 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#if defined(_WIN32) + #include <windows.h> + #include "critical_section_windows.h" +#else + #include "critical_section_linux.h" +#endif + +namespace webrtc { +CriticalSectionWrapper* CriticalSectionWrapper::CreateCriticalSection() +{ +#ifdef _WIN32 + return new CriticalSectionWindows(); +#else + return new CriticalSectionLinux(); +#endif +} +} // namespace webrtc diff --git a/src/system_wrappers/source/critical_section_linux.cc b/src/system_wrappers/source/critical_section_linux.cc new file mode 100644 index 0000000000..35e81aeac0 --- /dev/null +++ b/src/system_wrappers/source/critical_section_linux.cc @@ -0,0 +1,38 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "critical_section_linux.h" + +namespace webrtc { +CriticalSectionLinux::CriticalSectionLinux() +{ + pthread_mutexattr_t attr; + pthread_mutexattr_init(&attr); + pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE); + pthread_mutex_init(&_mutex, &attr); +} + +CriticalSectionLinux::~CriticalSectionLinux() +{ + pthread_mutex_destroy(&_mutex); +} + +void +CriticalSectionLinux::Enter() +{ + pthread_mutex_lock(&_mutex); +} + +void +CriticalSectionLinux::Leave() +{ + pthread_mutex_unlock(&_mutex); +} +} // namespace webrtc diff --git a/src/system_wrappers/source/critical_section_linux.h b/src/system_wrappers/source/critical_section_linux.h new file mode 100644 index 0000000000..5ada1cb47d --- /dev/null +++ b/src/system_wrappers/source/critical_section_linux.h @@ -0,0 +1,35 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_CRITICAL_SECTION_LINUX_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_CRITICAL_SECTION_LINUX_H_ + +#include "critical_section_wrapper.h" + +#include <pthread.h> + +namespace webrtc { +class CriticalSectionLinux : public CriticalSectionWrapper +{ +public: + CriticalSectionLinux(); + + virtual ~CriticalSectionLinux(); + + virtual void Enter(); + virtual void Leave(); + +private: + pthread_mutex_t _mutex; + friend class ConditionVariableLinux; +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_CRITICAL_SECTION_LINUX_H_ diff --git a/src/system_wrappers/source/event.cc b/src/system_wrappers/source/event.cc new file mode 100644 index 0000000000..384b96142f --- /dev/null +++ b/src/system_wrappers/source/event.cc @@ -0,0 +1,52 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "event_wrapper.h" + +#if defined(_WIN32) + #include <windows.h> + #include "event_windows.h" +#else + #include <pthread.h> + #include "event_linux.h" +#endif + +namespace webrtc { +EventWrapper* EventWrapper::Create() +{ +#if defined(_WIN32) + return new EventWindows(); +#else + return EventLinux::Create(); +#endif +} + +int EventWrapper::KeyPressed() +{ +#if defined(_WIN32) + int keyDown = 0; + for(int key = 0x20; key < 0x90; key++) + { + short res = GetAsyncKeyState(key); + keyDown |= res%2; // Get the LSB + } + if(keyDown) + { + return 1; + } + else + { + return 0; + } +#else + return -1; +#endif +} +} // namespace webrtc diff --git a/src/system_wrappers/source/event_linux.cc b/src/system_wrappers/source/event_linux.cc new file mode 100644 index 0000000000..dddd31c15c --- /dev/null +++ b/src/system_wrappers/source/event_linux.cc @@ -0,0 +1,324 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "event_linux.h" + +#include <errno.h> +#include <pthread.h> +#include <signal.h> +#include <stdio.h> +#include <string.h> +#include <sys/time.h> +#include <unistd.h> + +namespace webrtc { +const long int E6 = 1000000; +const long int E9 = 1000 * E6; + +EventWrapper* EventLinux::Create() +{ + EventLinux* ptr = new EventLinux; + if (!ptr) + { + return NULL; + } + + const int error = ptr->Construct(); + if (error) + { + delete ptr; + return NULL; + } + return ptr; +} + + +EventLinux::EventLinux() + : _timerThread(0), + _timerEvent(0), + _periodic(false), + _time(0), + _count(0), + _state(kDown) +{ +} + +int EventLinux::Construct() +{ + // Set start time to zero + memset(&_tCreate, 0, sizeof(_tCreate)); + + int result = pthread_mutex_init(&mutex, 0); + if (result != 0) + { + return -1; + } +#ifdef WEBRTC_CLOCK_TYPE_REALTIME + result = pthread_cond_init(&cond, 0); + if (result != 0) + { + return -1; + } +#else + pthread_condattr_t condAttr; + result = pthread_condattr_init(&condAttr); + if (result != 0) + { + return -1; + } + result = pthread_condattr_setclock(&condAttr, CLOCK_MONOTONIC); + if (result != 0) + { + return -1; + } + result = pthread_cond_init(&cond, &condAttr); + if (result != 0) + { + return -1; + } + result = pthread_condattr_destroy(&condAttr); + if (result != 0) + { + return -1; + } +#endif + return 0; +} + +EventLinux::~EventLinux() +{ + StopTimer(); + pthread_cond_destroy(&cond); + pthread_mutex_destroy(&mutex); +} + +bool EventLinux::Reset() +{ + if (0 != pthread_mutex_lock(&mutex)) + { + return false; + } + _state = kDown; + pthread_mutex_unlock(&mutex); + return true; +} + +bool EventLinux::Set() +{ + if (0 != pthread_mutex_lock(&mutex)) + { + return false; + } + _state = kUp; + // Release all waiting threads + pthread_cond_broadcast(&cond); + pthread_mutex_unlock(&mutex); + return true; +} + +EventTypeWrapper EventLinux::Wait(unsigned long timeout) +{ + int retVal = 0; + if (0 != pthread_mutex_lock(&mutex)) + { + return kEventError; + } + + if (kDown == _state) + { + if (WEBRTC_EVENT_INFINITE != timeout) + { + timespec tEnd; +#ifndef WEBRTC_MAC +#ifdef WEBRTC_CLOCK_TYPE_REALTIME + clock_gettime(CLOCK_REALTIME, &tEnd); +#else + clock_gettime(CLOCK_MONOTONIC, &tEnd); +#endif +#else + timeval tVal; + struct timezone tZone; + tZone.tz_minuteswest = 0; + tZone.tz_dsttime = 0; + gettimeofday(&tVal,&tZone); + TIMEVAL_TO_TIMESPEC(&tVal,&tEnd); +#endif + tEnd.tv_sec += timeout / 1000; + tEnd.tv_nsec += (timeout - (timeout / 1000) * 1000) * E6; + + if (tEnd.tv_nsec >= E9) + { + tEnd.tv_sec++; + tEnd.tv_nsec -= E9; + } + retVal = pthread_cond_timedwait(&cond, &mutex, &tEnd); + } else { + retVal = pthread_cond_wait(&cond, &mutex); + } + } + + _state = kDown; + pthread_mutex_unlock(&mutex); + + switch(retVal) + { + case 0: + return kEventSignaled; + case ETIMEDOUT: + return kEventTimeout; + default: + return kEventError; + } +} + +EventTypeWrapper EventLinux::Wait(timespec& tPulse) +{ + int retVal = 0; + if (0 != pthread_mutex_lock(&mutex)) + { + return kEventError; + } + + if (kUp != _state) + { + retVal = pthread_cond_timedwait(&cond, &mutex, &tPulse); + } + _state = kDown; + + pthread_mutex_unlock(&mutex); + + switch(retVal) + { + case 0: + return kEventSignaled; + case ETIMEDOUT: + return kEventTimeout; + default: + return kEventError; + } +} + +bool EventLinux::StartTimer(bool periodic, unsigned long time) +{ + if (_timerThread) + { + if(_periodic) + { + // Timer already started. + return false; + } else { + // New one shot timer + _time = time; + _tCreate.tv_sec = 0; + _timerEvent->Set(); + return true; + } + } + + // Start the timer thread + _timerEvent = static_cast<EventLinux*>(EventWrapper::Create()); + const char* threadName = "WebRtc_event_timer_thread"; + _timerThread = ThreadWrapper::CreateThread(Run, this, kRealtimePriority, + threadName); + _periodic = periodic; + _time = time; + unsigned int id = 0; + if (_timerThread->Start(id)) + { + return true; + } + return false; +} + +bool EventLinux::Run(ThreadObj obj) +{ + return static_cast<EventLinux*>(obj)->Process(); +} + +bool EventLinux::Process() +{ + if (_tCreate.tv_sec == 0) + { +#ifndef WEBRTC_MAC +#ifdef WEBRTC_CLOCK_TYPE_REALTIME + clock_gettime(CLOCK_REALTIME, &_tCreate); +#else + clock_gettime(CLOCK_MONOTONIC, &_tCreate); +#endif +#else + timeval tVal; + struct timezone tZone; + tZone.tz_minuteswest = 0; + tZone.tz_dsttime = 0; + gettimeofday(&tVal,&tZone); + TIMEVAL_TO_TIMESPEC(&tVal,&_tCreate); +#endif + _count=0; + } + + timespec tEnd; + unsigned long long time = _time * ++_count; + tEnd.tv_sec = _tCreate.tv_sec + time/1000; + tEnd.tv_nsec = _tCreate.tv_nsec + (time - (time/1000)*1000)*E6; + + if ( tEnd.tv_nsec >= E9 ) + { + tEnd.tv_sec++; + tEnd.tv_nsec -= E9; + } + + switch(_timerEvent->Wait(tEnd)) + { + case kEventSignaled: + return true; + case kEventError: + return false; + case kEventTimeout: + break; + } + if(_periodic || _count==1) + { + Set(); + } + return true; +} + +bool EventLinux::StopTimer() +{ + if(_timerThread) + { + _timerThread->SetNotAlive(); + } + if (_timerEvent) + { + _timerEvent->Set(); + } + if (_timerThread) + { + if(!_timerThread->Stop()) + { + return false; + } + + delete _timerThread; + _timerThread = 0; + } + if (_timerEvent) + { + delete _timerEvent; + _timerEvent = 0; + } + + // Set time to zero to force new reference time for the timer. + memset(&_tCreate, 0, sizeof(_tCreate)); + _count=0; + return true; +} +} // namespace webrtc diff --git a/src/system_wrappers/source/event_linux.h b/src/system_wrappers/source/event_linux.h new file mode 100644 index 0000000000..17d193f2be --- /dev/null +++ b/src/system_wrappers/source/event_linux.h @@ -0,0 +1,66 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_EVENT_LINUX_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_EVENT_LINUX_H_ + +#include "event_wrapper.h" + +#include <pthread.h> +#include <time.h> + +#include "thread_wrapper.h" + +namespace webrtc { +enum State +{ + kUp = 1, + kDown = 2 +}; + +class EventLinux : public EventWrapper +{ +public: + static EventWrapper* Create(); + + virtual ~EventLinux(); + + virtual EventTypeWrapper Wait(unsigned long maxTime); + virtual bool Set(); + virtual bool Reset(); + + virtual bool StartTimer(bool periodic, unsigned long time); + virtual bool StopTimer(); + +private: + EventLinux(); + int Construct(); + + static bool Run(ThreadObj obj); + bool Process(); + EventTypeWrapper Wait(timespec& tPulse); + + +private: + pthread_cond_t cond; + pthread_mutex_t mutex; + + ThreadWrapper* _timerThread; + EventLinux* _timerEvent; + timespec _tCreate; + + bool _periodic; + unsigned long _time; // In ms + unsigned long _count; + State _state; +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_EVENT_LINUX_H_ diff --git a/src/system_wrappers/source/file_impl.cc b/src/system_wrappers/source/file_impl.cc new file mode 100644 index 0000000000..6046c2c77c --- /dev/null +++ b/src/system_wrappers/source/file_impl.cc @@ -0,0 +1,267 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "file_impl.h" + +#include <cassert> + +#ifdef _WIN32 + #include <Windows.h> +#else + #include <stdarg.h> + #include <string.h> +#endif + +namespace webrtc { +FileWrapper* FileWrapper::Create() +{ + return new FileWrapperImpl(); +} + +FileWrapperImpl::FileWrapperImpl() + : _id(NULL), + _open(false), + _looping(false), + _readOnly(false), + _text(false), + _maxSizeInBytes(-1), + _sizeInBytes(0) +{ + memset(_fileNameUTF8, 0, kMaxFileNameSize); +} + +FileWrapperImpl::~FileWrapperImpl() +{ + if (_id != NULL) + { + fclose(_id); + } +} + +WebRtc_Word32 FileWrapperImpl::CloseFile() +{ + if (_id != NULL) + { + fclose(_id); + _id = NULL; + } + memset(_fileNameUTF8, 0, kMaxFileNameSize); + _open = false; + return 0; +} + +int FileWrapperImpl::Rewind() +{ + if(_looping || !_readOnly) + { + if (_id != NULL) + { + _sizeInBytes = 0; + return fseek(_id, 0, SEEK_SET); + } + } + return -1; +} + +WebRtc_Word32 FileWrapperImpl::SetMaxFileSize(WebRtc_Word32 bytes) +{ + _maxSizeInBytes = bytes; + return 0; +} + +WebRtc_Word32 FileWrapperImpl::Flush() +{ + if (_id != NULL) + { + return fflush(_id); + } + return -1; +} + +WebRtc_Word32 FileWrapperImpl::FileName(WebRtc_Word8* fileNameUTF8, + WebRtc_UWord32 size) const +{ + WebRtc_Word32 len = static_cast<WebRtc_Word32>(strlen(_fileNameUTF8)); + if(len > kMaxFileNameSize) + { + assert(false); + return -1; + } + if(len < 1) + { + return -1; + } + // Make sure to NULL terminate + if(size < (WebRtc_UWord32)len) + { + len = size - 1; + } + memcpy(fileNameUTF8, _fileNameUTF8, len); + fileNameUTF8[len] = 0; + return 0; +} + +bool +FileWrapperImpl::Open() const +{ + return _open; +} + +WebRtc_Word32 FileWrapperImpl::OpenFile(const WebRtc_Word8 *fileNameUTF8, + const bool readOnly, const bool loop, + const bool text) +{ + WebRtc_Word32 length = (WebRtc_Word32)strlen(fileNameUTF8); + if (length > kMaxFileNameSize) + { + return -1; + } + + _readOnly = readOnly; + + FILE *tmpId = NULL; +#if defined _WIN32 + wchar_t wideFileName[kMaxFileNameSize]; + wideFileName[0] = 0; + + MultiByteToWideChar(CP_UTF8, + 0 /*UTF8 flag*/, + fileNameUTF8, + -1 /*Null terminated string*/, + wideFileName, + kMaxFileNameSize); + if(text) + { + if(readOnly) + { + tmpId = _wfopen(wideFileName, L"rt"); + } else { + tmpId = _wfopen(wideFileName, L"wt"); + } + } else { + if(readOnly) + { + tmpId = _wfopen(wideFileName, L"rb"); + } else { + tmpId = _wfopen(wideFileName, L"wb"); + } + } +#else + if(text) + { + if(readOnly) + { + tmpId = fopen(fileNameUTF8, "rt"); + } else { + tmpId = fopen(fileNameUTF8, "wt"); + } + } else { + if(readOnly) + { + tmpId = fopen(fileNameUTF8, "rb"); + } else { + tmpId = fopen(fileNameUTF8, "wb"); + } + } +#endif + + if (tmpId != NULL) + { + // + 1 comes fro copying the NULL termination charachter too + memcpy(_fileNameUTF8, fileNameUTF8, length + 1); + if (_id != NULL) + { + fclose(_id); + } + _id = tmpId; + _looping = loop; + _open = true; + return 0; + } + return -1; +} + +int FileWrapperImpl::Read(void *buf, int len) +{ + if(len < 0) + { + return 0; + } + if (_id != NULL) + { + WebRtc_Word32 res = static_cast<WebRtc_Word32>(fread(buf, 1, len, _id)); + if (res != len) + { + if(!_looping) + { + CloseFile(); + } + } + return res; + } + return -1; +} + +WebRtc_Word32 FileWrapperImpl::WriteText(const WebRtc_Word8* text, ...) +{ + assert(!_readOnly); + assert(!_text); + + if (_id == NULL) + { + return -1; + } + + char tempBuff[kFileMaxTextMessageSize]; + if (text) + { + va_list args; + va_start(args, text); +#ifdef _WIN32 + _vsnprintf(tempBuff, kFileMaxTextMessageSize-1, text, args); +#else + vsnprintf(tempBuff, kFileMaxTextMessageSize-1, text, args); +#endif + va_end(args); + WebRtc_Word32 nBytes; + nBytes = fprintf(_id, "%s", tempBuff); + if (nBytes > 0) + { + return 0; + } + CloseFile(); + } + return -1; +} + +bool FileWrapperImpl::Write(const void* buf, int len) +{ + assert(!_readOnly); + if (_id != NULL) + { + // Check if it's time to stop writing. + if ((_maxSizeInBytes != -1) && + _sizeInBytes + len > (WebRtc_UWord32)_maxSizeInBytes) + { + Flush(); + return false; + } + + size_t nBytes = fwrite((WebRtc_UWord8*)buf, 1, len, _id); + if (nBytes > 0) + { + _sizeInBytes += static_cast<WebRtc_Word32>(nBytes); + return true; + } + CloseFile(); + } + return false; +} +} // namespace webrtc diff --git a/src/system_wrappers/source/file_impl.h b/src/system_wrappers/source/file_impl.h new file mode 100644 index 0000000000..cf6b7347f9 --- /dev/null +++ b/src/system_wrappers/source/file_impl.h @@ -0,0 +1,57 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_FILE_IMPL_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_FILE_IMPL_H_ + +#include "file_wrapper.h" + +#include <stdio.h> + +namespace webrtc { +class FileWrapperImpl : public FileWrapper +{ +public: + FileWrapperImpl(); + virtual ~FileWrapperImpl(); + + virtual WebRtc_Word32 FileName(WebRtc_Word8* fileNameUTF8, + WebRtc_UWord32 size) const; + + virtual bool Open() const; + + virtual WebRtc_Word32 OpenFile(const WebRtc_Word8* fileNameUTF8, + const bool readOnly, + const bool loop = false, + const bool text = false); + + virtual WebRtc_Word32 CloseFile(); + virtual WebRtc_Word32 SetMaxFileSize(WebRtc_Word32 bytes); + virtual WebRtc_Word32 Flush(); + + virtual int Read(void* buf, int len); + virtual bool Write(const void *buf, int len); + virtual int Rewind(); + + virtual WebRtc_Word32 WriteText(const WebRtc_Word8* text, ...); + +private: + FILE* _id; + bool _open; + bool _looping; + bool _readOnly; + bool _text; + WebRtc_Word32 _maxSizeInBytes; // -1 indicates file size limitation is off + WebRtc_UWord32 _sizeInBytes; + WebRtc_Word8 _fileNameUTF8[kMaxFileNameSize]; +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_FILE_IMPL_H_ diff --git a/src/system_wrappers/source/list_no_stl.cc b/src/system_wrappers/source/list_no_stl.cc new file mode 100644 index 0000000000..d45f27b310 --- /dev/null +++ b/src/system_wrappers/source/list_no_stl.cc @@ -0,0 +1,289 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "list_wrapper.h" + +#include "critical_section_wrapper.h" +#include "trace.h" + +namespace webrtc { +ListItem::ListItem(const void* item) + : next_(0), + prev_(0), + item_ptr_(item), + item_(0) +{ +} + +ListItem::ListItem(const unsigned int item) + : next_(0), + prev_(0), + item_ptr_(0), + item_(item) +{ +} + +ListItem::~ListItem() +{ +} + +void* ListItem::GetItem() const +{ + return const_cast<void*>(item_ptr_); +} + +unsigned int ListItem::GetUnsignedItem() const +{ + return item_; +} + +ListWrapper::ListWrapper() + : critical_section_(CriticalSectionWrapper::CreateCriticalSection()), + first_(0), + last_(0), + size_(0) +{ +} + +ListWrapper::~ListWrapper() +{ + if (!Empty()) + { + // TODO (hellner) I'm not sure this loggin is useful. + WEBRTC_TRACE(kTraceMemory, kTraceUtility, -1, + "Potential memory leak in ListWrapper"); + // Remove all remaining list items. + while (Erase(First()) == 0) + {} + } + delete critical_section_; +} + +bool ListWrapper::Empty() const +{ + return !first_ && !last_; +} + +unsigned int ListWrapper::GetSize() const +{ + return size_; +} + +int ListWrapper::PushBack(const void* ptr) +{ + ListItem* item = new ListItem(ptr); + CriticalSectionScoped lock(*critical_section_); + PushBackImpl(item); + return 0; +} + +int ListWrapper::PushBack(const unsigned int item_id) +{ + ListItem* item = new ListItem(item_id); + CriticalSectionScoped lock(*critical_section_); + PushBackImpl(item); + return 0; +} + +int ListWrapper::PushFront(const unsigned int item_id) +{ + ListItem* item = new ListItem(item_id); + CriticalSectionScoped lock(*critical_section_); + PushFrontImpl(item); + return 0; +} + +int ListWrapper::PushFront(const void* ptr) +{ + ListItem* item = new ListItem(ptr); + CriticalSectionScoped lock(*critical_section_); + PushFrontImpl(item); + return 0; +} + +int ListWrapper::PopFront() +{ + return Erase(first_); +} + +int ListWrapper::PopBack() +{ + return Erase(last_); +} + +ListItem* ListWrapper::First() const +{ + return first_; +} + +ListItem* ListWrapper::Last() const +{ + return last_; +} + +ListItem* ListWrapper::Next(ListItem* item) const +{ + if(!item) + { + return 0; + } + return item->next_; +} + +ListItem* ListWrapper::Previous(ListItem* item) const +{ + if (!item) + { + return 0; + } + return item->prev_; +} + +int ListWrapper::Insert(ListItem* existing_previous_item, ListItem* new_item) +{ + if (!new_item) + { + return -1; + } + // Allow existing_previous_item to be NULL if the list is empty. + // TODO (hellner) why allow this? Keep it as is for now to avoid + // breaking API contract. + if (!existing_previous_item && !Empty()) + { + return -1; + } + CriticalSectionScoped lock(*critical_section_); + if (!existing_previous_item) + { + PushBackImpl(new_item); + return 0; + } + ListItem* next_item = existing_previous_item->next_; + new_item->next_ = existing_previous_item->next_; + new_item->prev_ = existing_previous_item; + existing_previous_item->next_ = new_item; + if (next_item) + { + next_item->prev_ = new_item; + } + else + { + last_ = new_item; + } + size_++; + return 0; +} + +int ListWrapper::InsertBefore(ListItem* existing_next_item, + ListItem* new_item) +{ + if (!new_item) + { + return -1; + } + // Allow existing_next_item to be NULL if the list is empty. + // Todo: why allow this? Keep it as is for now to avoid breaking API + // contract. + if (!existing_next_item && !Empty()) + { + return -1; + } + CriticalSectionScoped lock(*critical_section_); + if (!existing_next_item) + { + PushBackImpl(new_item); + return 0; + } + + ListItem* previous_item = existing_next_item->prev_; + new_item->next_ = existing_next_item; + new_item->prev_ = previous_item; + existing_next_item->prev_ = new_item; + if (previous_item) + { + previous_item->next_ = new_item; + } + else + { + first_ = new_item; + } + size_++; + return 0; +} + +int ListWrapper::Erase(ListItem* item) +{ + if (!item) + { + return -1; + } + size_--; + ListItem* previous_item = item->prev_; + ListItem* next_item = item->next_; + if (!previous_item) + { + if(next_item) + { + next_item->prev_ = 0; + } + first_ = next_item; + } + else + { + previous_item->next_ = next_item; + } + if (!next_item) + { + if(previous_item) + { + previous_item->next_ = 0; + } + last_ = previous_item; + } + else + { + next_item->prev_ = previous_item; + } + delete item; + return 0; +} + +void ListWrapper::PushBackImpl(ListItem* item) +{ + if (Empty()) + { + first_ = item; + last_ = item; + size_++; + return; + } + + item->prev_ = last_; + last_->next_ = item; + last_ = item; + size_++; +} + +void ListWrapper::PushFrontImpl(ListItem* item) +{ + if (Empty()) + { + first_ = item; + last_ = item; + size_++; + return; + } + + item->next_ = first_; + first_->prev_ = item; + first_ = item; + size_++; +} +} //namespace webrtc diff --git a/src/system_wrappers/source/list_no_stl.h b/src/system_wrappers/source/list_no_stl.h new file mode 100644 index 0000000000..26d844c782 --- /dev/null +++ b/src/system_wrappers/source/list_no_stl.h @@ -0,0 +1,79 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_LIST_NO_STL_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_LIST_NO_STL_H_ + +#include "constructor_magic.h" + +namespace webrtc { +class CriticalSectionWrapper; + +class ListNoStlItem +{ +public: + ListNoStlItem(const void* ptr); + ListNoStlItem(const unsigned int item); + virtual ~ListNoStlItem(); + void* GetItem() const; + unsigned int GetUnsignedItem() const; + +protected: + ListNoStlItem* next_; + ListNoStlItem* prev_; + +private: + friend class ListNoStl; + + const void* item_ptr_; + const unsigned int item_; + DISALLOW_COPY_AND_ASSIGN(ListNoStlItem); +}; + + +class ListNoStl +{ +public: + ListNoStl(); + virtual ~ListNoStl(); + + // ListWrapper functions + unsigned int GetSize() const; + int PushBack(const void* ptr); + int PushBack(const unsigned int item_id); + int PushFront(const void* ptr); + int PushFront(const unsigned int item_id); + int PopFront(); + int PopBack(); + bool Empty() const; + ListNoStlItem* First() const; + ListNoStlItem* Last() const; + ListNoStlItem* Next(ListNoStlItem* item) const; + ListNoStlItem* Previous(ListNoStlItem* item) const; + int Erase(ListNoStlItem* item); + int Insert(ListNoStlItem* existing_previous_item, + ListNoStlItem* new_item); + + int InsertBefore(ListNoStlItem* existing_next_item, + ListNoStlItem* new_item); + +private: + void PushBack(ListNoStlItem* item); + void PushFront(ListNoStlItem* item); + + CriticalSectionWrapper* critical_section_; + ListNoStlItem* first_; + ListNoStlItem* last_; + unsigned int size_; + DISALLOW_COPY_AND_ASSIGN(ListNoStl); +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_LIST_NO_STL_H_ diff --git a/src/system_wrappers/source/list_stl.cc b/src/system_wrappers/source/list_stl.cc new file mode 100644 index 0000000000..dcc63c3d0d --- /dev/null +++ b/src/system_wrappers/source/list_stl.cc @@ -0,0 +1,244 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "list_wrapper.h" + +#include "trace.h" + +namespace webrtc { +ListItem::ListItem(const void* item) + : this_iter_(), + item_ptr_(item), + item_(0) +{ +} + +ListItem::ListItem(const unsigned int item) + : this_iter_(), + item_ptr_(0), + item_(item) +{ +} + +ListItem::~ListItem() +{ +} + +void* ListItem::GetItem() const +{ + return const_cast<void*>(item_ptr_); +} + +unsigned int ListItem::GetUnsignedItem() const +{ + return item_; +} + +ListWrapper::ListWrapper() : list_() +{ +} + +ListWrapper::~ListWrapper() +{ + if (!Empty()) + { + // TODO (hellner) I'm not sure this loggin is useful. + WEBRTC_TRACE(kTraceMemory, kTraceUtility, -1, + "Potential memory leak in ListWrapper"); + // Remove all remaining list items. + while (Erase(First()) == 0) + {} + } +} + +bool ListWrapper::Empty() const +{ + return list_.empty(); +} + +unsigned int ListWrapper::GetSize() const +{ + return list_.size(); +} + +int ListWrapper::PushBack(const void* ptr) +{ + ListItem* item = new ListItem(ptr); + list_.push_back(item); + return 0; +} + +int ListWrapper::PushBack(const unsigned int item_id) +{ + ListItem* item = new ListItem(item_id); + list_.push_back(item); + return 0; +} + +int ListWrapper::PushFront(const unsigned int item_id) +{ + ListItem* item = new ListItem(item_id); + list_.push_front(item); + return 0; +} + +int ListWrapper::PushFront(const void* ptr) +{ + ListItem* item = new ListItem(ptr); + list_.push_front(item); + return 0; +} + +int ListWrapper::PopFront() +{ + if(list_.empty()) + { + return -1; + } + list_.pop_front(); + return 0; +} + +int ListWrapper::PopBack() +{ + if(list_.empty()) + { + return -1; + } + list_.pop_back(); + return 0; +} + +ListItem* ListWrapper::First() const +{ + if(list_.empty()) + { + return NULL; + } + std::list<ListItem*>::iterator item_iter = list_.begin(); + ListItem* return_item = (*item_iter); + return_item->this_iter_ = item_iter; + return return_item; +} + +ListItem* ListWrapper::Last() const +{ + if(list_.empty()) + { + return NULL; + } + // std::list::end() addresses the last item + 1. Decrement so that the + // actual last is accessed. + std::list<ListItem*>::iterator item_iter = list_.end(); + --item_iter; + ListItem* return_item = (*item_iter); + return_item->this_iter_ = item_iter; + return return_item; +} + +ListItem* ListWrapper::Next(ListItem* item) const +{ + if(item == NULL) + { + return NULL; + } + std::list<ListItem*>::iterator item_iter = item->this_iter_; + ++item_iter; + if (item_iter == list_.end()) + { + return NULL; + } + ListItem* return_item = (*item_iter); + return_item->this_iter_ = item_iter; + return return_item; +} + +ListItem* ListWrapper::Previous(ListItem* item) const +{ + if(item == NULL) + { + return NULL; + } + std::list<ListItem*>::iterator item_iter = item->this_iter_; + if (item_iter == list_.begin()) + { + return NULL; + } + --item_iter; + ListItem* return_item = (*item_iter); + return_item->this_iter_ = item_iter; + return return_item; +} + +int ListWrapper::Insert(ListItem* existing_previous_item, + ListItem* new_item) +{ + // Allow existingPreviousItem to be NULL if the list is empty. + // TODO (hellner) why allow this? Keep it as is for now to avoid + // breaking API contract. + if (!existing_previous_item && !Empty()) + { + return -1; + } + + if (!new_item) + { + return -1; + } + + std::list<ListItem*>::iterator insert_location = list_.begin(); + if (!Empty()) + { + insert_location = existing_previous_item->this_iter_; + if(insert_location != list_.end()) + { + ++insert_location; + } + } + + list_.insert(insert_location,new_item); + return 0; +} + +int ListWrapper::InsertBefore(ListItem* existing_next_item, + ListItem* new_item) +{ + // Allow existing_next_item to be NULL if the list is empty. + // Todo: why allow this? Keep it as is for now to avoid breaking API + // contract. + if (!existing_next_item && !Empty()) + { + return -1; + } + if (!new_item) + { + return -1; + } + + std::list<ListItem*>::iterator insert_location = list_.begin(); + if (!Empty()) + { + insert_location = existing_next_item->this_iter_; + } + + list_.insert(insert_location,new_item); + return 0; +} + +int ListWrapper::Erase(ListItem* item) +{ + if(item == NULL) + { + return -1; + } + list_.erase(item->this_iter_); + return 0; +} +} // namespace webrtc diff --git a/src/system_wrappers/source/list_stl.h b/src/system_wrappers/source/list_stl.h new file mode 100644 index 0000000000..b83a6648ca --- /dev/null +++ b/src/system_wrappers/source/list_stl.h @@ -0,0 +1,66 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_LIST_STL_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_LIST_STL_H_ + +#include <list> + +#include "constructor_magic.h" + +namespace webrtc { +class ListItem +{ +friend class ListWrapper; + +public: + ListItem(const void* ptr); + ListItem(const unsigned int item); + virtual ~ListItem(); + void* GetItem() const; + unsigned int GetUnsignedItem() const; + +private: + mutable std::list<ListItem*>::iterator this_iter_; + const void* item_ptr_; + const unsigned int item_; + DISALLOW_COPY_AND_ASSIGN(ListItem); +}; + +class ListWrapper +{ +public: + ListWrapper(); + ~ListWrapper(); + + // ListWrapper functions + unsigned int GetSize() const; + int PushBack(const void* ptr); + int PushBack(const unsigned int item_id); + int PushFront(const void* ptr); + int PushFront(const unsigned int item_id); + int PopFront(); + int PopBack(); + bool Empty() const; + ListItem* First() const; + ListItem* Last() const; + ListItem* Next(ListItem* item) const; + ListItem* Previous(ListItem* item) const; + int Erase(ListItem* item); + int Insert(ListItem* existing_previous_item, ListItem* new_item); + int InsertBefore(ListItem* existing_next_item, ListItem* new_item); + +private: + mutable std::list<ListItem*> list_; + DISALLOW_COPY_AND_ASSIGN(ListWrapper); +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_LIST_STL_H_ diff --git a/src/system_wrappers/source/list_unittest.cc b/src/system_wrappers/source/list_unittest.cc new file mode 100644 index 0000000000..3f3c88ffb7 --- /dev/null +++ b/src/system_wrappers/source/list_unittest.cc @@ -0,0 +1,475 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "gtest/gtest.h" + +#include "list_wrapper.h" + +using ::webrtc::ListWrapper; +using ::webrtc::ListItem; + +// Note: kNumberOfElements needs to be even. +const unsigned int kNumberOfElements = 10; + +// An opaque implementation of dynamic or statically allocated unsigned ints. +// This class makes it possible to use the exact same code for testing of both +// the dynamic and static implementation of ListWrapper. +// Clarification: ListWrapper has two versions of PushBack(..). It takes an +// unsigned integer or a void pointer. The integer implementation takes care +// of memory management. The void pointer version expect the caller to manage +// the memory associated with the void pointer. +// This class works like the integer version but can be implemented on top of +// either the integer version or void pointer version of ListWrapper. +// Note: the non-virtual fuctions behave the same for both versions. +class ListWrapperSimple { +public: + static ListWrapperSimple* Create(bool static_allocation); + virtual ~ListWrapperSimple() {} + + // These three functions should be used for manipulating ListItems so that + // they are the type corresponding to the underlying implementation. + virtual unsigned int GetUnsignedItem( + const ListItem* item) const = 0; + virtual ListItem* CreateListItem(unsigned int item_id) = 0; + virtual bool DestroyListItem(ListItem* item) = 0; + + unsigned int GetSize() const { + return list_.GetSize(); + } + virtual int PushBack(const unsigned int item_id) = 0; + virtual int PushFront(const unsigned int item_id) = 0; + virtual int PopFront() = 0; + virtual int PopBack() = 0; + bool Empty() const { + return list_.Empty(); + } + ListItem* First() const { + return list_.First(); + } + ListItem* Last() const { + return list_.Last(); + } + ListItem* Next(ListItem* item) const { + return list_.Next(item); + } + ListItem* Previous(ListItem* item) const { + return list_.Previous(item); + } + virtual int Erase(ListItem* item) = 0; + int Insert(ListItem* existing_previous_item, + ListItem* new_item) { + return list_.Insert(existing_previous_item, new_item); + } + + int InsertBefore(ListItem* existing_next_item, + ListItem* new_item) { + return list_.InsertBefore(existing_next_item, new_item); + } +protected: + ListWrapperSimple() {} + + ListWrapper list_; +}; + +class ListWrapperStatic : public ListWrapperSimple { +public: + ListWrapperStatic() {} + virtual ~ListWrapperStatic() {} + + virtual unsigned int GetUnsignedItem(const ListItem* item) const { + return item->GetUnsignedItem(); + } + virtual ListItem* CreateListItem(unsigned int item_id) { + return new ListItem(item_id); + } + virtual bool DestroyListItem(ListItem* item) { + if (item == NULL) { + return false; + } + delete item; + return true; + } + virtual int PushBack(const unsigned int item_id) { + return list_.PushBack(item_id); + } + virtual int PushFront(const unsigned int item_id) { + return list_.PushFront(item_id); + } + virtual int PopFront() { + return list_.PopFront(); + } + virtual int PopBack() { + return list_.PopBack(); + } + virtual int Erase(ListItem* item) { + return list_.Erase(item); + } +}; + +class ListWrapperDynamic : public ListWrapperSimple { +public: + ListWrapperDynamic() {} + virtual ~ListWrapperDynamic() {} + + virtual unsigned int GetUnsignedItem(const ListItem* item) const { + const unsigned int* return_value_pointer = + reinterpret_cast<unsigned int*> (item->GetItem()); + if (return_value_pointer == NULL) { + return -1; + } + return *return_value_pointer; + } + virtual ListItem* CreateListItem(unsigned int item_id) { + unsigned int* item_id_pointer = new unsigned int; + if (item_id_pointer == NULL) { + return NULL; + } + *item_id_pointer = item_id; + ListItem* return_value = new ListItem( + reinterpret_cast<void*>(item_id_pointer)); + if (return_value == NULL) { + delete item_id_pointer; + return NULL; + } + return return_value; + } + virtual bool DestroyListItem(ListItem* item) { + if (item == NULL) { + return false; + } + bool return_value = false; + unsigned int* item_id_ptr = reinterpret_cast<unsigned int*>( + item->GetItem()); + if (item_id_ptr != NULL) { + return_value = true; + delete item_id_ptr; + } + delete item; + return return_value; + } + virtual int PushBack(const unsigned int item_id) { + unsigned int* item_id_ptr = new unsigned int; + if (item_id_ptr == NULL) { + return -1; + } + *item_id_ptr = item_id; + const int return_value = list_.PushBack( + reinterpret_cast<void*>(item_id_ptr)); + if (return_value != 0) { + delete item_id_ptr; + } + return return_value; + } + virtual int PushFront(const unsigned int item_id) { + unsigned int* item_id_ptr = new unsigned int; + if (item_id_ptr == NULL) { + return -1; + } + *item_id_ptr = item_id; + const int return_value = list_.PushFront( + reinterpret_cast<void*>(item_id_ptr)); + if (return_value != 0) { + delete item_id_ptr; + } + return return_value; + } + virtual int PopFront() { + return Erase(list_.First()); + } + virtual int PopBack() { + return Erase(list_.Last()); + } + virtual int Erase(ListItem* item) { + if (item == NULL) { + return -1; + } + unsigned int* item_id_ptr = reinterpret_cast<unsigned int*> ( + item->GetItem()); + int return_value = -1; + if (item_id_ptr != NULL) { + delete item_id_ptr; + return_value = 0; + } + if (list_.Erase(item) != 0) { + return -1; + } + return return_value; + } +}; + +ListWrapperSimple* ListWrapperSimple::Create(bool static_allocation) { + if(static_allocation) + { + return new ListWrapperStatic(); + } + return new ListWrapperDynamic(); +} + +void ClearList(ListWrapperSimple* list) { + if (list == NULL) + { + return; + } + while (list->Erase(list->First()) == 0) { + } +} + +ListWrapperSimple* CreateAscendingList(bool static_allocation) { + ListWrapperSimple* return_value = ListWrapperSimple::Create( + static_allocation); + if (return_value == NULL) { + return NULL; + } + for (unsigned int i = 0; i < kNumberOfElements; ++i) { + if (return_value->PushBack(i) == -1) { + ClearList(return_value); + delete return_value; + return NULL; + } + } + return return_value; +} + +ListWrapperSimple* CreateDecendingList(bool static_allocation) { + ListWrapperSimple* return_value = ListWrapperSimple::Create( + static_allocation); + if (return_value == NULL) { + return NULL; + } + for (unsigned int i = 0; i < kNumberOfElements; ++i) { + if (return_value->PushBack(kNumberOfElements - i - 1) == -1) { + ClearList(return_value); + delete return_value; + return NULL; + } + } + return return_value; +} + +// [0,kNumberOfElements - 1,1,kNumberOfElements - 2,...] (this is why +// kNumberOfElements need to be even) +ListWrapperSimple* CreateInterleavedList(bool static_allocation) { + ListWrapperSimple* return_value = ListWrapperSimple::Create( + static_allocation); + if (return_value == NULL) { + return NULL; + } + unsigned int uneven_count = 0; + unsigned int even_count = 0; + for (unsigned int i = 0; i < kNumberOfElements; i++) { + unsigned int push_value = 0; + if ((i % 2) == 0) { + push_value = even_count; + even_count++; + } else { + push_value = kNumberOfElements - uneven_count - 1; + uneven_count++; + } + if (return_value->PushBack(push_value) == -1) { + ClearList(return_value); + delete return_value; + return NULL; + } + } + return return_value; +} + +void PrintList(const ListWrapperSimple* list) { + ListItem* list_item = list->First(); + printf("["); + while (list_item != NULL) + { + printf("%3u", list->GetUnsignedItem(list_item)); + list_item = list->Next(list_item); + } + printf("]\n"); +} + +bool CompareLists(const ListWrapperSimple* lhs, const ListWrapperSimple* rhs) { + const unsigned int list_size = lhs->GetSize(); + if (lhs->GetSize() != rhs->GetSize()) { + return false; + } + if (lhs->Empty()) { + return rhs->Empty(); + } + unsigned int i = 0; + ListItem* lhs_item = lhs->First(); + ListItem* rhs_item = rhs->First(); + while (i < list_size) { + if (lhs_item == NULL) { + return false; + } + if (rhs_item == NULL) { + return false; + } + if (lhs->GetUnsignedItem(lhs_item) != rhs->GetUnsignedItem(rhs_item)) { + return false; + } + i++; + lhs_item = lhs->Next(lhs_item); + rhs_item = rhs->Next(rhs_item); + } + return true; +} + +TEST(ListWrapperTest,ReverseNewIntList) { + // Create a new temporary list with elements reversed those of + // new_int_list_ + const ListWrapperSimple* decending_list = CreateDecendingList(rand()%2); + ASSERT_FALSE(decending_list == NULL); + ASSERT_FALSE(decending_list->Empty()); + ASSERT_EQ(kNumberOfElements,decending_list->GetSize()); + + const ListWrapperSimple* ascending_list = CreateAscendingList(rand()%2); + ASSERT_FALSE(ascending_list == NULL); + ASSERT_FALSE(ascending_list->Empty()); + ASSERT_EQ(kNumberOfElements,ascending_list->GetSize()); + + ListWrapperSimple* list_to_reverse = ListWrapperSimple::Create(rand()%2); + + // Reverse the list using PushBack and Previous. + for (ListItem* item = ascending_list->Last(); item != NULL; + item = ascending_list->Previous(item)) { + list_to_reverse->PushBack(ascending_list->GetUnsignedItem(item)); + } + + ASSERT_TRUE(CompareLists(decending_list,list_to_reverse)); + + ListWrapperSimple* list_to_un_reverse = + ListWrapperSimple::Create(rand()%2); + ASSERT_FALSE(list_to_un_reverse == NULL); + // Reverse the reversed list using PushFront and Next. + for (ListItem* item = list_to_reverse->First(); item != NULL; + item = list_to_reverse->Next(item)) { + list_to_un_reverse->PushFront(list_to_reverse->GetUnsignedItem(item)); + } + + ASSERT_TRUE(CompareLists(ascending_list,list_to_un_reverse)); +} + +TEST(ListWrapperTest,PopTest) { + ListWrapperSimple* ascending_list = CreateAscendingList(rand()%2); + ASSERT_FALSE(ascending_list == NULL); + ASSERT_FALSE(ascending_list->Empty()); + EXPECT_EQ(0,ascending_list->PopFront()); + EXPECT_EQ(1,ascending_list->GetUnsignedItem(ascending_list->First())); + + EXPECT_EQ(0,ascending_list->PopBack()); + EXPECT_EQ(kNumberOfElements - 2,ascending_list->GetUnsignedItem( + ascending_list->Last())); + EXPECT_EQ(kNumberOfElements - 2, ascending_list->GetSize()); +} + +// Use Insert to interleave two lists. +TEST(ListWrapperTest,InterLeaveTest) { + ListWrapperSimple* interleave_list = CreateAscendingList(rand()%2); + ASSERT_FALSE(interleave_list == NULL); + ASSERT_FALSE(interleave_list->Empty()); + + ListWrapperSimple* decending_list = CreateDecendingList(rand()%2); + ASSERT_FALSE(decending_list == NULL); + + for (int i = 0; i < kNumberOfElements/2; ++i) { + ASSERT_EQ(0,interleave_list->PopBack()); + ASSERT_EQ(0,decending_list->PopBack()); + } + ASSERT_EQ(kNumberOfElements/2,interleave_list->GetSize()); + ASSERT_EQ(kNumberOfElements/2,decending_list->GetSize()); + + int insert_position = kNumberOfElements/2; + ASSERT_EQ(insert_position * 2, kNumberOfElements); + while (!decending_list->Empty()) + { + ListItem* item = decending_list->Last(); + ASSERT_FALSE(item == NULL); + + const unsigned int item_id = decending_list->GetUnsignedItem(item); + ASSERT_EQ(0,decending_list->Erase(item)); + + ListItem* insert_item = interleave_list->CreateListItem(item_id); + ASSERT_FALSE(insert_item == NULL); + item = interleave_list->First(); + ASSERT_FALSE(item == NULL); + for (int j = 0; j < insert_position - 1; ++j) { + item = interleave_list->Next(item); + ASSERT_FALSE(item == NULL); + } + if (0 != interleave_list->Insert(item,insert_item)) { + interleave_list->DestroyListItem(insert_item); + FAIL(); + } + --insert_position; + } + + ListWrapperSimple* interleaved_list = CreateInterleavedList(rand()%2); + ASSERT_FALSE(interleaved_list == NULL); + ASSERT_FALSE(interleaved_list->Empty()); + + ASSERT_TRUE(CompareLists(interleaved_list,interleave_list)); +} + +// Use InsertBefore to interleave two lists. +TEST(ListWrapperTest,InterLeaveTestII) { + ListWrapperSimple* interleave_list = CreateDecendingList(rand()%2); + ASSERT_FALSE(interleave_list == NULL); + ASSERT_FALSE(interleave_list->Empty()); + + ListWrapperSimple* ascending_list = CreateAscendingList(rand()%2); + ASSERT_FALSE(ascending_list == NULL); + + for (int i = 0; i < kNumberOfElements/2; ++i) { + ASSERT_EQ(0,interleave_list->PopBack()); + ASSERT_EQ(0,ascending_list->PopBack()); + } + ASSERT_EQ(kNumberOfElements/2,interleave_list->GetSize()); + ASSERT_EQ(kNumberOfElements/2,ascending_list->GetSize()); + + int insert_position = kNumberOfElements/2; + ASSERT_EQ(insert_position * 2, kNumberOfElements); + while (!ascending_list->Empty()) + { + ListItem* item = ascending_list->Last(); + ASSERT_FALSE(item == NULL); + + const unsigned int item_id = ascending_list->GetUnsignedItem(item); + ASSERT_EQ(0,ascending_list->Erase(item)); + + ListItem* insert_item = interleave_list->CreateListItem(item_id); + ASSERT_FALSE(insert_item == NULL); + item = interleave_list->First(); + ASSERT_FALSE(item == NULL); + for (int j = 0; j < insert_position - 1; ++j) { + item = interleave_list->Next(item); + ASSERT_FALSE(item == NULL); + } + if (0 != interleave_list->InsertBefore(item,insert_item)) { + interleave_list->DestroyListItem(insert_item); + FAIL(); + } + --insert_position; + } + + ListWrapperSimple* interleaved_list = CreateInterleavedList(rand()%2); + ASSERT_FALSE(interleaved_list == NULL); + ASSERT_FALSE(interleaved_list->Empty()); + + ASSERT_TRUE(CompareLists(interleaved_list,interleave_list)); +} + +int main(int argc, char **argv) +{ + ::testing::InitGoogleTest(&argc, argv); + // Added return_value so that it's convenient to put a breakpoint before + // exiting please note that the return value from RUN_ALL_TESTS() must + // be returned by the main function. + const int return_value = RUN_ALL_TESTS(); + return return_value; +} diff --git a/src/system_wrappers/source/map.cc b/src/system_wrappers/source/map.cc new file mode 100644 index 0000000000..0bff155be4 --- /dev/null +++ b/src/system_wrappers/source/map.cc @@ -0,0 +1,166 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "map_wrapper.h" + +#include "trace.h" + +namespace webrtc { +MapItem::MapItem(int id, void* item) : item_pointer_(item), item_id_(id) +{ +} + +MapItem::~MapItem() +{ +} + +void* MapItem::GetItem() +{ + return item_pointer_; +} + +int MapItem::GetId() +{ + return item_id_; +} + +unsigned int MapItem::GetUnsignedId() +{ + return static_cast<unsigned int>(item_id_); +} + +void MapItem::SetItem(void* ptr) +{ + item_pointer_ = ptr; +} + +MapWrapper::MapWrapper() : map_() +{ +} + +MapWrapper::~MapWrapper() +{ + if (!map_.empty()) + { + WEBRTC_TRACE(kTraceMemory, kTraceUtility, -1, + "Potential memory leak in MapWrapper"); + // Remove all map items. Please note that std::map::clear() can't be + // used because each item has some dynamically allocated memory + // associated with it (i.e. using std::map::clear would introduce a + // memory leak). + while (Erase(First()) == 0) + {} + } +} + +int MapWrapper::Size() const +{ + return (int)map_.size(); +} + +int MapWrapper::Insert(int id, void* ptr) +{ + map_[id] = new MapItem(id,ptr); + return 0; +} + +MapItem* MapWrapper::First() const +{ + std::map<int, MapItem*>::const_iterator it = map_.begin(); + if (it != map_.end()) + { + return it->second; + } + return 0; +} + +MapItem* MapWrapper::Last() const +{ + std::map<int, MapItem*>::const_reverse_iterator it = map_.rbegin(); + if (it != map_.rend()) + { + return it->second; + } + return 0; +} + +MapItem* MapWrapper::Next(MapItem* item) const +{ + if (item == 0) + { + return 0; + } + std::map<int, MapItem*>::const_iterator it = map_.find(item->item_id_); + if (it != map_.end()) + { + it++; + if (it != map_.end()) + { + return it->second; + } + } + return 0; +} + +MapItem* MapWrapper::Previous(MapItem* item) const +{ + if (item == 0) + { + return 0; + } + + std::map<int, MapItem*>::const_iterator it = map_.find(item->item_id_); + if ((it != map_.end()) && + (it != map_.begin())) + { + --it; + return it->second; + } + return 0; +} + +MapItem* MapWrapper::Find(int id) const +{ + std::map<int, MapItem*>::const_iterator it = map_.find(id); + if (it != map_.end()) + { + return it->second; + } + return 0; +} + +int MapWrapper::Erase(MapItem* item) +{ + if (item == 0) + { + return -1; + } + std::map<int, MapItem*>::iterator it = map_.find(item->item_id_); + if (it != map_.end()) + { + delete it->second; + map_.erase(it); + return 0; + } + return -1; +} + +int MapWrapper::Erase(const int id) +{ + std::map<int, MapItem*>::iterator it = map_.find(id); + if (it != map_.end()) + { + delete it->second; + map_.erase(it); + return 0; + } + return -1; +} +} // namespace webrtc diff --git a/src/system_wrappers/source/map_no_stl.cc b/src/system_wrappers/source/map_no_stl.cc new file mode 100644 index 0000000000..cb0ac00296 --- /dev/null +++ b/src/system_wrappers/source/map_no_stl.cc @@ -0,0 +1,217 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "map_no_stl.h" + +#include "critical_section_wrapper.h" +#include "trace.h" + +namespace webrtc { +MapNoStlItem::MapNoStlItem(int id, void* item) + : next_(0), + prev_(0), + item_id_(id), + item_ptr_(item) +{ +} + +MapNoStlItem::~MapNoStlItem() +{ +} + +void* MapNoStlItem::GetItem() +{ + return item_ptr_; +} + +int MapNoStlItem::GetId() +{ + return item_id_; +} + +unsigned int MapNoStlItem::GetUnsignedId() +{ + return static_cast<unsigned int>(item_id_); +} + +void MapNoStlItem::SetItem(void* ptr) +{ + item_ptr_ = ptr; +} + +MapNoStl::MapNoStl() + : critical_section_(CriticalSectionWrapper::CreateCriticalSection()), + first_(0), + last_(0), + size_(0) +{ +} + +MapNoStl::~MapNoStl() +{ + if (First()) + { + WEBRTC_TRACE(kTraceMemory, kTraceUtility, -1, + "Potential memory leak in MapNoStl"); + while (Erase(First()) == 0) + {} + } + delete critical_section_; +} + +int MapNoStl::Size() const +{ + return size_; +} + +int MapNoStl::Insert(int id, void* ptr) +{ + MapNoStlItem* new_item = new MapNoStlItem(id, ptr); + + CriticalSectionScoped lock(*critical_section_); + MapNoStlItem* item = first_; + size_++; + if (!item) + { + first_ = new_item; + last_ = new_item; + return 0; + } + while(item->next_) + { + // Three scenarios + // 1. Item should be inserted first. + // 2. Item should be inserted between two items + // 3. Item should be inserted last + if (item->GetId() > id) + { + new_item->next_ = item; + item->prev_ = new_item; + if (item == first_) + { + first_ = new_item; + } + else + { + new_item->prev_ = item->prev_; + new_item->prev_->next_ = new_item; + } + return 0; + } + item = item->next_; + } + // 3 + item->next_ = new_item; + new_item->prev_ = item; + last_ = new_item; + return 0; +} + +MapNoStlItem* MapNoStl::First() const +{ + return first_; +} + +MapNoStlItem* MapNoStl::Last() const +{ + return last_; +} + +MapNoStlItem* MapNoStl::Next(MapNoStlItem* item) const +{ + if (!item) + { + return 0; + } + return item->next_; +} + +MapNoStlItem* MapNoStl::Previous(MapNoStlItem* item) const +{ + if (!item) + { + return 0; + } + return item->prev_; +} + +MapNoStlItem* MapNoStl::Find(int id) const +{ + CriticalSectionScoped lock(*critical_section_); + MapNoStlItem* item = Locate(id); + return item; +} + +int MapNoStl::Erase(MapNoStlItem* item) +{ + if(!item) + { + return -1; + } + CriticalSectionScoped lock(*critical_section_); + return Remove(item); +} + +int MapNoStl::Erase(const int id) +{ + CriticalSectionScoped lock(*critical_section_); + MapNoStlItem* item = Locate(id); + if(!item) + { + return -1; + } + return Remove(item); +} + +MapNoStlItem* MapNoStl::Locate(int id) const +{ + MapNoStlItem* item = first_; + while(item) + { + if (item->GetId() == id) + { + return item; + } + item = item->next_; + } + return 0; +} + +int MapNoStl::Remove(MapNoStlItem* item) +{ + if (!item) + { + return -1; + } + size_--; + MapNoStlItem* previous_item = item->prev_; + MapNoStlItem* next_item = item->next_; + if (!previous_item) + { + next_item->prev_ = 0; + first_ = next_item; + } + else + { + previous_item->next_ = next_item; + } + if (!next_item) + { + previous_item->next_ = 0; + last_ = previous_item; + } + else + { + next_item->prev_ = previous_item; + } + delete item; + return 0; +} +} // namespace webrtc diff --git a/src/system_wrappers/source/map_no_stl.h b/src/system_wrappers/source/map_no_stl.h new file mode 100644 index 0000000000..51bc011439 --- /dev/null +++ b/src/system_wrappers/source/map_no_stl.h @@ -0,0 +1,70 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_MAP_NO_STL_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_MAP_NO_STL_H_ + +#include "constructor_magic.h" + +namespace webrtc { +class CriticalSectionWrapper; + +class MapNoStlItem +{ +friend class Map; + +public: + MapNoStlItem(int id, void* ptr); + virtual ~MapNoStlItem(); + void* GetItem(); + int GetId(); + unsigned int GetUnsignedId(); + void SetItem(void* ptr); + +protected: + MapNoStlItem* next_; + MapNoStlItem* prev_; + +private: + int item_id_; + void* item_ptr_; + DISALLOW_COPY_AND_ASSIGN(MapNoStlItem); +}; + +class MapNoStl +{ +public: + MapNoStl(); + virtual ~MapNoStl(); + + // MapWrapper functions. + int Insert(int id, void* ptr); + int Erase(MapNoStlItem* item); + int Erase(int id); + int Size() const; + MapNoStlItem* First() const; + MapNoStlItem* Last() const; + MapNoStlItem* Next(MapNoStlItem* item) const; + MapNoStlItem* Previous(MapNoStlItem* item) const; + MapNoStlItem* Find(int id) const; + +private: + MapNoStlItem* Locate(int id) const; + int Remove(MapNoStlItem* item); + + CriticalSection* critical_section_; + MapNoStlItem* first_; + MapNoStlItem* last_; + int size_; + DISALLOW_COPY_AND_ASSIGN(MapNoStl); +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_MAP_NO_STL_H_ diff --git a/src/system_wrappers/source/map_unittest.cc b/src/system_wrappers/source/map_unittest.cc new file mode 100644 index 0000000000..8e8ea074a7 --- /dev/null +++ b/src/system_wrappers/source/map_unittest.cc @@ -0,0 +1,231 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "gtest/gtest.h" + +#include "map_wrapper.h" + +using ::webrtc::MapWrapper; +using ::webrtc::MapItem; + +const unsigned int kNumberOfElements = 10; + +int* ItemPointer(MapItem* item) { + if (item == NULL) { + return NULL; + } + return reinterpret_cast<int*>(item->GetItem()); +} + +bool DeleteItemContent(MapItem* item) { + if(item == NULL) { + return false; + } + int* value_ptr = ItemPointer(item); + delete value_ptr; + return true; +} + +int ItemValue(MapItem* item) { + if (item == NULL) { + return -1; + } + const int* value_ptr = ItemPointer(item); + if (value_ptr == 0) { + return -1; + } + return *value_ptr; +} + +void PrintToConsole(const char* message, bool supress) { + if (supress) { + return; + } + printf(message); +} + +bool CreateAscendingMap(MapWrapper* ascending_map) { + int* insert_value = NULL; + for (int i = 0; i < kNumberOfElements; ++i) { + insert_value = new int; + if (insert_value == NULL) { + return false; + } + *insert_value = i; + if (0 != ascending_map->Insert( + i, + reinterpret_cast<void*>(insert_value))) { + return false; + } + } + return true; +} + +bool ClearMap(MapWrapper* clear_map) { + bool success = true; + while (clear_map->Size() != 0) { + MapItem* remove_item = clear_map->First(); + if (remove_item == NULL) { + return false; + } + if (!DeleteItemContent(remove_item)) { + success = false; + } + if (clear_map->Erase(remove_item) != 0) { + return false; + } + } + return success; +} + +void PrintMapItem(MapItem* item, bool supress) { + const int id = item->GetId(); + const int value = ItemValue(item); + char print_buffer[16]; + sprintf(print_buffer, "(%3i,%3i) ", id, value); + PrintToConsole(print_buffer, supress); +} + +// Succeeds only if all the items were printed. +bool PrintMap(const MapWrapper& print_map, bool supress) { + const int elements_to_print = print_map.Size(); + int elements_printed = 0; + MapItem* item = print_map.First(); + PrintToConsole("[", supress); + while (item != NULL) { + PrintMapItem(item, supress); + ++elements_printed; + item = print_map.Next(item); + } + PrintToConsole("]\n", supress); + return elements_printed == elements_to_print; +} + +// Succeeds only if all the items were printed. +bool ReversePrintMap(const MapWrapper& print_map, bool supress) { + const int elements_to_print = print_map.Size(); + int elements_printed = 0; + MapItem* item = print_map.Last(); + PrintToConsole("[", supress); + while (item != NULL) { + PrintMapItem(item, supress); + ++elements_printed; + item = print_map.Previous(item); + } + PrintToConsole("]\n", supress); + return elements_printed == elements_to_print; +} + +// Returns true if the map items contain the same item. +bool CompareItems(MapItem* lhs_item, MapItem* rhs_item) { + if ((lhs_item == NULL) || (rhs_item == NULL)) { + return false; + } + if (lhs_item->GetId() != rhs_item->GetId()) { + return false; + } + return lhs_item->GetItem() == rhs_item->GetItem(); +} + +// Returns true if the map contains the same items. +bool CompareMaps(const MapWrapper& lhs, const MapWrapper& rhs) { + const int map_size = lhs.Size(); + if (map_size != rhs.Size()) { + return false; + } + int item_count = 0; + MapItem* lhs_item = lhs.First(); + while (lhs_item != NULL) { + MapItem* rhs_item = rhs.Find(lhs_item->GetId()); + if (rhs_item == NULL) { + return false; + } + if (!CompareItems(lhs_item, rhs_item)) { + return false; + } + ++item_count; + lhs_item = lhs.Next(lhs_item); + } + return item_count == map_size; +} + +class MapWrapperTest : public ::testing::Test { +protected: + virtual void SetUp() { + ASSERT_TRUE(CreateAscendingMap(&ascending_map_)); + } + + virtual void TearDown() { + EXPECT_TRUE(ClearMap(&ascending_map_)); + } + MapWrapper ascending_map_; +}; + +TEST_F(MapWrapperTest,RemoveTest) { + // Erase using int id + { // Create local scope to avoid accidental re-use + MapItem* item_first = ascending_map_.First(); + ASSERT_FALSE(item_first == NULL); + const int first_value_id = item_first->GetId(); + const int first_value = ItemValue(item_first); + EXPECT_TRUE(first_value == 0); + EXPECT_EQ(first_value_id,first_value); + EXPECT_FALSE(NULL == ascending_map_.Find(first_value_id)); + EXPECT_TRUE(DeleteItemContent(item_first)); + ascending_map_.Erase(first_value_id); + EXPECT_TRUE(NULL == ascending_map_.Find(first_value_id)); + EXPECT_EQ(kNumberOfElements-1,ascending_map_.Size()); + } + + // Erase using MapItem* item + MapItem* item_last = ascending_map_.Last(); + ASSERT_FALSE(item_last == NULL); + const int last_value_id = item_last->GetId(); + const int last_value = ItemValue(item_last); + EXPECT_TRUE(last_value == kNumberOfElements - 1); + EXPECT_EQ(last_value_id, last_value); + EXPECT_FALSE(NULL == ascending_map_.Find(last_value_id)); + EXPECT_TRUE(DeleteItemContent(item_last)); + ascending_map_.Erase(last_value_id); + EXPECT_TRUE(NULL == ascending_map_.Find(last_value_id)); + EXPECT_EQ(kNumberOfElements-2,ascending_map_.Size()); +} + +TEST_F(MapWrapperTest, PrintTest) { + const bool supress = true; // Don't spam the console + + EXPECT_TRUE(PrintMap(ascending_map_, supress)); + EXPECT_TRUE(ReversePrintMap(ascending_map_, supress)); +} + +TEST_F(MapWrapperTest, CopyTest) { + MapWrapper compare_map; + ASSERT_TRUE(CreateAscendingMap(&compare_map)); + const int map_size = compare_map.Size(); + ASSERT_EQ(ascending_map_.Size(), map_size); + // CompareMaps compare the pointers not value of the pointers. + // (the values are the same since both are ascending maps). + EXPECT_FALSE(CompareMaps(compare_map,ascending_map_)); + + int copy_count = 0; + MapItem* ascend_item = ascending_map_.First(); + while (ascend_item != NULL) { + MapItem* compare_item = compare_map.Find(ascend_item->GetId()); + ASSERT_FALSE(compare_item == NULL); + DeleteItemContent(compare_item); + compare_item->SetItem(ascend_item->GetItem()); + ascend_item = ascending_map_.Next(ascend_item); + ++copy_count; + } + EXPECT_TRUE(CompareMaps(compare_map,ascending_map_)); + while (compare_map.Erase(compare_map.First()) == 0) { + } + EXPECT_EQ(map_size, copy_count); +} diff --git a/src/system_wrappers/source/rw_lock.cc b/src/system_wrappers/source/rw_lock.cc new file mode 100644 index 0000000000..47901d346b --- /dev/null +++ b/src/system_wrappers/source/rw_lock.cc @@ -0,0 +1,46 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "rw_lock_wrapper.h" + +#include <assert.h> + +#if defined(_WIN32) + #include "rw_lock_windows.h" +#elif defined(ANDROID) + #include <stdlib.h> + #include "rw_lock_generic.h" +#else + #include "rw_lock_linux.h" +#endif + +namespace webrtc { +RWLockWrapper* RWLockWrapper::CreateRWLock() +{ +#ifdef _WIN32 + RWLockWrapper* lock = new RWLockWindows(); +#elif defined(ANDROID) + RWLockWrapper* lock = new RWLockWrapperGeneric(); +#else + RWLockWrapper* lock = new RWLockLinux(); +#endif + if(lock->Init() != 0) + { + delete lock; + assert(false); + return NULL; + } + return lock; +} + +RWLockWrapper::~RWLockWrapper() +{ +} +} // namespace webrtc diff --git a/src/system_wrappers/source/rw_lock_generic.cc b/src/system_wrappers/source/rw_lock_generic.cc new file mode 100644 index 0000000000..a468ef3b16 --- /dev/null +++ b/src/system_wrappers/source/rw_lock_generic.cc @@ -0,0 +1,106 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "rw_lock_generic.h" + +#include "condition_variable_wrapper.h" +#include "critical_section_wrapper.h" + +namespace webrtc { +RWLockWrapperGeneric::RWLockWrapperGeneric() + : _readersActive(0), + _writerActive(false), + _readersWaiting(0), + _writersWaiting(0) +{ + _critSectPtr = CriticalSectionWrapper::CreateCriticalSection(); + _readCondPtr = ConditionVariableWrapper::CreateConditionVariable(); + _writeCondPtr = ConditionVariableWrapper::CreateConditionVariable(); +} + +RWLockWrapperGeneric::~RWLockWrapperGeneric() +{ + delete _writeCondPtr; + delete _readCondPtr; + delete _critSectPtr; +} + +int RWLockWrapperGeneric::Init() +{ + return 0; +} + +void RWLockWrapperGeneric::AcquireLockExclusive() +{ + _critSectPtr->Enter(); + + if (_writerActive || _readersActive > 0) + { + ++_writersWaiting; + + while (_writerActive || _readersActive > 0) + { + _writeCondPtr->SleepCS(*_critSectPtr); + } + + --_writersWaiting; + } + _writerActive = true; + _critSectPtr->Leave(); +} + +void RWLockWrapperGeneric::ReleaseLockExclusive() +{ + _critSectPtr->Enter(); + + _writerActive = false; + + if (_writersWaiting > 0) + { + _writeCondPtr->Wake(); + + }else if (_readersWaiting > 0) + { + _readCondPtr->WakeAll(); + } + _critSectPtr->Leave(); +} + +void RWLockWrapperGeneric::AcquireLockShared() +{ + _critSectPtr->Enter(); + + if (_writerActive || _writersWaiting > 0) + { + ++_readersWaiting; + + while (_writerActive || _writersWaiting > 0) + { + _readCondPtr->SleepCS(*_critSectPtr); + } + --_readersWaiting; + } + ++_readersActive; + _critSectPtr->Leave(); +} + +void RWLockWrapperGeneric::ReleaseLockShared() +{ + _critSectPtr->Enter(); + + --_readersActive; + + if (_readersActive == 0 && _writersWaiting > 0) + { + _writeCondPtr->Wake(); + } + _critSectPtr->Leave(); +} +} // namespace webrtc diff --git a/src/system_wrappers/source/rw_lock_generic.h b/src/system_wrappers/source/rw_lock_generic.h new file mode 100644 index 0000000000..fff5e5d2ed --- /dev/null +++ b/src/system_wrappers/source/rw_lock_generic.h @@ -0,0 +1,46 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_RW_LOCK_GENERIC_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_RW_LOCK_GENERIC_H_ + +#include "rw_lock_wrapper.h" + +namespace webrtc { +class CriticalSectionWrapper; +class ConditionVariableWrapper; + +class RWLockWrapperGeneric : public RWLockWrapper +{ +public: + RWLockWrapperGeneric(); + virtual ~RWLockWrapperGeneric(); + + virtual void AcquireLockExclusive(); + virtual void ReleaseLockExclusive(); + + virtual void AcquireLockShared(); + virtual void ReleaseLockShared(); + +protected: + virtual int Init(); + +private: + CriticalSectionWrapper* _critSectPtr; + ConditionVariableWrapper* _readCondPtr; + ConditionVariableWrapper* _writeCondPtr; + + int _readersActive; + bool _writerActive; + int _readersWaiting; + int _writersWaiting; +}; +} // namespace webrtc +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_RW_LOCK_GENERIC_H_ diff --git a/src/system_wrappers/source/rw_lock_linux.cc b/src/system_wrappers/source/rw_lock_linux.cc new file mode 100644 index 0000000000..084dce8618 --- /dev/null +++ b/src/system_wrappers/source/rw_lock_linux.cc @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "rw_lock_linux.h" + +namespace webrtc { +RWLockLinux::RWLockLinux() : _lock() +{ +} + +RWLockLinux::~RWLockLinux() +{ + pthread_rwlock_destroy(&_lock); +} + +int RWLockLinux::Init() +{ + return pthread_rwlock_init(&_lock, 0); +} + +void RWLockLinux::AcquireLockExclusive() +{ + pthread_rwlock_wrlock(&_lock); +} + +void RWLockLinux::ReleaseLockExclusive() +{ + pthread_rwlock_unlock(&_lock); +} + +void RWLockLinux::AcquireLockShared() +{ + pthread_rwlock_rdlock(&_lock); +} + +void RWLockLinux::ReleaseLockShared() +{ + pthread_rwlock_unlock(&_lock); +} +} // namespace webrtc diff --git a/src/system_wrappers/source/rw_lock_linux.h b/src/system_wrappers/source/rw_lock_linux.h new file mode 100644 index 0000000000..391ee8fe61 --- /dev/null +++ b/src/system_wrappers/source/rw_lock_linux.h @@ -0,0 +1,39 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_RW_LOCK_LINUX_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_RW_LOCK_LINUX_H_ + +#include "rw_lock_wrapper.h" + +#include <pthread.h> + +namespace webrtc { +class RWLockLinux : public RWLockWrapper +{ +public: + RWLockLinux(); + virtual ~RWLockLinux(); + + virtual void AcquireLockExclusive(); + virtual void ReleaseLockExclusive(); + + virtual void AcquireLockShared(); + virtual void ReleaseLockShared(); + +protected: + virtual int Init(); + +private: + pthread_rwlock_t _lock; +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_RW_LOCK_LINUX_H_ diff --git a/src/system_wrappers/source/sort.cc b/src/system_wrappers/source/sort.cc new file mode 100644 index 0000000000..f44b644978 --- /dev/null +++ b/src/system_wrappers/source/sort.cc @@ -0,0 +1,551 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +// When the platform supports STL, the functions are implemented using a +// templated spreadsort algorithm (http://sourceforge.net/projects/spreadsort/), +// part of the Boost C++ library collection. Otherwise, the C standard library's +// qsort() will be used. + +#include "sort.h" + +#include <cassert> +#include <cstring> // memcpy +#include <new> // nothrow new + +#ifdef NO_STL +#include <cstdlib> // qsort +#else +#include <algorithm> // std::sort +#include <vector> +#include "spreadsort.hpp" // TODO (ajm) upgrade to spreadsortv2. +#endif + +#ifdef NO_STL +#define COMPARE_DEREFERENCED(XT, YT) \ + do \ + { \ + if ((XT) > (YT)) \ + { \ + return 1; \ + } \ + else if ((XT) < (YT)) \ + { \ + return -1; \ + } \ + \ + return 0; \ + } \ + while(0) + +#define COMPARE_FOR_QSORT(X, Y, TYPE) \ + do \ + { \ + TYPE xT = static_cast<TYPE>(*static_cast<const TYPE*>(X)); \ + TYPE yT = static_cast<TYPE>(*static_cast<const TYPE*>(Y)); \ + COMPARE_DEREFERENCED(xT, yT); \ + } \ + while(0) + +#define COMPARE_KEY_FOR_QSORT(SORT_KEY_X, SORT_KEY_Y, TYPE) \ + do \ + { \ + TYPE xT = static_cast<TYPE>(*static_cast<TYPE*> \ + (static_cast<const SortKey*>(SORT_KEY_X)->key)); \ + TYPE yT = static_cast<TYPE>(*static_cast<TYPE*> \ + (static_cast<const SortKey*>(SORT_KEY_Y)->key)); \ + COMPARE_DEREFERENCED(xT, yT); \ + } \ + while(0) + +#define KEY_QSORT(SORT_KEY, KEY, NUM_OF_ELEMENTS, KEY_TYPE, COMPARE_FUNC) \ + do \ + { \ + KEY_TYPE* keyT = (KEY_TYPE*)(key); \ + for (WebRtc_UWord32 i = 0; i < (NUM_OF_ELEMENTS); i++) \ + { \ + ptrSortKey[i].key = &keyT[i]; \ + ptrSortKey[i].index = i; \ + } \ + \ + qsort((SORT_KEY), (NUM_OF_ELEMENTS), sizeof(SortKey), (COMPARE_FUNC));\ + } \ + while(0) +#endif + +namespace webrtc +{ +#ifdef NO_STL + struct SortKey + { + void* key; + WebRtc_UWord32 index; + }; +#else + template<typename KeyType> + struct SortKey + { + KeyType key; + WebRtc_UWord32 index; + }; +#endif + + namespace // Unnamed namespace provides internal linkage. + { +#ifdef NO_STL + int CompareWord8(const void* x, const void* y) + { + COMPARE_FOR_QSORT(x, y, WebRtc_Word8); + } + + int CompareUWord8(const void* x, const void* y) + { + COMPARE_FOR_QSORT(x, y, WebRtc_UWord8); + } + + int CompareWord16(const void* x, const void* y) + { + COMPARE_FOR_QSORT(x, y, WebRtc_Word16); + } + + int CompareUWord16(const void* x, const void* y) + { + COMPARE_FOR_QSORT(x, y, WebRtc_UWord16); + } + + int CompareWord32(const void* x, const void* y) + { + COMPARE_FOR_QSORT(x, y, WebRtc_Word32); + } + + int CompareUWord32(const void* x, const void* y) + { + COMPARE_FOR_QSORT(x, y, WebRtc_UWord32); + } + + int CompareWord64(const void* x, const void* y) + { + COMPARE_FOR_QSORT(x, y, WebRtc_Word64); + } + + int CompareUWord64(const void* x, const void* y) + { + COMPARE_FOR_QSORT(x, y, WebRtc_UWord64); + } + + int CompareFloat32(const void* x, const void* y) + { + COMPARE_FOR_QSORT(x, y, float); + } + + int CompareFloat64(const void* x, const void* y) + { + COMPARE_FOR_QSORT(x, y, double); + } + + int CompareKeyWord8(const void* sortKeyX, const void* sortKeyY) + { + COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word8); + } + + int CompareKeyUWord8(const void* sortKeyX, const void* sortKeyY) + { + COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord8); + } + + int CompareKeyWord16(const void* sortKeyX, const void* sortKeyY) + { + COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word16); + } + + int CompareKeyUWord16(const void* sortKeyX, const void* sortKeyY) + { + COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord16); + } + + int CompareKeyWord32(const void* sortKeyX, const void* sortKeyY) + { + COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word32); + } + + int CompareKeyUWord32(const void* sortKeyX, const void* sortKeyY) + { + COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord32); + } + + int CompareKeyWord64(const void* sortKeyX, const void* sortKeyY) + { + COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_Word64); + } + + int CompareKeyUWord64(const void* sortKeyX, const void* sortKeyY) + { + COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, WebRtc_UWord64); + } + + int CompareKeyFloat32(const void* sortKeyX, const void* sortKeyY) + { + COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, float); + } + + int CompareKeyFloat64(const void* sortKeyX, const void* sortKeyY) + { + COMPARE_KEY_FOR_QSORT(sortKeyX, sortKeyY, double); + } +#else + template <typename KeyType> + struct KeyLessThan + { + bool operator()(const SortKey<KeyType>& sortKeyX, + const SortKey<KeyType>& sortKeyY) const + { + return sortKeyX.key < sortKeyY.key; + } + }; + + template <typename KeyType> + struct KeyRightShift + { + KeyType operator()(const SortKey<KeyType>& sortKey, + const unsigned offset) const + { + return sortKey.key >> offset; + } + }; + + template <typename DataType> + inline void IntegerSort(void* data, WebRtc_UWord32 numOfElements) + { + DataType* dataT = static_cast<DataType*>(data); + boost::integer_sort(dataT, dataT + numOfElements); + } + + template <typename DataType, typename IntegerType> + inline void FloatSort(void* data, WebRtc_UWord32 numOfElements) + { + DataType* dataT = static_cast<DataType*>(data); + IntegerType cVal = 0; + boost::float_sort_cast(dataT, dataT + numOfElements, cVal); + } + + template <typename DataType> + inline void StdSort(void* data, WebRtc_UWord32 numOfElements) + { + DataType* dataT = static_cast<DataType*>(data); + std::sort(dataT, dataT + numOfElements); + } + + template<typename KeyType> + inline WebRtc_Word32 SetupKeySort(void* key, + SortKey<KeyType>*& ptrSortKey, + WebRtc_UWord32 numOfElements) + { + ptrSortKey = new(std::nothrow) SortKey<KeyType>[numOfElements]; + if (ptrSortKey == NULL) + { + return -1; + } + + KeyType* keyT = static_cast<KeyType*>(key); + for (WebRtc_UWord32 i = 0; i < numOfElements; i++) + { + ptrSortKey[i].key = keyT[i]; + ptrSortKey[i].index = i; + } + + return 0; + } + + template<typename KeyType> + inline WebRtc_Word32 TeardownKeySort(void* data, + SortKey<KeyType>* ptrSortKey, + WebRtc_UWord32 numOfElements, WebRtc_UWord32 sizeOfElement) + { + WebRtc_UWord8* ptrData = static_cast<WebRtc_UWord8*>(data); + WebRtc_UWord8* ptrDataSorted = new(std::nothrow) WebRtc_UWord8 + [numOfElements * sizeOfElement]; + if (ptrDataSorted == NULL) + { + return -1; + } + + for (WebRtc_UWord32 i = 0; i < numOfElements; i++) + { + memcpy(ptrDataSorted + i * sizeOfElement, ptrData + + ptrSortKey[i].index * sizeOfElement, sizeOfElement); + } + memcpy(ptrData, ptrDataSorted, numOfElements * sizeOfElement); + delete[] ptrSortKey; + delete[] ptrDataSorted; + return 0; + } + + template<typename KeyType> + inline WebRtc_Word32 IntegerKeySort(void* data, void* key, + WebRtc_UWord32 numOfElements, + WebRtc_UWord32 sizeOfElement) + { + SortKey<KeyType>* ptrSortKey; + if (SetupKeySort<KeyType>(key, ptrSortKey, numOfElements) != 0) + { + return -1; + } + + boost::integer_sort(ptrSortKey, ptrSortKey + numOfElements, + KeyRightShift<KeyType>(), KeyLessThan<KeyType>()); + + if (TeardownKeySort<KeyType>(data, ptrSortKey, numOfElements, + sizeOfElement) != 0) + { + return -1; + } + + return 0; + } + + template<typename KeyType> + inline WebRtc_Word32 StdKeySort(void* data, void* key, + WebRtc_UWord32 numOfElements, + WebRtc_UWord32 sizeOfElement) + { + SortKey<KeyType>* ptrSortKey; + if (SetupKeySort<KeyType>(key, ptrSortKey, numOfElements) != 0) + { + return -1; + } + + std::sort(ptrSortKey, ptrSortKey + numOfElements, + KeyLessThan<KeyType>()); + + if (TeardownKeySort<KeyType>(data, ptrSortKey, numOfElements, + sizeOfElement) != 0) + { + return -1; + } + + return 0; + } +#endif + } + + WebRtc_Word32 Sort(void* data, WebRtc_UWord32 numOfElements, Type type) + { + if (data == NULL) + { + return -1; + } + +#ifdef NO_STL + switch (type) + { + case TYPE_Word8: + qsort(data, numOfElements, sizeof(WebRtc_Word8), CompareWord8); + break; + case TYPE_UWord8: + qsort(data, numOfElements, sizeof(WebRtc_UWord8), CompareUWord8); + break; + case TYPE_Word16: + qsort(data, numOfElements, sizeof(WebRtc_Word16), CompareWord16); + break; + case TYPE_UWord16: + qsort(data, numOfElements, sizeof(WebRtc_UWord16), CompareUWord16); + break; + case TYPE_Word32: + qsort(data, numOfElements, sizeof(WebRtc_Word32), CompareWord32); + break; + case TYPE_UWord32: + qsort(data, numOfElements, sizeof(WebRtc_UWord32), CompareUWord32); + break; + case TYPE_Word64: + qsort(data, numOfElements, sizeof(WebRtc_Word64), CompareWord64); + break; + case TYPE_UWord64: + qsort(data, numOfElements, sizeof(WebRtc_UWord64), CompareUWord64); + break; + case TYPE_Float32: + qsort(data, numOfElements, sizeof(float), CompareFloat32); + break; + case TYPE_Float64: + qsort(data, numOfElements, sizeof(double), CompareFloat64); + break; + default: + return -1; + } +#else + // Fall back to std::sort for 64-bit types and floats due to compiler + // warnings and VS 2003 build crashes respectively with spreadsort. + switch (type) + { + case TYPE_Word8: + IntegerSort<WebRtc_Word8>(data, numOfElements); + break; + case TYPE_UWord8: + IntegerSort<WebRtc_UWord8>(data, numOfElements); + break; + case TYPE_Word16: + IntegerSort<WebRtc_Word16>(data, numOfElements); + break; + case TYPE_UWord16: + IntegerSort<WebRtc_UWord16>(data, numOfElements); + break; + case TYPE_Word32: + IntegerSort<WebRtc_Word32>(data, numOfElements); + break; + case TYPE_UWord32: + IntegerSort<WebRtc_UWord32>(data, numOfElements); + break; + case TYPE_Word64: + StdSort<WebRtc_Word64>(data, numOfElements); + break; + case TYPE_UWord64: + StdSort<WebRtc_UWord64>(data, numOfElements); + break; + case TYPE_Float32: + StdSort<float>(data, numOfElements); + break; + case TYPE_Float64: + StdSort<double>(data, numOfElements); + break; + default: + return -1; + } +#endif + return 0; + } + + WebRtc_Word32 KeySort(void* data, void* key, WebRtc_UWord32 numOfElements, + WebRtc_UWord32 sizeOfElement, Type keyType) + { + if (data == NULL) + { + return -1; + } + + if (key == NULL) + { + return -1; + } + + if ((WebRtc_UWord64)numOfElements * sizeOfElement > 0xffffffff) + { + return -1; + } + +#ifdef NO_STL + SortKey* ptrSortKey = new(std::nothrow) SortKey[numOfElements]; + if (ptrSortKey == NULL) + { + return -1; + } + + switch (keyType) + { + case TYPE_Word8: + KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word8, + CompareKeyWord8); + break; + case TYPE_UWord8: + KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord8, + CompareKeyUWord8); + break; + case TYPE_Word16: + KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word16, + CompareKeyWord16); + break; + case TYPE_UWord16: + KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord16, + CompareKeyUWord16); + break; + case TYPE_Word32: + KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word32, + CompareKeyWord32); + break; + case TYPE_UWord32: + KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord32, + CompareKeyUWord32); + break; + case TYPE_Word64: + KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_Word64, + CompareKeyWord64); + break; + case TYPE_UWord64: + KEY_QSORT(ptrSortKey, key, numOfElements, WebRtc_UWord64, + CompareKeyUWord64); + break; + case TYPE_Float32: + KEY_QSORT(ptrSortKey, key, numOfElements, float, + CompareKeyFloat32); + break; + case TYPE_Float64: + KEY_QSORT(ptrSortKey, key, numOfElements, double, + CompareKeyFloat64); + break; + default: + return -1; + } + + // Shuffle into sorted position based on index map. + WebRtc_UWord8* ptrData = static_cast<WebRtc_UWord8*>(data); + WebRtc_UWord8* ptrDataSorted = new(std::nothrow) WebRtc_UWord8 + [numOfElements * sizeOfElement]; + if (ptrDataSorted == NULL) + { + return -1; + } + + for (WebRtc_UWord32 i = 0; i < numOfElements; i++) + { + memcpy(ptrDataSorted + i * sizeOfElement, ptrData + + ptrSortKey[i].index * sizeOfElement, sizeOfElement); + } + memcpy(ptrData, ptrDataSorted, numOfElements * sizeOfElement); + + delete[] ptrSortKey; + delete[] ptrDataSorted; + + return 0; +#else + // Fall back to std::sort for 64-bit types and floats due to compiler + // warnings and errors respectively with spreadsort. + switch (keyType) + { + case TYPE_Word8: + return IntegerKeySort<WebRtc_Word8>(data, key, numOfElements, + sizeOfElement); + case TYPE_UWord8: + return IntegerKeySort<WebRtc_UWord8>(data, key, numOfElements, + sizeOfElement); + case TYPE_Word16: + return IntegerKeySort<WebRtc_Word16>(data, key, numOfElements, + sizeOfElement); + case TYPE_UWord16: + return IntegerKeySort<WebRtc_UWord16>(data, key, numOfElements, + sizeOfElement); + case TYPE_Word32: + return IntegerKeySort<WebRtc_Word32>(data, key, numOfElements, + sizeOfElement); + case TYPE_UWord32: + return IntegerKeySort<WebRtc_UWord32>(data, key, numOfElements, + sizeOfElement); + case TYPE_Word64: + return StdKeySort<WebRtc_Word64>(data, key, numOfElements, + sizeOfElement); + case TYPE_UWord64: + return StdKeySort<WebRtc_UWord64>(data, key, numOfElements, + sizeOfElement); + case TYPE_Float32: + return StdKeySort<float>(data, key, numOfElements, sizeOfElement); + case TYPE_Float64: + return StdKeySort<double>(data, key, numOfElements, sizeOfElement); + default: + return -1; + } +#endif + } +} // namespace webrtc diff --git a/src/system_wrappers/source/spreadsortlib/constants.hpp b/src/system_wrappers/source/spreadsortlib/constants.hpp new file mode 100644 index 0000000000..fa81ece869 --- /dev/null +++ b/src/system_wrappers/source/spreadsortlib/constants.hpp @@ -0,0 +1,42 @@ +/*Boost Software License - Version 1.0 - August 17th, 2003
+
+Permission is hereby granted, free of charge, to any person or organization
+obtaining a copy of the software and accompanying documentation covered by
+this license (the "Software") to use, reproduce, display, distribute,
+execute, and transmit the Software, and to prepare derivative works of the
+Software, and to permit third-parties to whom the Software is furnished to
+do so, all subject to the following:
+
+The copyright notices in the Software and this entire statement, including
+the above license grant, this restriction and the following disclaimer,
+must be included in all copies of the Software, in whole or in part, and
+all derivative works of the Software, unless such copies or derivative
+works are solely in the form of machine-executable object code generated by
+a source language processor.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
+SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
+FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
+ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+DEALINGS IN THE SOFTWARE.*/
+#ifndef BOOST_SPREADSORT_CONSTANTS
+#define BOOST_SPREADSORT_CONSTANTS
+namespace boost {
+namespace detail {
+//Tuning constants
+//Sets the minimum number of items per bin.
+static const unsigned LOG_MEAN_BIN_SIZE = 2;
+//This should be tuned to your processor cache; if you go too large you get cache misses on bins
+//The smaller this number, the less worst-case memory usage. If too small, too many recursions slow down spreadsort
+static const unsigned MAX_SPLITS = 10;
+//Used to force a comparison-based sorting for small bins, if it's faster. Minimum value 0
+static const unsigned LOG_MIN_SPLIT_COUNT = 5;
+//There is a minimum size below which it is not worth using spreadsort
+static const long MIN_SORT_SIZE = 1000;
+//This is the constant on the log base n of m calculation; make this larger the faster std::sort is relative to spreadsort
+static const unsigned LOG_CONST = 2;
+}
+}
+#endif
diff --git a/src/system_wrappers/source/spreadsortlib/spreadsort.hpp b/src/system_wrappers/source/spreadsortlib/spreadsort.hpp new file mode 100644 index 0000000000..2d1529aacd --- /dev/null +++ b/src/system_wrappers/source/spreadsortlib/spreadsort.hpp @@ -0,0 +1,1688 @@ +//Templated spread_sort library
+
+// Copyright Steven J. Ross 2001 - 2009.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
+/*
+Some improvements suggested by:
+Phil Endecott and Frank Gennari
+Cygwin fix provided by:
+Scott McMurray
+*/
+
+#ifndef BOOST_SPREAD_SORT_H
+#define BOOST_SPREAD_SORT_H
+#include <algorithm>
+#include <vector>
+#include "constants.hpp"
+#include <cstring>
+
+namespace boost {
+ namespace detail {
+ //This only works on unsigned data types
+ template <typename T>
+ inline unsigned
+ rough_log_2_size(const T& input)
+ {
+ unsigned result = 0;
+ //The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance
+ while((input >> result) && (result < (8*sizeof(T)))) ++result;
+ return result;
+ }
+
+ //Gets the maximum size which we'll call spread_sort on to control worst-case performance
+ //Maintains both a minimum size to recurse and a check of distribution size versus count
+ //This is called for a set of bins, instead of bin-by-bin, to avoid performance overhead
+ inline size_t
+ get_max_count(unsigned log_range, size_t count)
+ {
+ unsigned divisor = rough_log_2_size(count);
+ //Making sure the divisor is positive
+ if(divisor > LOG_MEAN_BIN_SIZE)
+ divisor -= LOG_MEAN_BIN_SIZE;
+ else
+ divisor = 1;
+ unsigned relative_width = (LOG_CONST * log_range)/((divisor > MAX_SPLITS) ? MAX_SPLITS : divisor);
+ //Don't try to bitshift more than the size of an element
+ if((8*sizeof(size_t)) <= relative_width)
+ relative_width = (8*sizeof(size_t)) - 1;
+ return (size_t)1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT)) ?
+ (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) : relative_width);
+ }
+
+ //Find the minimum and maximum using <
+ template <class RandomAccessIter>
+ inline void
+ find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min)
+ {
+ min = max = current;
+ //Start from the second item, as max and min are initialized to the first
+ while(++current < last) {
+ if(*max < *current)
+ max = current;
+ else if(*current < *min)
+ min = current;
+ }
+ }
+
+ //Uses a user-defined comparison operator to find minimum and maximum
+ template <class RandomAccessIter, class compare>
+ inline void
+ find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAccessIter & max, RandomAccessIter & min, compare comp)
+ {
+ min = max = current;
+ while(++current < last) {
+ if(comp(*max, *current))
+ max = current;
+ else if(comp(*current, *min))
+ min = current;
+ }
+ }
+
+ //Gets a non-negative right bit shift to operate as a logarithmic divisor
+ inline int
+ get_log_divisor(size_t count, unsigned log_range)
+ {
+ int log_divisor;
+ //If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so
+ if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && log_range < MAX_SPLITS)
+ log_divisor = 0;
+ else {
+ //otherwise divide the data into an optimized number of pieces
+ log_divisor += LOG_MEAN_BIN_SIZE;
+ if(log_divisor < 0)
+ log_divisor = 0;
+ //Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically
+ if((log_range - log_divisor) > MAX_SPLITS)
+ log_divisor = log_range - MAX_SPLITS;
+ }
+ return log_divisor;
+ }
+
+ template <class RandomAccessIter>
+ inline RandomAccessIter *
+ size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
+ {
+ //Assure space for the size of each bin, followed by initializing sizes
+ if(bin_count > bin_sizes.size())
+ bin_sizes.resize(bin_count);
+ for(size_t u = 0; u < bin_count; u++)
+ bin_sizes[u] = 0;
+ //Make sure there is space for the bins
+ cache_end = cache_offset + bin_count;
+ if(cache_end > bin_cache.size())
+ bin_cache.resize(cache_end);
+ return &(bin_cache[cache_offset]);
+ }
+
+ //Implementation for recursive integer sorting
+ template <class RandomAccessIter, class div_type, class data_type>
+ inline void
+ spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+ , std::vector<size_t> &bin_sizes)
+ {
+ //This step is roughly 10% of runtime, but it helps avoid worst-case behavior and improve behavior with real data
+ //If you know the maximum and minimum ahead of time, you can pass those values in and skip this step for the first iteration
+ RandomAccessIter max, min;
+ find_extremes(first, last, max, min);
+ //max and min will be the same (the first item) iff all values are equivalent
+ if(max == min)
+ return;
+ RandomAccessIter * target_bin;
+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(*max >> 0) - (*min >> 0)));
+ div_type div_min = *min >> log_divisor;
+ div_type div_max = *max >> log_divisor;
+ unsigned bin_count = div_max - div_min + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+
+ //Calculating the size of each bin; this takes roughly 10% of runtime
+ for (RandomAccessIter current = first; current != last;)
+ bin_sizes[(*(current++) >> log_divisor) - div_min]++;
+ //Assign the bin positions
+ bins[0] = first;
+ for(unsigned u = 0; u < bin_count - 1; u++)
+ bins[u + 1] = bins[u] + bin_sizes[u];
+
+ //Swap into place
+ //This dominates runtime, mostly in the swap and bin lookups
+ RandomAccessIter nextbinstart = first;
+ for(unsigned u = 0; u < bin_count - 1; ++u) {
+ RandomAccessIter * local_bin = bins + u;
+ nextbinstart += bin_sizes[u];
+ //Iterating over each element in this bin
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ //Swapping elements in current into place until the correct element has been swapped in
+ for(target_bin = (bins + ((*current >> log_divisor) - div_min)); target_bin != local_bin;
+ target_bin = bins + ((*current >> log_divisor) - div_min)) {
+ //3-way swap; this is about 1% faster than a 2-way swap with integers
+ //The main advantage is less copies are involved per item put in the correct place
+ data_type tmp;
+ RandomAccessIter b = (*target_bin)++;
+ RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min);
+ if (b_bin != local_bin) {
+ RandomAccessIter c = (*b_bin)++;
+ tmp = *c;
+ *c = *b;
+ }
+ else
+ tmp = *b;
+ *b = *current;
+ *current = tmp;
+ }
+ }
+ *local_bin = nextbinstart;
+ }
+ bins[bin_count - 1] = last;
+
+ //If we've bucketsorted, the array is sorted and we should skip recursion
+ if(!log_divisor)
+ return;
+
+ //Recursing; log_divisor is the remaining range
+ size_t max_count = get_max_count(log_divisor, last - first);
+ RandomAccessIter lastPos = first;
+ for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ //don't sort unless there are at least two items to compare
+ if(count < 2)
+ continue;
+ //using std::sort if its worst-case is better
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[u]);
+ else
+ spread_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
+ }
+ }
+
+ //Generic bitshift-based 3-way swapping code
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+ inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
+ , const unsigned log_divisor, const div_type div_min)
+ {
+ RandomAccessIter * local_bin = bins + ii;
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ for(RandomAccessIter * target_bin = (bins + (shift(*current, log_divisor) - div_min)); target_bin != local_bin;
+ target_bin = bins + (shift(*current, log_divisor) - div_min)) {
+ data_type tmp;
+ RandomAccessIter b = (*target_bin)++;
+ RandomAccessIter * b_bin = bins + (shift(*b, log_divisor) - div_min);
+ //Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
+ if (b_bin != local_bin) {
+ RandomAccessIter c = (*b_bin)++;
+ tmp = *c;
+ *c = *b;
+ }
+ //Note: we could increment current once the swap is done in this case, but that seems to impair performance
+ else
+ tmp = *b;
+ *b = *current;
+ *current = tmp;
+ }
+ }
+ *local_bin = nextbinstart;
+ }
+
+ //Standard swapping wrapper for ascending values
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+ inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii, right_shift &shift
+ , const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min)
+ {
+ nextbinstart += bin_sizes[ii];
+ inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, log_divisor, div_min);
+ }
+
+ //Functor implementation for recursive sorting
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+ inline void
+ spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+ , std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
+ {
+ RandomAccessIter max, min;
+ find_extremes(first, last, max, min, comp);
+ if(max == min)
+ return;
+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
+ div_type div_min = shift(*min, log_divisor);
+ div_type div_max = shift(*max, log_divisor);
+ unsigned bin_count = div_max - div_min + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+
+ //Calculating the size of each bin
+ for (RandomAccessIter current = first; current != last;)
+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+ bins[0] = first;
+ for(unsigned u = 0; u < bin_count - 1; u++)
+ bins[u + 1] = bins[u] + bin_sizes[u];
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ for(unsigned u = 0; u < bin_count - 1; ++u)
+ swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min);
+ bins[bin_count - 1] = last;
+
+ //If we've bucketsorted, the array is sorted and we should skip recursion
+ if(!log_divisor)
+ return;
+
+ //Recursing
+ size_t max_count = get_max_count(log_divisor, last - first);
+ RandomAccessIter lastPos = first;
+ for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[u], comp);
+ else
+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
+ }
+ }
+
+ //Functor implementation for recursive sorting with only Shift overridden
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+ inline void
+ spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+ , std::vector<size_t> &bin_sizes, right_shift shift)
+ {
+ RandomAccessIter max, min;
+ find_extremes(first, last, max, min);
+ if(max == min)
+ return;
+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(shift(*max, 0)) - (shift(*min, 0))));
+ div_type div_min = shift(*min, log_divisor);
+ div_type div_max = shift(*max, log_divisor);
+ unsigned bin_count = div_max - div_min + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+
+ //Calculating the size of each bin
+ for (RandomAccessIter current = first; current != last;)
+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+ bins[0] = first;
+ for(unsigned u = 0; u < bin_count - 1; u++)
+ bins[u + 1] = bins[u] + bin_sizes[u];
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ for(unsigned ii = 0; ii < bin_count - 1; ++ii)
+ swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
+ bins[bin_count - 1] = last;
+
+ //If we've bucketsorted, the array is sorted and we should skip recursion
+ if(!log_divisor)
+ return;
+
+ //Recursing
+ size_t max_count = get_max_count(log_divisor, last - first);
+ RandomAccessIter lastPos = first;
+ for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[u]);
+ else
+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
+ }
+ }
+
+ //Holds the bin vector and makes the initial recursive call
+ template <class RandomAccessIter, class div_type, class data_type>
+ inline void
+ spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type)
+ {
+ std::vector<size_t> bin_sizes;
+ std::vector<RandomAccessIter> bin_cache;
+ spread_sort_rec<RandomAccessIter, div_type, data_type>(first, last, bin_cache, 0, bin_sizes);
+ }
+
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+ inline void
+ spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
+ {
+ std::vector<size_t> bin_sizes;
+ std::vector<RandomAccessIter> bin_cache;
+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp);
+ }
+
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+ inline void
+ spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
+ {
+ std::vector<size_t> bin_sizes;
+ std::vector<RandomAccessIter> bin_cache;
+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
+ }
+ }
+
+ //Top-level sorting call for integers
+ template <class RandomAccessIter>
+ inline void integer_sort(RandomAccessIter first, RandomAccessIter last)
+ {
+ //Don't sort if it's too small to optimize
+ if(last - first < detail::MIN_SORT_SIZE)
+ std::sort(first, last);
+ else
+ detail::spread_sort(first, last, *first >> 0, *first);
+ }
+
+ //integer_sort with functors
+ template <class RandomAccessIter, class right_shift, class compare>
+ inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
+ right_shift shift, compare comp) {
+ if(last - first < detail::MIN_SORT_SIZE)
+ std::sort(first, last, comp);
+ else
+ detail::spread_sort(first, last, shift(*first, 0), *first, shift, comp);
+ }
+
+ //integer_sort with right_shift functor
+ template <class RandomAccessIter, class right_shift>
+ inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
+ right_shift shift) {
+ if(last - first < detail::MIN_SORT_SIZE)
+ std::sort(first, last);
+ else
+ detail::spread_sort(first, last, shift(*first, 0), *first, shift);
+ }
+
+ //------------------------------------------------------ float_sort source --------------------------------------
+ //Casts a RandomAccessIter to the specified data type
+ template<class cast_type, class RandomAccessIter>
+ inline cast_type
+ cast_float_iter(const RandomAccessIter & floatiter)
+ {
+ cast_type result;
+ std::memcpy(&result, &(*floatiter), sizeof(cast_type));
+ return result;
+ }
+
+ //Casts a data element to the specified datinner_float_a type
+ template<class data_type, class cast_type>
+ inline cast_type
+ mem_cast(const data_type & data)
+ {
+ cast_type result;
+ std::memcpy(&result, &data, sizeof(cast_type));
+ return result;
+ }
+
+ namespace detail {
+ template <class RandomAccessIter, class div_type, class right_shift>
+ inline void
+ find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift)
+ {
+ min = max = shift(*current, 0);
+ while(++current < last) {
+ div_type value = shift(*current, 0);
+ if(max < value)
+ max = value;
+ else if(value < min)
+ min = value;
+ }
+ }
+
+ //Specialized swap loops for floating-point casting
+ template <class RandomAccessIter, class div_type, class data_type>
+ inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomAccessIter & nextbinstart, unsigned ii
+ , const unsigned log_divisor, const div_type div_min)
+ {
+ RandomAccessIter * local_bin = bins + ii;
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ for(RandomAccessIter * target_bin = (bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)); target_bin != local_bin;
+ target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) {
+ data_type tmp;
+ RandomAccessIter b = (*target_bin)++;
+ RandomAccessIter * b_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(b) >> log_divisor) - div_min);
+ //Three-way swap; if the item to be swapped doesn't belong in the current bin, swap it to where it belongs
+ if (b_bin != local_bin) {
+ RandomAccessIter c = (*b_bin)++;
+ tmp = *c;
+ *c = *b;
+ }
+ else
+ tmp = *b;
+ *b = *current;
+ *current = tmp;
+ }
+ }
+ *local_bin = nextbinstart;
+ }
+
+ template <class RandomAccessIter, class div_type, class data_type>
+ inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii
+ , const std::vector<size_t> &bin_sizes, const unsigned log_divisor, const div_type div_min)
+ {
+ nextbinstart += bin_sizes[ii];
+ inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, log_divisor, div_min);
+ }
+
+ template <class RandomAccessIter, class cast_type>
+ inline void
+ find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min)
+ {
+ min = max = cast_float_iter<cast_type, RandomAccessIter>(current);
+ while(++current < last) {
+ cast_type value = cast_float_iter<cast_type, RandomAccessIter>(current);
+ if(max < value)
+ max = value;
+ else if(value < min)
+ min = value;
+ }
+ }
+
+ //Special-case sorting of positive floats with casting instead of a right_shift
+ template <class RandomAccessIter, class div_type, class data_type>
+ inline void
+ positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+ , std::vector<size_t> &bin_sizes)
+ {
+ div_type max, min;
+ find_extremes(first, last, max, min);
+ if(max == min)
+ return;
+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+ div_type div_min = min >> log_divisor;
+ div_type div_max = max >> log_divisor;
+ unsigned bin_count = div_max - div_min + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+
+ //Calculating the size of each bin
+ for (RandomAccessIter current = first; current != last;)
+ bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
+ bins[0] = first;
+ for(unsigned u = 0; u < bin_count - 1; u++)
+ bins[u + 1] = bins[u] + bin_sizes[u];
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ for(unsigned u = 0; u < bin_count - 1; ++u)
+ float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, bin_sizes, log_divisor, div_min);
+ bins[bin_count - 1] = last;
+
+ //Return if we've completed bucketsorting
+ if(!log_divisor)
+ return;
+
+ //Recursing
+ size_t max_count = get_max_count(log_divisor, last - first);
+ RandomAccessIter lastPos = first;
+ for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[u]);
+ else
+ positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
+ }
+ }
+
+ //Sorting negative_ float_s
+ //Note that bins are iterated in reverse order because max_neg_float = min_neg_int
+ template <class RandomAccessIter, class div_type, class data_type>
+ inline void
+ negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+ , std::vector<size_t> &bin_sizes)
+ {
+ div_type max, min;
+ find_extremes(first, last, max, min);
+ if(max == min)
+ return;
+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+ div_type div_min = min >> log_divisor;
+ div_type div_max = max >> log_divisor;
+ unsigned bin_count = div_max - div_min + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+
+ //Calculating the size of each bin
+ for (RandomAccessIter current = first; current != last;)
+ bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
+ bins[bin_count - 1] = first;
+ for(int ii = bin_count - 2; ii >= 0; --ii)
+ bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ //The last bin will always have the correct elements in it
+ for(int ii = bin_count - 1; ii > 0; --ii)
+ float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, ii, bin_sizes, log_divisor, div_min);
+ //Since we don't process the last bin, we need to update its end position
+ bin_cache[cache_offset] = last;
+
+ //Return if we've completed bucketsorting
+ if(!log_divisor)
+ return;
+
+ //Recursing
+ size_t max_count = get_max_count(log_divisor, last - first);
+ RandomAccessIter lastPos = first;
+ for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
+ size_t count = bin_cache[ii] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[ii]);
+ else
+ negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
+ }
+ }
+
+ //Sorting negative_ float_s
+ //Note that bins are iterated in reverse order because max_neg_float = min_neg_int
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+ inline void
+ negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+ , std::vector<size_t> &bin_sizes, right_shift shift)
+ {
+ div_type max, min;
+ find_extremes(first, last, max, min, shift);
+ if(max == min)
+ return;
+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+ div_type div_min = min >> log_divisor;
+ div_type div_max = max >> log_divisor;
+ unsigned bin_count = div_max - div_min + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+
+ //Calculating the size of each bin
+ for (RandomAccessIter current = first; current != last;)
+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+ bins[bin_count - 1] = first;
+ for(int ii = bin_count - 2; ii >= 0; --ii)
+ bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ //The last bin will always have the correct elements in it
+ for(int ii = bin_count - 1; ii > 0; --ii)
+ swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
+ //Since we don't process the last bin, we need to update its end position
+ bin_cache[cache_offset] = last;
+
+ //Return if we've completed bucketsorting
+ if(!log_divisor)
+ return;
+
+ //Recursing
+ size_t max_count = get_max_count(log_divisor, last - first);
+ RandomAccessIter lastPos = first;
+ for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
+ size_t count = bin_cache[ii] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[ii]);
+ else
+ negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
+ }
+ }
+
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+ inline void
+ negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+ , std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
+ {
+ div_type max, min;
+ find_extremes(first, last, max, min, shift);
+ if(max == min)
+ return;
+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+ div_type div_min = min >> log_divisor;
+ div_type div_max = max >> log_divisor;
+ unsigned bin_count = div_max - div_min + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+
+ //Calculating the size of each bin
+ for (RandomAccessIter current = first; current != last;)
+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+ bins[bin_count - 1] = first;
+ for(int ii = bin_count - 2; ii >= 0; --ii)
+ bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ //The last bin will always have the correct elements in it
+ for(int ii = bin_count - 1; ii > 0; --ii)
+ swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);
+ //Since we don't process the last bin, we need to update its end position
+ bin_cache[cache_offset] = last;
+
+ //Return if we've completed bucketsorting
+ if(!log_divisor)
+ return;
+
+ //Recursing
+ size_t max_count = get_max_count(log_divisor, last - first);
+ RandomAccessIter lastPos = first;
+ for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = bin_cache[ii], --ii) {
+ size_t count = bin_cache[ii] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[ii], comp);
+ else
+ negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
+ }
+ }
+
+ //Casting special-case for floating-point sorting
+ template <class RandomAccessIter, class div_type, class data_type>
+ inline void
+ float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+ , std::vector<size_t> &bin_sizes)
+ {
+ div_type max, min;
+ find_extremes(first, last, max, min);
+ if(max == min)
+ return;
+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+ div_type div_min = min >> log_divisor;
+ div_type div_max = max >> log_divisor;
+ unsigned bin_count = div_max - div_min + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+
+ //Calculating the size of each bin
+ for (RandomAccessIter current = first; current != last;)
+ bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(current++) >> log_divisor) - div_min]++;
+ //The index of the first positive bin
+ div_type first_positive = (div_min < 0) ? -div_min : 0;
+ //Resetting if all bins are negative
+ if(cache_offset + first_positive > cache_end)
+ first_positive = cache_end - cache_offset;
+ //Reversing the order of the negative bins
+ //Note that because of the negative/positive ordering direction flip
+ //We can not depend upon bin order and positions matching up
+ //so bin_sizes must be reused to contain the end of the bin
+ if(first_positive > 0) {
+ bins[first_positive - 1] = first;
+ for(int ii = first_positive - 2; ii >= 0; --ii) {
+ bins[ii] = first + bin_sizes[ii + 1];
+ bin_sizes[ii] += bin_sizes[ii + 1];
+ }
+ //Handling positives following negatives
+ if((unsigned)first_positive < bin_count) {
+ bins[first_positive] = first + bin_sizes[0];
+ bin_sizes[first_positive] += bin_sizes[0];
+ }
+ }
+ else
+ bins[0] = first;
+ for(unsigned u = first_positive; u < bin_count - 1; u++) {
+ bins[u + 1] = first + bin_sizes[u];
+ bin_sizes[u + 1] += bin_sizes[u];
+ }
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ for(unsigned u = 0; u < bin_count; ++u) {
+ nextbinstart = first + bin_sizes[u];
+ inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bins, nextbinstart, u, log_divisor, div_min);
+ }
+
+ if(!log_divisor)
+ return;
+
+ //Handling negative values first
+ size_t max_count = get_max_count(log_divisor, last - first);
+ RandomAccessIter lastPos = first;
+ for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
+ size_t count = bin_cache[ii] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[ii]);
+ //sort negative values using reversed-bin spread_sort
+ else
+ negative_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);
+ }
+
+ for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[u]);
+ //sort positive values using normal spread_sort
+ else
+ positive_float_sort_rec<RandomAccessIter, div_type, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);
+ }
+ }
+
+ //Functor implementation for recursive sorting
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+ inline void
+ float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+ , std::vector<size_t> &bin_sizes, right_shift shift)
+ {
+ div_type max, min;
+ find_extremes(first, last, max, min, shift);
+ if(max == min)
+ return;
+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+ div_type div_min = min >> log_divisor;
+ div_type div_max = max >> log_divisor;
+ unsigned bin_count = div_max - div_min + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+
+ //Calculating the size of each bin
+ for (RandomAccessIter current = first; current != last;)
+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+ //The index of the first positive bin
+ div_type first_positive = (div_min < 0) ? -div_min : 0;
+ //Resetting if all bins are negative
+ if(cache_offset + first_positive > cache_end)
+ first_positive = cache_end - cache_offset;
+ //Reversing the order of the negative bins
+ //Note that because of the negative/positive ordering direction flip
+ //We can not depend upon bin order and positions matching up
+ //so bin_sizes must be reused to contain the end of the bin
+ if(first_positive > 0) {
+ bins[first_positive - 1] = first;
+ for(int ii = first_positive - 2; ii >= 0; --ii) {
+ bins[ii] = first + bin_sizes[ii + 1];
+ bin_sizes[ii] += bin_sizes[ii + 1];
+ }
+ //Handling positives following negatives
+ if((unsigned)first_positive < bin_count) {
+ bins[first_positive] = first + bin_sizes[0];
+ bin_sizes[first_positive] += bin_sizes[0];
+ }
+ }
+ else
+ bins[0] = first;
+ for(unsigned u = first_positive; u < bin_count - 1; u++) {
+ bins[u + 1] = first + bin_sizes[u];
+ bin_sizes[u + 1] += bin_sizes[u];
+ }
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ for(unsigned u = 0; u < bin_count; ++u) {
+ nextbinstart = first + bin_sizes[u];
+ inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
+ }
+
+ //Return if we've completed bucketsorting
+ if(!log_divisor)
+ return;
+
+ //Handling negative values first
+ size_t max_count = get_max_count(log_divisor, last - first);
+ RandomAccessIter lastPos = first;
+ for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
+ size_t count = bin_cache[ii] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[ii]);
+ //sort negative values using reversed-bin spread_sort
+ else
+ negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift);
+ }
+
+ for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[u]);
+ //sort positive values using normal spread_sort
+ else
+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift);
+ }
+ }
+
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+ inline void
+ float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
+ , std::vector<size_t> &bin_sizes, right_shift shift, compare comp)
+ {
+ div_type max, min;
+ find_extremes(first, last, max, min, shift);
+ if(max == min)
+ return;
+ unsigned log_divisor = get_log_divisor(last - first, rough_log_2_size((size_t)(max) - min));
+ div_type div_min = min >> log_divisor;
+ div_type div_max = max >> log_divisor;
+ unsigned bin_count = div_max - div_min + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
+
+ //Calculating the size of each bin
+ for (RandomAccessIter current = first; current != last;)
+ bin_sizes[shift(*(current++), log_divisor) - div_min]++;
+ //The index of the first positive bin
+ div_type first_positive = (div_min < 0) ? -div_min : 0;
+ //Resetting if all bins are negative
+ if(cache_offset + first_positive > cache_end)
+ first_positive = cache_end - cache_offset;
+ //Reversing the order of the negative bins
+ //Note that because of the negative/positive ordering direction flip
+ //We can not depend upon bin order and positions matching up
+ //so bin_sizes must be reused to contain the end of the bin
+ if(first_positive > 0) {
+ bins[first_positive - 1] = first;
+ for(int ii = first_positive - 2; ii >= 0; --ii) {
+ bins[ii] = first + bin_sizes[ii + 1];
+ bin_sizes[ii] += bin_sizes[ii + 1];
+ }
+ //Handling positives following negatives
+ if((unsigned)first_positive < bin_count) {
+ bins[first_positive] = first + bin_sizes[0];
+ bin_sizes[first_positive] += bin_sizes[0];
+ }
+ }
+ else
+ bins[0] = first;
+ for(unsigned u = first_positive; u < bin_count - 1; u++) {
+ bins[u + 1] = first + bin_sizes[u];
+ bin_sizes[u + 1] += bin_sizes[u];
+ }
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ for(unsigned u = 0; u < bin_count; ++u) {
+ nextbinstart = first + bin_sizes[u];
+ inner_swap_loop<RandomAccessIter, div_type, data_type, right_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);
+ }
+
+ //Return if we've completed bucketsorting
+ if(!log_divisor)
+ return;
+
+ //Handling negative values first
+ size_t max_count = get_max_count(log_divisor, last - first);
+ RandomAccessIter lastPos = first;
+ for(int ii = cache_offset + first_positive - 1; ii >= (int)cache_offset ; lastPos = bin_cache[ii--]) {
+ size_t count = bin_cache[ii] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[ii]);
+ //sort negative values using reversed-bin spread_sort
+ else
+ negative_float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes, shift, comp);
+ }
+
+ for(unsigned u = cache_offset + first_positive; u < cache_end; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ if(count < 2)
+ continue;
+ if(count < max_count)
+ std::sort(lastPos, bin_cache[u]);
+ //sort positive values using normal spread_sort
+ else
+ spread_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shift, comp);
+ }
+ }
+
+ template <class RandomAccessIter, class cast_type, class data_type>
+ inline void
+ float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, data_type)
+ {
+ std::vector<size_t> bin_sizes;
+ std::vector<RandomAccessIter> bin_cache;
+ float_sort_rec<RandomAccessIter, cast_type, data_type>(first, last, bin_cache, 0, bin_sizes);
+ }
+
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift>
+ inline void
+ float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift)
+ {
+ std::vector<size_t> bin_sizes;
+ std::vector<RandomAccessIter> bin_cache;
+ float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift);
+ }
+
+ template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>
+ inline void
+ float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data_type, right_shift shift, compare comp)
+ {
+ std::vector<size_t> bin_sizes;
+ std::vector<RandomAccessIter> bin_cache;
+ float_sort_rec<RandomAccessIter, div_type, data_type, right_shift>(first, last, bin_cache, 0, bin_sizes, shift, comp);
+ }
+ }
+
+ //float_sort with casting
+ //The cast_type must be equal in size to the data type, and must be a signed integer
+ template <class RandomAccessIter, class cast_type>
+ inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cast_type cVal)
+ {
+ if(last - first < detail::MIN_SORT_SIZE)
+ std::sort(first, last);
+ else
+ detail::float_Sort(first, last, cVal, *first);
+ }
+
+ //float_sort with casting to an int
+ //Only use this with IEEE floating-point numbers
+ template <class RandomAccessIter>
+ inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter last)
+ {
+ int cVal = 0;
+ float_sort_cast(first, last, cVal);
+ }
+
+ //float_sort with functors
+ template <class RandomAccessIter, class right_shift>
+ inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift)
+ {
+ if(last - first < detail::MIN_SORT_SIZE)
+ std::sort(first, last);
+ else
+ detail::float_Sort(first, last, shift(*first, 0), *first, shift);
+ }
+
+ template <class RandomAccessIter, class right_shift, class compare>
+ inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_shift shift, compare comp)
+ {
+ if(last - first < detail::MIN_SORT_SIZE)
+ std::sort(first, last, comp);
+ else
+ detail::float_Sort(first, last, shift(*first, 0), *first, shift, comp);
+ }
+
+ //------------------------------------------------- string_sort source ---------------------------------------------
+ namespace detail {
+ //Offsetting on identical characters. This function works a character at a time for optimal worst-case performance.
+ template<class RandomAccessIter>
+ inline void
+ update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset)
+ {
+ unsigned nextOffset = char_offset;
+ bool done = false;
+ while(!done) {
+ RandomAccessIter curr = first;
+ do {
+ //ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
+ if((*curr).size() > char_offset && ((*curr).size() <= (nextOffset + 1) || (*curr)[nextOffset] != (*first)[nextOffset])) {
+ done = true;
+ break;
+ }
+ } while(++curr != finish);
+ if(!done)
+ ++nextOffset;
+ }
+ char_offset = nextOffset;
+ }
+
+ //Offsetting on identical characters. This function works a character at a time for optimal worst-case performance.
+ template<class RandomAccessIter, class get_char, class get_length>
+ inline void
+ update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length)
+ {
+ unsigned nextOffset = char_offset;
+ bool done = false;
+ while(!done) {
+ RandomAccessIter curr = first;
+ do {
+ //ignore empties, but if the nextOffset would exceed the length or not match, exit; we've found the last matching character
+ if(length(*curr) > char_offset && (length(*curr) <= (nextOffset + 1) || getchar((*curr), nextOffset) != getchar((*first), nextOffset))) {
+ done = true;
+ break;
+ }
+ } while(++curr != finish);
+ if(!done)
+ ++nextOffset;
+ }
+ char_offset = nextOffset;
+ }
+
+ //A comparison functor for strings that assumes they are identical up to char_offset
+ template<class data_type, class unsignedchar_type>
+ struct offset_lessthan {
+ offset_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
+ inline bool operator()(const data_type &x, const data_type &y) const
+ {
+ unsigned minSize = std::min(x.size(), y.size());
+ for(unsigned u = fchar_offset; u < minSize; ++u) {
+ if(static_cast<unsignedchar_type>(x[u]) < static_cast<unsignedchar_type>(y[u]))
+ return true;
+ else if(static_cast<unsignedchar_type>(y[u]) < static_cast<unsignedchar_type>(x[u]))
+ return false;
+ }
+ return x.size() < y.size();
+ }
+ unsigned fchar_offset;
+ };
+
+ //A comparison functor for strings that assumes they are identical up to char_offset
+ template<class data_type, class unsignedchar_type>
+ struct offset_greaterthan {
+ offset_greaterthan(unsigned char_offset) : fchar_offset(char_offset){}
+ inline bool operator()(const data_type &x, const data_type &y) const
+ {
+ unsigned minSize = std::min(x.size(), y.size());
+ for(unsigned u = fchar_offset; u < minSize; ++u) {
+ if(static_cast<unsignedchar_type>(x[u]) > static_cast<unsignedchar_type>(y[u]))
+ return true;
+ else if(static_cast<unsignedchar_type>(y[u]) > static_cast<unsignedchar_type>(x[u]))
+ return false;
+ }
+ return x.size() > y.size();
+ }
+ unsigned fchar_offset;
+ };
+
+ //A comparison functor for strings that assumes they are identical up to char_offset
+ template<class data_type, class get_char, class get_length>
+ struct offset_char_lessthan {
+ offset_char_lessthan(unsigned char_offset) : fchar_offset(char_offset){}
+ inline bool operator()(const data_type &x, const data_type &y) const
+ {
+ unsigned minSize = std::min(length(x), length(y));
+ for(unsigned u = fchar_offset; u < minSize; ++u) {
+ if(getchar(x, u) < getchar(y, u))
+ return true;
+ else if(getchar(y, u) < getchar(x, u))
+ return false;
+ }
+ return length(x) < length(y);
+ }
+ unsigned fchar_offset;
+ get_char getchar;
+ get_length length;
+ };
+
+ //String sorting recursive implementation
+ template <class RandomAccessIter, class data_type, class unsignedchar_type>
+ inline void
+ string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+ , unsigned cache_offset, std::vector<size_t> &bin_sizes)
+ {
+ //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+ //Iterate to the end of the empties. If all empty, return
+ while((*first).size() <= char_offset) {
+ if(++first == last)
+ return;
+ }
+ RandomAccessIter finish = last - 1;
+ //Getting the last non-empty
+ for(;(*finish).size() <= char_offset; --finish) { }
+ ++finish;
+ //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
+ update_offset(first, finish, char_offset);
+
+ const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+ //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+ const unsigned max_size = bin_count;
+ const unsigned membin_count = bin_count + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
+
+ //Calculating the size of each bin; this takes roughly 10% of runtime
+ for (RandomAccessIter current = first; current != last; ++current) {
+ if((*current).size() <= char_offset) {
+ bin_sizes[0]++;
+ }
+ else
+ bin_sizes[static_cast<unsignedchar_type>((*current)[char_offset]) + 1]++;
+ }
+ //Assign the bin positions
+ bin_cache[cache_offset] = first;
+ for(unsigned u = 0; u < membin_count - 1; u++)
+ bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ //handling empty bins
+ RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
+ nextbinstart += bin_sizes[0];
+ RandomAccessIter * target_bin;
+ //Iterating over each element in the bin of empties
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ //empties belong in this bin
+ while((*current).size() > char_offset) {
+ target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]);
+ iter_swap(current, (*target_bin)++);
+ }
+ }
+ *local_bin = nextbinstart;
+ //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+ unsigned last_bin = bin_count - 1;
+ for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
+ //This dominates runtime, mostly in the swap and bin lookups
+ for(unsigned u = 0; u < last_bin; ++u) {
+ local_bin = bins + u;
+ nextbinstart += bin_sizes[u + 1];
+ //Iterating over each element in this bin
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ //Swapping elements in current into place until the correct element has been swapped in
+ for(target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]); target_bin != local_bin;
+ target_bin = bins + static_cast<unsignedchar_type>((*current)[char_offset]))
+ iter_swap(current, (*target_bin)++);
+ }
+ *local_bin = nextbinstart;
+ }
+ bins[last_bin] = last;
+ //Recursing
+ RandomAccessIter lastPos = bin_cache[cache_offset];
+ //Skip this loop for empties
+ for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ //don't sort unless there are at least two items to compare
+ if(count < 2)
+ continue;
+ //using std::sort if its worst-case is better
+ if(count < max_size)
+ std::sort(lastPos, bin_cache[u], offset_lessthan<data_type, unsignedchar_type>(char_offset + 1));
+ else
+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
+ }
+ }
+
+ //Sorts strings in reverse order, with empties at the end
+ template <class RandomAccessIter, class data_type, class unsignedchar_type>
+ inline void
+ reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+ , unsigned cache_offset, std::vector<size_t> &bin_sizes)
+ {
+ //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+ RandomAccessIter curr = first;
+ //Iterate to the end of the empties. If all empty, return
+ while((*curr).size() <= char_offset) {
+ if(++curr == last)
+ return;
+ }
+ //Getting the last non-empty
+ while((*(--last)).size() <= char_offset) { }
+ ++last;
+ //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
+ update_offset(curr, last, char_offset);
+ RandomAccessIter * target_bin;
+
+ const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+ //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+ const unsigned max_size = bin_count;
+ const unsigned membin_count = bin_count + 1;
+ const unsigned max_bin = bin_count - 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
+ RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin]);
+
+ //Calculating the size of each bin; this takes roughly 10% of runtime
+ for (RandomAccessIter current = first; current != last; ++current) {
+ if((*current).size() <= char_offset) {
+ bin_sizes[bin_count]++;
+ }
+ else
+ bin_sizes[max_bin - static_cast<unsignedchar_type>((*current)[char_offset])]++;
+ }
+ //Assign the bin positions
+ bin_cache[cache_offset] = first;
+ for(unsigned u = 0; u < membin_count - 1; u++)
+ bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+
+ //Swap into place
+ RandomAccessIter nextbinstart = last;
+ //handling empty bins
+ RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
+ RandomAccessIter lastFull = *local_bin;
+ //Iterating over each element in the bin of empties
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ //empties belong in this bin
+ while((*current).size() > char_offset) {
+ target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]);
+ iter_swap(current, (*target_bin)++);
+ }
+ }
+ *local_bin = nextbinstart;
+ nextbinstart = first;
+ //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+ unsigned last_bin = max_bin;
+ for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
+ //This dominates runtime, mostly in the swap and bin lookups
+ for(unsigned u = 0; u < last_bin; ++u) {
+ local_bin = bins + u;
+ nextbinstart += bin_sizes[u];
+ //Iterating over each element in this bin
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ //Swapping elements in current into place until the correct element has been swapped in
+ for(target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]); target_bin != local_bin;
+ target_bin = end_bin - static_cast<unsignedchar_type>((*current)[char_offset]))
+ iter_swap(current, (*target_bin)++);
+ }
+ *local_bin = nextbinstart;
+ }
+ bins[last_bin] = lastFull;
+ //Recursing
+ RandomAccessIter lastPos = first;
+ //Skip this loop for empties
+ for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ //don't sort unless there are at least two items to compare
+ if(count < 2)
+ continue;
+ //using std::sort if its worst-case is better
+ if(count < max_size)
+ std::sort(lastPos, bin_cache[u], offset_greaterthan<data_type, unsignedchar_type>(char_offset + 1));
+ else
+ reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes);
+ }
+ }
+
+ //String sorting recursive implementation
+ template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length>
+ inline void
+ string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+ , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length)
+ {
+ //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+ //Iterate to the end of the empties. If all empty, return
+ while(length(*first) <= char_offset) {
+ if(++first == last)
+ return;
+ }
+ RandomAccessIter finish = last - 1;
+ //Getting the last non-empty
+ for(;length(*finish) <= char_offset; --finish) { }
+ ++finish;
+ update_offset(first, finish, char_offset, getchar, length);
+
+ const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+ //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+ const unsigned max_size = bin_count;
+ const unsigned membin_count = bin_count + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
+
+ //Calculating the size of each bin; this takes roughly 10% of runtime
+ for (RandomAccessIter current = first; current != last; ++current) {
+ if(length(*current) <= char_offset) {
+ bin_sizes[0]++;
+ }
+ else
+ bin_sizes[getchar((*current), char_offset) + 1]++;
+ }
+ //Assign the bin positions
+ bin_cache[cache_offset] = first;
+ for(unsigned u = 0; u < membin_count - 1; u++)
+ bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ //handling empty bins
+ RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
+ nextbinstart += bin_sizes[0];
+ RandomAccessIter * target_bin;
+ //Iterating over each element in the bin of empties
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ //empties belong in this bin
+ while(length(*current) > char_offset) {
+ target_bin = bins + getchar((*current), char_offset);
+ iter_swap(current, (*target_bin)++);
+ }
+ }
+ *local_bin = nextbinstart;
+ //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+ unsigned last_bin = bin_count - 1;
+ for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
+ //This dominates runtime, mostly in the swap and bin lookups
+ for(unsigned ii = 0; ii < last_bin; ++ii) {
+ local_bin = bins + ii;
+ nextbinstart += bin_sizes[ii + 1];
+ //Iterating over each element in this bin
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ //Swapping elements in current into place until the correct element has been swapped in
+ for(target_bin = bins + getchar((*current), char_offset); target_bin != local_bin;
+ target_bin = bins + getchar((*current), char_offset))
+ iter_swap(current, (*target_bin)++);
+ }
+ *local_bin = nextbinstart;
+ }
+ bins[last_bin] = last;
+
+ //Recursing
+ RandomAccessIter lastPos = bin_cache[cache_offset];
+ //Skip this loop for empties
+ for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ //don't sort unless there are at least two items to compare
+ if(count < 2)
+ continue;
+ //using std::sort if its worst-case is better
+ if(count < max_size)
+ std::sort(lastPos, bin_cache[u], offset_char_lessthan<data_type, get_char, get_length>(char_offset + 1));
+ else
+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length);
+ }
+ }
+
+ //String sorting recursive implementation
+ template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
+ inline void
+ string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+ , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
+ {
+ //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+ //Iterate to the end of the empties. If all empty, return
+ while(length(*first) <= char_offset) {
+ if(++first == last)
+ return;
+ }
+ RandomAccessIter finish = last - 1;
+ //Getting the last non-empty
+ for(;length(*finish) <= char_offset; --finish) { }
+ ++finish;
+ update_offset(first, finish, char_offset, getchar, length);
+
+ const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+ //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+ const unsigned max_size = bin_count;
+ const unsigned membin_count = bin_count + 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count) + 1;
+
+ //Calculating the size of each bin; this takes roughly 10% of runtime
+ for (RandomAccessIter current = first; current != last; ++current) {
+ if(length(*current) <= char_offset) {
+ bin_sizes[0]++;
+ }
+ else
+ bin_sizes[getchar((*current), char_offset) + 1]++;
+ }
+ //Assign the bin positions
+ bin_cache[cache_offset] = first;
+ for(unsigned u = 0; u < membin_count - 1; u++)
+ bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+
+ //Swap into place
+ RandomAccessIter nextbinstart = first;
+ //handling empty bins
+ RandomAccessIter * local_bin = &(bin_cache[cache_offset]);
+ nextbinstart += bin_sizes[0];
+ RandomAccessIter * target_bin;
+ //Iterating over each element in the bin of empties
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ //empties belong in this bin
+ while(length(*current) > char_offset) {
+ target_bin = bins + getchar((*current), char_offset);
+ iter_swap(current, (*target_bin)++);
+ }
+ }
+ *local_bin = nextbinstart;
+ //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+ unsigned last_bin = bin_count - 1;
+ for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }
+ //This dominates runtime, mostly in the swap and bin lookups
+ for(unsigned u = 0; u < last_bin; ++u) {
+ local_bin = bins + u;
+ nextbinstart += bin_sizes[u + 1];
+ //Iterating over each element in this bin
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ //Swapping elements in current into place until the correct element has been swapped in
+ for(target_bin = bins + getchar((*current), char_offset); target_bin != local_bin;
+ target_bin = bins + getchar((*current), char_offset))
+ iter_swap(current, (*target_bin)++);
+ }
+ *local_bin = nextbinstart;
+ }
+ bins[last_bin] = last;
+
+ //Recursing
+ RandomAccessIter lastPos = bin_cache[cache_offset];
+ //Skip this loop for empties
+ for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ //don't sort unless there are at least two items to compare
+ if(count < 2)
+ continue;
+ //using std::sort if its worst-case is better
+ if(count < max_size)
+ std::sort(lastPos, bin_cache[u], comp);
+ else
+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
+ , bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
+ }
+ }
+
+ //Sorts strings in reverse order, with empties at the end
+ template <class RandomAccessIter, class data_type, class unsignedchar_type, class get_char, class get_length, class compare>
+ inline void
+ reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache
+ , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_char getchar, get_length length, compare comp)
+ {
+ //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.
+ RandomAccessIter curr = first;
+ //Iterate to the end of the empties. If all empty, return
+ while(length(*curr) <= char_offset) {
+ if(++curr == last)
+ return;
+ }
+ //Getting the last non-empty
+ while(length(*(--last)) <= char_offset) { }
+ ++last;
+ //Offsetting on identical characters. This section works a character at a time for optimal worst-case performance.
+ update_offset(first, last, char_offset, getchar, length);
+
+ const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));
+ //Equal worst-case between radix and comparison-based is when bin_count = n*log(n).
+ const unsigned max_size = bin_count;
+ const unsigned membin_count = bin_count + 1;
+ const unsigned max_bin = bin_count - 1;
+ unsigned cache_end;
+ RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset, cache_end, membin_count);
+ RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]);
+
+ //Calculating the size of each bin; this takes roughly 10% of runtime
+ for (RandomAccessIter current = first; current != last; ++current) {
+ if(length(*current) <= char_offset) {
+ bin_sizes[bin_count]++;
+ }
+ else
+ bin_sizes[max_bin - getchar((*current), char_offset)]++;
+ }
+ //Assign the bin positions
+ bin_cache[cache_offset] = first;
+ for(unsigned u = 0; u < membin_count - 1; u++)
+ bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];
+
+ //Swap into place
+ RandomAccessIter nextbinstart = last;
+ //handling empty bins
+ RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_count]);
+ RandomAccessIter lastFull = *local_bin;
+ RandomAccessIter * target_bin;
+ //Iterating over each element in the bin of empties
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ //empties belong in this bin
+ while(length(*current) > char_offset) {
+ target_bin = end_bin - getchar((*current), char_offset);
+ iter_swap(current, (*target_bin)++);
+ }
+ }
+ *local_bin = nextbinstart;
+ nextbinstart = first;
+ //iterate backwards to find the last bin with elements in it; this saves iterations in multiple loops
+ unsigned last_bin = max_bin;
+ for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }
+ //This dominates runtime, mostly in the swap and bin lookups
+ for(unsigned u = 0; u < last_bin; ++u) {
+ local_bin = bins + u;
+ nextbinstart += bin_sizes[u];
+ //Iterating over each element in this bin
+ for(RandomAccessIter current = *local_bin; current < nextbinstart; ++current) {
+ //Swapping elements in current into place until the correct element has been swapped in
+ for(target_bin = end_bin - getchar((*current), char_offset); target_bin != local_bin;
+ target_bin = end_bin - getchar((*current), char_offset))
+ iter_swap(current, (*target_bin)++);
+ }
+ *local_bin = nextbinstart;
+ }
+ bins[last_bin] = lastFull;
+ //Recursing
+ RandomAccessIter lastPos = first;
+ //Skip this loop for empties
+ for(unsigned u = cache_offset; u <= cache_offset + last_bin; lastPos = bin_cache[u], ++u) {
+ size_t count = bin_cache[u] - lastPos;
+ //don't sort unless there are at least two items to compare
+ if(count < 2)
+ continue;
+ //using std::sort if its worst-case is better
+ if(count < max_size)
+ std::sort(lastPos, bin_cache[u], comp);
+ else
+ reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(lastPos
+ , bin_cache[u], char_offset + 1, bin_cache, cache_end, bin_sizes, getchar, length, comp);
+ }
+ }
+
+ //Holds the bin vector and makes the initial recursive call
+ template <class RandomAccessIter, class data_type, class unsignedchar_type>
+ inline void
+ string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
+ {
+ std::vector<size_t> bin_sizes;
+ std::vector<RandomAccessIter> bin_cache;
+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
+ }
+
+ //Holds the bin vector and makes the initial recursive call
+ template <class RandomAccessIter, class data_type, class unsignedchar_type>
+ inline void
+ reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_type, unsignedchar_type)
+ {
+ std::vector<size_t> bin_sizes;
+ std::vector<RandomAccessIter> bin_cache;
+ reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>(first, last, 0, bin_cache, 0, bin_sizes);
+ }
+
+ //Holds the bin vector and makes the initial recursive call
+ template <class RandomAccessIter, class get_char, class get_length, class data_type, class unsignedchar_type>
+ inline void
+ string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, data_type, unsignedchar_type)
+ {
+ std::vector<size_t> bin_sizes;
+ std::vector<RandomAccessIter> bin_cache;
+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length);
+ }
+
+ //Holds the bin vector and makes the initial recursive call
+ template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
+ inline void
+ string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
+ {
+ std::vector<size_t> bin_sizes;
+ std::vector<RandomAccessIter> bin_cache;
+ string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
+ }
+
+ //Holds the bin vector and makes the initial recursive call
+ template <class RandomAccessIter, class get_char, class get_length, class compare, class data_type, class unsignedchar_type>
+ inline void
+ reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp, data_type, unsignedchar_type)
+ {
+ std::vector<size_t> bin_sizes;
+ std::vector<RandomAccessIter> bin_cache;
+ reverse_string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);
+ }
+ }
+
+ //Allows character-type overloads
+ template <class RandomAccessIter, class unsignedchar_type>
+ inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsignedchar_type unused)
+ {
+ //Don't sort if it's too small to optimize
+ if(last - first < detail::MIN_SORT_SIZE)
+ std::sort(first, last);
+ else
+ detail::string_sort(first, last, *first, unused);
+ }
+
+ //Top-level sorting call; wraps using default of unsigned char
+ template <class RandomAccessIter>
+ inline void string_sort(RandomAccessIter first, RandomAccessIter last)
+ {
+ unsigned char unused = '\0';
+ string_sort(first, last, unused);
+ }
+
+ //Allows character-type overloads
+ template <class RandomAccessIter, class compare, class unsignedchar_type>
+ inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused)
+ {
+ //Don't sort if it's too small to optimize
+ if(last - first < detail::MIN_SORT_SIZE)
+ std::sort(first, last, comp);
+ else
+ detail::reverse_string_sort(first, last, *first, unused);
+ }
+
+ //Top-level sorting call; wraps using default of unsigned char
+ template <class RandomAccessIter, class compare>
+ inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp)
+ {
+ unsigned char unused = '\0';
+ reverse_string_sort(first, last, comp, unused);
+ }
+
+ template <class RandomAccessIter, class get_char, class get_length>
+ inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length)
+ {
+ //Don't sort if it's too small to optimize
+ if(last - first < detail::MIN_SORT_SIZE)
+ std::sort(first, last);
+ else {
+ //skipping past empties at the beginning, which allows us to get the character type
+ //.empty() is not used so as not to require a user declaration of it
+ while(!length(*first)) {
+ if(++first == last)
+ return;
+ }
+ detail::string_sort(first, last, getchar, length, *first, getchar((*first), 0));
+ }
+ }
+
+ template <class RandomAccessIter, class get_char, class get_length, class compare>
+ inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp)
+ {
+ //Don't sort if it's too small to optimize
+ if(last - first < detail::MIN_SORT_SIZE)
+ std::sort(first, last, comp);
+ else {
+ //skipping past empties at the beginning, which allows us to get the character type
+ //.empty() is not used so as not to require a user declaration of it
+ while(!length(*first)) {
+ if(++first == last)
+ return;
+ }
+ detail::string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
+ }
+ }
+
+ template <class RandomAccessIter, class get_char, class get_length, class compare>
+ inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp)
+ {
+ //Don't sort if it's too small to optimize
+ if(last - first < detail::MIN_SORT_SIZE)
+ std::sort(first, last, comp);
+ else {
+ //skipping past empties at the beginning, which allows us to get the character type
+ //.empty() is not used so as not to require a user declaration of it
+ while(!length(*(--last))) {
+ //Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order
+ if(first == last)
+ return;
+ }
+ //making last just after the end of the non-empty part of the array
+ ++last;
+ detail::reverse_string_sort(first, last, getchar, length, comp, *first, getchar((*first), 0));
+ }
+ }
+}
+
+#endif
diff --git a/src/system_wrappers/source/system_wrappers.gyp b/src/system_wrappers/source/system_wrappers.gyp new file mode 100644 index 0000000000..0448941796 --- /dev/null +++ b/src/system_wrappers/source/system_wrappers.gyp @@ -0,0 +1,146 @@ +# Copyright (c) 2009 The Chromium Authors. All rights reserved. +# Use of this source code is governed by a BSD-style license that can be +# found in the LICENSE file. + +# TODO: Rename files to use *_linux.cpp etc. names, to automatically include relevant files. Remove conditions section. + +{ + 'includes': [ + '../../common_settings.gypi', # Common settings + ], + 'targets': [ + { + 'target_name': 'system_wrappers', + 'type': '<(library)', + 'include_dirs': [ + 'spreadsortlib', + '../interface', + ], + 'direct_dependent_settings': { + 'include_dirs': [ + '../interface', + ], + }, + 'sources': [ + '../interface/aligned_malloc.h', + '../interface/atomic32_wrapper.h', + '../interface/condition_variable_wrapper.h', + '../interface/cpu_wrapper.h', + '../interface/cpu_features_wrapper.h', + '../interface/critical_section_wrapper.h', + '../interface/event_wrapper.h', + '../interface/file_wrapper.h', + '../interface/list_wrapper.h', + '../interface/map_wrapper.h', + '../interface/rw_lock_wrapper.h', + '../interface/sort.h', + '../interface/thread_wrapper.h', + '../interface/tick_util.h', + '../interface/trace.h', + 'aligned_malloc.cc', + 'atomic32.cc', + 'atomic32_linux.h', + 'atomic32_mac.h', + 'atomic32_windows.h', + 'condition_variable.cc', + 'condition_variable_linux.h', + 'condition_variable_windows.h', + 'cpu.cc', + 'cpu_linux.h', + 'cpu_mac.h', + 'cpu_windows.h', + 'cpu_features.cc', + 'critical_section.cc', + 'critical_section_linux.h', + 'critical_section_windows.h', + 'event.cc', + 'event_linux.h', + 'event_windows.h', + 'file_impl.cc', + 'file_impl.h', + 'list_no_stl.cc', + 'map.cc', + 'rw_lock.cc', + 'rw_lock_linux.h', + 'rw_lock_windows.h', + 'sort.cc', + 'thread.cc', + 'thread_linux.h', + 'thread_windows.h', + 'trace_impl.cc', + 'trace_impl.h', + 'trace_linux.h', + 'trace_windows.h', + ], + 'conditions': [ + ['OS=="linux"', { + 'sources': [ + 'condition_variable_linux.cc', + 'cpu_linux.cc', + 'critical_section_linux.cc', + 'event_linux.cc', + 'thread_linux.cc', + 'trace_linux.cc', + 'rw_lock_linux.cc', + ], + 'link_settings': { + 'libraries': [ + '-lrt', + ], + }, + }], + ['OS=="mac"', { + 'sources': [ + 'condition_variable_linux.cc', + 'cpu_mac.cc', + 'critical_section_linux.cc', + 'event_linux.cc', + 'rw_lock_linux.cc', + 'thread_linux.cc', + 'trace_linux.cc', + ], + }], + ['OS=="win"', { + 'sources': [ + 'atomic32_windows.h', + 'condition_variable_windows.cc', + 'condition_variable_windows.h', + 'cpu_windows.cc', + 'cpu_windows.h', + 'critical_section_windows.cc', + 'critical_section_windows.h', + 'event_windows.cc', + 'event_windows.h', + 'rw_lock_windows.cc', + 'rw_lock_windows.h', + 'thread_windows.cc', + 'thread_windows.h', + 'trace_windows.cc', + 'trace_windows.h', + ], + 'link_settings': { + 'libraries': [ + '-lwinmm.lib', + ], + }, + }], + ] # conditions + }, + { + 'target_name': 'system_wrappersTest', + 'type': 'executable', + 'dependencies': [ + 'system_wrappers' + ], + 'sources': [ + '../test/Test.cpp', + ], + }, + ], # targets +} + +# Local Variables: +# tab-width:2 +# indent-tabs-mode:nil +# End: +# vim: set expandtab tabstop=2 shiftwidth=2: diff --git a/src/system_wrappers/source/system_wrappers_tests.gyp b/src/system_wrappers/source/system_wrappers_tests.gyp new file mode 100644 index 0000000000..856f0c1033 --- /dev/null +++ b/src/system_wrappers/source/system_wrappers_tests.gyp @@ -0,0 +1,37 @@ +# Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. +# +# Use of this source code is governed by a BSD-style license +# that can be found in the LICENSE file in the root of the source +# tree. An additional intellectual property rights grant can be found +# in the file PATENTS. All contributing project authors may +# be found in the AUTHORS file in the root of the source tree. + +{ + 'includes': [ + '../../common_settings.gypi', + ], + 'targets': [ + { + 'target_name': 'unittest', + 'type': 'executable', + 'dependencies': [ + '../../system_wrappers/source/system_wrappers.gyp:system_wrappers', + '../../../testing/gtest.gyp:gtest', + '../../../testing/gtest.gyp:gtest_main', + ], + 'include_dirs': [ + '../../../testing/gtest/include', + ], + 'sources': [ + 'list_unittest.cc', + 'map_unittest.cc', + ], + }, + ], +} + +# Local Variables: +# tab-width:2 +# indent-tabs-mode:nil +# End: +# vim: set expandtab tabstop=2 shiftwidth=2: diff --git a/src/system_wrappers/source/thread.cc b/src/system_wrappers/source/thread.cc new file mode 100644 index 0000000000..a136cbaf11 --- /dev/null +++ b/src/system_wrappers/source/thread.cc @@ -0,0 +1,30 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "thread_wrapper.h" + +#if defined(_WIN32) + #include "thread_windows.h" +#else + #include "thread_linux.h" +#endif + +namespace webrtc { +ThreadWrapper* ThreadWrapper::CreateThread(ThreadRunFunction func, + ThreadObj obj, ThreadPriority prio, + const char* threadName) +{ +#if defined(_WIN32) + return new ThreadWindows(func, obj, prio, threadName); +#else + return ThreadLinux::Create(func, obj, prio, threadName); +#endif +} +} // namespace webrtc diff --git a/src/system_wrappers/source/thread_linux.cc b/src/system_wrappers/source/thread_linux.cc new file mode 100644 index 0000000000..1281c1b0d1 --- /dev/null +++ b/src/system_wrappers/source/thread_linux.cc @@ -0,0 +1,340 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "thread_linux.h" + +#include <errno.h> +#include <string.h> // strncpy +#include <time.h> // nanosleep +#include <unistd.h> +#ifdef WEBRTC_LINUX +#include <sys/types.h> +#include <sched.h> +#include <sys/syscall.h> +#include <linux/unistd.h> +#include <sys/prctl.h> +#endif + +#include "event_wrapper.h" +#include "trace.h" + +namespace webrtc { +extern "C" +{ + static void* StartThread(void* lpParameter) + { + static_cast<ThreadLinux*>(lpParameter)->Run(); + return 0; + } +} + +#if (defined(WEBRTC_LINUX) && !defined(ANDROID)) +static pid_t gettid() +{ +#if defined(__NR_gettid) + return syscall(__NR_gettid); +#else + return -1; +#endif +} +#endif + +ThreadWrapper* ThreadLinux::Create(ThreadRunFunction func, ThreadObj obj, + ThreadPriority prio, const char* threadName) +{ + ThreadLinux* ptr = new ThreadLinux(func, obj, prio, threadName); + if (!ptr) + { + return NULL; + } + const int error = ptr->Construct(); + if (error) + { + delete ptr; + return NULL; + } + return ptr; +} + +ThreadLinux::ThreadLinux(ThreadRunFunction func, ThreadObj obj, + ThreadPriority prio, const char* threadName) + : _runFunction(func), + _obj(obj), + _alive(false), + _dead(true), + _prio(prio), + _event(EventWrapper::Create()), + _setThreadName(false) +{ +#ifdef WEBRTC_LINUX + _linuxPid = -1; +#endif + if (threadName != NULL) + { + _setThreadName = true; + strncpy(_name, threadName, kThreadMaxNameLength); + } +} + +int ThreadLinux::Construct() +{ + int result = 0; +#if !defined(ANDROID) + // Enable immediate cancellation if requested, see Shutdown() + result = pthread_setcancelstate(PTHREAD_CANCEL_ENABLE, NULL); + if (result != 0) + { + return -1; + } + result = pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS, NULL); + if (result != 0) + { + return -1; + } +#endif + result = pthread_attr_init(&_attr); + if (result != 0) + { + return -1; + } + + return 0; +} + +ThreadLinux::~ThreadLinux() +{ + pthread_attr_destroy(&_attr); + delete _event; +} + +#define HAS_THREAD_ID !defined(MAC_IPHONE) && !defined(MAC_IPHONE_SIM) && \ + !defined(WEBRTC_MAC) && !defined(WEBRTC_MAC_INTEL) && \ + !defined(MAC_DYLIB) && !defined(MAC_INTEL_DYLIB) +#if HAS_THREAD_ID +bool ThreadLinux::Start(unsigned int& threadID) +#else +bool ThreadLinux::Start(unsigned int& /*threadID*/) +#endif +{ + if (!_runFunction) + { + return false; + } + int result = pthread_attr_setdetachstate(&_attr, PTHREAD_CREATE_DETACHED); + // Set the stack stack size to 1M. + result |= pthread_attr_setstacksize(&_attr, 1024*1024); +#ifdef WEBRTC_THREAD_RR + const int policy = SCHED_RR; +#else + const int policy = SCHED_FIFO; +#endif + _event->Reset(); + result |= pthread_create(&_thread, &_attr, &StartThread, this); + if (result != 0) + { + return false; + } + + // Wait up to 10 seconds for the OS to call the callback function. Prevents + // race condition if Stop() is called too quickly after start. + if (kEventSignaled != _event->Wait(WEBRTC_EVENT_10_SEC)) + { + // Timed out. Something went wrong. + _runFunction = NULL; + return false; + } + +#if HAS_THREAD_ID + threadID = static_cast<unsigned int>(_thread); +#endif + sched_param param; + + const int minPrio = sched_get_priority_min(policy); + const int maxPrio = sched_get_priority_max(policy); + if ((minPrio == EINVAL) || (maxPrio == EINVAL)) + { + return false; + } + + switch (_prio) + { + case kLowPriority: + param.sched_priority = minPrio + 1; + break; + case kNormalPriority: + param.sched_priority = (minPrio + maxPrio) / 2; + break; + case kHighPriority: + param.sched_priority = maxPrio - 3; + break; + case kHighestPriority: + param.sched_priority = maxPrio - 2; + break; + case kRealtimePriority: + param.sched_priority = maxPrio - 1; + break; + default: + return false; + } + result = pthread_setschedparam(_thread, policy, ¶m); + if (result == EINVAL) + { + return false; + } + return true; +} + +#if (defined(WEBRTC_LINUX) && !defined(ANDROID)) +bool ThreadLinux::SetAffinity(const int* processorNumbers, + const unsigned int amountOfProcessors) +{ + if (!processorNumbers || (amountOfProcessors == 0)) + { + return false; + } + + cpu_set_t mask; + CPU_ZERO(&mask); + + for(unsigned int processor = 0; + processor < amountOfProcessors; + processor++) + { + CPU_SET(processorNumbers[processor], &mask); + } + const int result = sched_setaffinity(_linuxPid, (unsigned int)sizeof(mask), + &mask); + if (result != 0) + { + return false; + + } + return true; +} +#else +// NOTE: On Mac OS X, use the Thread affinity API in +// /usr/include/mach/thread_policy.h: thread_policy_set and mach_thread_self() +// instead of Linux gettid() syscall. +bool ThreadLinux::SetAffinity(const int* , const unsigned int) +{ + return false; +} +#endif + +void ThreadLinux::SetNotAlive() +{ + _alive = false; +} + +bool ThreadLinux::Shutdown() +{ +#if !defined(ANDROID) + if (_thread && (0 != pthread_cancel(_thread))) + { + return false; + } + + return true; +#else + return false; +#endif +} + +bool ThreadLinux::Stop() +{ + _alive = false; + + // TODO (hellner) why not use an event here? + // Wait up to 10 seconds for the thread to terminate + for (int i = 0; i < 1000 && !_dead; i++) + { + timespec t; + t.tv_sec = 0; + t.tv_nsec = 10*1000*1000; + nanosleep(&t, NULL); + } + if (_dead) + { + return true; + } + else + { + return false; + } +} + +void ThreadLinux::Run() +{ + _alive = true; + _dead = false; +#ifdef WEBRTC_LINUX + if(_linuxPid == -1) + { + _linuxPid = gettid(); + } +#endif + // The event the Start() is waiting for. + _event->Set(); + + if (_setThreadName) + { +#ifdef WEBRTC_LINUX + WEBRTC_TRACE(kTraceStateInfo, kTraceUtility,-1, + "Thread with id:%d name:%s started ", _linuxPid, _name); + prctl(PR_SET_NAME, (unsigned long)_name, 0, 0, 0); +#else + WEBRTC_TRACE(kTraceStateInfo, kTraceUtility,-1, + "Thread with name:%s started ", _name); +#endif + }else + { +#ifdef WEBRTC_LINUX + WEBRTC_TRACE(kTraceStateInfo, kTraceUtility, -1, + "Thread with id:%d without name started", _linuxPid); +#else + WEBRTC_TRACE(kTraceStateInfo, kTraceUtility, -1, + "Thread without name started"); +#endif + } + do + { + if (_runFunction) + { + if (!_runFunction(_obj)) + { + _alive = false; + } + } + else + { + _alive = false; + } + } + while (_alive); + + if (_setThreadName) + { + // Don't set the name for the trace thread because it may cause a + // deadlock. TODO (hellner) there should be a better solution than + // coupling the thread and the trace class like this. + if (strcmp(_name, "Trace")) + { + WEBRTC_TRACE(kTraceStateInfo, kTraceUtility,-1, + "Thread with name:%s stopped", _name); + } + } + else + { + WEBRTC_TRACE(kTraceStateInfo, kTraceUtility,-1, + "Thread without name stopped"); + } + _dead = true; +} +} // namespace webrtc diff --git a/src/system_wrappers/source/thread_linux.h b/src/system_wrappers/source/thread_linux.h new file mode 100644 index 0000000000..3e2b90806f --- /dev/null +++ b/src/system_wrappers/source/thread_linux.h @@ -0,0 +1,69 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_THREAD_LINUX_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_THREAD_LINUX_H_ + +#include "thread_wrapper.h" +#include <pthread.h> + +namespace webrtc { +class EventWrapper; + +class ThreadLinux : public ThreadWrapper +{ +public: + static ThreadWrapper* Create(ThreadRunFunction func, ThreadObj obj, + ThreadPriority prio, const char* threadName); + + ThreadLinux(ThreadRunFunction func, ThreadObj obj, ThreadPriority prio, + const char* threadName); + ~ThreadLinux(); + + // From ThreadWrapper + virtual void SetNotAlive(); + virtual bool Start(unsigned int& id); + // Not implemented on Mac + virtual bool SetAffinity(const int* processorNumbers, + unsigned int amountOfProcessors); + virtual bool Stop(); + virtual bool Shutdown(); + + void Run(); + +private: + int Construct(); + +private: + // processing function + ThreadRunFunction _runFunction; + ThreadObj _obj; + + // internal state + bool _alive; + bool _dead; + ThreadPriority _prio; + EventWrapper* _event; + + // zero-terminated thread name string + char _name[kThreadMaxNameLength]; + bool _setThreadName; + + // handle to thread + pthread_attr_t _attr; + pthread_t _thread; +#ifdef WEBRTC_LINUX + pid_t _linuxPid; +#endif + +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_THREAD_LINUX_H_ diff --git a/src/system_wrappers/source/trace_impl.cc b/src/system_wrappers/source/trace_impl.cc new file mode 100644 index 0000000000..0a5f9db461 --- /dev/null +++ b/src/system_wrappers/source/trace_impl.cc @@ -0,0 +1,949 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "trace_impl.h" + +#include <cassert> +#include <string.h> // memset + +#ifdef _WIN32 +#include "trace_windows.h" +#include "fix_interlocked_exchange_pointer_windows.h" +#else +#include <stdio.h> +#include <time.h> +#include <stdarg.h> +#include "trace_linux.h" +#endif // _WIN32 + +#define KEY_LEN_CHARS 31 + +#ifdef _WIN32 + #pragma warning(disable:4355) +// VS 2005: Disable warnings for default initialized arrays. + #pragma warning(disable:4351) +#endif // _WIN32 + +namespace webrtc { +static WebRtc_UWord32 levelFilter = kTraceDefault; + +// Construct On First Use idiom. Avoids "static initialization order fiasco". +Trace* TraceImpl::StaticInstance(TraceCount inc, const TraceLevel level) +{ + // TODO (hellner): use atomic wrapper instead. + static volatile long theTraceCount = 0; + static Trace* volatile theTrace = NULL; + + TraceCreate state = WEBRTC_TRACE_EXIST; + + // Sanitys to avoid taking lock unless absolutely necessary (for + // performance reasons). inc == WEBRTC_TRACE_INC_NO_CREATE) implies that + // a message will be written to file. + if(level != kTraceAll && inc == WEBRTC_TRACE_INC_NO_CREATE) + { + if(!(level & levelFilter)) + { + return NULL; + } + } + +#ifndef _WIN32 + // TODO (pwestin): crtiSect is never reclaimed. Fix memory leak. + static CriticalSectionWrapper* crtiSect( + CriticalSectionWrapper::CreateCriticalSection()); + CriticalSectionScoped lock(*crtiSect); + + if(inc == WEBRTC_TRACE_INC_NO_CREATE && theTraceCount == 0) + { + return NULL; + } + + if(inc == WEBRTC_TRACE_INC || inc == WEBRTC_TRACE_INC_NO_CREATE) + { + theTraceCount++; + if(theTraceCount == 1) + { + state = WEBRTC_TRACE_CREATE; + } + } else { + theTraceCount--; + if(theTraceCount == 0) + { + state = WEBRTC_TRACE_DESTROY; + } + } + if(state == WEBRTC_TRACE_CREATE) + { + theTrace = TraceImpl::CreateTrace(); + + } else if(state == WEBRTC_TRACE_DESTROY) { + Trace* oldValue = theTrace; + theTrace = NULL; + // The lock is held by the scoped critical section. Release the lock + // temporarily so that the trace can be safely deleted. If the lock + // was kept during the delete, e.g. creating and destroying the trace + // too quickly may lead to a deadlock. + // This is due to the fact that starting and stopping a ThreadWrapper + // thread will trigger writing of trace messages. + // TODO (hellner): remove the tight coupling with the thread + // implementation. + crtiSect->Leave(); + if(oldValue) + { + delete static_cast<TraceImpl*>(oldValue); + } + // Re-aqcuire the lock. + crtiSect->Enter(); + return NULL; + } +#else // _WIN32 + if(inc == WEBRTC_TRACE_INC_NO_CREATE && theTraceCount == 0) + { + return NULL; + } + if(inc == WEBRTC_TRACE_INC_NO_CREATE) + { + if(1 == InterlockedIncrement(&theTraceCount)) + { + // The trace has been destroyed by some other thread. Rollback. + InterlockedDecrement(&theTraceCount); + assert(false); + return NULL; + } + // Sanity to catch corrupt state. + if(theTrace == NULL) + { + assert(false); + InterlockedDecrement(&theTraceCount); + return NULL; + } + } else if(inc == WEBRTC_TRACE_INC) { + if(theTraceCount == 0) + { + state = WEBRTC_TRACE_CREATE; + } else { + if(1 == InterlockedIncrement(&theTraceCount)) + { + // InterlockedDecrement because reference count should not be + // updated just yet (that's done when the trace is created). + InterlockedDecrement(&theTraceCount); + state = WEBRTC_TRACE_CREATE; + } + } + } else { + int newValue = InterlockedDecrement(&theTraceCount); + if(newValue == 0) + { + state = WEBRTC_TRACE_DESTROY; + } + } + + if(state == WEBRTC_TRACE_CREATE) + { + // Create trace and let whichever thread finishes first assign its local + // copy to the global instance. All other threads reclaim their local + // copy. + Trace* newTrace = TraceImpl::CreateTrace(); + if(1 == InterlockedIncrement(&theTraceCount)) + { + Trace* oldValue = (Trace*)InterlockedExchangePointer( + reinterpret_cast<void* volatile*>(&theTrace), newTrace); + assert(oldValue == NULL); + assert(theTrace); + } else { + InterlockedDecrement(&theTraceCount); + if(newTrace) + { + delete static_cast<TraceImpl*>(newTrace); + } + } + return NULL; + } else if(state == WEBRTC_TRACE_DESTROY) + { + Trace* oldValue = (Trace*)InterlockedExchangePointer( + reinterpret_cast<void* volatile*>(&theTrace), NULL); + if(oldValue) + { + delete static_cast<TraceImpl*>(oldValue); + } + return NULL; + } +#endif // #ifndef _WIN32 + return theTrace; +} + +void Trace::CreateTrace() +{ + TraceImpl::StaticInstance(WEBRTC_TRACE_INC); +} + +void Trace::ReturnTrace() +{ + TraceImpl::StaticInstance(WEBRTC_TRACE_DEC); +} + +TraceImpl* TraceImpl::GetTrace(const TraceLevel level) +{ + return (TraceImpl*)StaticInstance(WEBRTC_TRACE_INC_NO_CREATE, level); +} + +Trace* TraceImpl::CreateTrace() +{ +#if defined(_WIN32) + return new TraceWindows(); +#else + return new TraceLinux(); +#endif +} + +TraceImpl::TraceImpl() + : _critsectInterface(*CriticalSectionWrapper::CreateCriticalSection()), + _callback(NULL), + _rowCountText(0), + _fileCountText(0), + _traceFile(*FileWrapper::Create()), + _thread(*ThreadWrapper::CreateThread(TraceImpl::Run, this, + kHighestPriority, "Trace")), + _event(*EventWrapper::Create()), + _critsectArray(*CriticalSectionWrapper::CreateCriticalSection()), + _nextFreeIdx(), + _level(), + _length(), + _messageQueue(), + _activeQueue(0) +{ + _nextFreeIdx[0] = 0; + _nextFreeIdx[1] = 0; + + unsigned int tid = 0; + _thread.Start(tid); + + for(int m = 0; m < WEBRTC_TRACE_NUM_ARRAY; m++) + { + for(int n = 0; n < WEBRTC_TRACE_MAX_QUEUE; n++) + { + _messageQueue[m][n] = new + WebRtc_Word8[WEBRTC_TRACE_MAX_MESSAGE_SIZE]; + } + } +} + +bool TraceImpl::StopThread() +{ + // Release the worker thread so that it can flush any lingering messages. + _event.Set(); + + // Allow 10 ms for pending messages to be flushed out. + // TODO (hellner): why not use condition variables to do this? Or let the + // worker thread die and let this thread flush remaining + // messages? +#ifdef _WIN32 + Sleep(10); +#else + timespec t; + t.tv_sec = 0; + t.tv_nsec = 10*1000000; + nanosleep(&t,NULL); +#endif + + _thread.SetNotAlive(); + // Make sure the thread finishes as quickly as possible (instead of having + // to wait for the timeout). + _event.Set(); + bool stopped = _thread.Stop(); + + CriticalSectionScoped lock(_critsectInterface); + _traceFile.Flush(); + _traceFile.CloseFile(); + return stopped; +} + +TraceImpl::~TraceImpl() +{ + StopThread(); + delete &_event; + delete &_traceFile; + delete &_thread; + delete &_critsectInterface; + delete &_critsectArray; + + for(int m = 0; m < WEBRTC_TRACE_NUM_ARRAY; m++) + { + for(int n = 0; n < WEBRTC_TRACE_MAX_QUEUE; n++) + { + delete [] _messageQueue[m][n]; + } + } +} + +WebRtc_Word32 TraceImpl::AddLevel(char* szMessage, const TraceLevel level) const +{ + switch (level) + { + case kTraceStateInfo: + sprintf (szMessage, "STATEINFO ; "); + break; + case kTraceWarning: + sprintf (szMessage, "WARNING ; "); + break; + case kTraceError: + sprintf (szMessage, "ERROR ; "); + break; + case kTraceCritical: + sprintf (szMessage, "CRITICAL ; "); + break; + case kTraceInfo: + sprintf (szMessage, "DEBUGINFO ; "); + break; + case kTraceModuleCall: + sprintf (szMessage, "MODULECALL; "); + break; + case kTraceMemory: + sprintf (szMessage, "MEMORY ; "); + break; + case kTraceTimer: + sprintf (szMessage, "TIMER ; "); + break; + case kTraceStream: + sprintf (szMessage, "STREAM ; "); + break; + case kTraceApiCall: + sprintf (szMessage, "APICALL ; "); + break; + case kTraceDebug: + sprintf (szMessage, "DEBUG ; "); + break; + default: + assert(false); + return 0; + } + // All messages are 12 characters. + return 12; +} + +WebRtc_Word32 TraceImpl::AddModuleAndId(char* traceMessage, + const TraceModule module, + const WebRtc_Word32 id) const +{ + // Use long int to prevent problems with different definitions of + // WebRtc_Word32. + // TODO (hellner): is this actually a problem? If so, it should be better to + // clean up WebRtc_Word32 + const long int idl = id; + if(idl != -1) + { + const unsigned long int idEngine = id>>16; + const unsigned long int idChannel = id & 0xffff; + + switch (module) + { + case kTraceVoice: + sprintf(traceMessage, " VOICE:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceVideo: + sprintf(traceMessage, " VIDEO:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceUtility: + sprintf(traceMessage, " UTILITY:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceRtpRtcp: + sprintf(traceMessage, " RTP/RTCP:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceTransport: + sprintf(traceMessage, " TRANSPORT:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceAudioCoding: + sprintf(traceMessage, "AUDIO CODING:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceSrtp: + sprintf(traceMessage, " SRTP:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceAudioMixerServer: + sprintf(traceMessage, " AUDIO MIX/S:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceAudioMixerClient: + sprintf(traceMessage, " AUDIO MIX/C:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceVideoCoding: + sprintf(traceMessage, "VIDEO CODING:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceVideoMixer: + // Print sleep time and API call + sprintf(traceMessage, " VIDEO MIX:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceFile: + sprintf(traceMessage, " FILE:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceAudioProcessing: + sprintf(traceMessage, " AUDIO PROC:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceAudioDevice: + sprintf(traceMessage, "AUDIO DEVICE:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceVideoRenderer: + sprintf(traceMessage, "VIDEO RENDER:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceVideoCapture: + sprintf(traceMessage, "VIDEO CAPTUR:%5ld %5ld;", idEngine, + idChannel); + break; + case kTraceVideoPreocessing: + sprintf(traceMessage, " VIDEO PROC:%5ld %5ld;", idEngine, + idChannel); + break; + default: + assert(false); + return 0; + } + } else { + switch (module) + { + case kTraceVoice: + sprintf (traceMessage, " VOICE:%11ld;", idl); + break; + case kTraceVideo: + sprintf (traceMessage, " VIDEO:%11ld;", idl); + break; + case kTraceUtility: + sprintf (traceMessage, " UTILITY:%11ld;", idl); + break; + case kTraceRtpRtcp: + sprintf (traceMessage, " RTP/RTCP:%11ld;", idl); + break; + case kTraceTransport: + sprintf (traceMessage, " TRANSPORT:%11ld;", idl); + break; + case kTraceAudioCoding: + sprintf (traceMessage, "AUDIO CODING:%11ld;", idl); + break; + case kTraceSrtp: + sprintf (traceMessage, " SRTP:%11ld;", idl); + break; + case kTraceAudioMixerServer: + sprintf (traceMessage, " AUDIO MIX/S:%11ld;", idl); + break; + case kTraceAudioMixerClient: + sprintf (traceMessage, " AUDIO MIX/C:%11ld;", idl); + break; + case kTraceVideoCoding: + sprintf (traceMessage, "VIDEO CODING:%11ld;", idl); + break; + case kTraceVideoMixer: + sprintf (traceMessage, " VIDEO MIX:%11ld;", idl); + break; + case kTraceFile: + sprintf (traceMessage, " FILE:%11ld;", idl); + break; + case kTraceAudioProcessing: + sprintf (traceMessage, " AUDIO PROC:%11ld;", idl); + break; + case kTraceAudioDevice: + sprintf (traceMessage, "AUDIO DEVICE:%11ld;", idl); + break; + case kTraceVideoRenderer: + sprintf (traceMessage, "VIDEO RENDER:%11ld;", idl); + break; + case kTraceVideoCapture: + sprintf (traceMessage, "VIDEO CAPTUR:%11ld;", idl); + break; + case kTraceVideoPreocessing: + sprintf (traceMessage, " VIDEO PROC:%11ld;", idl); + break; + default: + assert(false); + return 0; + } + } + // All messages are 25 characters. + return 25; +} + +WebRtc_Word32 TraceImpl::SetTraceFileImpl(const WebRtc_Word8* fileNameUTF8, + const bool addFileCounter) +{ + CriticalSectionScoped lock(_critsectInterface); + + _traceFile.Flush(); + _traceFile.CloseFile(); + + if(fileNameUTF8) + { + if(addFileCounter) + { + _fileCountText = 1; + + WebRtc_Word8 fileNameWithCounterUTF8[FileWrapper::kMaxFileNameSize]; + CreateFileName(fileNameUTF8, fileNameWithCounterUTF8, + _fileCountText); + if(_traceFile.OpenFile(fileNameWithCounterUTF8, false, false, + true) == -1) + { + return -1; + } + }else { + _fileCountText = 0; + if(_traceFile.OpenFile(fileNameUTF8, false, false, true) == -1) + { + return -1; + } + } + } + _rowCountText = 0; + return 0; +} + +WebRtc_Word32 TraceImpl::TraceFileImpl( + WebRtc_Word8 fileNameUTF8[FileWrapper::kMaxFileNameSize]) +{ + CriticalSectionScoped lock(_critsectInterface); + return _traceFile.FileName(fileNameUTF8, FileWrapper::kMaxFileNameSize); +} + +WebRtc_Word32 TraceImpl::SetTraceCallbackImpl(TraceCallback* callback) +{ + CriticalSectionScoped lock(_critsectInterface); + _callback = callback; + return 0; +} + +WebRtc_Word32 TraceImpl::AddMessage( + char* traceMessage, + const char msg[WEBRTC_TRACE_MAX_MESSAGE_SIZE], + const WebRtc_UWord16 writtenSoFar) const + +{ + int length = 0; + if(writtenSoFar >= WEBRTC_TRACE_MAX_MESSAGE_SIZE) + { + return -1; + } + // - 2 to leave room for newline and NULL termination +#ifdef _WIN32 + length = _snprintf(traceMessage, + WEBRTC_TRACE_MAX_MESSAGE_SIZE - writtenSoFar - 2, + "%s",msg); + if(length < 0) + { + length = WEBRTC_TRACE_MAX_MESSAGE_SIZE - writtenSoFar - 2; + traceMessage[length] = 0; + } +#else + length = snprintf(traceMessage, + WEBRTC_TRACE_MAX_MESSAGE_SIZE-writtenSoFar-2, "%s",msg); + if(length < 0 || length > WEBRTC_TRACE_MAX_MESSAGE_SIZE-writtenSoFar - 2) + { + length = WEBRTC_TRACE_MAX_MESSAGE_SIZE - writtenSoFar - 2; + traceMessage[length] = 0; + } +#endif + // Length with NULL termination. + return length+1; +} + +void TraceImpl::AddMessageToList( + const char traceMessage[WEBRTC_TRACE_MAX_MESSAGE_SIZE], + const WebRtc_UWord16 length, + const TraceLevel level) +{ + CriticalSectionScoped lock(_critsectArray); + + if(_nextFreeIdx[_activeQueue] >= WEBRTC_TRACE_MAX_QUEUE) + { + if( ! _traceFile.Open() && + !_callback) + { + // Keep at least the last 1/4 of old messages when not logging. + // TODO (hellner): isn't this redundant. The user will make it known + // when to start logging. Why keep messages before + // that? + for(int n = 0; n < WEBRTC_TRACE_MAX_QUEUE/4; n++) + { + const int lastQuarterOffset = (3*WEBRTC_TRACE_MAX_QUEUE/4); + memcpy(_messageQueue[_activeQueue][n], + _messageQueue[_activeQueue][n + lastQuarterOffset], + WEBRTC_TRACE_MAX_MESSAGE_SIZE); + } + _nextFreeIdx[_activeQueue] = WEBRTC_TRACE_MAX_QUEUE/4; + } else { + // More messages are being written than there is room for in the + // buffer. Drop any new messages. + // TODO (hellner): its probably better to drop old messages instead + // of new ones. One step further: if this happens + // it's due to writing faster than what can be + // processed. Maybe modify the filter at this point. + // E.g. turn of STREAM. + return; + } + } + + WebRtc_UWord16 idx = _nextFreeIdx[_activeQueue]; + _nextFreeIdx[_activeQueue]++; + + _level[_activeQueue][idx] = level; + _length[_activeQueue][idx] = length; + memcpy(_messageQueue[_activeQueue][idx], traceMessage, length); + + if(_nextFreeIdx[_activeQueue] == WEBRTC_TRACE_MAX_QUEUE-1) + { + // Loggin more messages than can be worked off. Log a warning. + memcpy(_messageQueue[_activeQueue][_nextFreeIdx[_activeQueue]], + "WARNING MISSING TRACE MESSAGES\n", 32); + _nextFreeIdx[_activeQueue]++; + } +} + +bool TraceImpl::Run(void* obj) +{ + return static_cast<TraceImpl*>(obj)->Process(); +} + +bool TraceImpl::Process() +{ + if(_event.Wait(1000) == kEventSignaled) + { + if(_traceFile.Open() || _callback) + { + // File mode (not calback mode). + WriteToFile(); + } + } else { + _traceFile.Flush(); + } + return true; +} + +void TraceImpl::WriteToFile() +{ + WebRtc_UWord8 localQueueActive = 0; + WebRtc_UWord16 localNextFreeIdx = 0; + + // There are two buffer. One for reading (for writing to file) and one for + // writing (for storing new messages). Let new messages be posted to the + // unused buffer so that the current buffer can be flushed safely. + { + CriticalSectionScoped lock(_critsectArray); + localNextFreeIdx = _nextFreeIdx[_activeQueue]; + _nextFreeIdx[_activeQueue] = 0; + localQueueActive = _activeQueue; + if(_activeQueue == 0) + { + _activeQueue = 1; + } else + { + _activeQueue = 0; + } + } + if(localNextFreeIdx == 0) + { + return; + } + + CriticalSectionScoped lock(_critsectInterface); + + for(WebRtc_UWord16 idx = 0; idx <localNextFreeIdx; idx++) + { + TraceLevel localLevel = _level[localQueueActive][idx]; + if(_callback) + { + _callback->Print(localLevel, _messageQueue[localQueueActive][idx], + _length[localQueueActive][idx]); + } + if(_traceFile.Open()) + { + if(_rowCountText > WEBRTC_TRACE_MAX_FILE_SIZE) + { + // wrap file + _rowCountText = 0; + _traceFile.Flush(); + + if(_fileCountText == 0) + { + _traceFile.Rewind(); + } else + { + WebRtc_Word8 oldFileName[FileWrapper::kMaxFileNameSize]; + WebRtc_Word8 newFileName[FileWrapper::kMaxFileNameSize]; + + // get current name + _traceFile.FileName(oldFileName, + FileWrapper::kMaxFileNameSize); + _traceFile.CloseFile(); + + _fileCountText++; + + UpdateFileName(oldFileName, newFileName, _fileCountText); + + if(_traceFile.OpenFile(newFileName, false, false, + true) == -1) + { + return; + } + } + } + if(_rowCountText == 0) + { + WebRtc_Word8 message[WEBRTC_TRACE_MAX_MESSAGE_SIZE + 1]; + WebRtc_Word32 length = AddDateTimeInfo(message); + if(length != -1) + { + message[length] = 0; + message[length-1] = '\n'; + _traceFile.Write(message, length); + _rowCountText++; + } + length = AddBuildInfo(message); + if(length != -1) + { + message[length+1] = 0; + message[length] = '\n'; + message[length-1] = '\n'; + _traceFile.Write(message, length+1); + _rowCountText++; + _rowCountText++; + } + } + WebRtc_UWord16 length = _length[localQueueActive][idx]; + _messageQueue[localQueueActive][idx][length] = 0; + _messageQueue[localQueueActive][idx][length-1] = '\n'; + _traceFile.Write(_messageQueue[localQueueActive][idx], length); + _rowCountText++; + } + } +} + +void TraceImpl::AddImpl(const TraceLevel level, const TraceModule module, + const WebRtc_Word32 id, + const char msg[WEBRTC_TRACE_MAX_MESSAGE_SIZE]) +{ + if (TraceCheck(level)) + { + char traceMessage[WEBRTC_TRACE_MAX_MESSAGE_SIZE]; + char* meassagePtr = traceMessage; + + WebRtc_Word32 len = 0; + WebRtc_Word32 ackLen = 0; + + len = AddLevel(meassagePtr, level); + if(len == -1) + { + return; + } + meassagePtr += len; + ackLen += len; + + len = AddTime(meassagePtr, level); + if(len == -1) + { + return; + } + meassagePtr += len; + ackLen += len; + + len = AddModuleAndId(meassagePtr, module, id); + if(len == -1) + { + return; + } + meassagePtr += len; + ackLen += len; + + len = AddThreadId(meassagePtr); + if(len == -1) + { + return; + } + meassagePtr += len; + ackLen += len; + + len = AddMessage(meassagePtr, msg, (WebRtc_UWord16)ackLen); + if(len == -1) + { + return; + } + ackLen += len; + AddMessageToList(traceMessage,(WebRtc_UWord16)ackLen, level); + + // Make sure that messages are written as soon as possible. + _event.Set(); + } +} + +bool TraceImpl::TraceCheck(const TraceLevel level) const +{ + return (level & levelFilter)? true:false; +} + +bool TraceImpl::UpdateFileName( + const WebRtc_Word8 fileNameUTF8[FileWrapper::kMaxFileNameSize], + WebRtc_Word8 fileNameWithCounterUTF8[FileWrapper::kMaxFileNameSize], + const WebRtc_UWord32 newCount) const +{ + WebRtc_Word32 length = (WebRtc_Word32)strlen(fileNameUTF8); + if(length < 0) + { + return false; + } + + WebRtc_Word32 lengthWithoutFileEnding = length-1; + while(lengthWithoutFileEnding > 0) + { + if(fileNameUTF8[lengthWithoutFileEnding] == '.') + { + break; + } else { + lengthWithoutFileEnding--; + } + } + if(lengthWithoutFileEnding == 0) + { + lengthWithoutFileEnding = length; + } + WebRtc_Word32 lengthTo_ = lengthWithoutFileEnding - 1; + while(lengthTo_ > 0) + { + if(fileNameUTF8[lengthTo_] == '_') + { + break; + } else { + lengthTo_--; + } + } + + memcpy(fileNameWithCounterUTF8, fileNameUTF8, lengthTo_); + sprintf(fileNameWithCounterUTF8+lengthTo_, "_%lu%s", newCount, + fileNameUTF8+lengthWithoutFileEnding); + return true; +} + +bool TraceImpl::CreateFileName( + const WebRtc_Word8 fileNameUTF8[FileWrapper::kMaxFileNameSize], + WebRtc_Word8 fileNameWithCounterUTF8[FileWrapper::kMaxFileNameSize], + const WebRtc_UWord32 newCount) const +{ + WebRtc_Word32 length = (WebRtc_Word32)strlen(fileNameUTF8); + if(length < 0) + { + return false; + } + + WebRtc_Word32 lengthWithoutFileEnding = length-1; + while(lengthWithoutFileEnding > 0) + { + if(fileNameUTF8[lengthWithoutFileEnding] == '.') + { + break; + }else + { + lengthWithoutFileEnding--; + } + } + if(lengthWithoutFileEnding == 0) + { + lengthWithoutFileEnding = length; + } + memcpy(fileNameWithCounterUTF8, fileNameUTF8, lengthWithoutFileEnding); + sprintf(fileNameWithCounterUTF8+lengthWithoutFileEnding, "_%lu%s", + newCount, fileNameUTF8+lengthWithoutFileEnding); + return true; +} + +WebRtc_Word32 Trace::SetLevelFilter(WebRtc_UWord32 filter) +{ + levelFilter = filter; + return 0; +}; + +WebRtc_Word32 Trace::LevelFilter(WebRtc_UWord32& filter) +{ + filter = levelFilter; + return 0; +}; + +WebRtc_Word32 Trace::TraceFile(WebRtc_Word8 fileName[FileWrapper::kMaxFileNameSize]) +{ + TraceImpl* trace = TraceImpl::GetTrace(); + if(trace) + { + int retVal = trace->TraceFileImpl(fileName); + ReturnTrace(); + return retVal; + } + return -1; +} + +WebRtc_Word32 Trace::SetTraceFile(const WebRtc_Word8* fileName, + const bool addFileCounter) +{ + TraceImpl* trace = TraceImpl::GetTrace(); + if(trace) + { + int retVal = trace->SetTraceFileImpl(fileName, addFileCounter); + ReturnTrace(); + return retVal; + } + return -1; +} + +WebRtc_Word32 Trace::SetTraceCallback(TraceCallback* callback) +{ + TraceImpl* trace = TraceImpl::GetTrace(); + if(trace) + { + int retVal = trace->SetTraceCallbackImpl(callback); + ReturnTrace(); + return retVal; + } + return -1; +} + +void Trace::Add(const TraceLevel level, const TraceModule module, + const WebRtc_Word32 id, const char* msg, ...) + +{ + TraceImpl* trace = TraceImpl::GetTrace(level); + if(trace) + { + if(trace->TraceCheck(level)) + { + char tempBuff[WEBRTC_TRACE_MAX_MESSAGE_SIZE]; + char* buff = 0; + if(msg) + { + va_list args; + va_start(args, msg); +#ifdef _WIN32 + _vsnprintf(tempBuff,WEBRTC_TRACE_MAX_MESSAGE_SIZE-1,msg,args); +#else + vsnprintf(tempBuff,WEBRTC_TRACE_MAX_MESSAGE_SIZE-1,msg,args); +#endif + va_end(args); + buff = tempBuff; + } + trace->AddImpl(level, module, id, buff); + } + ReturnTrace(); + } +} +} // namespace webrtc diff --git a/src/system_wrappers/source/trace_impl.h b/src/system_wrappers/source/trace_impl.h new file mode 100644 index 0000000000..42e82fec70 --- /dev/null +++ b/src/system_wrappers/source/trace_impl.h @@ -0,0 +1,141 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_TRACE_IMPL_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_TRACE_IMPL_H_ + +#include "system_wrappers/interface/critical_section_wrapper.h" +#include "system_wrappers/interface/event_wrapper.h" +#include "system_wrappers/interface/file_wrapper.h" +#include "system_wrappers/interface/trace.h" +#include "system_wrappers/interface/thread_wrapper.h" + +namespace webrtc { +enum TraceCount +{ + WEBRTC_TRACE_DEC = 0, + WEBRTC_TRACE_INC = 1, + WEBRTC_TRACE_INC_NO_CREATE = 2 +}; + +enum TraceCreate +{ + WEBRTC_TRACE_EXIST = 0, + WEBRTC_TRACE_CREATE = 1, + WEBRTC_TRACE_DESTROY = 2 +}; + +// TODO (pwestin) WEBRTC_TRACE_MAX_QUEUE needs to be tweaked +// TODO (hellner) the buffer should be close to how much the system can write to +// file. Increasing the buffer will not solve anything. Sooner or +// later the buffer is going to fill up anyways. +#if defined(MAC_IPHONE) + #define WEBRTC_TRACE_MAX_QUEUE 2000 +#else + #define WEBRTC_TRACE_MAX_QUEUE 8000 +#endif +#define WEBRTC_TRACE_NUM_ARRAY 2 +#define WEBRTC_TRACE_MAX_MESSAGE_SIZE 256 +// Total buffer size is WEBRTC_TRACE_NUM_ARRAY (number of buffer partitions) * +// WEBRTC_TRACE_MAX_QUEUE (number of lines per buffer partition) * +// WEBRTC_TRACE_MAX_MESSAGE_SIZE (number of 1 byte charachters per line) = +// 1 or 4 Mbyte + +#define WEBRTC_TRACE_MAX_FILE_SIZE 100*1000 +// Number of rows that may be written to file. On average 110 bytes per row (max +// 256 bytes per row). So on average 110*100*1000 = 11 Mbyte, max 256*100*1000 = +// 25.6 Mbyte + +class TraceImpl : public Trace +{ +public: + virtual ~TraceImpl(); + + static Trace* CreateTrace(); + static TraceImpl* GetTrace(const TraceLevel level = kTraceAll); + + static Trace* StaticInstance(TraceCount inc, + const TraceLevel level = kTraceAll); + + WebRtc_Word32 SetTraceFileImpl(const WebRtc_Word8* fileName, + const bool addFileCounter); + WebRtc_Word32 TraceFileImpl( + WebRtc_Word8 fileName[FileWrapper::kMaxFileNameSize]); + + WebRtc_Word32 SetTraceCallbackImpl(TraceCallback* callback); + + void AddImpl(const TraceLevel level, const TraceModule module, + const WebRtc_Word32 id, const char* msg); + + bool StopThread(); + + bool TraceCheck(const TraceLevel level) const; + +protected: + TraceImpl(); + + // OS specific implementations + virtual WebRtc_Word32 AddThreadId(char* traceMessage) const = 0; + virtual WebRtc_Word32 AddTime(char* traceMessage, + const TraceLevel level) const = 0; + + virtual WebRtc_Word32 AddBuildInfo(char* traceMessage) const = 0; + virtual WebRtc_Word32 AddDateTimeInfo(char* traceMessage) const = 0; + + static bool Run(void* obj); + bool Process(); + +private: + WebRtc_Word32 AddLevel(char* szMessage, const TraceLevel level) const; + + WebRtc_Word32 AddModuleAndId(char* traceMessage, const TraceModule module, + const WebRtc_Word32 id) const; + + WebRtc_Word32 AddMessage(char* traceMessage, + const char msg[WEBRTC_TRACE_MAX_MESSAGE_SIZE], + const WebRtc_UWord16 writtenSoFar) const; + + void AddMessageToList( + const char traceMessage[WEBRTC_TRACE_MAX_MESSAGE_SIZE], + const WebRtc_UWord16 length, + const TraceLevel level); + + bool UpdateFileName( + const WebRtc_Word8 fileNameUTF8[FileWrapper::kMaxFileNameSize], + WebRtc_Word8 fileNameWithCounterUTF8[FileWrapper::kMaxFileNameSize], + const WebRtc_UWord32 newCount) const; + + bool CreateFileName( + const WebRtc_Word8 fileNameUTF8[FileWrapper::kMaxFileNameSize], + WebRtc_Word8 fileNameWithCounterUTF8[FileWrapper::kMaxFileNameSize], + const WebRtc_UWord32 newCount) const; + + void WriteToFile(); + + CriticalSectionWrapper& _critsectInterface; + TraceCallback* _callback; + WebRtc_UWord32 _rowCountText; + WebRtc_UWord32 _fileCountText; + + FileWrapper& _traceFile; + ThreadWrapper& _thread; + EventWrapper& _event; + + // _critsectArray protects _activeQueue + CriticalSectionWrapper& _critsectArray; + WebRtc_UWord16 _nextFreeIdx[WEBRTC_TRACE_NUM_ARRAY]; + TraceLevel _level[WEBRTC_TRACE_NUM_ARRAY][WEBRTC_TRACE_MAX_QUEUE]; + WebRtc_UWord16 _length[WEBRTC_TRACE_NUM_ARRAY][WEBRTC_TRACE_MAX_QUEUE]; + WebRtc_Word8* _messageQueue[WEBRTC_TRACE_NUM_ARRAY][WEBRTC_TRACE_MAX_QUEUE]; + WebRtc_UWord8 _activeQueue; +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_TRACE_IMPL_H_ diff --git a/src/system_wrappers/source/trace_linux.cc b/src/system_wrappers/source/trace_linux.cc new file mode 100644 index 0000000000..8dba3beba8 --- /dev/null +++ b/src/system_wrappers/source/trace_linux.cc @@ -0,0 +1,135 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#include "trace_linux.h" + +#include <cassert> +#include <stdarg.h> +#include <stdio.h> +#include <string.h> +#include <time.h> + +#ifdef ANDROID + #include <pthread.h> +#else + #include <iostream> +#endif + +#if defined(_DEBUG) + #define BUILDMODE "d" +#elif defined(DEBUG) + #define BUILDMODE "d" +#elif defined(NDEBUG) + #define BUILDMODE "r" +#else + #define BUILDMODE "?" +#endif +#define BUILDTIME __TIME__ +#define BUILDDATE __DATE__ +// example: "Oct 10 2002 12:05:30 r" +#define BUILDINFO BUILDDATE " " BUILDTIME " " BUILDMODE + +namespace webrtc { +TraceLinux::TraceLinux() +{ + _prevAPITickCount = time(NULL); + _prevTickCount = _prevAPITickCount; +} + +TraceLinux::~TraceLinux() +{ + StopThread(); +} + +WebRtc_Word32 TraceLinux::AddThreadId(char* traceMessage) const +{ + WebRtc_UWord64 threadId = (WebRtc_UWord64)pthread_self(); + sprintf(traceMessage, "%10llu; ", threadId); + // 12 bytes are written. + return 12; +} + +WebRtc_Word32 TraceLinux::AddTime(char* traceMessage, + const TraceLevel level) const +{ + time_t dwCurrentTimeInSeconds = time(NULL); + struct tm systemTime; + gmtime_r(&dwCurrentTimeInSeconds, &systemTime); + + if(level == kTraceApiCall) + { + WebRtc_UWord32 dwDeltaTime = dwCurrentTimeInSeconds - _prevTickCount; + _prevTickCount = dwCurrentTimeInSeconds; + + if(_prevTickCount == 0) + { + dwDeltaTime = 0; + } + if(dwDeltaTime > 0x0fffffff) + { + // Either wraparound or data race. + dwDeltaTime = 0; + } + if(dwDeltaTime > 99999) + { + dwDeltaTime = 99999; + } + + sprintf(traceMessage, "(%2u:%2u:%2u:%3u |%5lu) ", systemTime.tm_hour, + systemTime.tm_min, systemTime.tm_sec, 0, + static_cast<unsigned long>(dwDeltaTime)); + } else { + WebRtc_UWord32 dwDeltaTime = dwCurrentTimeInSeconds - _prevAPITickCount; + _prevAPITickCount = dwCurrentTimeInSeconds; + if(_prevAPITickCount == 0) + { + dwDeltaTime = 0; + } + if(dwDeltaTime > 0x0fffffff) + { + // Either wraparound or data race. + dwDeltaTime = 0; + } + if(dwDeltaTime > 99999) + { + dwDeltaTime = 99999; + } + sprintf(traceMessage, "(%2u:%2u:%2u:%3u |%5lu) ", systemTime.tm_hour, + systemTime.tm_min, systemTime.tm_sec, 0, + static_cast<unsigned long>(dwDeltaTime)); + } + // Messages is 22 characters. + return 22; +} + +WebRtc_Word32 TraceLinux::AddBuildInfo(char* traceMessage) const +{ + sprintf(traceMessage, "Build info: %s", BUILDINFO); + // Include NULL termination (hence + 1). + return strlen(traceMessage) + 1; +} + +WebRtc_Word32 TraceLinux::AddDateTimeInfo(char* traceMessage) const +{ + time_t t; + time(&t); + sprintf(traceMessage, "Local Date: %s", ctime(&t)); + WebRtc_Word32 len = static_cast<WebRtc_Word32>(strlen(traceMessage)); + + if ('\n' == traceMessage[len - 1]) + { + traceMessage[len - 1] = '\0'; + --len; + } + + // Messages is 12 characters. + return len + 1; +} +} // namespace webrtc diff --git a/src/system_wrappers/source/trace_linux.h b/src/system_wrappers/source/trace_linux.h new file mode 100644 index 0000000000..6e327a0b72 --- /dev/null +++ b/src/system_wrappers/source/trace_linux.h @@ -0,0 +1,37 @@ +/* + * Copyright (c) 2011 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef WEBRTC_SYSTEM_WRAPPERS_SOURCE_TRACE_LINUX_H_ +#define WEBRTC_SYSTEM_WRAPPERS_SOURCE_TRACE_LINUX_H_ + +#include "critical_section_wrapper.h" +#include "trace_impl.h" + +namespace webrtc { +class TraceLinux : public TraceImpl +{ +public: + TraceLinux(); + virtual ~TraceLinux(); + + virtual WebRtc_Word32 AddThreadId(char *traceMessage) const; + virtual WebRtc_Word32 AddTime(char* traceMessage, + const TraceLevel level) const; + + virtual WebRtc_Word32 AddBuildInfo(char* traceMessage) const; + virtual WebRtc_Word32 AddDateTimeInfo(char* traceMessage) const; + +private: + volatile mutable WebRtc_UWord32 _prevAPITickCount; + volatile mutable WebRtc_UWord32 _prevTickCount; +}; +} // namespace webrtc + +#endif // WEBRTC_SYSTEM_WRAPPERS_SOURCE_TRACE_LINUX_H_ |