Context Navigation

← Previous Revision
Next Revision →
Blame
Revision Log

source: tags/initial/PROBE/probe_tree.hxx

Visit:

Last change on this file was 2, checked in by oldcode, 25 years ago
Initial revision
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 12.2 KB

Line
1	#if (!defined(NO_INLINE)) \|\| defined(IMPLEMENT_PROBE_TREE)
2
3	#define PTM_magic 0xf4
4	#define PTM_TABLE_SIZE (1024*256)
5	#define PTM_ALIGNED 1
6	#define PTM_LD_ALIGNED 0
7	#define PTM_MAX_TABLES 64
8	#define PTM_MAX_SIZE (PTM_MAX_TABLES*PTM_ALIGNED)
9	#define PT_CHAIN_END 0xff
10	#define PT_CHAIN_NTERM 250
11	#define PT_SHORT_SIZE 0xffff
12	#define PT_BLOCK_SIZE 0x800
13	#define PT_INIT_CHAIN_SIZE 20
14	#define PT_NEXT_CHAIN_SIZE(x) = (x*3/2);
15
16	typedef void * PT_PNTR;
17
18	extern struct PTM_struct {
19	char *data;
20	int size;
21	int allsize;
22	char *tables[PTM_MAX_TABLES+1];
23	#ifdef PTM_DEBUG
24	long debug[PTM_MAX_TABLES+1];
25	#endif
26	PT_NODE_TYPE flag_2_type[256];
27	} PTM;
28
29	extern char PT_count_bits[PT_B_MAX+1][256]; // returns how many bits are set
30	// e.g. PT_count_bits[3][n] is the number of the 3 lsb bits
31
32	#if 0
33	/*
34
35	/ ****************
36	Their are 3 stages of data format:
37	1st: Creation of the tree
38	2nd: find equal or nearly equal subtrees
39	3nd: minimum sized tree
40
41	The generic pointer (father):
42	1st create: Pointer to the father
43	1st save:
44	2nd load rel ptr of 'this' in the output file
45	(==0 indicates not saved)
46
47	**************** /
48	/ * data format: * /
49
50	/ ******************* Written object ********************* /
51	byte =32 bit[7] = bit[6] = 0; bit[5] = 1
52	bit[4] free
53	bit[0-3] size of former entry -4
54	if ==0 then size follows
55	int rel start of the real object
56	[int size] if bit[0-3] == 0;
57
58	/ ******************* tip (7-13 +4) ********************* /
59	byte <32 bit[7] = bit[6] = bit[5] = 0
60	bit[3-4] free
61	[PT_PNTR father] if main->mode
62	short/int name int if bit[0]
63	short/int rel pos int if bit[1]
64	short/int abs pos int if bit[2]
65
66	/ ********************* inner node (1 + 4[1-6] +4) (stage 1 + 2) ********************** /
67	byte >128 bit[7] = 1
68	bit[6] = 0
69	[PT_PNTR father] if main->mode
70	[PT_PNTR son0] if bit[0]
71	...
72	[PT_PNTR son5] if bit[5]
73
74	/ ******************* inner node (3-22 +4) (stage 3 only) ********************* /
75	byte bit[7] = 1 bit[6] = 0
76	byte2 if bit2[7] then int/short else short/char
77	[char/short/int son0] if bit[0] short/int if bit2[0] else char/short
78	[char/short/int son1] if bit[1]
79	[char/short/int son5] if bit[5]
80
81	/ ******************* inner nodesingle (1) (stage3 only) ********************* /
82	byte bit[7] = 1 bit[6] = 1
83	bit[0-2] base
84	bit[3-5] offset 0->1 1->3 2->4 3->5 ....
85
86
87	/ ******************* chain (8-n +4) stage 1 ********************* /
88	byte =64/65 bit[7] = 0, bit[6] = 1 bit[5] = 0
89	[PT_PNTR father] if main->mode
90	short/int ref abs pos int if bit[0]
91	PT_PNTR firstelem
92
93	/ ** chain elems * /
94	PT_PNTR next element
95	short/int name
96	if bit[15] than integer
97	-1 not allowed
98	short/int rel pos
99	if bit[15] than integer
100	short/int apos short if bit[15] = 0]
101	]
102
103
104	/ ******************* chain (8-n +4) stage 2/3 ********************* /
105
106	byte =64/65 bit[7] = 0, bit[6] = 1 bit[5] = 0
107	[int father] if main->mode
108	short/int ref abs pos int if bit[0]
109	[ char/short/int rel name [ to last name eg. rel names 10 30 20 50 -> abs names = 10 40 60 110
110	if bit[7] than short
111	if bit[7] and bit[6] than integer
112	-1 not allowed
113	short/int rel pos
114	if bit[15] -> the next bytes are the apos else use ref_abs_pos
115	if bit[14] -> this(==rel_pos) is integer
116	[short/int] [apos short if bit[15] = 0]
117	]
118	char -1 end flag
119
120	only few functions can be used, when the tree is reloaded (stage 3):
121	PT_read_type
122	PT_read_son
123	PT_read_xpos
124	PT_read_name
125	PT_read_chain
126	*/
127	#endif
128
129	#define IS_SINGLE_BRANCH_NODE 0x40
130	#define LONG_SONS 0x80
131
132	/******************* Get the size of entries (stage 1) only*********************/
133
134	#define PT_EMPTY_LEAF_SIZE (1+sizeof(PT_PNTR)+6) /* tag father name rel apos */
135	#define PT_LEAF_SIZE(leaf) (1+sizeof(PT_PNTR)+6+2*PT_count_bits[3][leaf->flags])
136	#define PT_EMPTY_CHAIN_SIZE (1+sizeof(PT_PNTR)+2+sizeof(PT_PNTR)) // tag father apos first_elem
137	#define PT_EMPTY_NODE_SIZE (1+sizeof(PT_PNTR)) // tag father
138	#define PT_NODE_COUNT_SONS(leaf) PT_count_bits[3][leaf->flags];
139	#define PT_NODE_SIZE(node,size) size = PT_EMPTY_NODE_SIZE + sizeof(PT_PNTR)*PT_count_bits[PT_B_MAX][node->flags]
140
141	/******************* Read and write type *********************/
142
143	#define PT_GET_TYPE(pt) (PTM.flag_2_type[pt->flags])
144	#define PT_SET_TYPE(pt,i,j) (pt->flags = (i<<6)+j)
145
146	/******************* Read and write to memory *********************/
147
148	#define PT_READ_INT(ptr,my_int_i) do { unsigned char mycharp=(unsigned char )ptr; \
149	my_int_i= mycharp[0]<<24 \| mycharp[1]<<16 \| mycharp[2]<<8 \| mycharp[3]; \
150	} while(0)
151
152	#define PT_WRITE_INT(ptr,my_int_i) do { unsigned char mycharp=(unsigned char )(ptr);unsigned long myinti = (unsigned long)(my_int_i); \
153	mycharp[0]= (unsigned char)(myinti>>24); \
154	mycharp[1]= (unsigned char)(myinti>>16); \
155	mycharp[2]= (unsigned char)(myinti>>8); \
156	mycharp[3]= (unsigned char)myinti; \
157	} while(0)
158
159	#define PT_READ_SHORT(ptr,my_int_i) do { unsigned char mycharp=(unsigned char )ptr; \
160	my_int_i= mycharp[0]<<8 \| mycharp[1]; \
161	} while(0)
162
163	#define PT_WRITE_SHORT(ptr,my_int_i) do { \
164	unsigned char mycharp=(unsigned char )ptr;unsigned long myinti = (unsigned long)my_int_i; \
165	mycharp[0]= (unsigned char)(myinti>>8); \
166	mycharp[1]= (unsigned char)(myinti); \
167	} while(0)
168
169	#define PT_WRITE_CHAR(ptr,my_int_i) do { (unsigned char )(ptr) = my_int_i; } while(0)
170
171	#define PT_READ_CHAR(ptr,my_int_i) do { my_int_i = (unsigned char )(ptr); } while(0)
172
173
174
175
176	#ifdef DIGITAL
177
178	/* DIGITAL */
179
180	# define PT_READ_PNTR(ptr,my_int_i) \
181	do { \
182	if (sizeof(my_int_i)==4) GB_CORE; \
183	unsigned char mycharp=(unsigned char )ptr; \
184	my_int_i= mycharp[0]<<56 \| mycharp[1]<<48 \| mycharp[2]<<40 \| mycharp[3] << 32 \| \
185	mycharp[4]<<24 \| mycharp[5]<<16 \| mycharp[6]<<8 \| mycharp[7]; \
186	} while(0)
187
188	# define PT_WRITE_PNTR(ptr,my_int_i) \
189	do { \
190	unsigned char mycharp=(unsigned char )(ptr);unsigned long myinti = (unsigned long)(my_int_i); \
191	mycharp[0]= (unsigned char)(myinti>>56); \
192	mycharp[1]= (unsigned char)(myinti>>48); \
193	mycharp[2]= (unsigned char)(myinti>>40); \
194	mycharp[3]= (unsigned char)(myinti>>32); \
195	mycharp[4]= (unsigned char)(myinti>>24); \
196	mycharp[5]= (unsigned char)(myinti>>16); \
197	mycharp[6]= (unsigned char)(myinti>>8); \
198	mycharp[7]= (unsigned char)myinti; \
199	} while(0)
200
201
202	#else
203
204	/* not DIGITAL */
205
206	# define PT_READ_PNTR(ptr,my_int_i) PT_READ_INT(ptr, my_int_i)
207	# define PT_WRITE_PNTR(ptr,my_int_i) PT_WRITE_INT(ptr, my_int_i)
208
209	#endif
210
211
212
213	#define PT_WRITE_NAT(ptr,i) do { \
214	if (i<0) GB_CORE; \
215	if (i>= 0x7FFE) \
216	{ \
217	PT_WRITE_INT(ptr,i\|0x80000000); \
218	ptr += sizeof(int); \
219	} \
220	else \
221	{ \
222	PT_WRITE_SHORT(ptr,i); \
223	ptr += sizeof(short); \
224	} \
225	} while (0)
226
227	#define PT_READ_NAT(ptr,i) \
228	do { \
229	if (*ptr & 0x80) { \
230	PT_READ_INT(ptr,i); ptr+= sizeof(int); i &= 0x7fffffff; \
231	}else{ \
232	PT_READ_SHORT(ptr,i); ptr+= sizeof(short); \
233	} \
234	} while(0)
235
236
237	/******************* PT_READ_CHAIN_ENTRY *********************/
238
239	#define PT_READ_CHAIN_ENTRY(ptr,mainapos,name,apos,rpos) do { \
240	unsigned int rcei; \
241	unsigned char rcep = (unsigned char)ptr; \
242	int isapos; \
243	apos = 0; \
244	rpos = 0; \
245	rcei = (*rcep); \
246	if (rcei==PT_CHAIN_END) { name = -1; ptr++; \
247	}else { \
248	if (rcei&0x80) {if (rcei&0x40) { PT_READ_INT(rcep,rcei); rcep+=4; rcei &= 0x3fffffff; \
249	}else{ PT_READ_SHORT(rcep,rcei); rcep+=2; rcei &= 0x3fff; \
250	} \
251	}else{ rcei&= 0x7f;rcep++; } \
252	name += rcei; \
253	rcei = (*rcep); \
254	if (rcei&0x80) isapos = 1; else isapos = 0; \
255	if (rcei&0x40) { PT_READ_INT(rcep,rcei); rcep+=4; rcei &= 0x3fffffff; \
256	}else{ PT_READ_SHORT(rcep,rcei); rcep+=2; rcei &= 0x3fff; \
257	} \
258	rpos = (int)rcei; \
259	if (isapos) { \
260	rcei = (*rcep); \
261	if (rcei&0x80) { PT_READ_INT(rcep,rcei); rcep+=4; rcei &= 0x7fffffff; \
262	}else{ PT_READ_SHORT(rcep,rcei); rcep+=2; rcei &= 0x7fff; \
263	} \
264	apos = (int)rcei; \
265	}else{ \
266	apos = (int)mainapos;} \
267	ptr = (char *)rcep; \
268	} } while(0)
269
270
271	/* stage 1 */
272	GB_INLINE char PT_WRITE_CHAIN_ENTRY(char ptr,int mainapos,int name,int apos,int rpos)
273	{
274	register unsigned char wcep = (unsigned char )ptr;
275	int isapos;
276	if (name < 0x7f) { /* write the name */
277	*(wcep++) = name;
278	} else if (name <0x3fff) {
279	name \|= 0x8000;
280	PT_WRITE_SHORT(wcep,name);
281	wcep += 2;
282	} else {
283	name\|=0xc0000000;
284	PT_WRITE_INT(wcep,name);
285	wcep += 4;
286	}
287	if (apos == mainapos) isapos = 0; else isapos = 0x80;
288	if (rpos < 0x7fff) { /* write the rpos */
289	PT_WRITE_SHORT(wcep,rpos);
290	*wcep \|= isapos;
291	wcep += 2;
292	} else {
293	PT_WRITE_INT(wcep,rpos);
294	*wcep \|= 0x40+isapos;
295	wcep += 4;
296	}
297	if (isapos){ /* write the apos */
298	if (apos < 0x7fff) {
299	PT_WRITE_SHORT(wcep,apos);
300	wcep += 2;
301	} else {
302	PT_WRITE_INT(wcep,apos);
303	*wcep \|= 0x80;
304	wcep += 4;
305	}
306	}
307	return (char *)wcep;
308	}
309	// calculate the index of the pointer in a node
310
311	GB_INLINE POS_TREE PT_read_son(PTM2 ptmain, POS_TREE *node, PT_BASES base)
312	{
313	register long i;
314	register uint sec;
315	register uint offset;
316	if (ptmain->stage3) { // stage 3 no father
317	if (node->flags & IS_SINGLE_BRANCH_NODE){
318	if (base != (node->flags & 0x7)) return 0; // no son
319	i = (node->flags >> 3)&0x7; // this son
320	if (!i) i = 1; else i+=2; // offset mapping
321	return (POS_TREE )(((char )node)-i);
322	}
323	if (!( (1<<base) & node->flags)) return 0; /* bit not set */
324	sec = (uchar)node->data; // read second byte for charshort/shortlong info
325	i = PT_count_bits[base][node->flags];
326	i+= PT_count_bits[base][sec];
327	if (sec & LONG_SONS) {
328	offset = i+i;
329	if ( (1<<base) & sec) {
330	PT_READ_INT((&node->data+1)+offset,i);
331	}else{
332	PT_READ_SHORT((&node->data+1)+offset,i);
333	}
334	}else{
335	offset = i;
336	if ( (1<<base) & sec) {
337	PT_READ_SHORT((&node->data+1)+offset,i);
338	}else{
339	PT_READ_CHAR((&node->data+1)+offset,i);
340	}
341	}
342	return (POS_TREE *)(((ulong)node)-i);
343
344	}else{ // stage 1 or 2 ->father
345	if (!( (1<<base) & node->flags)) return 0; /* bit not set */
346	base = (PT_BASES)PT_count_bits[base][node->flags];
347	PT_READ_PNTR((&node->data)+sizeof(PT_PNTR)*base+ptmain->mode,i);
348	return (POS_TREE *)(i+ptmain->base);
349	}
350	}
351
352	GB_INLINE POS_TREE PT_read_son_stage_1(PTM2 ptmain, POS_TREE *node, PT_BASES base)
353	{
354	register long i;
355	if (!( (1<<base) & node->flags)) return 0; /* bit not set */
356	base = (PT_BASES)PT_count_bits[base][node->flags];
357	PT_READ_PNTR((&node->data)+sizeof(PT_PNTR)*base+ptmain->mode,i);
358	return (POS_TREE *)(i+ptmain->base);
359	}
360
361	GB_INLINE PT_NODE_TYPE PT_read_type(POS_TREE *node)
362	{
363	return (PT_NODE_TYPE)PT_GET_TYPE(node);
364	}
365
366	GB_INLINE int PT_read_name(PTM2 ptmain,POS_TREE node)
367	{
368	int i;
369	if (node->flags&1){
370	PT_READ_INT((&node->data)+ptmain->mode,i);
371	}else{
372	PT_READ_SHORT((&node->data)+ptmain->mode,i);
373	}
374	return i;
375	}
376
377	GB_INLINE int PT_read_rpos(PTM2 ptmain,POS_TREE node)
378	{
379	int i;
380	char *data = (&node->data)+2+ptmain->mode;
381	if (node->flags&1) data+=2;
382	if (node->flags&2){
383	PT_READ_INT(data,i);
384	}else{
385	PT_READ_SHORT(data,i);
386	}
387	return i;
388	}
389
390	GB_INLINE int PT_read_apos(PTM2 ptmain,POS_TREE node)
391	{
392	int i;
393	char data = (&node->data)+ptmain->mode+4; / father 4 name 2 rpos 2 */
394	if (node->flags&1) data+=2;
395	if (node->flags&2) data+=2;
396	if (node->flags&4){
397	PT_READ_INT(data,i);
398	}else{
399	PT_READ_SHORT(data,i);
400	}
401	return i;
402	}
403
404	GB_INLINE int PT_read_chain(PTM2 ptmain,POS_TREE node, int func(int name,int apos,int rpos, long clientdata), long clientdata)
405	{
406	int pos, apos, rpos;
407	int cname;
408	int error;
409	char *data;
410
411	data = (&node->data) + ptmain->mode;
412	if (node->flags&1){
413	PT_READ_INT(data,pos);
414	data += 4;
415	}else{
416	PT_READ_SHORT(data,pos);
417	data += 2;
418	}
419	error = 0;
420	cname = 0;
421	while (cname>=0){
422	PT_READ_CHAIN_ENTRY(data,pos,cname,apos,rpos);
423	if (cname>=0){
424	error = func(cname,apos,rpos,clientdata);
425	if (error) return error;
426	}
427	}
428	return error;
429	}
430
431	#endif

Note: See TracBrowser for help on using the repository browser.

Download in other formats: