[irc/evilnet/x3.git] / rx / rxhash.c

/*	Copyright (C) 1995, 1996 Tom Lord
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as published by
 * the Free Software Foundation; either version 2, 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 Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public License
 * along with this software; see the file COPYING.  If not, write to
 * the Free Software Foundation, 59 Temple Place - Suite 330, 
 * Boston, MA 02111-1307, USA. 
 */

\f
/*
 * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
 */
\f

#include "rxall.h"
#include "rxhash.h"

\f

#ifdef __STDC__
static struct rx_hash *
default_hash_alloc (struct rx_hash_rules * rules)
#else
static struct rx_hash *
default_hash_alloc (rules)
     struct rx_hash_rules * rules;
#endif
{
  return (struct rx_hash *)malloc (sizeof (struct rx_hash));
}


#ifdef __STDC__
static struct rx_hash_item *
default_hash_item_alloc (struct rx_hash_rules * rules, void * value)
#else
static struct rx_hash_item *
default_hash_item_alloc (rules, value)
     struct rx_hash_rules * rules;
     void * value;
#endif
{
  struct rx_hash_item * it;
  it = (struct rx_hash_item *)malloc (sizeof (*it));
  if (it)
    {
      it->data = value;
      it->binding = 0;
    }
  return it;
}


#ifdef __STDC__
static void
default_free_hash (struct rx_hash * tab,
		    struct rx_hash_rules * rules)
#else
static void
default_free_hash (tab, rules)
     struct rx_hash * tab;
     struct rx_hash_rules * rules;
#endif
{
  free ((char *)tab);
}


#ifdef __STDC__
static void
default_free_hash_item (struct rx_hash_item * item,
			 struct rx_hash_rules * rules)
#else
static void
default_free_hash_item (item, rules)
     struct rx_hash_item * item;
     struct rx_hash_rules * rules;
#endif
{
  free ((char *)item);
}

#ifdef __STDC__
static int 
default_eq (void * va, void * vb)
#else
static int 
default_eq (va, vb)
     void * va;
     void * vb;
#endif
{
  return va == vb;
}

\f

#define EQ(rules) ((rules && rules->eq) ? rules->eq : default_eq)
#define HASH_ALLOC(rules) ((rules && rules->hash_alloc) ? rules->hash_alloc : default_hash_alloc)
#define FREE_HASH(rules) ((rules && rules->free_hash) ? rules->free_hash : default_free_hash)
#define ITEM_ALLOC(rules) ((rules && rules->hash_item_alloc) ? rules->hash_item_alloc : default_hash_item_alloc)
#define FREE_HASH_ITEM(rules) ((rules && rules->free_hash_item) ? rules->free_hash_item : default_free_hash_item)

\f
static unsigned long rx_hash_masks[4] =
{
  0x12488421,
  0x96699669,
  0xbe7dd7eb,
  0xffffffff
};

/* hash to bucket */
#define JOIN_BYTE(H, B)  (((H) + ((H) << 3) + (B)) & 0xf)

#define H2B(X) JOIN_BYTE (JOIN_BYTE (JOIN_BYTE ((X & 0xf), ((X>>8) & 0xf)), ((X>>16) & 0xf)), ((X>>24) & 0xf))

#define BKTS 16

/* Hash tables */
#ifdef __STDC__
struct rx_hash_item * 
rx_hash_find (struct rx_hash * table,
	      unsigned long hash,
	      void * value,
	      struct rx_hash_rules * rules)
#else
struct rx_hash_item * 
rx_hash_find (table, hash, value, rules)
     struct rx_hash * table;
     unsigned long hash;
     void * value;
     struct rx_hash_rules * rules;
#endif
{
  rx_hash_eq eq = EQ (rules);
  int maskc = 0;
  long mask = rx_hash_masks [0];
  int bucket = H2B(hash & mask);

  while (RX_bitset_member (&table->nested_p, bucket))
    {
      table = (struct rx_hash *)(table->children [bucket]);
      ++maskc;
      mask = rx_hash_masks[maskc];
      bucket = H2B (hash & mask);
    }

  {
    struct rx_hash_item * it;
    it = (struct rx_hash_item *)(table->children[bucket]);
    while (it)
      if (eq (it->data, value))
	return it;
      else
	it = it->next_same_hash;
  }

  return 0;
}


#ifdef __STDC__
static int 
listlen (struct rx_hash_item * bucket)
#else
static int 
listlen (bucket)
     struct rx_hash_item * bucket;
#endif
{
  int i;
  for (i = 0; bucket; ++i, bucket = bucket->next_same_hash)
    ;
  return i;
}

