summaryrefslogtreecommitdiff
path: root/server/leasechain.c
blob: 42a3fc6c8e74440349ce4dd0cb4440dba8784a6a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
/* leasechain.c

   Additional support for in-memory database support */

/*
 * Copyright (c) 2015-2017 by Internet Systems Consortium, Inc. ("ISC")
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT
 * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 *
 *   Internet Systems Consortium, Inc.
 *   950 Charter Street
 *   Redwood City, CA 94063
 *   <info@isc.org>
 *   https://www.isc.org/
 *
 */

/*! \file server\leasechaing.c
 *
 * \page leasechain structures overview
 *
 * A brief description of the leasechain structures
 * 
 * This file provides additional data structures for a leasecain to
 * provide faster access to leases on the queues associated with a pool
 * than a linear walk.  Each pool has a set of queues: active, free, backup,
 * expired and abandoned to track leases as they are handed out and returned.
 * The original code use a simply linear list for each of those pools but
 * this can present performance issues if the pool is large and the lists are
 * long.
 * This code adds an array on top of the list allowing us to search the list
 * in a binary fashion instead of a linear walk.
 *
 * \verbatim
 * leasechain
 * +------------+    +-------+-------+-------+-------+
 * | lease list |--> | lease | lease | lease | lease |....
 * | start      |    |  ptr  |  ptr  |  ptr  |  ptr  |
 * | end        |    +-------+-------+-------+-------+
 * | max        |                |       |
 * +------------+                V       V
 *                          +-------+  +-------+
 *                          | lease |  | lease |
 *                          |       |  |       |
 *                          |  next |->|  next |->NULL
 *                   NULL<- | prev  |<-| prev  |
 *                          +-------+  +-------+
 * 
 * The linked list is maintained in an ordered state.  Inserting an entry is
 * accomplished by doing a binary search on the array to find the proper place
 * in the list and then updating the pointers in the linked list to include the
 * new entry.  The entry is added into the array by copying the remainder of 
 * the array to provide space for the new entry.
 * Removing an entry is the reverse.
 * The arrays for the queues will be pre-allocated but not all of them will be
 * large enough to hold all of the leases.  If additional space is required the
 * array will be grown.
 */

#include "dhcpd.h"

#if defined (BINARY_LEASES)
/* Default number number of lease pointers to add to the leasechain array
 * everytime it grows beyond the current size
 */
#define LC_GROWTH_DELTA 256

/*!
 *
 * \brief Check if leasechain isn't empty
 *
 * \param lc The leasechain to check
 *
 * \return 1 if leasechain isn't empty
 */
int
lc_not_empty( struct leasechain *lc ) {
#if defined (DEBUG_BINARY_LEASES)
	log_debug("LC empty check %s:%d", MDL);
	INSIST(lc != NULL);
#endif

	return (lc->nelem > 0 ? 1 : 0);
}

/*!
 *
 * \brief Get the first lease from a leasechain
 *
 * \param lc The leasechain to check
 *
 * \return A pointer to the first lease from a lease chain, or NULL if none found
 */
struct lease *
lc_get_first_lease(struct leasechain *lc) {
#if defined (DEBUG_BINARY_LEASES)
	log_debug("LC Get first %s:%d", MDL);
	INSIST(lc != NULL);
	INSIST(lc->total >= lc->nelem);
#endif

	if (lc->nelem > 0) {
		return (lc->list)[0];
	}
	return (NULL);
}

/*!
 *
 * \brief Get the next lease from the chain, based on the lease passed in.
 *
 * \param lc The leasechain to check
 * \param lp The lease to start from
 *
 * \return The next lease in the ordered list after lp
 */
struct lease *
lc_get_next(struct leasechain *lc, struct lease *lp) {
#if defined (DEBUG_BINARY_LEASES)
	log_debug("LC Get next %s:%d", MDL);
	INSIST(lc != NULL);
	INSIST(lp != NULL);
#endif

	return lp->next;
}

/*!
 *
 * \brief Find the best position for inserting a lease
 *
 * Given a potential range of the array to insert the lease into this routine
 * will recursively examine the range to find the proper place in which to
 * insert the lease.
 * 
 * \param lc The leasechain to add the lease to
 * \param lp The lease to insert
 * \param min The minium index of the potential range for insertion
 * \param max The maximum index of the potential range for insertion
 *
 * \return The index of the array entry to insert the lease
 */
