« back to all changes in this revision
Viewing changes to array.c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): James Troup
- Date: 2001-07-18 20:40:37 UTC
- Revision ID: james.westby@ubuntu.com-20010718204037-8hrndw7iapy9yj3w
Tags: upstream-1.3.3
Import upstream version 1.3.3
- files added:
- atarist
- config-user
- examples
- man
- msdos
- msdos/examples
- rexp
- test
- v7
added
removed
array.c
1
/*
2
array.c
3
copyright 1991-96, Michael D. Brennan
4
5
This is a source file for mawk, an implementation of
6
the AWK programming language.
7
8
Mawk is distributed without warranty under the terms of
9
the GNU General Public License, version 2, 1991.
10
*/
11
12
/*
13
This file was generated with the command
14
15
notangle -R'"array.c"' array.w > array.c
16
17
Notangle is part of Norman Ramsey's noweb literate programming package
18
available from CTAN(ftp.shsu.edu).
19
20
It's easiest to read or modify this file by working with array.w.
21
*/
22
23
#include "mawk.h"
24
#include "symtype.h"
25
#include "memory.h"
26
#include "field.h"
27
#include "bi_vars.h"
28
struct anode ;
29
typedef struct {struct anode *slink, *ilink ;} DUAL_LINK ;
30
31
typedef struct anode {
32
struct anode *slink ;
33
struct anode *ilink ;
34
STRING *sval ;
35
unsigned hval ;
36
Int ival ;
37
CELL cell ;
38
} ANODE ;
39
40
41
#define NOT_AN_IVALUE (-Max_Int-1) /* usually 0x80000000 */
42
43
#define STARTING_HMASK 63 /* 2^6-1, must have form 2^n-1 */
44
#define MAX_AVE_LIST_LENGTH 12
45
#define hmask_to_limit(x) (((x)+1)*MAX_AVE_LIST_LENGTH)
46
47
static ANODE* PROTO(find_by_ival,(ARRAY, Int, int)) ;
48
static ANODE* PROTO(find_by_sval,(ARRAY, STRING*, int)) ;
49
static void PROTO(add_string_associations,(ARRAY)) ;
50
static void PROTO(make_empty_table,(ARRAY, int)) ;
51
static void PROTO(convert_split_array_to_table,(ARRAY)) ;
52
static void PROTO(double_the_hash_table,(ARRAY)) ;
53
static unsigned PROTO(ahash, (STRING*)) ;
54
55
56
CELL* array_find(A, cp, create_flag)
57
ARRAY A ;
58
CELL *cp ;
59
int create_flag ;
60
{
61
ANODE *ap ;
62
if (A->size == 0 && !create_flag)
63
/* eliminating this trivial case early avoids unnecessary conversions later */
64
return (CELL*) 0 ;
65
switch (cp->type) {
66
case C_DOUBLE:
67
{
68
double d = cp->dval ;
69
Int ival = d_to_I(d) ;
70
if ((double)ival == d) {
71
if (A->type == AY_SPLIT) {
72
if (ival >= 1 && ival <= A->size)
73
return (CELL*)A->ptr+(ival-1) ;
74
if (!create_flag) return (CELL*) 0 ;
75
convert_split_array_to_table(A) ;
76
}
77
else if (A->type == AY_NULL) make_empty_table(A, AY_INT) ;
78
ap = find_by_ival(A, ival, create_flag) ;
79
}
80
else {
81
/* convert to string */
82
char buff[260] ;
83
STRING *sval ;
84
sprintf(buff, string(CONVFMT)->str, d) ;
85
sval = new_STRING(buff) ;
86
ap = find_by_sval(A,sval,create_flag) ;
87
free_STRING(sval) ;
88
}
89
}
90
91
break ;
92
case C_NOINIT:
93
ap = find_by_sval(A, &null_str, create_flag) ;
94
break ;
95
default:
96
ap = find_by_sval(A, string(cp), create_flag) ;
97
break ;
98
}
99
return ap ? &ap->cell : (CELL *) 0 ;
100
}
101
102
void array_delete(A, cp)
103
ARRAY A ;
104
CELL *cp ;
105
{
106
ANODE *ap ;
107
if (A->size == 0) return ;
108
switch(cp->type) {
109
case C_DOUBLE :
110
{
111
double d = cp->dval ;
112
Int ival = d_to_I(d) ;
113
if ((double)ival == d) {
114
if (A->type == AY_SPLIT)
115
if (ival >=1 && ival <= A->size) convert_split_array_to_table(A) ;
116
else return ; /* ival not in range */
117
ap = find_by_ival(A, ival, NO_CREATE) ;
118
if (ap) { /* remove from the front of the ilist */
119
DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
120
table[ap->ival & A->hmask].ilink = ap->ilink ;
121
if (ap->sval) {
122
ANODE *p, *q = 0 ;
123
int index = ap->hval & A->hmask ;
124
p = table[index].slink ;
125
while(p != ap) { q = p ; p = q->slink ; }
126
if (q) q->slink = p->slink ;
127
else table[index].slink = p->slink ;
128
free_STRING(ap->sval) ;
129
}
130
131
cell_destroy(&ap->cell) ;
132
ZFREE(ap) ;
133
if (--A->size == 0) array_clear(A) ;
134
135
136
}
137
return ;
138
}
139
140
else { /* get the string value */
141
char buff[260] ;
142
STRING *sval ;
143
sprintf(buff, string(CONVFMT)->str, d) ;
144
sval = new_STRING(buff) ;
145
ap = find_by_sval(A, sval, NO_CREATE) ;
146
free_STRING(sval) ;
147
}
148
}
149
break ;
150
case C_NOINIT :
151
ap = find_by_sval(A, &null_str, NO_CREATE) ;
152
break ;
153
default :
154
ap = find_by_sval(A, string(cp), NO_CREATE) ;
155
break ;
156
}
157
if (ap) { /* remove from the front of the slist */
158
DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
159
table[ap->hval&A->hmask].slink = ap->slink ;
160
if (ap->ival != NOT_AN_IVALUE) {
161
ANODE *p, *q = 0 ;
162
int index = ap->ival & A->hmask ;
163
p = table[index].ilink ;
164
while(p != ap) { q = p ; p = q->ilink ; }
165
if (q) q->ilink = p->ilink ;
166
else table[index].ilink = p->ilink ;
167
}
168
169
free_STRING(ap->sval) ;
170
cell_destroy(&ap->cell) ;
171
ZFREE(ap) ;
172
if (--A->size == 0) array_clear(A) ;
173
174
175
}
176
}
177
178
void array_load(A, cnt)
179
ARRAY A ;
180
int cnt ;
181
{
182
CELL *cells ; /* storage for A[1..cnt] */
183
int i ; /* index into cells[] */
184
if (A->type != AY_SPLIT || A->limit < cnt) {
185
array_clear(A) ;
186
A->limit = (cnt&~3)+4 ;
187
A->ptr = zmalloc(A->limit*sizeof(CELL)) ;
188
A->type = AY_SPLIT ;
189
}
190
else
191
for(i=0;i < A->size; i++) cell_destroy((CELL*)A->ptr+i) ;
192
193
cells = (CELL*) A->ptr ;
194
A->size = cnt ;
195
if (cnt > MAX_SPLIT) {
196
SPLIT_OV *p = split_ov_list ;
197
SPLIT_OV *q ;
198
split_ov_list = (SPLIT_OV*) 0 ;
199
i = MAX_SPLIT ;
200
while( p ) {
201
cells[i].type = C_MBSTRN ;
202
cells[i].ptr = (PTR) p->sval ;
203
q = p ; p = q->link ; ZFREE(q) ;
204
i++ ;
205
}
206
cnt = MAX_SPLIT ;
207
}
208
209
for(i=0;i < cnt; i++) {
210
cells[i].type = C_MBSTRN ;
211
cells[i].ptr = split_buff[i] ;
212
}
213
}
214
215
void array_clear(A)
216
ARRAY A ;
217
{
218
int i ;
219
ANODE *p, *q ;
220
if (A->type == AY_SPLIT) {
221
for(i=0;i < A->size; i++) cell_destroy((CELL*)A->ptr+i) ;
222
zfree(A->ptr, A->limit * sizeof(CELL)) ;
223
}
224
else if (A->type & AY_STR) {
225
DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
226
for(i=0;i <= A->hmask; i++) {
227
p = table[i].slink ;
228
while(p) {
229
q = p ; p = q->slink ;
230
free_STRING(q->sval) ;
231
cell_destroy(&q->cell) ;
232
ZFREE(q) ;
233
}
234
}
235
zfree(A->ptr, (A->hmask+1)*sizeof(DUAL_LINK)) ;
236
}
237
else if (A->type & AY_INT) {
238
DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
239
for(i=0;i <= A->hmask; i++) {
240
p = table[i].ilink ;
241
while(p) {
242
q = p ; p = q->ilink ;
243
cell_destroy(&q->cell) ;
244
ZFREE(q) ;
245
}
246
}
247
zfree(A->ptr, (A->hmask+1)*sizeof(DUAL_LINK)) ;
248
}
249
memset(A, 0, sizeof(*A)) ;
250
}
251
252
253
254
STRING** array_loop_vector(A, sizep)
255
ARRAY A ;
256
unsigned *sizep ;
257
{
258
STRING** ret ;
259
*sizep = A->size ;
260
if (A->size > 0) {
261
if (!(A->type & AY_STR)) add_string_associations(A) ;
262
ret = (STRING**) zmalloc(A->size*sizeof(STRING*)) ;
263
{
264
int r = 0 ; /* indexes ret */
265
DUAL_LINK* table = (DUAL_LINK*) A->ptr ;
266
int i ; /* indexes table */
267
ANODE *p ; /* walks slists */
268
for(i=0;i <= A->hmask; i++) {
269
for(p = table[i].slink; p ; p = p->slink) {
270
ret[r++] = p->sval ;
271
p->sval->ref_cnt++ ;
272
}
273
}
274
}
275
276
return ret ;
277
}
278
else return (STRING**) 0 ;
279
}
280
281
CELL *array_cat(sp, cnt)
282
CELL *sp ;
283
int cnt ;
284
{
285
CELL *p ; /* walks the eval stack */
286
CELL subsep ; /* local copy of SUBSEP */
287
unsigned subsep_len ; /* string length of subsep_str */
288
char *subsep_str ;
289
290
unsigned total_len ; /* length of cat'ed expression */
291
CELL *top ; /* value of sp at entry */
292
char *target ; /* build cat'ed char* here */
293
STRING *sval ; /* build cat'ed STRING here */
294
cellcpy(&subsep, SUBSEP) ;
295
if ( subsep.type < C_STRING ) cast1_to_s(&subsep) ;
296
subsep_len = string(&subsep)->len ;
297
subsep_str = string(&subsep)->str ;
298
299
top = sp ; sp -= (cnt-1) ;
300
301
total_len = (cnt-1)*subsep_len ;
302
for(p = sp ; p <= top ; p++) {
303
if ( p->type < C_STRING ) cast1_to_s(p) ;
304
total_len += string(p)->len ;
305
}
306
307
sval = new_STRING0(total_len) ;
308
target = sval->str ;
309
for(p = sp ; p < top ; p++) {
310
memcpy(target, string(p)->str, string(p)->len) ;
311
target += string(p)->len ;
312
memcpy(target, subsep_str, subsep_len) ;
313
target += subsep_len ;
314
}
315
/* now p == top */
316
memcpy(target, string(p)->str, string(p)->len) ;
317
318
for(p = sp; p <= top ; p++) free_STRING(string(p)) ;
319
free_STRING(string(&subsep)) ;
320
/* set contents of sp , sp->type > C_STRING is possible so reset */
321
sp->type = C_STRING ;
322
sp->ptr = (PTR) sval ;
323
return sp ;
324
325
}
326
327
static ANODE* find_by_ival(A, ival, create_flag)
328
ARRAY A ;
329
Int ival ;
330
int create_flag ;
331
{
332
DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
333
unsigned index = ival & A->hmask ;
334
ANODE *p = table[index].ilink ; /* walks ilist */
335
ANODE *q = (ANODE*) 0 ; /* trails p */
336
while(1) {
337
if (!p) {
338
/* search failed */
339
if (A->type & AY_STR) {
340
/* need to search by string */
341
char buff[256] ;
342
STRING *sval ;
343
sprintf(buff, INT_FMT, ival) ;
344
sval = new_STRING(buff) ;
345
p = find_by_sval(A, sval, create_flag) ;
346
free_STRING(sval) ;
347
if (!p) return (ANODE*) 0 ;
348
}
349
else if (create_flag) {
350
p = ZMALLOC(ANODE) ;
351
p->sval = (STRING*) 0 ;
352
p->cell.type = C_NOINIT ;
353
if (++A->size > A->limit) {
354
double_the_hash_table(A) ; /* changes table, may change index */
355
table = (DUAL_LINK*) A->ptr ;
356
index = A->hmask & ival ;
357
}
358
}
359
else return (ANODE*) 0 ;
360
p->ival = ival ;
361
A->type |= AY_INT ;
362
363
break ;
364
}
365
else if (p->ival == ival) {
366
/* found it, now move to the front */
367
if (!q) /* already at the front */
368
return p ;
369
/* delete for insertion at the front */
370
q->ilink = p->ilink ;
371
break ;
372
}
373
q = p ; p = q->ilink ;
374
}
375
/* insert at the front */
376
p->ilink = table[index].ilink ;
377
table[index].ilink = p ;
378
return p ;
379
}
380
381
static ANODE* find_by_sval(A, sval, create_flag)
382
ARRAY A ;
383
STRING *sval ;
384
int create_flag ;
385
{
386
unsigned hval = ahash(sval) ;
387
char *str = sval->str ;
388
DUAL_LINK *table ;
389
int index ;
390
ANODE *p ; /* walks list */
391
ANODE *q = (ANODE*) 0 ; /* trails p */
392
if (! (A->type & AY_STR)) add_string_associations(A) ;
393
table = (DUAL_LINK*) A->ptr ;
394
index = hval & A->hmask ;
395
p = table[index].slink ;
396
while(1) {
397
if (!p) {
398
if (create_flag) {
399
{
400
p = ZMALLOC(ANODE) ;
401
p->sval = sval ;
402
sval->ref_cnt++ ;
403
p->ival = NOT_AN_IVALUE ;
404
p->hval = hval ;
405
p->cell.type = C_NOINIT ;
406
if (++A->size > A->limit) {
407
double_the_hash_table(A) ; /* changes table, may change index */
408
table = (DUAL_LINK*) A->ptr ;
409
index = hval & A->hmask ;
410
}
411
}
412
413
break ;
414
}
415
else return (ANODE*) 0 ;
416
}
417
else if (p->hval == hval && strcmp(p->sval->str,str) == 0 ) {
418
/* found */
419
if (!q) /* already at the front */
420
return p ;
421
else { /* delete for move to the front */
422
q->slink = p->slink ;
423
break ;
424
}
425
}
426
q = p ; p = q->slink ;
427
}
428
p->slink = table[index].slink ;
429
table[index].slink = p ;
430
return p ;
431
}
432
433
static void add_string_associations(A)
434
ARRAY A ;
435
{
436
if (A->type == AY_NULL) make_empty_table(A, AY_STR) ;
437
else {
438
DUAL_LINK *table ;
439
int i ; /* walks table */
440
ANODE *p ; /* walks ilist */
441
char buff[256] ;
442
if (A->type == AY_SPLIT) convert_split_array_to_table(A) ;
443
table = (DUAL_LINK*) A->ptr ;
444
for(i=0;i <= A->hmask; i++) {
445
p = table[i].ilink ;
446
while(p) {
447
sprintf(buff, INT_FMT, p->ival) ;
448
p->sval = new_STRING(buff) ;
449
p->hval = ahash(p->sval) ;
450
p->slink = table[A->hmask&p->hval].slink ;
451
table[A->hmask&p->hval].slink = p ;
452
p = p->ilink ;
453
}
454
}
455
A->type |= AY_STR ;
456
}
457
}
458
459
static void make_empty_table(A, type)
460
ARRAY A ;
461
int type ; /* AY_INT or AY_STR */
462
{
463
size_t sz = (STARTING_HMASK+1)*sizeof(DUAL_LINK) ;
464
A->type = type ;
465
A->hmask = STARTING_HMASK ;
466
A->limit = hmask_to_limit(STARTING_HMASK) ;
467
A->ptr = memset(zmalloc(sz), 0, sz) ;
468
}
469
470
static void convert_split_array_to_table(A)
471
ARRAY A ;
472
{
473
CELL *cells = (CELL*) A->ptr ;
474
int i ; /* walks cells */
475
DUAL_LINK *table ;
476
int j ; /* walks table */
477
unsigned entry_limit = A->limit ;
478
A->hmask = STARTING_HMASK ;
479
A->limit = hmask_to_limit(STARTING_HMASK) ;
480
while(A->size > A->limit) {
481
A->hmask = (A->hmask<<1) + 1 ; /* double the size */
482
A->limit = hmask_to_limit(A->hmask) ;
483
}
484
{
485
size_t sz = (A->hmask+1)*sizeof(DUAL_LINK) ;
486
A->ptr = memset(zmalloc(sz), 0, sz) ;
487
table = (DUAL_LINK*) A->ptr ;
488
}
489
490
491
/* insert each cells[i] in the new hash table on an ilist */
492
for(i=0, j=1 ;i < A->size; i++) {
493
ANODE *p = ZMALLOC(ANODE) ;
494
p->sval = (STRING*) 0 ;
495
p->ival = i+1 ;
496
p->cell = cells[i] ;
497
p->ilink = table[j].ilink ;
498
table[j].ilink = p ;
499
j++ ; j &= A->hmask ;
500
}
501
A->type = AY_INT ;
502
zfree(cells, entry_limit*sizeof(CELL)) ;
503
}
504
505
static void double_the_hash_table(A)
506
ARRAY A ;
507
{
508
unsigned old_hmask = A->hmask ;
509
unsigned new_hmask = (old_hmask<<1)+1 ;
510
DUAL_LINK *table ;
511
A->ptr = zrealloc(A->ptr, (old_hmask+1)*sizeof(DUAL_LINK),
512
(new_hmask+1)*sizeof(DUAL_LINK)) ;
513
table = (DUAL_LINK*) A->ptr ;
514
/* zero out the new part which is the back half */
515
memset(&table[old_hmask+1], 0, (old_hmask+1)*sizeof(DUAL_LINK)) ;
516
517
if (A->type & AY_STR) {
518
int i ; /* index to old lists */
519
int j ; /* index to new lists */
520
ANODE *p ; /* walks an old list */
521
ANODE *q ; /* trails p for deletion */
522
ANODE *tail ; /* builds new list from the back */
523
ANODE dummy0, dummy1 ;
524
for(i=0, j=old_hmask+1;i <= old_hmask; i++, j++)
525
{
526
q = &dummy0 ;
527
q->slink = p = table[i].slink ;
528
tail = &dummy1 ;
529
while (p) {
530
if ((p->hval&new_hmask) != i) { /* move it */
531
q->slink = p->slink ;
532
tail = tail->slink = p ;
533
}
534
else q = p ;
535
p = q->slink ;
536
}
537
table[i].slink = dummy0.slink ;
538
tail->slink = (ANODE*) 0 ;
539
table[j].slink = dummy1.slink ;
540
}
541
542
}
543
544
if (A->type & AY_INT) {
545
int i ; /* index to old lists */
546
int j ; /* index to new lists */
547
ANODE *p ; /* walks an old list */
548
ANODE *q ; /* trails p for deletion */
549
ANODE *tail ; /* builds new list from the back */
550
ANODE dummy0, dummy1 ;
551
for(i=0, j=old_hmask+1;i <= old_hmask; i++, j++)
552
{
553
q = &dummy0 ;
554
q->ilink = p = table[i].ilink ;
555
tail = &dummy1 ;
556
while (p) {
557
if ((p->ival&new_hmask) != i) { /* move it */
558
q->ilink = p->ilink ;
559
tail = tail->ilink = p ;
560
}
561
else q = p ;
562
p = q->ilink ;
563
}
564
table[i].ilink = dummy0.ilink ;
565
tail->ilink = (ANODE*) 0 ;
566
table[j].ilink = dummy1.ilink ;
567
}
568
569
}
570
571
A->hmask = new_hmask ;
572
A->limit = hmask_to_limit(new_hmask) ;
573
}
574
575
576
static unsigned ahash(sval)
577
STRING* sval ;
578
{
579
unsigned sum1 = sval->len ;
580
unsigned sum2 = sum1 ;
581
unsigned char *p , *q ;
582
if (sum1 <= 10) {
583
for(p=(unsigned char*)sval->str; *p ; p++) {
584
sum1 += sum1 + *p ;
585
sum2 += sum1 ;
586
}
587
}
588
else {
589
int cnt = 5 ;
590
p = (unsigned char*)sval->str ; /* p starts at the front */
591
q = (unsigned char*)sval->str + (sum1-1) ; /* q starts at the back */
592
while( cnt ) {
593
cnt-- ;
594
sum1 += sum1 + *p ;
595
sum2 += sum1 ;
596
sum1 += sum1 + *q ;
597
sum2 += sum1 ;
598
p++ ; q-- ;
599
}
600
}
601
return sum2 ;
602
}
603
604
605
Loggerhead is a web-based interface for Breezy
Version: 2.0.1