⛏️ index : haiku.git

9f786b6af7bead1c60ed5e497dfc0a6fc0bc2930 [patch]

1171436f138dd05f9d963578277cdf75512a14b3

9c4c97f7f18c159db6a5567ca1f4011ad9984e18

9f786b6af7bead1c60ed5e497dfc0a6fc0bc2930.tar.gz

Rename "headers/private/utils" to "util".

This undoes some changes from cf930b7e6c1ec2b0fef6815a3cf1a5f1d6652c9d.

Nearly all the other utility directories in the tree are named "util"
not "utils", so let's be consistent.

Diff

 headers/private/util/BitUtils.h                           | 140 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 headers/private/utils/BitUtils.h                          | 140 --------------------------------------------------------------------------------
 src/libs/compat/freebsd_network/malloc.cpp                |   2 +-
 src/system/kernel/util/Bitmap.cpp                         |   2 +-
 src/system/kernel/vm/vm.cpp                               |   3 +--
 src/add-ons/input_server/devices/mouse/movement_maker.cpp |   2 +-
 src/add-ons/kernel/file_systems/ramfs/DataContainer.cpp   |   3 +--
 src/system/kernel/arch/x86/arch_cpu.cpp                   |   3 +--
 src/add-ons/kernel/busses/scsi/ahci/ahci_controller.cpp   |   3 +--
 9 files changed, 147 insertions(+), 151 deletions(-)

diff --git a/headers/private/util/BitUtils.h b/headers/private/util/BitUtils.h
new file mode 100644
index 0000000..ed092ca 100644
--- /dev/null
+++ b/headers/private/util/BitUtils.h
@@ -1,0 +1,140 @@
/*
 * Copyright 2013 Haiku, Inc. All rights reserved.
 * Distributed under the terms of the MIT License.
 *
 * Authors:
 *		Paweł Dziepak, pdziepak@quarnos.org
 */
#ifndef KERNEL_UTIL_BITUTIL_H
#define KERNEL_UTIL_BITUTIL_H


#include <string.h>

#include <SupportDefs.h>


// http://graphics.stanford.edu/~seander/bithacks.html
static inline uint32
next_power_of_2(uint32 v)
{
	v--;
	v |= v >> 1;
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;
	v++;

	return v;
}


// http://graphics.stanford.edu/~seander/bithacks.html
static inline uint32
count_set_bits(uint32 v)
{
	v = v - ((v >> 1) & 0x55555555);
	v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
	return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
}


static inline uint32
fls(uint32 value)
{
	if (value == 0)
		return 0;

#if __has_builtin(__builtin_clz)

	return ((sizeof(value) * 8) - __builtin_clz(value));
#else
	// https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
	static const uint32 masks[] = {
		0xaaaaaaaa,
		0xcccccccc,
		0xf0f0f0f0,
		0xff00ff00,
		0xffff0000
	};
	uint32 result = (value & masks[0]) != 0;
	for (int i = 4; i > 0; i--)
		result |= ((value & masks[i]) != 0) << i;
	return result + 1;
#endif
}


static inline uint32
log2(uint32 v)
{
	static const int MultiplyDeBruijnBitPosition[32] = {
		0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
		8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
	};

	v |= v >> 1;
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;

	return MultiplyDeBruijnBitPosition[(uint32)(v * 0x07C4ACDDU) >> 27];
}


template<typename T>
void
bitmap_shift(T* bits, size_t bitCount, ssize_t shift)
{
	if (shift == 0)
		return;

	const size_t bitsPerElement = sizeof(T) * 8;
	const size_t elementsCount = (bitCount + bitsPerElement - 1) / bitsPerElement;
	const size_t absoluteShift = (shift > 0) ? shift : -shift;
	const size_t nElements = absoluteShift / bitsPerElement;
	const size_t nBits = absoluteShift % bitsPerElement;
	if (nElements != 0) {
		if (shift > 0) {
			// "Left" shift.
			memmove(&bits[nElements], bits, sizeof(T) * (elementsCount - nElements));
			memset(bits, 0, sizeof(T) * nElements);
		} else if (shift < 0) {
			// "Right" shift.
			memmove(bits, &bits[nElements], sizeof(T) * (elementsCount - nElements));
			memset(&bits[elementsCount - nElements], 0, sizeof(T) * nElements);
		}
	}

	// If the shift was by a multiple of the element size, nothing more to do.
	if (nBits == 0)
		return;

	// One set of bits comes from the "current" element and are shifted in the
	// direction of the shift; the other set comes from the next-processed
	// element and are shifted in the opposite direction.
	if (shift > 0) {
		// "Left" shift.
		for (ssize_t i = elementsCount - 1; i >= 0; i--) {
			T low = 0;
			if (i != 0)
				low = bits[i - 1] >> (bitsPerElement - nBits);
			const T high = bits[i] << nBits;
			bits[i] = low | high;
		}
	} else if (shift < 0) {
		// "Right" shift.
		for (size_t i = 0; i < elementsCount; i++) {
			const T low = bits[i] >> nBits;
			T high = 0;
			if (i != (elementsCount - 1))
				high = bits[i + 1] << (bitsPerElement - nBits);
			bits[i] = low | high;
		}
	}
}