size_t 
lc_binary_search_insert_point(struct leasechain *lc,
			      struct lease *lp,
			      size_t min, size_t max)
{
	size_t mid_index = ((max - min)/2) + min;

	if ((lc->list[mid_index]->sort_time > lp->sort_time) ||
	    ((lc->list[mid_index]->sort_time == lp->sort_time) &&
	     (lc->list[mid_index]->sort_tiebreaker > lp->sort_tiebreaker))) {
		if (mid_index == min) {
			/* insert in the min position, as sort_time is larger */
			return (min);
		}
		/* try again with lower half of list */
		return (lc_binary_search_insert_point(lc, lp,
						      min, mid_index - 1));
	} else  if ((lc->list[mid_index]->sort_time < lp->sort_time) ||
		    ((lc->list[mid_index]->sort_time == lp->sort_time) && 
		     (lc->list[mid_index]->sort_tiebreaker < lp->sort_tiebreaker))) {
		if (mid_index == max) {
			/* insert in mid_index + 1 as sort_time is smaller */
			return (mid_index+1);
		}
		/* try again with upper half of list */
		return (lc_binary_search_insert_point(lc, lp,
						      mid_index + 1, max));
	}

	/* sort_time and sort_tiebreaker match, so insert in this position */
	return (mid_index);
}

/*!
 *
 * \brief Find an exact match for a lease
 *
 * Given a potential range of the array to search this routine
 * will recursively examine the range to find the proper lease
 * 
 * \param lc The leasechain to check
 * \param lp The lease to find
 * \param min The minium index of the search range
 * \param max The maximum index of the search range
 *
 * \return The index of the array entry for the lease, SIZE_MAX if the lease
 * wasn't found
 */

size_t
lc_binary_search_lease(struct leasechain *lc,
		       struct lease *lp,
		       size_t min, size_t max)
{
	size_t mid_index;
	size_t i;

	if (max < min) {
		/* lease not found */
		return (SIZE_MAX);
	}

	mid_index = ((max - min)/2) + min;

	if ((lc->list[mid_index]->sort_time > lp->sort_time) ||
	    ((lc->list[mid_index]->sort_time == lp->sort_time) &&
	     (lc->list[mid_index]->sort_tiebreaker > lp->sort_tiebreaker))) {
		if (mid_index == min) {
			/* lease not found */
			return (SIZE_MAX);
		} 
		/* try the lower half of the list */
		return (lc_binary_search_lease(lc, lp, min, mid_index - 1));
	} else if ((lc->list[mid_index]->sort_time < lp->sort_time) ||
		   ((lc->list[mid_index]->sort_time == lp->sort_time) &&
		    (lc->list[mid_index]->sort_tiebreaker < lp->sort_tiebreaker))) {
		/* try the upper half of the list */	  
		return (lc_binary_search_lease(lc, lp, mid_index + 1, max));
	}

	/*
	 * As sort_time/sort_tiebreaker may not be unique in the list, once we
	 * find a match, we need to look before and after from this position
	 * for all matching sort_time/sort_tiebreaker until we find the exact
	 * lease or until no matching lease is found
	 */
	if (lp == lc->list[mid_index]) {
		return (mid_index);
	}

	/* Check out entries below the mid_index */
	if (mid_index > min) {
		/* We will break out of the loop if we either go past the
	         * canddiates or hit the end of the range when i == min.  As
		 * i is unsigned we can't check it in the for loop itself.
		 */
		for (i = mid_index - 1; ; i--) {
			if (lp == lc->list[i]) {
				return (i);
			}

			/* Are we done with this range? */
			if ((i == min) ||
			    ((lc->list[i]->sort_time != lp->sort_time) || 
			     ((lc->list[i]->sort_time == lp->sort_time) &&
			      (lc->list[i]->sort_tiebreaker != lp->sort_tiebreaker)))) {
				break;
			}
		}
	}

	/* Check out entries above the mid_index */
	if (mid_index < max) {
		/* We will break out of the loop if we either go past the 
	         * canddiates or hit the end of the range when i == max.
		 */
		for (i = mid_index + 1; i <= max; i++) {
			if (lp == lc->list[i]) {
				return (i);
			}

			if ((lc->list[i]->sort_time != lp->sort_time) ||
			    ((lc->list[i]->sort_time == lp->sort_time) &&
			     (lc->list[i]->sort_tiebreaker != lp->sort_tiebreaker))) {
				break;
			}
		}
	}

	/* Lease not found */
	return (SIZE_MAX);
}

