cyclefind.h

/*-
 * Copyright (c) 2021 Ryo Shimizu <ryo@nerv.org>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef _CYCLEFIND_H_
#define _CYCLEFIND_H_

/*
 * simple and faster version of Floyd's cycle-finding algorithm
 */

#define CYCLEFIND_DECL(name, type)					\
struct name {								\
	unsigned long n;						\
	unsigned long limit;						\
	unsigned long n2;						\
	type ctx;							\
}
#define CYCLEFIND_INIT(cf, lim)						\
	do {								\
		(cf)->n = 0;						\
		(cf)->n2 = 1;						\
		(cf)->limit = (lim);					\
	} while (0 /*CONSTCOND*/)

#define CYCLEFIND_OVERLIMIT(cf)						\
	((cf)->n >= (cf)->limit)

#define CYCLEFIND_TEST(cf, ctxp)					\
	(								\
	 ((cf)->n != 0 &&						\
	   memcmp(&(cf)->ctx, ctxp, sizeof((cf)->ctx)) == 0) ?		\
	 (((cf)->n) - ((cf)->n2 / 2) + 1) :				\
	 ((cf)->n++, ((cf)->n == (cf)->n2) && ((cf)->n2 <<= 1,		\
	  memcpy(&(cf)->ctx, ctxp, sizeof((cf)->ctx)), 0))		\
	)

#endif /* _CYCLEFIND_H_ */