go play outside Skyler posted:

C++ code:

template <int order>
void apply_lowpass(std::vector<double> & signal) {
	Iir::Butterworth::LowPass<order> f;
	// do the filtering on the signal
}

void run_lowpass(std::vector<double> & signal, int order) {
	if (order == 1) {
		apply_lowpass<1>(signal);
	} else if (order == 2) {
		apply_lowpass<2>(signal);
	} 
	// ...
	} else {
		throw std::invalid_argument("Filter orders > 10 are not supported");
	}
}

rjmccall posted:

Plorkyeran posted:

You have to make a struct which is partially specialized which has a single static function that contains your actual implementation and then call that from your public function. It's a ton of boilerplate unfortunately.

Alternatively, if you're using c++17 you can just do if constexpr (std::is_same_v<TimeType, float>) { ... } rather than template specialization. This is a little more limited in what can differ between the types but it's going to be way less code in this case.

Rocko Bonaparte posted:

I'm trying to understand the Linux kernel's hashtable.h. Right up at the beginning there's some pretty crazy macros:

code:

#define DEFINE_HASHTABLE(name, bits)						\
	struct hlist_head name[1 << (bits)] =					\
			{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

#define DEFINE_READ_MOSTLY_HASHTABLE(name, bits)				\
	struct hlist_head name[1 << (bits)] __read_mostly =			\
			{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

The thing is that I don't even understand that syntax! Like, what the heck does putting square brackets on the left side with three dots, then assigning something to it even mean?

If it matters, my compiler doesn't seem to get it either:

code:

userspace_hashtable.h:19:7: error: expected identifier before numeric constant
   19 |    { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

I'm first trying to use this in a userspace version that replaces the list implementation with a userspace-compatible one. I've used that particular code before fine. I don't think it's really coming into play here, but perhaps using g++ (since I'm trying to run Catch unit tests using this userspace hashtable) is causing problems. Is this something different between C and C++?

Rocko Bonaparte posted:

I'm trying to understand the Linux kernel's hashtable.h. Right up at the beginning there's some pretty crazy macros:

code:

#define DEFINE_HASHTABLE(name, bits)						\
	struct hlist_head name[1 << (bits)] =					\
			{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

#define DEFINE_READ_MOSTLY_HASHTABLE(name, bits)				\
	struct hlist_head name[1 << (bits)] __read_mostly =			\
			{ [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

The thing is that I don't even understand that syntax! Like, what the heck does putting square brackets on the left side with three dots, then assigning something to it even mean?

If it matters, my compiler doesn't seem to get it either:

code:

userspace_hashtable.h:19:7: error: expected identifier before numeric constant
   19 |    { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

I'm first trying to use this in a userspace version that replaces the list implementation with a userspace-compatible one. I've used that particular code before fine. I don't think it's really coming into play here, but perhaps using g++ (since I'm trying to run Catch unit tests using this userspace hashtable) is causing problems. Is this something different between C and C++?

Raenir Salazar posted:

I read afterwards that maybe the tree might have been unbalanced might have reduced the search efficiency to O(N); is there some trick to this problem?

rjmccall posted:

Honestly, that looks optimal; all the dependencies are inherent. A good compiler should even have everything it needs to do the core comparisons with one compare instruction plus branches on flags. If that solution is timing out then either the timeout is unreasonable, the tree is very badly unbalanced, or the tree is corrupt (e.g. has a loop). It’s reasonable to expect you to be able to identify those possibilities (well, assuming this is an appropriate question at all), but none of them are your responsibility to solve in a standard search-tree find algorithm. If you also implemented insertion, that’s different.

Jabor posted:

You can probably do better than tortoise+hare for the specific case of a binary search tree though - if you make a leftward transition, you have an exclusive upper bound for the subtree you are now searching, and similarly if you make a rightward transition then you now know an exclusive lower bound - and these bounds tighten as you get deeper in the tree. If there's a loop in the tree, that condition will be violated on some edge, so all you need to do is track your bounds and you can identify that edge the moment you see it.

roomforthetuna posted:

Don't even have to keep track of the bounds really - either left.data>=current.data or right.data<=current.data means some kind of tree corruption has occurred, and one of those must occur in case of a loop. (May also be caused by a malsorted tree though so if you're *specifically* looking for a loop then I think you'd still need to tortoise it.)

Jabor posted:

Not necessarily - consider the case where a.right = b, and b.left = a. The invariant appears to be maintained if you're looking at edges in isolation, but keeping track of overall bounds will tell you when you're linking back up the tree.

OddObserver posted:

But what if all values are the same?

Edit: I should go sleep. People don't normally make multisets.

Jabor posted:

If you're writing an implementation that needs to handle that then typically one of your bounds will be inclusive instead of exclusive (e.g. "elements to the right are greater or equal").

Jabor posted:

Not necessarily - consider the case where a.right = b, and b.left = a. The invariant appears to be maintained if you're looking at edges in isolation, but keeping track of overall bounds will tell you when you're linking back up the tree.

Xerophyte posted:

That sort of invariant can be useful but can also be problematic. Maintaining it means that rotations are not generally valid, and that it's not generally possible to balance the tree. If you control all the tree operations and don't need rotations or need to care about balancing, at least in the degenerate cases, then sure. My experience is that they're rare in practice; being able to do arbitrary rotations is useful.

The Scientist posted:

Can anyone help me understand a C networking programming mystery? Might need to repost in the sh/sc networking thread