/*!
 *
 * \brief Increase the size of the array for the lease chain
 *
 * \param lc The leasechain to expand
 *
 * If we are unable to allocate memory we log a fatal error.  There's
 * not much else to do as we can't figure out where to put the lease.
 *
 * If we can allocate memory we copy the old lease chain to the new
 * lease chain and free the old.
 */
void
lc_grow_chain(struct leasechain *lc) {
#if defined (DEBUG_BINARY_LEASES)
	log_debug("LC grow lease chain max was %zu, %s:%d", lc->total, MDL);
#endif

	void *p;
	size_t temp_size;

	if (lc->growth == 0) 
		temp_size = lc->total + LC_GROWTH_DELTA;
	else
		temp_size = lc->total + lc->growth;

	/* try to allocate the memory */
	p = dmalloc(sizeof(struct lease *) * temp_size, MDL);
	if (p == NULL) {
		log_fatal("LC grow, unable to allocated memory %s:%d", MDL);
	}

	/* Success, copy the lease chain and install the new one */
	if (lc->list != NULL) {
		memcpy(p, lc->list, sizeof(struct lease *) * lc->nelem);
		dfree(lc->list, MDL);
	}
	lc->list = (struct lease **) p;
	lc->total = temp_size;

	return;
}


/*!
 *
 * \brief Link a lease to a lease chain position
 *
 * This function may increase the size of the lease chain if necessary and will
 * probably need to move entries in the lease chain around.
 *
 * \param lc The leasechain to update
 * \param lp The lease to insert
 * \param n  The position in which to insert the lease
 *
 */
void
lc_link_lcp(struct leasechain *lc, struct lease *lp, size_t n) {
#if defined (DEBUG_BINARY_LEASES)
	log_debug("LC link lcp %s:%d", MDL);
	INSIST (lc != NULL);
	INSIST (lp != NULL);
#endif

	if (lc->nelem == lc->total) {
		lc_grow_chain(lc);
	}

#if defined (DEBUG_BINARY_LEASES)
	log_debug("LC Link lcp position %zu, elem %zu, %s:%d",
		  n, lc->nelem, MDL);
#endif

	/* create room for the new pointer */
	if (n < lc->nelem) {
#if defined (DEBUG_BINARY_LEASES)
		log_debug("LC link lcp moving position %zu, moving %zu. %s:%d",
			  n, (lc->nelem-n), MDL);
#endif
		memmove(lc->list + n + 1,  lc->list + n,
			sizeof(struct lease *) * (lc->nelem-n));
	}

	/* clean any stale pointer info from this position before calling 
	 * lease_reference as it won't work if pointer is not NULL
	 */
	lc->list[n] = NULL;
	lease_reference(&(lc->list[n]), lp, MDL);

	lc->nelem++;

	lp->lc = lc;

	return;
}

/*!
 * 
 * \brief Insert the lease at the specified position in both the lease chain
 * and the linked list
 *
 * This function may increase the size of the lease chain if necessary and will
 * probably need to move entries in the lease chain around.
 * \param lc The leasechain to update
 * \param lp The lease to insert
 * \param n  The position in which to insert the lease
 *
 */
void
lc_add_lease_pos(struct leasechain *lc, struct lease *lp, size_t pos) {
#if defined (DEBUG_BINARY_LEASES)
	log_debug("LC Add lease position %zu, %s:%d", pos, MDL);
	INSIST (lc != NULL);
	INSIST (lp != NULL);
#endif
	lc_link_lcp(lc, lp, pos);

#if 0
	/* this shoudln't be necessary, if we still have pointers on
	 *  the lease being inserted things are broken
	 */
	if (lp->prev) {
		lease_dereference(&lp->prev, MDL);
	}
	if (lp->next) {
		lease_dereference(&lp->next, MDL);
	}
#endif

	/* not the first element? */
	if (pos > 0) {
		if (lc->list[pos-1]->next) {
			lease_dereference(&(lc->list[pos-1]->next), MDL);
		}
		lease_reference(&(lc->list[pos-1]->next), lp, MDL);
		lease_reference(&lp->prev, lc->list[pos-1], MDL );
	}

	/* not the last element? we've already bumped nelem when linking
	 * into the lease chain so nelem should never be zero here */
	if (pos < (lc->nelem-1)) {
		if (lc->list[pos+1]->prev) {
			lease_dereference(&(lc->list[pos+1]->prev), MDL);
		}
		lease_reference(&(lc->list[pos+1]->prev), lp,  MDL);
		lease_reference(&lp->next, lc->list[pos+1], MDL);
	}

	return;
}

