1 /*-
2  * SPDX-License-Identifier: BSD-2-Clause
4  * Copyright (c) 1998-2002,2010 Luigi Rizzo, Universita` di Pisa
72 #define HEAP_FATHER(x) ( ( (x) - 1 ) / 2 )
82 	if ((unsigned int)h->size >= new_size )	/* have enough room */  in heap_resize()
95 		printf("--- %s, resize %d failed\n", __func__, new_size );  in heap_resize()
98 	if (h->size > 0) {  in heap_resize()
99 		bcopy(h->p, p, h->size * sizeof(*p) );  in heap_resize()
100 		free(h->p, M_DN_HEAP);  in heap_resize()
102 	h->p = p;  in heap_resize()
103 	h->size = new_size;  in heap_resize()
112 	h->elements = 0;  in heap_init()
113 	h->ofs = ofs;  in heap_init()
121  * bubble-up.
128 	if (h->ofs > 0)						\
129 	    *((int32_t *)((char *)(h->p[i].object) + h->ofs)) = i;	\
136 	if (h->ofs > 0)						\
137 	    *((int32_t *)((char *)(h->p[i].object) + h->ofs)) = -16;	\
143 	int son = h->elements;  in heap_insert()
149 		son = h->elements;  in heap_insert()
150 		if (son == h->size) /* need resize... */  in heap_insert()
152 			if (heap_resize(h, h->elements+16) )  in heap_insert()
154 		h->p[son].object = p;  in heap_insert()
155 		h->p[son].key = key1;  in heap_insert()
156 		h->elements++;  in heap_insert()
163 		if (DN_KEY_LT( h->p[father].key, h->p[son].key ) )  in heap_insert()
166 		HEAP_SWAP(h->p[son], h->p[father], tmp);  in heap_insert()
180 	int child, father, max = h->elements - 1;  in heap_extract()  local
182 	if (max < 0) {  in heap_extract()
188 		if (h->ofs <= 0)  in heap_extract()
191 		father = *((int *)((char *)obj + h->ofs));  in heap_extract()
192 		if (father < 0 || father >= h->elements)  in heap_extract()
197 	if (obj != NULL && h->p[father].object != obj)  in heap_extract()
207 	while ( (child = HEAP_LEFT(father)) <= max ) {  in heap_extract()
208 		if (child != max &&  in heap_extract()
209 		    DN_KEY_LT(h->p[child+1].key, h->p[child].key) )  in heap_extract()
211 		h->p[father] = h->p[child];  in heap_extract()
215 	h->elements--;  in heap_extract()
216 	if (father != max) {  in heap_extract()
221 		h->p[father] = h->p[max];  in heap_extract()
236 	int temp, i, max = h->elements-1;
239 	if (h->ofs <= 0)
241 	p = h->p;	/* shortcut */
243 	i = *((int *)((char *)object + h->ofs));
254 		while ( (temp = HEAP_LEFT(i)) <= max ) {
256 			if (temp != max &&
281 	for (i = 0; i < h->elements; i++ )  in heapify()
291 	for (i = found = 0 ; i < h->elements ;) {  in heap_scan()
292 		ret = fn(h->p[i].object, arg);  in heap_scan()
294 			h->elements-- ;  in heap_scan()
295 			h->p[i] = h->p[h->elements] ;  in heap_scan()
313 	if (h->size >0 )  in heap_free()
314 		free(h->p, M_DN_HEAP);  in heap_free()
323         int buckets;            /* how many buckets, really buckets - 1*/
359 	 * The ht->buckets variable store the bucket size - 1 to simply  in dn_ht_init()
360 	 * do an AND between the index returned by hash function and ht->bucket  in dn_ht_init()
364 	int b_max; /* max buckets */  in dn_ht_init()
368 		printf("--- missing hash or match function");  in dn_ht_init()
375 	/* calculate next power of 2, - 1*/  in dn_ht_init()
392 		if (buckets <= ht->buckets) {  in dn_ht_init()
393 			ht->buckets = buckets;  in dn_ht_init()
396 			if (ht->ht != (void *)(ht + 1))  in dn_ht_init()
397 				free(ht->ht, M_DN_HEAP);  in dn_ht_init()
410 		ht->ht = (void **)(ht + 1);  in dn_ht_init()
411 		ht->buckets = buckets;  in dn_ht_init()
412 		ht->ofs = ofs;  in dn_ht_init()
413 		ht->hash = h;  in dn_ht_init()
414 		ht->match = match;  in dn_ht_init()
415 		ht->newh = newh;  in dn_ht_init()
437 		if (ht->ht && ht->ht != (void *)(ht + 1))  in dn_ht_free()
438 			free(ht->ht, M_DN_HEAP);  in dn_ht_free()
446 	return ht ? ht->entries : 0;  in dn_ht_entries()
458 	i = (ht->buckets == 1) ? 0 :  in dn_ht_find()
459 		(ht->hash(key, flags, arg) & ht->buckets);  in dn_ht_find()
461 	for (pp = &ht->ht[i]; (p = *pp); pp = (void **)((char *)p + ht->ofs)) {  in dn_ht_find()
465 		} else if (ht->match(p, key, flags, arg)) /* found match */  in dn_ht_find()
471 			*pp = *(void **)((char *)p + ht->ofs);  in dn_ht_find()
472 			*(void **)((char *)p + ht->ofs) = NULL;  in dn_ht_find()
473 			ht->entries--;  in dn_ht_find()
477 		//	__FUNCTION__, i, ht->ofs);  in dn_ht_find()
478 		p = ht->newh ? ht->newh(key, flags, arg) : (void *)key;  in dn_ht_find()
481 			ht->entries++;  in dn_ht_find()
482 			*(void **)((char *)p + ht->ofs) = ht->ht[i];  in dn_ht_find()
483 			ht->ht[i] = p;  in dn_ht_find()
497 	void **curp, *cur, *next;  in dn_ht_scan()  local
501 	for (i = 0; i <= ht->buckets; i++) {  in dn_ht_scan()
502 		curp = &ht->ht[i];  in dn_ht_scan()
503 		while ( (cur = *curp) != NULL) {  in dn_ht_scan()
504 			next = *(void **)((char *)cur + ht->ofs);  in dn_ht_scan()
505 			ret = fn(cur, arg);  in dn_ht_scan()
508 				ht->entries--;  in dn_ht_scan()
511 				curp = (void **)((char *)cur + ht->ofs);  in dn_ht_scan()
524  * If the callback returns DNHT_SCAN_END, the function move the ht->ht[i]
533 	void **curp, *cur, *next;  in dn_ht_scan_bucket()  local
537 	if (*bucket > ht->buckets)  in dn_ht_scan_bucket()
541 	curp = &ht->ht[i];  in dn_ht_scan_bucket()
542 	while ( (cur = *curp) != NULL) {  in dn_ht_scan_bucket()
543 		next = *(void **)((char *)cur + ht->ofs);  in dn_ht_scan_bucket()
544 		ret = fn(cur, arg);  in dn_ht_scan_bucket()
547 			ht->entries--;  in dn_ht_scan_bucket()
550 			curp = (void **)((char *)cur + ht->ofs);  in dn_ht_scan_bucket()