gdsl_hash.c

书籍上的数据结构源代码

		    l = ht->lists[indix];
		}
	}

    if (gdsl_list_insert_head (l, he) == NULL)
	{
	    ht->free_func (he->content);
	    free (he);
	    return NULL;
	}
  
    return he->content;
}

extern gdsl_element_t
gdsl_hash_remove (gdsl_hash_t ht, const char* key)
{
    ushort         indix;
    hash_element   he;
    gdsl_element_t e;

    indix = ht->hash_func (key) % ht->lists_count;

    he = (hash_element) gdsl_list_remove (ht->lists [indix], 
					  search_element_by_key, 
					  (void *) key);

    if (he == NULL)
	{
	    return NULL;
	}

    e = he->content;
    free (he);

    return e;
}

extern gdsl_hash_t
gdsl_hash_delete (gdsl_hash_t ht, const char* key)
{
    gdsl_element_t e;

    e = gdsl_hash_remove (ht, key);

    if (e == NULL)
	{
	    return NULL;
	}

    ht->free_func (e);

    return ht;
}

extern gdsl_hash_t
gdsl_hash_modify (gdsl_hash_t ht, ushort new_size, ushort new_max_lists_size)
{
    ushort i;
    ushort j;
    gdsl_list_t* lists;

    assert (ht != NULL);

    /* First, we create a vector of new lists */
    lists = (gdsl_list_t*) malloc (new_size * sizeof (gdsl_list_t));

    if (lists == NULL)
	{
	    return NULL;
	}

    /* Second, we initialize vector elements with new lists */
    for (i = 0; i < new_size; i++)
	{
	    lists [i] = gdsl_list_alloc (NULL, NULL, NULL);

	    if (lists [i] == NULL)
		{
		    for (j = 0; j < i; j++)
			{
			    gdsl_list_free (lists [j]);
			}

		    free (lists);
		    return NULL;
		}
	}

    /* Now, we can insert in this new structure all elements of H */
    for (i = 0; i < ht->lists_count; i++)
	{
	    gdsl_list_t l = ht->lists [i];
	    gdsl_list_cursor_t c = gdsl_list_cursor_alloc (l);
	    hash_element he;

	    for (gdsl_list_cursor_move_to_head (c); (he = gdsl_list_cursor_get_content (c)); gdsl_list_cursor_step_forward (c))
		{
		    ushort indix = ht->hash_func (he->key) % new_size;
		    gdsl_list_t l2 = lists [indix];

		    if (gdsl_list_insert_head (l2, he) == NULL)
			{
			    return NULL;
			}
		}

	    gdsl_list_cursor_free (c);
	}

    /* Then, we replace the entries of H by new entries */
    for (i = 0; i < ht->lists_count; i++)
	{
	    gdsl_list_flush (ht->lists [i]);
	}
    free (ht->lists);

    ht->lists = lists;
    ht->lists_count = new_size;
    ht->lists_max_size = new_max_lists_size;

    return ht;
}

/******************************************************************************/
/* Search functions of hashtables                                             */
/******************************************************************************/

extern gdsl_element_t
gdsl_hash_search (const gdsl_hash_t ht, const char* key)
{
    ushort       indix;
    hash_element he;

    indix = ht->hash_func (key) % ht->lists_count;

    he = (hash_element) gdsl_list_search (ht->lists [indix], 
					  search_element_by_key, 
					  (void*) key);
    if (he == NULL)
	{
	    return NULL;
	}

    return he->content;
}

/******************************************************************************/
/* Parse functions of hashtables                                              */
/******************************************************************************/

extern gdsl_element_t
gdsl_hash_map (const gdsl_hash_t ht, gdsl_map_func_t f, void* user_data)
{
    ushort       i;
    struct infos infos;

    infos.f = (hash_fct_ptr_t) f;
    infos.d = user_data;
    infos.e = NULL;

    for (i = 0; i < ht->lists_count; i++)
	{
	    if (gdsl_list_get_size (ht->lists [i]) == 0)
		{
		    continue;
		}

	    if (gdsl_list_map_forward (ht->lists [i], local_map_f, 
				       (void*) &infos) != NULL)
		{
		    return infos.e;
		}
	}

    return NULL;
}

/******************************************************************************/
/* Input/output functions of hashtables                                       */
/******************************************************************************/

extern void
gdsl_hash_write (const gdsl_hash_t ht, gdsl_write_func_t f, FILE* file, 
		 void* user_data)
{
    ushort       i;
    struct infos infos;

    infos.f  = (hash_fct_ptr_t) f;
    infos.d  = (void*) file;
    infos.ud = user_data;

    for (i = 0; i < ht->lists_count; i++)
	{
	    if (gdsl_list_get_size (ht->lists [i]) != 0)
		{
		    gdsl_list_write (ht->lists [i], local_write_f, file, 
				     (void*) &infos);
		}
	}
}

extern void
gdsl_hash_write_xml (const gdsl_hash_t ht, gdsl_write_func_t f, FILE* file, 
		     void* user_data)
{
    ushort       i;
    struct infos infos;

    infos.f  = (hash_fct_ptr_t) f;
    infos.d  = (void *) file;
    infos.ud = user_data;

    fprintf (file, "<GDSL_HASH REF=\"%p\" NAME=\"%s\" SIZE=\"%ld\" ENTRIES_COUNT=\"%d\">\n", 
	     (void*) ht, ht->name == NULL ? "" : ht->name, 
	     gdsl_hash_get_size (ht), ht->lists_count);

    for (i = 0; i < ht->lists_count; i++)
	{
	    if (gdsl_list_get_size (ht->lists[i]) != 0)
		{
		    fprintf (file, "<GDSL_HASH_ENTRY VALUE=\"%d\">\n", i);
		    gdsl_list_write_xml (ht->lists [i], local_write_xml_f, file, 
					 (void*) &infos);
		    fprintf (file, "</GDSL_HASH_ENTRY>\n");
		}
	}

    fprintf (file, "</GDSL_HASH>\n");
}

extern void
gdsl_hash_dump (const gdsl_hash_t ht, gdsl_write_func_t f, FILE* file, 
		void* user_data)
{
    ushort       i;
    struct infos infos;

    infos.f  = (hash_fct_ptr_t) f;
    infos.d  = file;
    infos.ud = user_data;

    fprintf (file, "<GDSL_HASH REF=\"%p\" NAME=\"%s\" SIZE=\"%ld\" ENTRIES_COUNT=\"%d\" MAX_LISTS_SIZE=\"%d\">\n", 
	     (void*) ht, ht->name == NULL ? "" : ht->name,
	     gdsl_hash_get_size (ht), ht->lists_count, ht->lists_max_size);

    for (i = 0; i < ht->lists_count; i++)
	{
	    fprintf (file, "<GDSL_HASH_ENTRY VALUE=\"%d\">\n", i);
	    gdsl_list_dump (ht->lists [i], local_write_xml_f, file, (void*) &infos);
	    fprintf (file, "</GDSL_HASH_ENTRY>\n");
	}
  
    fprintf (file, "</GDSL_HASH>\n");
}

/******************************************************************************/
/* Private functions                                                          */
/******************************************************************************/

static gdsl_element_t 
default_alloc (void* e)
{
    return e;
}

static void 
default_free (gdsl_element_t e)
{
    ;
}

static const char* 
default_key (gdsl_element_t e)
{
    return (const char*) e;
}

static long int 
search_element_by_key (gdsl_element_t e, void* key)
{
    hash_element he = (hash_element) e;

    return strcmp (he->key, (const char*) key);
}

static int 
local_map_f (gdsl_element_t e, gdsl_location_t location, void* user_data)
{
    hash_element    he    = (hash_element) e;
    struct infos*   infos = (struct infos*) user_data;
    gdsl_map_func_t map   = (gdsl_map_func_t) (infos->f);

    infos->e = he->content;

    return map (he->content, GDSL_LOCATION_UNDEF, infos->d);
}

static void
local_write_f (gdsl_element_t e, FILE* file, gdsl_location_t location, void* user_data)
{
    hash_element  he        = (hash_element) e;
    struct infos* infos     = (struct infos*) user_data;
    gdsl_write_func_t write = (gdsl_write_func_t) (infos->f);

    write (he->content, file, GDSL_LOCATION_UNDEF, infos->ud);
}

static void
local_write_xml_f (gdsl_element_t e, FILE* file, gdsl_location_t location, void* user_data)
{
    hash_element  he        = (hash_element) e;
    struct infos* infos     = (struct infos*) user_data;
    gdsl_write_func_t write = (gdsl_write_func_t) (infos->f);

    fprintf (file, "\n<CONTENT KEY=\"%s\">", he->key);
    write (he->content, file, GDSL_LOCATION_UNDEF, infos->ud);
    fprintf (file, "</CONTENT>\n");
}

static int
destroy_element (gdsl_element_t e, gdsl_location_t location, void* user_infos)
{
    gdsl_hash_t  ht = (gdsl_hash_t) user_infos;
    hash_element he = (hash_element) e;

    (ht->free_func) (he->content);
    free (he);
    
    return GDSL_MAP_CONT;
}


/** EMACS **
 * Local variables:
 * mode: c
 * c-basic-offset: 4
 * End:
 */