https://github.com/torvalds/linux
Revision 5885b9b3f030f9b430f6b1c7fa396c885033f2f8 authored by Linus Torvalds on 16 December 2011, 19:14:42 UTC, committed by Linus Torvalds on 16 December 2011, 19:14:42 UTC
* 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound: ALSA: HDA: Use LPIB Position fix for Intel SCH Poulsbo ALSA: hda: fix mute led polarity for HP laptops with buggy BIOS ALSA: HDA: Set position fix to LPIB for an Atom/Poulsbo based device ASoC: Fix hx4700 error handling to free gpios if snd_soc_register_card fails ASoC: WM8958: correctly show firmware magic on mismatch ASoC: mxs: Add appropriate MODULE_ALIAS() ASoC: mxs: Add missing MODULE_LICENSE("GPL") ASoC: Fix WM8996 24.576MHz clock operation ASoC: Include linux/module.h for smdk2443_wm9710 ASoC: Fix a typo in jive_wm8750 ASoC: Fix build dependency for SND_SOC_JZ4740_CODEC ASoC: Include linux/io.h for jz4740 codec
Tip revision: 5885b9b3f030f9b430f6b1c7fa396c885033f2f8 authored by Linus Torvalds on 16 December 2011, 19:14:42 UTC
Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound
Merge branch 'for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tiwai/sound
Tip revision: 5885b9b
prio_heap.c
/*
* Simple insertion-only static-sized priority heap containing
* pointers, based on CLR, chapter 7
*/
#include <linux/slab.h>
#include <linux/prio_heap.h>
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);
}
void *heap_insert(struct ptr_heap *heap, void *p)
{
void *res;
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 */
res = ptrs[0];
ptrs[0] = p;
pos = 0;
while (1) {
int left = 2 * pos + 1;
int right = 2 * pos + 2;
int largest = pos;
if (left < heap->size && heap->gt(ptrs[left], p))
largest = left;
if (right < heap->size && heap->gt(ptrs[right], ptrs[largest]))
largest = right;
if (largest == pos)
break;
/* Push p down the heap one level and bump one up */
ptrs[pos] = ptrs[largest];
ptrs[largest] = p;
pos = largest;
}
return res;
}
Computing file changes ...