1/* 2 * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de. 3 * All rights reserved. Distributed under the terms of the MIT license. 4 */ 5#ifndef MISC_H 6#define MISC_H 7 8#include <SupportDefs.h> 9 10#include "String.h" 11 12// min and max 13// We don't want to include <algobase.h> otherwise we also get <iostream.h> 14// and other undesired things. 15template<typename C> 16static inline C min(const C &a, const C &b) { return (a < b ? a : b); } 17template<typename C> 18static inline C max(const C &a, const C &b) { return (a > b ? a : b); } 19 20// find last (most significant) set bit 21static inline 22int 23fls(uint32 value) 24{ 25 if (!value) 26 return -1; 27 int index = 0; 28#define HAND_OPTIMIZED_FLS 1 29#if !HAND_OPTIMIZED_FLS 30// This is the algorithm in its pure form. 31 const uint32 masks[] = { 32 0xffff0000, 33 0xff00ff00, 34 0xf0f0f0f0, 35 0xcccccccc, 36 0xaaaaaaaa, 37 }; 38 int range = 16; 39 for (int i = 0; i < 5; i++) { 40 if (value & masks[i]) { 41 index += range; 42 value &= masks[i]; 43 } 44 range /= 2; 45 } 46#else // HAND_OPTIMIZED_FLS 47// This is how the compiler should optimize it for us: Unroll the loop and 48// inline the masks. 49 // 0: 0xffff0000 50 if (value & 0xffff0000) { 51 index += 16; 52 value &= 0xffff0000; 53 } 54 // 1: 0xff00ff00 55 if (value & 0xff00ff00) { 56 index += 8; 57 value &= 0xff00ff00; 58 } 59 // 2: 0xf0f0f0f0 60 if (value & 0xf0f0f0f0) { 61 index += 4; 62 value &= 0xf0f0f0f0; 63 } 64 // 3: 0xcccccccc 65 if (value & 0xcccccccc) { 66 index += 2; 67 value &= 0xcccccccc; 68 } 69 // 4: 0xaaaaaaaa 70 if (value & 0xaaaaaaaa) 71 index++; 72#endif // HAND_OPTIMIZED_FLS 73 return index; 74} 75 76// node_child_hash 77static inline 78uint32 79node_child_hash(uint64 id, const char *name) 80{ 81 return uint32(id & 0xffffffff) ^ string_hash(name); 82} 83 84#endif // MISC_H 85