#ifdef __STDC__
static int
overflows (struct rx_hash_item * bucket)
#else
static int
overflows (bucket)
     struct rx_hash_item * bucket;
#endif
{
  return !(   bucket
	   && bucket->next_same_hash
	   && bucket->next_same_hash->next_same_hash
	   && bucket->next_same_hash->next_same_hash->next_same_hash);
}


#ifdef __STDC__
struct rx_hash_item *
rx_hash_store (struct rx_hash * table,
	       unsigned long hash,
	       void * value,
	       struct rx_hash_rules * rules)
#else
struct rx_hash_item *
rx_hash_store (table, hash, value, rules)
     struct rx_hash * table;
     unsigned long hash;
     void * value;
     struct rx_hash_rules * rules;
#endif
{
  rx_hash_eq eq = EQ (rules);
  int maskc = 0;
  long mask = rx_hash_masks [0];
  int bucket = H2B(hash & mask);
  int depth = 0;
  
  while (RX_bitset_member (&table->nested_p, bucket))
    {
      table = (struct rx_hash *)(table->children [bucket]);
      ++maskc;
      mask = rx_hash_masks[maskc];
      bucket = H2B(hash & mask);
      ++depth;
    }
  
  {
    struct rx_hash_item * it;
    it = (struct rx_hash_item *)(table->children[bucket]);
    while (it)
      if (eq (it->data, value))
	return it;
      else
	it = it->next_same_hash;
  }
  
  {
    if (   (depth < 3)
	&& (overflows ((struct rx_hash_item *)table->children [bucket])))
      {
	struct rx_hash * newtab;
	newtab = (struct rx_hash *) HASH_ALLOC(rules) (rules);
	if (!newtab)
	  goto add_to_bucket;
	rx_bzero ((char *)newtab, sizeof (*newtab));
	newtab->parent = table;
	{
	  struct rx_hash_item * them;
	  unsigned long newmask;
	  them = (struct rx_hash_item *)table->children[bucket];
	  newmask = rx_hash_masks[maskc + 1];
	  while (them)
	    {
	      struct rx_hash_item * save = them->next_same_hash;
	      int new_buck = H2B(them->hash & newmask);
	      them->next_same_hash = ((struct rx_hash_item *)
				      newtab->children[new_buck]);
	      ((struct rx_hash_item **)newtab->children)[new_buck] = them;
	      them->table = newtab;
	      them = save;
	      ++newtab->refs;
	      --table->refs;
	    }
	  ((struct rx_hash **)table->children)[bucket] = newtab;
	  RX_bitset_enjoin (&table->nested_p, bucket);
	  ++table->refs;
	  table = newtab;
	  bucket = H2B(hash & newmask);
	}
      }
  }
 add_to_bucket:
  {
    struct rx_hash_item  * it = ((struct rx_hash_item *)
				 ITEM_ALLOC(rules) (rules, value));
    if (!it)
      return 0;
    it->hash = hash;
    it->table = table;
    /* DATA and BINDING are to be set in hash_item_alloc */
    it->next_same_hash = (struct rx_hash_item *)table->children [bucket];
    ((struct rx_hash_item **)table->children)[bucket] = it;
    ++table->refs;
    return it;
  }
}


#ifdef __STDC__
void
rx_hash_free (struct rx_hash_item * it, struct rx_hash_rules * rules)
#else
void
rx_hash_free (it, rules)
     struct rx_hash_item * it;
     struct rx_hash_rules * rules;
#endif
{
  if (it)
    {
      struct rx_hash * table = it->table;
      unsigned long hash = it->hash;
      int depth = (table->parent
		   ? (table->parent->parent
		      ? (table->parent->parent->parent
			 ? 3
			 : 2)
		      : 1)
		   : 0);
      int bucket = H2B (hash & rx_hash_masks [depth]);
      struct rx_hash_item ** pos
	= (struct rx_hash_item **)&table->children [bucket];
      
      while (*pos != it)
	pos = &(*pos)->next_same_hash;
      *pos = it->next_same_hash;
      FREE_HASH_ITEM(rules) (it, rules);
      --table->refs;
      while (!table->refs && depth)
	{
	  struct rx_hash * save = table;
	  table = table->parent;
	  --depth;
	  bucket = H2B(hash & rx_hash_masks [depth]);
	  --table->refs;
	  table->children[bucket] = 0;
	  RX_bitset_remove (&table->nested_p, bucket);
	  FREE_HASH (rules) (save, rules);
	}
    }
}

