heap.c File Reference
#include "squid.h"
#include "heap.h"
#include "util.h"
Include dependency graph for heap.c:

Go to the source code of this file.

Macros

#define mutex_lock(m)   (void)0
 
#define mutex_unlock(m)   (void)0
 
#define mutex_trylock(m)   (void)0
 
#define mutex_init(m)   ((m)=123456)
 
#define Left(x)   (2 * (x) + 1)
 
#define Right(x)   (2 * (x) + 2)
 
#define Parent(x)   ((int)((x)-1)/2)
 
#define Threshold   10000
 
#define NormalRate   2
 
#define SlowRate   1.5
 
#define MinSize   32
 

Functions

static void _heap_ify_up (heap *hp, heap_node *elm)
 
static void _heap_ify_down (heap *hp, heap_node *elm)
 
static int _heap_should_grow (heap *hp)
 
static void _heap_grow (heap *hp)
 
static void _heap_swap_element (heap *hp, heap_node *elm1, heap_node *elm2)
 
static int _heap_node_exist (heap *hp, int id)
 
heapnew_heap (int initSize, heap_key_func gen_key)
 
void delete_heap (heap *hp)
 
heap_nodeheap_insert (heap *hp, void *dat)
 
heap_t heap_delete (heap *hp, heap_node *elm)
 
heap_key heap_gen_key (heap *hp, heap_t dat)
 
heap_t heap_extractmin (heap *hp)
 
heap_t heap_extractlast (heap *hp)
 
heap_t heap_update (heap *hp, heap_node *elm, void *dat)
 
void * heap_peepmin (heap *hp)
 
heap_key heap_peepminkey (heap *hp)
 
heap_key heap_peepkey (heap *hp, int n)
 
void * heap_peep (heap *hp, int n)
 
int heap_nodes (heap *hp)
 
int heap_empty (heap *hp)
 
static void heap_print_inorder (heap *hp, int id)
 
int verify_heap_property (heap *hp)
 

Macro Definition Documentation

#define Left (   x)    (2 * (x) + 1)

Definition at line 55 of file heap.c.

Referenced by _heap_ify_down(), and verify_heap_property().

#define MinSize   32

Definition at line 62 of file heap.c.

Referenced by new_heap().

#define mutex_init (   m)    ((m)=123456)

Definition at line 39 of file heap.c.

#define mutex_lock (   m)    (void)0

Definition at line 36 of file heap.c.

Referenced by heap_extractmin().

#define mutex_trylock (   m)    (void)0

Definition at line 38 of file heap.c.

#define mutex_unlock (   m)    (void)0

Definition at line 37 of file heap.c.

Referenced by heap_extractmin().

#define NormalRate   2

Definition at line 60 of file heap.c.

Referenced by _heap_grow().

#define Parent (   x)    ((int)((x)-1)/2)

Definition at line 57 of file heap.c.

Referenced by _heap_ify_up(), heap_delete(), and heap_update().

#define Right (   x)    (2 * (x) + 2)

Definition at line 56 of file heap.c.

Referenced by _heap_ify_down(), and verify_heap_property().

#define SlowRate   1.5

Definition at line 61 of file heap.c.

Referenced by _heap_grow().

#define Threshold   10000

Definition at line 59 of file heap.c.

Referenced by _heap_grow().

Function Documentation

static void _heap_grow ( heap hp)
static

Definition at line 405 of file heap.c.

References i, _heap::nodes, NormalRate, _heap::size, SlowRate, Threshold, xfree, and xrealloc().

Referenced by heap_insert().

static void _heap_ify_down ( heap hp,
heap_node elm 
)
static
static void _heap_ify_up ( heap hp,
heap_node elm 
)
static

Definition at line 352 of file heap.c.

References _heap_swap_element(), _heap_node::id, _heap_node::key, _heap::nodes, and Parent.

Referenced by heap_delete(), heap_insert(), and heap_update().

static int _heap_node_exist ( heap hp,
int  id 
)
static
static int _heap_should_grow ( heap hp)
static

Definition at line 394 of file heap.c.

References _heap::last, and _heap::size.

Referenced by heap_insert().

static void _heap_swap_element ( heap hp,
heap_node elm1,
heap_node elm2 
)
static

Definition at line 368 of file heap.c.

References _heap_node::id, and _heap::nodes.

Referenced by _heap_ify_down(), _heap_ify_up(), and heap_delete().

void delete_heap ( heap hp)

Definition at line 95 of file heap.c.

References assert, i, _heap::last, _heap::nodes, NULL, and xfree.

int heap_empty ( heap hp)

Definition at line 306 of file heap.c.

References _heap::last.

Referenced by heap_purgeNext().

heap_t heap_extractlast ( heap hp)

Definition at line 210 of file heap.c.

References _heap_node_exist(), assert, data, _heap_node::data, _heap::last, _heap::nodes, and xfree.

Referenced by heap_delete().

heap_t heap_extractmin ( heap hp)

Definition at line 188 of file heap.c.

References data, _heap_node::data, heap_delete(), _heap::last, _heap::lock, mutex_lock, mutex_unlock, _heap::nodes, and NULL.

Referenced by heap_purgeNext().

heap_key heap_gen_key ( heap hp,
heap_t  dat 
)

Definition at line 177 of file heap.c.

References _heap::age, and _heap::gen_key.

Referenced by heap_insert(), and heap_update().

heap_node* heap_insert ( heap hp,
void *  dat 
)
int heap_nodes ( heap hp)

Definition at line 294 of file heap.c.

References _heap::last.

Referenced by heap_walkNext().

void* heap_peep ( heap hp,
int  n 
)

Definition at line 281 of file heap.c.

References _heap_node_exist(), assert, data, _heap_node::data, and _heap::nodes.

Referenced by heap_walkNext().

heap_key heap_peepkey ( heap hp,
int  n 
)

Definition at line 268 of file heap.c.

References _heap_node_exist(), assert, _heap_node::key, and _heap::nodes.

void* heap_peepmin ( heap hp)

Definition at line 247 of file heap.c.

References _heap_node_exist(), assert, _heap_node::data, and _heap::nodes.

heap_key heap_peepminkey ( heap hp)

Definition at line 257 of file heap.c.

References _heap_node_exist(), assert, _heap_node::key, and _heap::nodes.

Referenced by heap_purgeNext().

static void heap_print_inorder ( heap hp,
int  id 
)
static

Definition at line 443 of file heap.c.

References _heap_node::key, last, and _heap::nodes.

Referenced by verify_heap_property().

heap_t heap_update ( heap hp,
heap_node elm,
void *  dat 
)
heap* new_heap ( int  initSize,
heap_key_func  gen_key 
)

Definition at line 72 of file heap.c.

References _heap::age, assert, _heap::gen_key, _heap::last, MinSize, _heap::nodes, NULL, _heap::size, xcalloc, and xmalloc.

Referenced by createRemovalPolicy_heap().

int verify_heap_property ( heap hp)

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors