src/common/hashtable.c

/*
 * Copyright (C) 2000,2001  Ross Combs (rocombs@cs.nmsu.edu)
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */
#define HASHTABLE_INTERNAL_ACCESS
#include "common/setup_before.h"
#ifdef HAVE_STDDEF_H
# include <stddef.h>
#else
# ifndef NULL
#  define NULL ((void *)0)
# endif
#endif
#ifdef STDC_HEADERS
# include <stdlib.h>
#else
# ifdef HAVE_MALLOC_H
#  include <malloc.h>
# endif
#endif
#include "common/eventlog.h"
#include "common/hashtable.h"
#include "common/xalloc.h"
#include "common/setup_after.h"


static int nodata; /* if data points to this, then the entry was actually deleted */
 

static t_entry * hashtable_entry_export(t_internentry * entry, t_hashtable const * hashtable, unsigned int row);


static t_entry * hashtable_entry_export(t_internentry * entry, t_hashtable const * hashtable, unsigned int row)
{
    t_entry * temp;
    
    if (!entry)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
        return NULL;
    }
    if (!hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
        return NULL;
    }
    if (row>=hashtable->num_rows)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got bad row %u (max %u)",row,hashtable->num_rows-1);
        return NULL;
    }

    temp = xmalloc(sizeof(t_entry));
    temp->row = row;
    temp->real = entry;
    temp->hashtable = hashtable;

    return temp;
}


extern t_hashtable * hashtable_create(unsigned int num_rows)
{
    t_hashtable * new;
    unsigned int  i;
    
    if (num_rows<1)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"num_rows must be at least 1");
        return NULL;
    }

    new = xmalloc(sizeof(t_hashtable));
    new->rows = xmalloc(sizeof(t_internentry *)*num_rows);
    new->num_rows = num_rows;
    new->len = 0;
    for (i=0; i<num_rows; i++)
        new->rows[i] = NULL;
    
    return new;
}


extern int hashtable_destroy(t_hashtable * hashtable)
{
    unsigned int i;
    
    if (!hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
        return -1;
    }
    
    hashtable_purge(hashtable);
    for (i=0; i<hashtable->num_rows; i++)
        if (hashtable->rows[i])
            eventlog(eventlog_level_error,__FUNCTION__,"got non-empty hashtable");
    
    xfree(hashtable->rows);
    xfree(hashtable);
    
    return 0;
}


extern int hashtable_purge(t_hashtable * hashtable)
{
    unsigned int      row;
    t_internentry *   curr;
    t_internentry *   head;
    t_internentry *   next;
    t_internentry * * change;
    
    if (!hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
        return -1;
    }
    
#ifdef HASHTABLE_DEBUG
    hashtable_check(hashtable);
#endif
    
    for (row=0; row<hashtable->num_rows; row++)
    {
        head = NULL;
        change = NULL;
        for (curr=hashtable->rows[row]; curr; curr=next)
        {
            next = curr->next;
            if (curr->data==&nodata)
            {
                if (change)
                    *change = next;
                xfree(curr);
            }
            else
            {
                if (!head)
                    head = curr;
                change = &curr->next;
            }
        }
        hashtable->rows[row] = head;
    }
    
    return 0;
}