#ifdef POINTER_DEBUG
/*!
 *
 * \brief Debug only code, check the lease to verify it is sorted
 *
 * \param lc The leasechain to verify
 *
 * Calls log_fatal if the leasechain is not properly sorted
 */
void
lc_check_lc_sort_order(struct leasechain *lc) {
	size_t i;
	TIME t = 0;
	long int tiebreak = 0;

	log_debug("LC check sort %s:%d", MDL);
	for (i = 0; i < lc->nelem; i++ ) {
		if ((lc->list[i]->sort_time < t)  ||
		    ((lc->list[i]->sort_time == t) && 
		     (lc->list[i]->tiebreaker < tiebreaker))) {
			if (i > 0) {
				print_lease(lc->list[i-1]);
			}
			print_lease(lc->list[i]);
			if (i < lc->nelem - 1) {
				print_lease(lc->list[i+1]);
			}
			log_fatal("lc[%p] not sorted properly", lc);
		}

		t = lc->list[i]->sort_time;
		tiebreak = lc->list[i]->sort_tiebreaker;
	}
}
#endif

/*!
 *
 * \brief Add a lease into the sorted lease and lease chain
 * The sort_time is set by the caller while the sort_tiebreaker is set here
 * The value doesn't much matter as long as it prvoides a way to have different
 * values in most of the leases.
 * 
 * When choosing a value for tiebreak we choose:
 *  0 for the first lease in the queue
 *  0 if the lease is going to the end of the queue with a sort_time greater
 *  than that of the current last lease
 *  previous tiebreaker + 1 if it is going to the end of the queue with a
 *  sort_time equal to that of the current last lease
 *  random if none of the above fit
 *
 * During startup when we can take advantage of the fact that leases may already
 * be sorted and so check the end of the list to see if we can simply add the
 * lease to the end.
 * 
 * \param lc The leasechain in which to insert the lease
 * \param lp The lease to insert
 *
 */
void
lc_add_sorted_lease(struct leasechain *lc, struct lease *lp) {
	size_t pos;

#if defined (DEBUG_BINARY_LEASES)
	log_debug("LC add sorted %s:%d", MDL);
	INSIST (lc != NULL);
	INSIST (lp != NULL);
#endif
	if (lc->nelem == 0) {
		/* The first lease start with a tiebreak of 0 and add it at
		 * the first position */
		lp->sort_tiebreaker = 0;

		lc_add_lease_pos(lc, lp, 0);
		/* log_debug("LC add sorted done, %s:%d", MDL); */

		return;
	}

	if (lp->sort_time > lc->list[lc->nelem-1]->sort_time) {
		/* Adding to end of queue, with a different sort time */
		lp->sort_tiebreaker = 0;
		pos = lc->nelem;
	} else if (lp->sort_time == lc->list[lc->nelem-1]->sort_time) {
		/* Adding to end of queue, with the same sort time */
		if (lc->list[lc->nelem-1]->sort_tiebreaker < LONG_MAX)
			lp->sort_tiebreaker =
			  lc->list[lc->nelem-1]->sort_tiebreaker+1;
		else
			lp->sort_tiebreaker = LONG_MAX;
		pos = lc->nelem;
	} else {
		/* Adding somewhere in the queue, just pick a random value */
		lp->sort_tiebreaker = random();
		pos = lc_binary_search_insert_point(lc, lp, 0, lc->nelem - 1);
	}

	/* Finally add it to the queue */
	lc_add_lease_pos(lc, lp, pos);

#if defined (DEBUG_BINARY_LEASES)
	log_debug("LC add sorted complete position %zu, elements %zu, %s:%d",
		  pos, lc->nelem, MDL);
#endif

#ifdef POINTER_DEBUG
	lc_check_lc_sort_order(lc);
#endif
}

