# beanstalk源码剖析——数据结构 - blockcipher

Datetime:2016-08-23 03:47:37         Topic: Data Structure  Source Code Analysis          Share        Original >>

beanstalk中两种重要的数据结构就是集合和最小堆。

1. 集合

```集合
struct ms {
size_t used, cap, last;
void **items;
ms_event_fn oninsert, onremove;
};

void
ms_init(ms a, ms_event_fn oninsert, ms_event_fn onremove)
{
a->used = a->cap = a->last = 0;
a->items = NULL;
a->oninsert = oninsert;
a->onremove = onremove;
}

static void
grow(ms a)
{
void **nitems;
size_t ncap = (a->cap << 1) ? : 1;

nitems = malloc(ncap * sizeof(void *));
if (!nitems) return;

memcpy(nitems, a->items, a->used * sizeof(void *));
free(a->items);
a->items = nitems;
a->cap = ncap;
}

int
ms_append(ms a, void *item)
{
if (a->used >= a->cap) grow(a);
if (a->used >= a->cap) return 0;

a->items[a->used++] = item;
if (a->oninsert) a->oninsert(a, item, a->used - 1);
return 1;
}

static int
ms_delete(ms a, size_t i)
{
void *item;

if (i >= a->used) return 0;
item = a->items[i];
a->items[i] = a->items[--a->used];

/* it has already been removed now */
if (a->onremove) a->onremove(a, item, i);
return 1;
}

void
ms_clear(ms a)
{
while (ms_delete(a, 0));
free(a->items);
ms_init(a, a->oninsert, a->onremove);
}

int
ms_remove(ms a, void *item)
{
size_t i;

for (i = 0; i < a->used; i++) {
if (a->items[i] == item) return ms_delete(a, i);
}
return 0;
}

int
ms_contains(ms a, void *item)
{
size_t i;

for (i = 0; i < a->used; i++) {
if (a->items[i] == item) return 1;
}
return 0;
}

void *
ms_take(ms a)
{
void *item;

if (!a->used) return NULL;

a->last = a->last % a->used;
item = a->items[a->last];
ms_delete(a, a->last);
++a->last;
return item;
}```

2. 最小堆

```最小堆
struct Heap {
int     cap;
int     len;
void    **data;
Less    less;
Record  rec;
};

static void
set(Heap *h, int k, void *x)
{
h->data[k] = x;
h->rec(x, k);
}

static void
swap(Heap *h, int a, int b)
{
void *tmp;

tmp = h->data[a];
set(h, a, h->data[b]);
set(h, b, tmp);
}

static int
less(Heap *h, int a, int b)
{
return h->less(h->data[a], h->data[b]);
}

static void
siftdown(Heap *h, int k)
{
for (;;) {
int p = (k-1) / 2; /* parent */

if (k == 0 || less(h, p, k)) {
return;
}

swap(h, k, p);
k = p;
}
}

static void
siftup(Heap *h, int k)
{
for (;;) {
int l, r, s;

l = k*2 + 1; /* left child */
r = k*2 + 2; /* right child */

/* find the smallest of the three */
s = k;
if (l < h->len && less(h, l, s)) s = l;
if (r < h->len && less(h, r, s)) s = r;

if (s == k) {
return; /* satisfies the heap property */
}

swap(h, k, s);
k = s;
}
}

// Heapinsert inserts x into heap h according to h->less.
// It returns 1 on success, otherwise 0.
int
heapinsert(Heap *h, void *x)
{
int k;

if (h->len == h->cap) {
void **ndata;
int ncap = (h->len+1) * 2; /* allocate twice what we need */

ndata = malloc(sizeof(void*) * ncap);
if (!ndata) {
return 0;
}

memcpy(ndata, h->data, sizeof(void*)*h->len);
free(h->data);
h->data = ndata;
h->cap = ncap;
}

k = h->len;
h->len++;
set(h, k, x);
siftdown(h, k);
return 1;
}

void *
heapremove(Heap *h, int k)
{
void *x;

if (k >= h->len) {
return 0;
}

x = h->data[k];
h->len--;
set(h, k, h->data[h->len]);
siftdown(h, k);
siftup(h, k);
h->rec(x, -1);
return x;
}```