extern int hashtable_check(t_hashtable const * hashtable)
{
    unsigned int          emptycnt;
    unsigned int          validcnt;
    unsigned int          row;
    unsigned int          temp;
    t_internentry const * tail;
    t_internentry const * curr;
    
    if (!hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
        return -1;
    }
    if (hashtable->num_rows<1)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"num_rows=%u",hashtable->num_rows);
        return -1;
    }
    if (!hashtable->rows)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"hashtable->rows is NULL");
        return -1;
    }
    
    emptycnt=validcnt = 0;
    for (row=0; row<hashtable->num_rows; row++)
    {
        tail = NULL;
        for (curr=hashtable->rows[row]; curr; curr=curr->next)
        {
            if (tail)
            {
                if (curr==tail) /* tail is currently the previous node */
                {
                    eventlog(eventlog_level_error,__FUNCTION__,"row %u is circular (curr==prev==%p)",row,curr);
                    return -1;
                }
                if (curr->next==tail)
                {
                    eventlog(eventlog_level_error,__FUNCTION__,"row %u is circular (curr->next==prev==%p)",row,curr);
                    return -1;
                }
                for (temp=0; temp<hashtable->num_rows; temp++)
                    if (curr==hashtable->rows[temp])
                    {
                        eventlog(eventlog_level_error,__FUNCTION__,"row %u is circular (curr==rows[%u]==%p)",row,temp,curr);
                        return -1;
                    }
            }
            if (curr->data==&nodata)
                emptycnt++;
            else
                validcnt++;
            tail = curr;
        }
    }
    
    if (emptycnt>10 && emptycnt>validcnt+5) /* arbitrary heuristic to detect missing list_purge() cal
ls */
        eventlog(eventlog_level_warn,__FUNCTION__,"emptycnt=%u but validcnt=%u",emptycnt,validcnt);
    if (hashtable->len!=validcnt)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"hashtable->len=%u but validcnt=%u",hashtable->len,validcnt);
        return -1;
    }
    
    return 0;
}


extern unsigned int hashtable_get_length(t_hashtable const * hashtable)
{
    if (!hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
        return 0;
    }
    
    return hashtable->len;
}


extern int hashtable_insert_data(t_hashtable * hashtable, void * data, unsigned int hash)
{
    unsigned int    row;
    t_internentry * entry;
    
    if (!hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
        return -1;
    }

    entry = xmalloc(sizeof(t_internentry));
    entry->data = data;
    
    row = hash%hashtable->num_rows;
    entry->next = hashtable->rows[row];
    hashtable->rows[row] = entry;
    hashtable->len++;
    
    return 0;
}


extern t_entry * hashtable_get_entry_by_data(t_hashtable const * hashtable, void const * data, unsigned int hash)
{
    unsigned int    row;
    t_internentry * curr;
    
    if (!hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
        return NULL;
    }
    
    row = hash%hashtable->num_rows;
    for (curr=hashtable->rows[row]; curr; curr=curr->next)
        if (curr->data==data)
            return hashtable_entry_export(curr,hashtable,row);
    
    return NULL;
}


extern t_entry const * hashtable_get_entry_by_data_const(t_hashtable const * hashtable, void const * data, unsigned int hash)
{
    unsigned int    row;
    t_internentry * curr;
    
    if (!hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
        return NULL;
    }
    
    row = hash%hashtable->num_rows;
    for (curr=hashtable->rows[row]; curr; curr=curr->next)
        if (curr->data==data)
            return hashtable_entry_export(curr,hashtable,row);
    
    return NULL;
}


extern int hashtable_remove_entry(t_hashtable * hashtable, t_entry * entry)
{
    if (!hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
        return -1;
    }
    if (!entry)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
        return -1;
    }
    if (!entry->real)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"entry has NULL real pointer");
        return -1;
    }
    if (entry->real->data==&nodata)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got deleted entry");
        return -1;
    }
    
    entry->real->data = &nodata;
    hashtable->len--;
    
    return 0;
}


extern int hashtable_remove_data(t_hashtable * hashtable, void const * data, unsigned int hash)
{
    t_entry * entry;
    int       retval;
    
    if (!hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
        return -1;
    }
    
    if (!(entry = hashtable_get_entry_by_data(hashtable,data,hash)))
        return -1;
    
    retval = hashtable_remove_entry(hashtable,entry);
    
    hashtable_entry_release(entry);
    
    return retval;
}


extern void * entry_get_data(t_entry const * entry)
{
    if (!entry)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
        return NULL;
    }
    if (!entry->real)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"entry has NULL real pointer");
        return NULL;
    }
    if (entry->real->data==&nodata)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got deleted entry");
        return NULL;
    }
    
    return entry->real->data;
}


extern void * hashtable_get_data_by_pos(t_hashtable const * hashtable, unsigned int pos)
{
    t_internentry const * curr;
    unsigned int          row;
    unsigned int          len;
    
    if (!hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
        return NULL;
    }
    
    len = 0;
    row = 0;
    curr = NULL;
    for (;;)
    {
        if (!curr)
        {
            if (row>=hashtable->num_rows)
                break;
            curr = hashtable->rows[row++];
            continue;
        }
        if (curr->data!=&nodata && len++==pos)
            return curr->data;
        curr = curr->next;
    }
    
    eventlog(eventlog_level_error,__FUNCTION__,"requested position %u but len=%u",pos,len);
    return NULL;
}