#endif	// KERNEL_UTIL_BITUTIL_H

diff --git a/headers/private/utils/BitUtils.h b/headers/private/utils/BitUtils.h
deleted file mode 100644
index ed092ca..0000000 100644
--- a/headers/private/utils/BitUtils.h
+++ /dev/null
@@ -1,140 +1,0 @@
/*
 * Copyright 2013 Haiku, Inc. All rights reserved.
 * Distributed under the terms of the MIT License.
 *
 * Authors:
 *		Paweł Dziepak, pdziepak@quarnos.org
 */
#ifndef KERNEL_UTIL_BITUTIL_H
#define KERNEL_UTIL_BITUTIL_H


#include <string.h>

#include <SupportDefs.h>


// http://graphics.stanford.edu/~seander/bithacks.html
static inline uint32
next_power_of_2(uint32 v)
{
	v--;
	v |= v >> 1;
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;
	v++;

	return v;
}


// http://graphics.stanford.edu/~seander/bithacks.html
static inline uint32
count_set_bits(uint32 v)
{
	v = v - ((v >> 1) & 0x55555555);
	v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
	return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24;
}


static inline uint32
fls(uint32 value)
{
	if (value == 0)
		return 0;

#if __has_builtin(__builtin_clz)

	return ((sizeof(value) * 8) - __builtin_clz(value));
#else
	// https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
	static const uint32 masks[] = {
		0xaaaaaaaa,
		0xcccccccc,
		0xf0f0f0f0,
		0xff00ff00,
		0xffff0000
	};
	uint32 result = (value & masks[0]) != 0;
	for (int i = 4; i > 0; i--)
		result |= ((value & masks[i]) != 0) << i;
	return result + 1;
#endif
}


static inline uint32
log2(uint32 v)
{
	static const int MultiplyDeBruijnBitPosition[32] = {
		0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
		8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
	};

	v |= v >> 1;
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;

	return MultiplyDeBruijnBitPosition[(uint32)(v * 0x07C4ACDDU) >> 27];
}


template<typename T>
void
bitmap_shift(T* bits, size_t bitCount, ssize_t shift)
{
	if (shift == 0)
		return;

	const size_t bitsPerElement = sizeof(T) * 8;
	const size_t elementsCount = (bitCount + bitsPerElement - 1) / bitsPerElement;
	const size_t absoluteShift = (shift > 0) ? shift : -shift;
	const size_t nElements = absoluteShift / bitsPerElement;
	const size_t nBits = absoluteShift % bitsPerElement;
	if (nElements != 0) {
		if (shift > 0) {
			// "Left" shift.
			memmove(&bits[nElements], bits, sizeof(T) * (elementsCount - nElements));
			memset(bits, 0, sizeof(T) * nElements);
		} else if (shift < 0) {
			// "Right" shift.
			memmove(bits, &bits[nElements], sizeof(T) * (elementsCount - nElements));
			memset(&bits[elementsCount - nElements], 0, sizeof(T) * nElements);
		}
	}

	// If the shift was by a multiple of the element size, nothing more to do.
	if (nBits == 0)
		return;

	// One set of bits comes from the "current" element and are shifted in the
	// direction of the shift; the other set comes from the next-processed
	// element and are shifted in the opposite direction.
	if (shift > 0) {
		// "Left" shift.
		for (ssize_t i = elementsCount - 1; i >= 0; i--) {
			T low = 0;
			if (i != 0)
				low = bits[i - 1] >> (bitsPerElement - nBits);
			const T high = bits[i] << nBits;
			bits[i] = low | high;
		}
	} else if (shift < 0) {
		// "Right" shift.
		for (size_t i = 0; i < elementsCount; i++) {
			const T low = bits[i] >> nBits;
			T high = 0;
			if (i != (elementsCount - 1))
				high = bits[i + 1] << (bitsPerElement - nBits);
			bits[i] = low | high;
		}
	}
}


#endif	// KERNEL_UTIL_BITUTIL_H

diff --git a/src/libs/compat/freebsd_network/malloc.cpp b/src/libs/compat/freebsd_network/malloc.cpp
index 54e4a11..c64deee 100644
--- a/src/libs/compat/freebsd_network/malloc.cpp
+++ b/src/libs/compat/freebsd_network/malloc.cpp
@@ -11,7 +11,7 @@
#include <stdio.h>
#include <string.h>

#include <utils/BitUtils.h>
#include <util/BitUtils.h>

#include <kernel/heap.h>
#include <kernel/vm/vm.h>
diff --git a/src/system/kernel/util/Bitmap.cpp b/src/system/kernel/util/Bitmap.cpp
index 5485cb6..0a11af9 100644
--- a/src/system/kernel/util/Bitmap.cpp
+++ b/src/system/kernel/util/Bitmap.cpp
@@ -11,7 +11,7 @@
#include <stdlib.h>
#include <string.h>

#include <utils/BitUtils.h>
#include <util/BitUtils.h>


namespace BKernel {
diff --git a/src/system/kernel/vm/vm.cpp b/src/system/kernel/vm/vm.cpp
index 24fe6ae..d88ccad 100644
--- a/src/system/kernel/vm/vm.cpp
+++ b/src/system/kernel/vm/vm.cpp
@@ -47,14 +47,13 @@
#include <team.h>
#include <tracing.h>
#include <util/AutoLock.h>
#include <util/BitUtils.h>
#include <util/ThreadAutoLock.h>
#include <vm/vm_page.h>
#include <vm/vm_priv.h>
#include <vm/VMAddressSpace.h>
#include <vm/VMArea.h>
#include <vm/VMCache.h>

#include <utils/BitUtils.h>

#include "VMAddressSpaceLocking.h"
#include "VMAnonymousCache.h"
diff --git a/src/add-ons/input_server/devices/mouse/movement_maker.cpp b/src/add-ons/input_server/devices/mouse/movement_maker.cpp
index e7739dd..f101071 100644
--- a/src/add-ons/input_server/devices/mouse/movement_maker.cpp
+++ b/src/add-ons/input_server/devices/mouse/movement_maker.cpp
@@ -23,7 +23,7 @@
#include <stdlib.h>
#include <math.h>

#include <private/utils/BitUtils.h>
#include <util/BitUtils.h>

//#define TRACE_MOVEMENT_MAKER

diff --git a/src/add-ons/kernel/file_systems/ramfs/DataContainer.cpp b/src/add-ons/kernel/file_systems/ramfs/DataContainer.cpp
index 3ec34fb..6d34268 100644
--- a/src/add-ons/kernel/file_systems/ramfs/DataContainer.cpp
+++ b/src/add-ons/kernel/file_systems/ramfs/DataContainer.cpp
@@ -8,11 +8,10 @@

#include <StackOrHeapArray.h>
#include <util/AutoLock.h>
#include <util/BitUtils.h>
#include <slab/Slab.h>
#include <thread.h>
#include <vfs.h>

#include <utils/BitUtils.h>

#include <vm/VMCache.h>
#include <vm/vm_page.h>
diff --git a/src/system/kernel/arch/x86/arch_cpu.cpp b/src/system/kernel/arch/x86/arch_cpu.cpp
index 1fc5eaf..c9fea50 100644
--- a/src/system/kernel/arch/x86/arch_cpu.cpp
+++ b/src/system/kernel/arch/x86/arch_cpu.cpp
@@ -26,11 +26,10 @@
#include <elf.h>
#include <safemode.h>
#include <smp.h>
#include <util/BitUtils.h>
#include <vm/vm.h>
#include <vm/vm_types.h>
#include <vm/VMAddressSpace.h>

#include <utils/BitUtils.h>

#include <arch_system_info.h>
#include <arch/x86/apic.h>
diff --git a/src/add-ons/kernel/busses/scsi/ahci/ahci_controller.cpp b/src/add-ons/kernel/busses/scsi/ahci/ahci_controller.cpp
index 63d5697..0bd81b0 100644
--- a/src/add-ons/kernel/busses/scsi/ahci/ahci_controller.cpp
+++ b/src/add-ons/kernel/busses/scsi/ahci/ahci_controller.cpp
@@ -11,8 +11,7 @@
#include <stdio.h>
#include <string.h>
#include <new>

#include <utils/BitUtils.h>
#include <util/BitUtils.h>

#define TRACE(a...) dprintf("ahci: " a)
#define FLOW(a...)	dprintf("ahci: " a)