Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1299643

[RFC 07/31] mars: add new module lib_pairing_heap

From Thomas Schoebel-Theuer <tst@schoebel-theuer.de>
Newsgroups linux.kernel
Subject [RFC 07/31] mars: add new module lib_pairing_heap
Date 2015-12-31 12:40 +0100
Message-ID <qLJKj-3PB-37@gated-at.bofh.it> (permalink)
References <qLJKi-3PB-3@gated-at.bofh.it>
Organization linux.* mail to news gateway

Show all headers | View raw

Signed-off-by: Thomas Schoebel-Theuer <tst@schoebel-theuer.de>
---
 include/linux/brick/lib_pairing_heap.h | 110 +++++++++++++++++++++++++++++++++
 1 file changed, 110 insertions(+)
 create mode 100644 include/linux/brick/lib_pairing_heap.h

diff --git a/include/linux/brick/lib_pairing_heap.h b/include/linux/brick/lib_pairing_heap.h
new file mode 100644
index 0000000..eb97097
--- /dev/null
+++ b/include/linux/brick/lib_pairing_heap.h
@@ -0,0 +1,110 @@
+/*
+ * MARS Long Distance Replication Software
+ *
+ * Copyright (C) 2010-2014 Thomas Schoebel-Theuer
+ * Copyright (C) 2011-2014 1&1 Internet AG
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ */
+
+#ifndef PAIRING_HEAP_H
+#define PAIRING_HEAP_H
+
+/* Algorithm: see http://en.wikipedia.org/wiki/Pairing_heap
+ * This is just an efficient translation from recursive to iterative form.
+ *
+ * Note: find_min() is so trivial that we don't implement it.
+ */
+
+/* generic version: KEYDEF is kept separate, allowing you to
+ * embed this structure into other container structures already
+ * possessing some key (just provide an empty KEYDEF in this case).
+ */
+#define _PAIRING_HEAP_TYPEDEF(KEYTYPE, KEYDEF)				\
+									\
+struct pairing_heap_##KEYTYPE {						\
+	KEYDEF								\
+	struct pairing_heap_##KEYTYPE *next;				\
+	struct pairing_heap_##KEYTYPE *subheaps;			\
+};									\
+/* this comment is for keeping TRAILING_SEMICOLON happy */
+
+/* less generic version: define the key inside.
+ */
+#define PAIRING_HEAP_TYPEDEF(KEYTYPE)					\
+	_PAIRING_HEAP_TYPEDEF(KEYTYPE, KEYTYPE key;)
+
+/* generic methods: allow arbitrary CMP() functions.
+ */
+#define _PAIRING_HEAP_FUNCTIONS(_STATIC, KEYTYPE, CMP)			\
+									\
+_STATIC									\
+struct pairing_heap_##KEYTYPE *_ph_merge_##KEYTYPE(struct pairing_heap_##KEYTYPE *heap1,\
+	struct pairing_heap_##KEYTYPE *heap2)				\
+{									\
+	if (!heap1)							\
+		return heap2;						\
+	if (!heap2)							\
+		return heap1;						\
+	if (CMP(heap1, heap2) < 0) {					\
+		heap2->next = heap1->subheaps;				\
+		heap1->subheaps = heap2;				\
+		return heap1;						\
+	}								\
+	heap1->next = heap2->subheaps;					\
+	heap2->subheaps = heap1;					\
+	return heap2;							\
+}									\
+									\
+_STATIC									\
+void ph_insert_##KEYTYPE(struct pairing_heap_##KEYTYPE **heap, struct pairing_heap_##KEYTYPE *new)\
+{									\
+	new->next = NULL;						\
+	new->subheaps = NULL;						\
+	*heap = _ph_merge_##KEYTYPE(*heap, new);			\
+}									\
+									\
+_STATIC									\
+void ph_delete_min_##KEYTYPE(struct pairing_heap_##KEYTYPE **heap)	\
+{									\
+	struct pairing_heap_##KEYTYPE *tmplist = NULL;			\
+	struct pairing_heap_##KEYTYPE *ptr;				\
+	struct pairing_heap_##KEYTYPE *next;				\
+	struct pairing_heap_##KEYTYPE *res;				\
+	if (!*heap) {							\
+		return;							\
+	}								\
+	for (ptr = (*heap)->subheaps; ptr; ptr = next) {		\
+		struct pairing_heap_##KEYTYPE *p2 = ptr->next;		\
+		next = p2;						\
+		if (p2) {						\
+			next = p2->next;				\
+			ptr = _ph_merge_##KEYTYPE(ptr, p2);		\
+		}							\
+		ptr->next = tmplist;					\
+		tmplist = ptr;						\
+	}								\
+	res = NULL;							\
+	for (ptr = tmplist; ptr; ptr = next) {				\
+		next = ptr->next;					\
+		res = _ph_merge_##KEYTYPE(res, ptr);			\
+	}								\
+	*heap = res;							\
+}
+
+/* some default CMP() function */
+#define PAIRING_HEAP_COMPARE(a, b) ((a)->key < (b)->key ? -1 : ((a)->key > (b)->key ? 1 : 0))
+
+/* less generic version: use the default CMP() function */
+#define PAIRING_HEAP_FUNCTIONS(_STATIC, KEYTYPE)			\
+	_PAIRING_HEAP_FUNCTIONS(_STATIC, KEYTYPE, PAIRING_HEAP_COMPARE)
+
+#endif
-- 
2.6.4

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[RFC 00/31] Current state of MARS Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:40 +0100
  [RFC 07/31] mars: add new module lib_pairing_heap Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:40 +0100
  [RFC 31/31] mars: activate build Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:40 +0100
  [RFC 04/31] mars: add new module brick_checking Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 29/31] mars: add new module Makefile Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 17/31] mars: add new module xio_bio Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 15/31] mars: add new module lib_mapfree Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 27/31] mars: add new module mars_proc Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 21/31] mars: add new module xio_copy Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 20/31] mars: add new module xio_if Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 13/31] mars: add new module xio Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 25/31] mars: add new module light_net Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 23/31] mars: add new module xio_server Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 01/31] mars: add new module lamport Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 19/31] mars: add new module xio_client Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 11/31] mars: add new module lib_timing Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 08/31] mars: add new module lib_queue Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 18/31] mars: add new module xio_sio Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 16/31] mars: add new module lib_log Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100
  [RFC 26/31] mars: add new module light_server_strategy Thomas Schoebel-Theuer <tst@schoebel-theuer.de> - 2015-12-31 12:50 +0100

csiph-web