/*!
 *
 * \brief Remove the Nth pointer from a leasechain structure and update counters.
 * The pointers in the array will be moved to fill in the hole if necessary.
 *
 * \param lc The lease chain to update
 * \param n the entry to remove from the lease chain
 */
void
lc_unlink_lcp(struct leasechain *lc, size_t n) {
#if defined (DEBUG_BINARY_LEASES)
	log_debug("LC unlink lcp %s:%d", MDL);

	/* element index to remove must be less than the number of elements present */
	INSIST(n < lc->nelem);
#endif

	/* Clear the pointer from the lease back to the LC */
	lc->list[n]->lc = NULL;

	/* Clear the pointer from the LC to the lease */
	lease_dereference(&(lc->list[n]), MDL);

	/*  memove unless we are removing the last element */
	if ((lc->nelem-1) > n) {
		memmove(lc->list + n, lc->list + n + 1,
			sizeof(struct lease *) * (lc->nelem-1-n));
	}
	lc->nelem--;
}

/*!
 *
 * \brief Remove a lease from a specific position. This will first unlink
 * the lease from the lease chain and then update the linked list.
 *
 * \param lc The lease chain to update
 * \param pos the entry to remove from the lease chain
 */
void
lc_unlink_lease_pos(struct leasechain *lc, size_t pos)
{
#if defined (DEBUG_BINARY_LEASES)
	INSIST(lc != NULL);
#endif

	struct lease *lp = NULL;
	lease_reference(&lp, lc->list[pos], MDL);

	/* unlink from lease chain list */
	lc_unlink_lcp(lc, pos);

	/* unlink from the linked list */
	if (lp->next) {
		lease_dereference(&lp->next->prev, MDL);
		if (lp->prev)
			lease_reference(&lp->next->prev, lp->prev, MDL);
	}
	if (lp->prev) {
		lease_dereference(&lp->prev->next, MDL);
		if (lp->next)
			lease_reference(&lp->prev->next, lp->next, MDL);
		lease_dereference(&lp->prev, MDL);
	}
	if (lp->next) {
		lease_dereference(&lp->next, MDL);
	}
	lease_dereference(&lp, MDL);
}

/*!
 *
 * \brief Find a lease in the lease chain and then remove it
 * If we can't find the lease on the given lease chain it's a fatal error.
 *
 * \param lc The lease chain to update
 * \param lp The lease to remove
 */
void
lc_unlink_lease(struct leasechain *lc, struct lease *lp) {
#if defined (DEBUG_BINARY_LEASES)
	log_debug("LC unlink lease %s:%d", MDL);

	INSIST(lc != NULL);
	INSIST(lc->list != NULL);
	INSIST(lp != NULL );
	INSIST(lp->lc != NULL );
	INSIST(lp->lc == lc );
#endif

	size_t pos = lc_binary_search_lease(lc, lp, 0, lc->nelem-1);
	if (pos == SIZE_MAX) {
		/* fatal, lease not found in leasechain */
		log_fatal("Lease with binding state %s not on its queue.",
			  (lp->binding_state < 1 ||
			   lp->binding_state > FTS_LAST)
			  ? "unknown"
			  : binding_state_names[lp->binding_state - 1]);
	}

	lc_unlink_lease_pos(lc, pos);
}

/*!
 *
 * \brief Unlink all the leases in the lease chain and free the
 * lease chain structure.  The leases will be freed if and when
 * any other references to them are cleared.
 *
 * \param lc the lease chain to clear
 */
void
lc_delete_all(struct leasechain *lc) {
	size_t i;

	if (lc->nelem > 0) {
		/* better to delete from the last one, to avoid the memmove */
		for (i = lc->nelem - 1; ; i--) {
			lc_unlink_lease_pos(lc, i);
			if (i == 0) {
				break;
			}
		}
	}

	/* and then get rid of the list itself */
	if (lc->list != NULL) {
		dfree(lc->list, MDL);
		lc->list = NULL;
	}

	lc->total = 0;
	lc->nelem = 0;
}

/*!
 *
 * \brief Set the growth value.  This is the number of elements to
 * add to the array whenever it needs to grow.
 *
 * \param lc the lease chain to set up
 * \param growth the growth value to use
 */
void
lc_init_growth(struct leasechain *lc, size_t growth) {
	lc->growth = growth;
}

#endif /* #if defined (BINARY_LEASES) */