#ifdef __STDC__
void
rx_free_hash_table (struct rx_hash * tab, rx_hash_freefn freefn,
		    struct rx_hash_rules * rules)
#else
void
rx_free_hash_table (tab, freefn, rules)
     struct rx_hash * tab;
     rx_hash_freefn freefn;
     struct rx_hash_rules * rules;
#endif
{
  int x;

  for (x = 0; x < BKTS; ++x)
    if (RX_bitset_member (&tab->nested_p, x))
      {
	rx_free_hash_table ((struct rx_hash *)tab->children[x],
			    freefn, rules);
	FREE_HASH (rules) ((struct rx_hash *)tab->children[x], rules);
      }
    else
      {
	struct rx_hash_item * them = (struct rx_hash_item *)tab->children[x];
	while (them)
	  {
	    struct rx_hash_item * that = them;
	    them = that->next_same_hash;
	    freefn (that);
	    FREE_HASH_ITEM (rules) (that, rules);
	  }
      }
}


#ifdef __STDC__
int 
rx_count_hash_nodes (struct rx_hash * st)
#else
int 
rx_count_hash_nodes (st)
     struct rx_hash * st;
#endif
{
  int x;
  int count = 0;
  for (x = 0; x < BKTS; ++x)
    count += ((RX_bitset_member (&st->nested_p, x))
	      ? rx_count_hash_nodes ((struct rx_hash *)st->children[x])
	      : listlen ((struct rx_hash_item *)(st->children[x])));
  
  return count;
}
Commit	Line	Data
d76ed9a9	1	/* Copyright (C) 1995, 1996 Tom Lord
	2	*
	3	* This program is free software; you can redistribute it and/or modify
	4	* it under the terms of the GNU Library General Public License as published by
	5	* the Free Software Foundation; either version 2, or (at your option)
	6	* any later version.
	7	*
	8	* This program is distributed in the hope that it will be useful,
	9	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	10	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	11	* GNU Library General Public License for more details.
	12	*
	13	* You should have received a copy of the GNU Library General Public License
	14	* along with this software; see the file COPYING. If not, write to
	15	* the Free Software Foundation, 59 Temple Place - Suite 330,
	16	* Boston, MA 02111-1307, USA.
	17	*/
	18
	19	\f
	20	/*
	21	* Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
	22	*/
	23	\f
	24
	25	#include "rxall.h"
	26	#include "rxhash.h"
	27
	28	\f
	29
	30	#ifdef __STDC__
	31	static struct rx_hash *
	32	default_hash_alloc (struct rx_hash_rules * rules)
	33	#else
	34	static struct rx_hash *
	35	default_hash_alloc (rules)
	36	struct rx_hash_rules * rules;
	37	#endif
	38	{
	39	return (struct rx_hash *)malloc (sizeof (struct rx_hash));
	40	}
	41
	42
	43	#ifdef __STDC__
	44	static struct rx_hash_item *
	45	default_hash_item_alloc (struct rx_hash_rules * rules, void * value)
	46	#else
	47	static struct rx_hash_item *
	48	default_hash_item_alloc (rules, value)
	49	struct rx_hash_rules * rules;
	50	void * value;
	51	#endif
	52	{
	53	struct rx_hash_item * it;
	54	it = (struct rx_hash_item )malloc (sizeof (it));
	55	if (it)
	56	{
	57	it->data = value;
	58	it->binding = 0;
	59	}
	60	return it;
	61	}
	62
	63
	64	#ifdef __STDC__