#ifdef HASHTABLE_DEBUG
extern t_entry * hashtable_get_first_real(t_hashtable const * hashtable, char const * fn, unsigned int ln)
#else
extern t_entry * hashtable_get_first(t_hashtable const * hashtable)
#endif
{
    unsigned int    row;
    t_internentry * curr;
    
    if (!hashtable)
    {
#ifdef HASHTABLE_DEBUG
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable from %s:%u",fn,ln);
#else
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
#endif
        return NULL;
    }
    
    for (row=0; row<hashtable->num_rows; row++)
        for (curr=hashtable->rows[row]; curr; curr=curr->next)
            if (curr->data!=&nodata)
                return hashtable_entry_export(curr,hashtable,row);
    
    return NULL;
}


extern t_entry * entry_get_next(t_entry * entry)
{
    t_hashtable const * hashtable;
    unsigned int        row;
    t_internentry *     curr;
    
    if (!entry)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
        return NULL;
    }
    
    hashtable = entry->hashtable;
    
    for (curr=entry->real->next; curr; curr=curr->next)
        if (curr->data!=&nodata)
        {
            entry->real = curr;
            return entry;
        }
    
    for (row=entry->row+1; row<hashtable->num_rows; row++)
        for (curr=hashtable->rows[row]; curr; curr=curr->next)
            if (curr->data!=&nodata)
            {
                entry->real = curr;
                entry->row = row;
                return entry;
            }
    
    hashtable_entry_release(entry);
    return NULL;
}


#ifdef HASHTABLE_DEBUG
extern t_entry * hashtable_get_first_matching_real(t_hashtable const * hashtable, unsigned int hash, char const * fn, unsigned int ln)
#else
extern t_entry * hashtable_get_first_matching(t_hashtable const * hashtable, unsigned int hash)
#endif
{
    unsigned int    row;
    t_internentry * curr;
    
    if (!hashtable)
    {
#ifdef HASHTABLE_DEBUG
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable from %s:%u",fn,ln);
#else
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
#endif
        return NULL;
    }
    
    row = hash%hashtable->num_rows;
    for (curr=hashtable->rows[row]; curr; curr=curr->next)
        if (curr->data!=&nodata)
            return hashtable_entry_export(curr,hashtable,row);
    
    return NULL;
}


extern t_entry * entry_get_next_matching(t_entry * entry)
{
    t_internentry * curr;
    
    if (!entry)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
        return NULL;
    }
    
    for (curr=entry->real->next; curr; curr=curr->next)
        if (curr->data!=&nodata)
        {
            entry->real = curr;
            return entry;
        }
    
    hashtable_entry_release(entry);
    return NULL;
}


extern int hashtable_entry_release(t_entry * entry)
{
    if (!entry)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
        return -1;
    }
    if (!entry->hashtable)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got entry with NULL hashtable");
        return -1;
    }
    if (!entry->real)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"got entry with NULL real pointer");
        return -1;
    }
    if (entry->row>=entry->hashtable->num_rows)
    {
        eventlog(eventlog_level_error,__FUNCTION__,"entry has bad row %u (max %u)",entry->row,entry->hashtable->num_rows-1);
        return -1;
    }
    
#ifdef HASHTABLE_DEBUG
    hashtable_check(entry->hashtable);
#endif
    xfree(entry);
    return 0;
}


extern int hashtable_stats(t_hashtable * hashtable)
{
    unsigned int      row;
    t_internentry *   curr;
    unsigned int      rcount, max, min;
    
    if (!hashtable)
    {
        eventlog(eventlog_level_error, __FUNCTION__,"got NULL hashtable");
        return -1;
    }
    
#ifdef HASHTABLE_DEBUG
    hashtable_check(hashtable);
#endif

    max = 0;
    min = hashtable->len;
    for (row=0; row<hashtable->num_rows; row++)
    {
        rcount = 0;
        for (curr=hashtable->rows[row]; curr; curr=curr->next)
            if (curr->data!=&nodata) rcount++;
        if (rcount > max) max = rcount;
        if (rcount < min) min = rcount;
    }

    eventlog(eventlog_level_info, __FUNCTION__, "hashsize: %u min: %u max: %u avg: %.2f diff: %.2f%c", hashtable->num_rows, min, max, (float)(min + max)/2, (float)(max - min)/max*100, '%');
    return 0;
}


