From 162769efd7bca728713c4bf8e609fc408d58f512 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Mon, 23 May 2011 11:28:58 -0400 Subject: [PATCH] Remove GPL code from prio_heap Signed-off-by: Mathieu Desnoyers --- lib/prio_heap/prio_heap.c | 67 ++++++++++------------------------ lib/prio_heap/prio_heap.h | 75 ++++++++++++--------------------------- 2 files changed, 41 insertions(+), 101 deletions(-) diff --git a/lib/prio_heap/prio_heap.c b/lib/prio_heap/prio_heap.c index 8945c2a0..e660b0cd 100644 --- a/lib/prio_heap/prio_heap.c +++ b/lib/prio_heap/prio_heap.c @@ -1,31 +1,28 @@ /* - * LICENSING: this file is copied from the Linux kernel. We should therefore - * assume a GPLv2 license for the code that comes from the Linux mainline. - */ - -/* - * Static-sized priority heap containing pointers. Based on CLR, chapter 7. + * prio_heap.c + * + * Static-sized priority heap containing pointers. Based on CLRS, + * chapter 6. + * + * Copyright 2011 - Mathieu Desnoyers + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. */ #include #include -int heap_init(struct ptr_heap *heap, size_t size, gfp_t gfp_mask, - int (*gt)(void *, void *)) -{ - heap->ptrs = kmalloc(size, gfp_mask); - if (!heap->ptrs) - return -ENOMEM; - heap->size = 0; - heap->max = size / sizeof(void *); - heap->gt = gt; - return 0; -} - -void heap_free(struct ptr_heap *heap) -{ - kfree(heap->ptrs); -} +/* + * TODO implement heap_init, heap_free, heap_insert. + */ static void heapify(struct ptr_heap *heap, int pos) { @@ -67,32 +64,6 @@ void *heap_replace_max(struct ptr_heap *heap, void *p) return res; } -void *heap_insert(struct ptr_heap *heap, void *p) -{ - void **ptrs = heap->ptrs; - int pos; - - if (heap->size < heap->max) { - /* Heap insertion */ - pos = heap->size++; - while (pos > 0 && heap->gt(p, ptrs[(pos-1)/2])) { - ptrs[pos] = ptrs[(pos-1)/2]; - pos = (pos-1)/2; - } - ptrs[pos] = p; - return NULL; - } - - /* The heap is full, so something will have to be dropped */ - - /* If the new pointer is greater than the current max, drop it */ - if (heap->gt(p, ptrs[0])) - return p; - - /* Replace the current max and heapify */ - return heap_replace_max(heap, p); -} - void *heap_remove(struct ptr_heap *heap) { void **ptrs = heap->ptrs; diff --git a/lib/prio_heap/prio_heap.h b/lib/prio_heap/prio_heap.h index 3c058871..12b1638f 100644 --- a/lib/prio_heap/prio_heap.h +++ b/lib/prio_heap/prio_heap.h @@ -1,30 +1,29 @@ -/* - * LICENSING: this file is copied from the Linux kernel. We should therefore - * assume a GPLv2 license for the code that comes from the Linux mainline. - */ - -#ifndef _LINUX_PRIO_HEAP_H -#define _LINUX_PRIO_HEAP_H +#ifndef _LTTNG_PRIO_HEAP_H +#define _LTTNG_PRIO_HEAP_H /* - * Static-sized priority heap containing pointers. Based on CLR, chapter 7. + * prio_heap.h + * + * Static-sized priority heap containing pointers. Based on CLRS, + * chapter 6. + * + * Copyright 2011 - Mathieu Desnoyers + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. */ -#include - -/** - * struct ptr_heap - simple static-sized priority heap - * @ptrs - pointer to data area - * @max - max number of elements that can be stored in @ptrs - * @size - current number of valid elements in @ptrs (in the range 0..@size-1 - * @gt: comparison operator, which should implement "greater than" +/* + * TODO: + * implement struct ptr_head, heap_init, heap_free, heap_insert. */ -struct ptr_heap { - void **ptrs; - int max; - int size; - int (*gt)(void *, void *); -}; /** * heap_maximum - return the largest element in the heap @@ -38,36 +37,6 @@ static inline void *heap_maximum(const struct ptr_heap *heap) return heap->size ? heap->ptrs[0] : NULL; } -/** - * heap_init - initialize an empty heap with a given memory size - * @heap: the heap structure to be initialized - * @size: amount of memory to use in bytes - * @gfp_mask: mask to pass to kmalloc() - * @gt: comparison operator, which should implement "greater than" - */ -extern int heap_init(struct ptr_heap *heap, size_t size, gfp_t gfp_mask, - int (*gt)(void *, void *)); - -/** - * heap_free - release a heap's storage - * @heap: the heap structure whose data should be released - */ -void heap_free(struct ptr_heap *heap); - -/** - * heap_insert - insert a value into the heap and return any overflowed value - * @heap: the heap to be operated on - * @p: the pointer to be inserted - * - * Attempts to insert the given value into the priority heap. If the - * heap is full prior to the insertion, then the resulting heap will - * consist of the smallest @max elements of the original heap and the - * new element; the greatest element will be removed from the heap and - * returned. Note that the returned element will be the new element - * (i.e. no change to the heap) if the new element is greater than all - * elements currently in the heap. - */ -extern void *heap_insert(struct ptr_heap *heap, void *p); /** * heap_remove - remove the largest element from the heap @@ -103,4 +72,4 @@ extern void *heap_cherrypick(struct ptr_heap *heap, void *p); */ extern void *heap_replace_max(struct ptr_heap *heap, void *p); -#endif /* _LINUX_PRIO_HEAP_H */ +#endif /* _LTTNG_PRIO_HEAP_H */ -- 2.34.1