--- act_hash_lh.c 2002/01/02 17:05:53 1.9
+++ act_hash_lh.c 2002/01/18 18:17:55 1.10
@@ -28,7 +28,7 @@
/*
** This module implements a Dynamic Hash Table, based on WITOLD LITWIN
-** and PER-AKE LARSON's ``Linear Hashing'' algorithm (1980/1988),
+** and PER-AKE LARSON's "Linear Hashing" algorithm (1980/1988),
** implemented on top of a two-level virtual array with separate
** collision chains as the backend data structure. Some ideas were
** taken over from MIKAEL PETTERSON's Linear Hashing enhancements
@@ -115,12 +115,15 @@
typedef struct act_hash_lh_st act_hash_lh_t;
struct act_hash_lh_st {
act_ctx_t *h_ctx; /* context structure */
+ act_grid_t *h_grid_seg; /* memory grid for segments */
+ act_grid_t *h_grid_el; /* memory grid for elements */
act_hash_fct_t h_func; /* hash function (copied from context) */
unsigned int h_p; /* pointer to start of unsplit region */
unsigned int h_pmax; /* pointer to end of unsplit region */
int h_slack; /* grow/shrink indicator */
unsigned h_dirsize; /* current size of directory */
segment_t **h_dir; /* pointer to directory */
+
};
/* on-the-fly calculate index into directory and segment from virtual array index */
@@ -143,18 +146,36 @@
return NULL;
h->h_ctx = ctx;
+ /* create the internal memory grid for segments */
+ if (act_grid_create(&h->h_grid_seg, ctx, sizeof(segment_t), 1) != ACT_OK) {
+ errno_safe(act_mem_free_ctx(ctx, h));
+ return NULL;
+ }
+
+ /* create the internal memory grid for elements */
+ if (act_grid_create(&h->h_grid_el, ctx, sizeof(element_t), SEGMENTSIZE) != ACT_OK) {
+ errno_safe(act_grid_destroy(h->h_grid_seg));
+ errno_safe(act_mem_free_ctx(ctx, h));
+ return NULL;
+ }
+
/* allocate and clear hash table directory */
h->h_dirsize = INITDIRSIZE;
if ((h->h_dir = (segment_t **)act_mem_alloc_ctx(
ctx, h->h_dirsize * sizeof(segment_t *))) == NULL) {
+ errno_safe(act_grid_destroy(h->h_grid_seg));
+ errno_safe(act_grid_destroy(h->h_grid_el));
errno_safe(act_mem_free_ctx(ctx, h));
return NULL;
}
act_mem_set(h->h_dir, 0, h->h_dirsize * sizeof(segment_t *));
/* allocate and clear first segment of hash table array */
- if ((h->h_dir[0] = (segment_t *)act_mem_alloc_ctx(ctx, sizeof(segment_t))) == NULL) {
- errno_safe(act_mem_free_ctx(ctx, h->h_dir); act_mem_free_ctx(ctx, h));
+ if (act_grid_alloc(h->h_grid_seg, (void **)&(h->h_dir[0])) != ACT_OK) {
+ errno_safe(act_grid_destroy(h->h_grid_seg));
+ errno_safe(act_grid_destroy(h->h_grid_el));
+ errno_safe(act_mem_free_ctx(ctx, h->h_dir));
+ errno_safe(act_mem_free_ctx(ctx, h));
return NULL;
}
act_mem_set(h->h_dir[0], 0, sizeof(segment_t));
@@ -200,7 +221,7 @@
/* have to create a new table segment? */
if (SEGINDEX(newaddr) == 0) {
- if ((seg = (segment_t *)act_mem_alloc_ctx(ctx, sizeof(segment_t))) == NULL)
+ if (act_grid_alloc(h->h_grid_seg, (void **)&seg) != ACT_OK)
return;
act_mem_set(seg, 0, sizeof(segment_t));
h->h_dir[DIRINDEX(newaddr)] = seg;
@@ -273,7 +294,7 @@
/* if possible, deallocate the last segment */
if (SEGINDEX(oldlast) == 0) {
h->h_dir[DIRINDEX(oldlast)] = NULL;
- free(lastseg);
+ act_grid_free(h->h_grid_seg, lastseg);
}
/* if possible, deallocate the end of the directory */
@@ -345,7 +366,7 @@
}
else {
/* allocate new element and chain into list */
- if ((el = (element_t *)act_mem_alloc_ctx(ctx, sizeof(element_t))) == 0) {
+ if (act_grid_alloc(h->h_grid_el, (void **)&el) != ACT_OK) {
act_mem_free_ctx(ctx, vp);
return FALSE;
}
@@ -447,7 +468,7 @@
else
lel->e_next = el->e_next;
/* deallocate element structure */
- act_mem_free_ctx(ctx, el);
+ act_grid_free(h->h_grid_el, el);
rv = TRUE;
break;
}
@@ -602,7 +623,7 @@
act_ctx_t *ctx,
act_hash_lh_t *h)
{
- element_t *el, **pel;
+ element_t *el, **pel, *el_next;
unsigned int i, j;
/* argument consistency check */
@@ -619,13 +640,16 @@
continue;
/* deallocate all elements in collision chain */
pel = &h->h_dir[i]->s_element[j];
- for (el = *pel; el != NULL; el = el->e_next) {
+ for (el = *pel; el != NULL; ) {
/* deallocate key+data memory chunk */
if (el->e_keyptr != NULL)
act_mem_free_ctx(ctx, el->e_keyptr);
+ el_next = el->e_next;
+ act_grid_free(h->h_grid_el, el);
+ el = el_next;
}
}
- act_mem_free_ctx(ctx, h->h_dir[i]);
+ act_grid_free(h->h_grid_seg, h->h_dir[i]);
}
/* deallocate hash table directory */
|