65	static void
66	default_free_hash (struct rx_hash * tab,
67	struct rx_hash_rules * rules)
68	#else
69	static void
70	default_free_hash (tab, rules)
71	struct rx_hash * tab;
72	struct rx_hash_rules * rules;
73	#endif
74	{
75	free ((char *)tab);
76	}
77
78
79	#ifdef __STDC__
80	static void
81	default_free_hash_item (struct rx_hash_item * item,
82	struct rx_hash_rules * rules)
83	#else
84	static void
85	default_free_hash_item (item, rules)
86	struct rx_hash_item * item;
87	struct rx_hash_rules * rules;
88	#endif
89	{
90	free ((char *)item);
91	}
92
93	#ifdef __STDC__
94	static int
95	default_eq (void * va, void * vb)
96	#else
97	static int
98	default_eq (va, vb)
99	void * va;
100	void * vb;
101	#endif
102	{
103	return va == vb;
104	}
105
106	\f
107
108	#define EQ(rules) ((rules && rules->eq) ? rules->eq : default_eq)
109	#define HASH_ALLOC(rules) ((rules && rules->hash_alloc) ? rules->hash_alloc : default_hash_alloc)
110	#define FREE_HASH(rules) ((rules && rules->free_hash) ? rules->free_hash : default_free_hash)
111	#define ITEM_ALLOC(rules) ((rules && rules->hash_item_alloc) ? rules->hash_item_alloc : default_hash_item_alloc)
112	#define FREE_HASH_ITEM(rules) ((rules && rules->free_hash_item) ? rules->free_hash_item : default_free_hash_item)
113
114	\f
115	static unsigned long rx_hash_masks[4] =
116	{
117	0x12488421,
118	0x96699669,
119	0xbe7dd7eb,
120	0xffffffff
121	};
122
123	/* hash to bucket */
124	#define JOIN_BYTE(H, B) (((H) + ((H) << 3) + (B)) & 0xf)
125
126	#define H2B(X) JOIN_BYTE (JOIN_BYTE (JOIN_BYTE ((X & 0xf), ((X>>8) & 0xf)), ((X>>16) & 0xf)), ((X>>24) & 0xf))
127
128	#define BKTS 16
129
130	/* Hash tables */
131	#ifdef __STDC__
132	struct rx_hash_item *
133	rx_hash_find (struct rx_hash * table,
134	unsigned long hash,
135	void * value,
136	struct rx_hash_rules * rules)
137	#else
138	struct rx_hash_item *
139	rx_hash_find (table, hash, value, rules)
140	struct rx_hash * table;
141	unsigned long hash;
142	void * value;
143	struct rx_hash_rules * rules;
144	#endif
145	{
146	rx_hash_eq eq = EQ (rules);
147	int maskc = 0;
148	long mask = rx_hash_masks [0];
149	int bucket = H2B(hash & mask);
150
151	while (RX_bitset_member (&table->nested_p, bucket))
152	{
153	table = (struct rx_hash *)(table->children [bucket]);
154	++maskc;
155	mask = rx_hash_masks[maskc];
156	bucket = H2B (hash & mask);
157	}
158
159	{
160	struct rx_hash_item * it;
161	it = (struct rx_hash_item *)(table->children[bucket]);
162	while (it)
163	if (eq (it->data, value))
164	return it;
165	else
166	it = it->next_same_hash;
167	}
168
169	return 0;
170	}
171
172
173	#ifdef __STDC__
174	static int
175	listlen (struct rx_hash_item * bucket)
176	#else
177	static int
178	listlen (bucket)
179	struct rx_hash_item * bucket;
180	#endif
181	{
182	int i;
183	for (i = 0; bucket; ++i, bucket = bucket->next_same_hash)
184	;
185	return i;
186	}
187
188	#ifdef __STDC__
189	static int
190	overflows (struct rx_hash_item * bucket)
191	#else
192	static int
193	overflows (bucket)
194	struct rx_hash_item * bucket;
195	#endif
196	{
197	return !( bucket
198	&& bucket->next_same_hash
199	&& bucket->next_same_hash->next_same_hash
200	&& bucket->next_same_hash->next_same_hash->next_same_hash);
201	}
202
203
204	#ifdef __STDC__
205	struct rx_hash_item *
206	rx_hash_store (struct rx_hash * table,
207	unsigned long hash,
208	void * value,
209	struct rx_hash_rules * rules)
210	#else
211	struct rx_hash_item *
212	rx_hash_store (table, hash, value, rules)
213	struct rx_hash * table;
214	unsigned long hash;
215	void * value;
216	struct rx_hash_rules * rules;
217	#endif
218	{
219	rx_hash_eq eq = EQ (rules);
220	int maskc = 0;
221	long mask = rx_hash_masks [0];
222	int bucket = H2B(hash & mask);
223	int depth = 0;
224
225	while (RX_bitset_member (&table->nested_p, bucket))
226	{
227	table = (struct rx_hash *)(table->children [bucket]);
228	++maskc;
229	mask = rx_hash_masks[maskc];
230	bucket = H2B(hash & mask);
231	++depth;
232	}
233
234	{
235	struct rx_hash_item * it;
236	it = (struct rx_hash_item *)(table->children[bucket]);
237	while (it)
238	if (eq (it->data, value))
239	return it;
240	else
241	it = it->next_same_hash;
242	}
243
244	{
245	if ( (depth < 3)
246	&& (overflows ((struct rx_hash_item *)table->children [bucket])))
247	{
248	struct rx_hash * newtab;
249	newtab = (struct rx_hash *) HASH_ALLOC(rules) (rules);
250	if (!newtab)
251	goto add_to_bucket;
252	rx_bzero ((char )newtab, sizeof (newtab));
253	newtab->parent = table;
254	{
255	struct rx_hash_item * them;
256	unsigned long newmask;
257	them = (struct rx_hash_item *)table->children[bucket];
258	newmask = rx_hash_masks[maskc + 1];
259	while (them)
260	{
261	struct rx_hash_item * save = them->next_same_hash;
262	int new_buck = H2B(them->hash & newmask);
263	them->next_same_hash = ((struct rx_hash_item *)
264	newtab->children[new_buck]);
265	((struct rx_hash_item **)newtab->children)[new_buck] = them;
266	them->table = newtab;
267	them = save;
268	++newtab->refs;
269	--table->refs;
270	}
271	((struct rx_hash **)table->children)[bucket] = newtab;
272	RX_bitset_enjoin (&table->nested_p, bucket);
273	++table->refs;
274	table = newtab;
275	bucket = H2B(hash & newmask);
276	}
277	}
278	}
279	add_to_bucket:
280	{
281	struct rx_hash_item * it = ((struct rx_hash_item *)
282	ITEM_ALLOC(rules) (rules, value));
283	if (!it)
284	return 0;
285	it->hash = hash;
286	it->table = table;
287	/* DATA and BINDING are to be set in hash_item_alloc */
288	it->next_same_hash = (struct rx_hash_item *)table->children [bucket];
289	((struct rx_hash_item **)table->children)[bucket] = it;
290	++table->refs;
291	return it;
292	}
293	}
294
295
296	#ifdef __STDC__
297	void
298	rx_hash_free (struct rx_hash_item * it, struct rx_hash_rules * rules)
299	#else
300	void
301	rx_hash_free (it, rules)
302	struct rx_hash_item * it;
303	struct rx_hash_rules * rules;
304	#endif
305	{
306	if (it)
307	{
308	struct rx_hash * table = it->table;
309	unsigned long hash = it->hash;
310	int depth = (table->parent
311	? (table->parent->parent
312	? (table->parent->parent->parent
313	? 3
314	: 2)
315	: 1)
316	: 0);
317	int bucket = H2B (hash & rx_hash_masks [depth]);
318	struct rx_hash_item ** pos
319	= (struct rx_hash_item **)&table->children [bucket];
320
321	while (*pos != it)
322	pos = &(*pos)->next_same_hash;
323	*pos = it->next_same_hash;
324	FREE_HASH_ITEM(rules) (it, rules);
325	--table->refs;
326	while (!table->refs && depth)
327	{
328	struct rx_hash * save = table;
329	table = table->parent;
330	--depth;
331	bucket = H2B(hash & rx_hash_masks [depth]);
332	--table->refs;
333	table->children[bucket] = 0;
334	RX_bitset_remove (&table->nested_p, bucket);
335	FREE_HASH (rules) (save, rules);
336	}
337	}
338	}
339
340	#ifdef __STDC__
341	void
342	rx_free_hash_table (struct rx_hash * tab, rx_hash_freefn freefn,
343	struct rx_hash_rules * rules)
344	#else
345	void
346	rx_free_hash_table (tab, freefn, rules)
347	struct rx_hash * tab;
348	rx_hash_freefn freefn;
349	struct rx_hash_rules * rules;
350	#endif
351	{
352	int x;
353
354	for (x = 0; x < BKTS; ++x)
355	if (RX_bitset_member (&tab->nested_p, x))
356	{
357	rx_free_hash_table ((struct rx_hash *)tab->children[x],
358	freefn, rules);
359	FREE_HASH (rules) ((struct rx_hash *)tab->children[x], rules);
360	}
361	else
362	{
363	struct rx_hash_item * them = (struct rx_hash_item *)tab->children[x];
364	while (them)
365	{
366	struct rx_hash_item * that = them;
367	them = that->next_same_hash;
368	freefn (that);
369	FREE_HASH_ITEM (rules) (that, rules);
370	}
371	}
372	}
373
374
375
376	#ifdef __STDC__
377	int
378	rx_count_hash_nodes (struct rx_hash * st)
379	#else
380	int
381	rx_count_hash_nodes (st)
382	struct rx_hash * st;
383	#endif
384	{
385	int x;
386	int count = 0;
387	for (x = 0; x < BKTS; ++x)
388	count += ((RX_bitset_member (&st->nested_p, x))
389	? rx_count_hash_nodes ((struct rx_hash *)st->children[x])
390	: listlen ((struct rx_hash_item *)(st->children[x])));
391
392	return count;
393	}
394