1	sysadm	1.1	/*
2			* Copyright (C) 2000,2001 Ross Combs (rocombs@cs.nmsu.edu)
3			*
4			* This program is free software; you can redistribute it and/or
5			* modify it under the terms of the GNU General Public License
6			* as published by the Free Software Foundation; either version 2
7			* of the License, or (at your option) any later version.
8			*
9			* This program is distributed in the hope that it will be useful,
10			* but WITHOUT ANY WARRANTY; without even the implied warranty of
11			* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12			* GNU General Public License for more details.
13			*
14			* You should have received a copy of the GNU General Public License
15			* along with this program; if not, write to the Free Software
16			* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17			*/
18			#define HASHTABLE_INTERNAL_ACCESS
19			#include "common/setup_before.h"
20			#ifdef HAVE_STDDEF_H
21			# include <stddef.h>
22			#else
23			# ifndef NULL
24			# define NULL ((void *)0)
25			# endif
26			#endif
27			#ifdef STDC_HEADERS
28			# include <stdlib.h>
29			#else
30			# ifdef HAVE_MALLOC_H
31			# include <malloc.h>
32			# endif
33			#endif
34			#include "common/eventlog.h"
35			#include "common/hashtable.h"
36			#include "common/xalloc.h"
37			#include "common/setup_after.h"
38
39
40			static int nodata; /* if data points to this, then the entry was actually deleted */
41
42
43			static t_entry * hashtable_entry_export(t_internentry * entry, t_hashtable const * hashtable, unsigned int row);
44
45
46			static t_entry * hashtable_entry_export(t_internentry * entry, t_hashtable const * hashtable, unsigned int row)
47			{
48			t_entry * temp;
49
50			if (!entry)
51			{
52			eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
53			return NULL;
54			}
55			if (!hashtable)
56			{
57			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
58			return NULL;
59			}
60			if (row>=hashtable->num_rows)
61			{
62			eventlog(eventlog_level_error,__FUNCTION__,"got bad row %u (max %u)",row,hashtable->num_rows-1);
63			return NULL;
64			}
65
66			temp = xmalloc(sizeof(t_entry));
67			temp->row = row;
68			temp->real = entry;
69			temp->hashtable = hashtable;
70
71			return temp;
72			}
73
74
75			extern t_hashtable * hashtable_create(unsigned int num_rows)
76			{
77			t_hashtable * new;
78			unsigned int i;
79
80			if (num_rows<1)
81			{
82			eventlog(eventlog_level_error,__FUNCTION__,"num_rows must be at least 1");
83			return NULL;
84			}
85
86			new = xmalloc(sizeof(t_hashtable));
87			new->rows = xmalloc(sizeof(t_internentry )num_rows);
88			new->num_rows = num_rows;
89			new->len = 0;
90			for (i=0; i<num_rows; i++)
91			new->rows[i] = NULL;
92
93			return new;
94			}
95
96
97			extern int hashtable_destroy(t_hashtable * hashtable)
98			{
99			unsigned int i;
100
101			if (!hashtable)
102			{
103			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
104			return -1;
105			}
106
107			hashtable_purge(hashtable);
108			for (i=0; i<hashtable->num_rows; i++)
109			if (hashtable->rows[i])
110			eventlog(eventlog_level_error,__FUNCTION__,"got non-empty hashtable");
111
112			xfree(hashtable->rows);
113			xfree(hashtable);
114
115			return 0;
116			}
117
118
119			extern int hashtable_purge(t_hashtable * hashtable)
120			{
121			unsigned int row;
122			t_internentry * curr;
123			t_internentry * head;
124			t_internentry * next;
125			t_internentry * * change;
126
127			if (!hashtable)
128			{
129			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
130			return -1;
131			}
132
133			#ifdef HASHTABLE_DEBUG
134			hashtable_check(hashtable);
135			#endif
136
137			for (row=0; row<hashtable->num_rows; row++)
138			{
139			head = NULL;
140			change = NULL;
141			for (curr=hashtable->rows[row]; curr; curr=next)
142			{
143			next = curr->next;
144			if (curr->data==&nodata)
145			{
146			if (change)
147			*change = next;
148			xfree(curr);
149			}
150			else
151			{
152			if (!head)
153			head = curr;
154			change = &curr->next;
155			}
156			}
157			hashtable->rows[row] = head;
158			}
159
160			return 0;
161			}
162
163
164			extern int hashtable_check(t_hashtable const * hashtable)
165			{
166			unsigned int emptycnt;
167			unsigned int validcnt;
168			unsigned int row;
169			unsigned int temp;
170			t_internentry const * tail;
171			t_internentry const * curr;
172
173			if (!hashtable)
174			{
175			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
176			return -1;
177			}
178			if (hashtable->num_rows<1)
179			{
180			eventlog(eventlog_level_error,__FUNCTION__,"num_rows=%u",hashtable->num_rows);
181			return -1;
182			}
183			if (!hashtable->rows)
184			{
185			eventlog(eventlog_level_error,__FUNCTION__,"hashtable->rows is NULL");
186			return -1;
187			}
188
189			emptycnt=validcnt = 0;
190			for (row=0; row<hashtable->num_rows; row++)
191			{
192			tail = NULL;
193			for (curr=hashtable->rows[row]; curr; curr=curr->next)
194			{
195			if (tail)
196			{
197			if (curr==tail) /* tail is currently the previous node */
198			{
199			eventlog(eventlog_level_error,__FUNCTION__,"row %u is circular (curr==prev==%p)",row,curr);
200			return -1;
201			}
202			if (curr->next==tail)
203			{
204			eventlog(eventlog_level_error,__FUNCTION__,"row %u is circular (curr->next==prev==%p)",row,curr);
205			return -1;
206			}
207			for (temp=0; temp<hashtable->num_rows; temp++)
208			if (curr==hashtable->rows[temp])
209			{
210			eventlog(eventlog_level_error,__FUNCTION__,"row %u is circular (curr==rows[%u]==%p)",row,temp,curr);
211			return -1;
212			}
213			}
214			if (curr->data==&nodata)
215			emptycnt++;
216			else
217			validcnt++;
218			tail = curr;
219			}
220			}
221
222			if (emptycnt>10 && emptycnt>validcnt+5) /* arbitrary heuristic to detect missing list_purge() cal
223			ls */
224			eventlog(eventlog_level_warn,__FUNCTION__,"emptycnt=%u but validcnt=%u",emptycnt,validcnt);
225			if (hashtable->len!=validcnt)
226			{
227			eventlog(eventlog_level_error,__FUNCTION__,"hashtable->len=%u but validcnt=%u",hashtable->len,validcnt);
228			return -1;
229			}
230
231			return 0;
232			}
233
234
235			extern unsigned int hashtable_get_length(t_hashtable const * hashtable)
236			{
237			if (!hashtable)
238			{
239			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
240			return 0;
241			}
242
243			return hashtable->len;
244			}
245
246
247			extern int hashtable_insert_data(t_hashtable * hashtable, void * data, unsigned int hash)
248			{
249			unsigned int row;
250			t_internentry * entry;
251
252			if (!hashtable)
253			{
254			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
255			return -1;
256			}
257
258			entry = xmalloc(sizeof(t_internentry));
259			entry->data = data;
260
261			row = hash%hashtable->num_rows;
262			entry->next = hashtable->rows[row];
263			hashtable->rows[row] = entry;
264			hashtable->len++;
265
266			return 0;
267			}
268
269
270			extern t_entry * hashtable_get_entry_by_data(t_hashtable const * hashtable, void const * data, unsigned int hash)
271			{
272			unsigned int row;
273			t_internentry * curr;
274
275			if (!hashtable)
276			{
277			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
278			return NULL;
279			}
280
281			row = hash%hashtable->num_rows;
282			for (curr=hashtable->rows[row]; curr; curr=curr->next)
283			if (curr->data==data)
284			return hashtable_entry_export(curr,hashtable,row);
285
286			return NULL;
287			}
288
289
290			extern t_entry const * hashtable_get_entry_by_data_const(t_hashtable const * hashtable, void const * data, unsigned int hash)
291			{
292			unsigned int row;
293			t_internentry * curr;
294
295			if (!hashtable)
296			{
297			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
298			return NULL;
299			}
300
301			row = hash%hashtable->num_rows;
302			for (curr=hashtable->rows[row]; curr; curr=curr->next)
303			if (curr->data==data)
304			return hashtable_entry_export(curr,hashtable,row);
305
306			return NULL;
307			}
308
309
310			extern int hashtable_remove_entry(t_hashtable * hashtable, t_entry * entry)
311			{
312			if (!hashtable)
313			{
314			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
315			return -1;
316			}
317			if (!entry)
318			{
319			eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
320			return -1;
321			}
322			if (!entry->real)
323			{
324			eventlog(eventlog_level_error,__FUNCTION__,"entry has NULL real pointer");
325			return -1;
326			}
327			if (entry->real->data==&nodata)
328			{
329			eventlog(eventlog_level_error,__FUNCTION__,"got deleted entry");
330			return -1;
331			}
332
333			entry->real->data = &nodata;
334			hashtable->len--;
335
336			return 0;
337			}
338
339
340			extern int hashtable_remove_data(t_hashtable * hashtable, void const * data, unsigned int hash)
341			{
342			t_entry * entry;
343			int retval;
344
345			if (!hashtable)
346			{
347			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
348			return -1;
349			}
350
351			if (!(entry = hashtable_get_entry_by_data(hashtable,data,hash)))
352			return -1;
353
354			retval = hashtable_remove_entry(hashtable,entry);
355
356			hashtable_entry_release(entry);
357
358			return retval;
359			}
360
361
362			extern void * entry_get_data(t_entry const * entry)
363			{
364			if (!entry)
365			{
366			eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
367			return NULL;
368			}
369			if (!entry->real)
370			{
371			eventlog(eventlog_level_error,__FUNCTION__,"entry has NULL real pointer");
372			return NULL;
373			}
374			if (entry->real->data==&nodata)
375			{
376			eventlog(eventlog_level_error,__FUNCTION__,"got deleted entry");
377			return NULL;
378			}
379
380			return entry->real->data;
381			}
382
383
384			extern void * hashtable_get_data_by_pos(t_hashtable const * hashtable, unsigned int pos)
385			{
386			t_internentry const * curr;
387			unsigned int row;
388			unsigned int len;
389
390			if (!hashtable)
391			{
392			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
393			return NULL;
394			}
395
396			len = 0;
397			row = 0;
398			curr = NULL;
399			for (;;)
400			{
401			if (!curr)
402			{
403			if (row>=hashtable->num_rows)
404			break;
405			curr = hashtable->rows[row++];
406			continue;
407			}
408			if (curr->data!=&nodata && len++==pos)
409			return curr->data;
410			curr = curr->next;
411			}
412
413			eventlog(eventlog_level_error,__FUNCTION__,"requested position %u but len=%u",pos,len);
414			return NULL;
415			}
416
417
418			#ifdef HASHTABLE_DEBUG
419			extern t_entry * hashtable_get_first_real(t_hashtable const * hashtable, char const * fn, unsigned int ln)
420			#else
421			extern t_entry * hashtable_get_first(t_hashtable const * hashtable)
422			#endif
423			{
424			unsigned int row;
425			t_internentry * curr;
426
427			if (!hashtable)
428			{
429			#ifdef HASHTABLE_DEBUG
430			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable from %s:%u",fn,ln);
431			#else
432			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
433			#endif
434			return NULL;
435			}
436
437			for (row=0; row<hashtable->num_rows; row++)
438			for (curr=hashtable->rows[row]; curr; curr=curr->next)
439			if (curr->data!=&nodata)
440			return hashtable_entry_export(curr,hashtable,row);
441
442			return NULL;
443			}
444
445
446			extern t_entry * entry_get_next(t_entry * entry)
447			{
448			t_hashtable const * hashtable;
449			unsigned int row;
450			t_internentry * curr;
451
452			if (!entry)
453			{
454			eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
455			return NULL;
456			}
457
458			hashtable = entry->hashtable;
459
460			for (curr=entry->real->next; curr; curr=curr->next)
461			if (curr->data!=&nodata)
462			{
463			entry->real = curr;
464			return entry;
465			}
466
467			for (row=entry->row+1; row<hashtable->num_rows; row++)
468			for (curr=hashtable->rows[row]; curr; curr=curr->next)
469			if (curr->data!=&nodata)
470			{
471			entry->real = curr;
472			entry->row = row;
473			return entry;
474			}
475
476			hashtable_entry_release(entry);
477			return NULL;
478			}
479
480
481			#ifdef HASHTABLE_DEBUG
482			extern t_entry * hashtable_get_first_matching_real(t_hashtable const * hashtable, unsigned int hash, char const * fn, unsigned int ln)
483			#else
484			extern t_entry * hashtable_get_first_matching(t_hashtable const * hashtable, unsigned int hash)
485			#endif
486			{
487			unsigned int row;
488			t_internentry * curr;
489
490			if (!hashtable)
491			{
492			#ifdef HASHTABLE_DEBUG
493			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable from %s:%u",fn,ln);
494			#else
495			eventlog(eventlog_level_error,__FUNCTION__,"got NULL hashtable");
496			#endif
497			return NULL;
498			}
499
500			row = hash%hashtable->num_rows;
501			for (curr=hashtable->rows[row]; curr; curr=curr->next)
502			if (curr->data!=&nodata)
503			return hashtable_entry_export(curr,hashtable,row);
504
505			return NULL;
506			}
507
508
509			extern t_entry * entry_get_next_matching(t_entry * entry)
510			{
511			t_internentry * curr;
512
513			if (!entry)
514			{
515			eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
516			return NULL;
517			}
518
519			for (curr=entry->real->next; curr; curr=curr->next)
520			if (curr->data!=&nodata)
521			{
522			entry->real = curr;
523			return entry;
524			}
525
526			hashtable_entry_release(entry);
527			return NULL;
528			}
529
530
531			extern int hashtable_entry_release(t_entry * entry)
532			{
533			if (!entry)
534			{
535			eventlog(eventlog_level_error,__FUNCTION__,"got NULL entry");
536			return -1;
537			}
538			if (!entry->hashtable)
539			{
540			eventlog(eventlog_level_error,__FUNCTION__,"got entry with NULL hashtable");
541			return -1;
542			}
543			if (!entry->real)
544			{
545			eventlog(eventlog_level_error,__FUNCTION__,"got entry with NULL real pointer");
546			return -1;
547			}
548			if (entry->row>=entry->hashtable->num_rows)
549			{
550			eventlog(eventlog_level_error,__FUNCTION__,"entry has bad row %u (max %u)",entry->row,entry->hashtable->num_rows-1);
551			return -1;
552			}
553
554			#ifdef HASHTABLE_DEBUG
555			hashtable_check(entry->hashtable);
556			#endif
557			xfree(entry);
558			return 0;
559			}
560
561
562			extern int hashtable_stats(t_hashtable * hashtable)
563			{
564			unsigned int row;
565			t_internentry * curr;
566			unsigned int rcount, max, min;
567
568			if (!hashtable)
569			{
570			eventlog(eventlog_level_error, __FUNCTION__,"got NULL hashtable");
571			return -1;
572			}
573
574			#ifdef HASHTABLE_DEBUG
575			hashtable_check(hashtable);
576			#endif
577
578			max = 0;
579			min = hashtable->len;
580			for (row=0; row<hashtable->num_rows; row++)
581			{
582			rcount = 0;
583			for (curr=hashtable->rows[row]; curr; curr=curr->next)
584			if (curr->data!=&nodata) rcount++;
585			if (rcount > max) max = rcount;
586			if (rcount < min) min = rcount;
587			}
588
589			eventlog(eventlog_level_info, __FUNCTION__, "hashsize: %u min: %u max: %u avg: %.2f diff: %.2f%c", hashtable->num_rows, min, max, (float)(min + max)/2, (float)(max - min)/max*100, '%');
590			return 0;
591			}
592
593
webmaster@leafok.com	ViewVC Help
Powered by ViewVC 1.3.0-beta1