3 copyright 1991-96, Michael D. Brennan
5 This is a source file for mawk, an implementation of
6 the AWK programming language.
8 Mawk is distributed without warranty under the terms of
9 the GNU General Public License, version 2, 1991.
13 This file was generated with the command
15 notangle -R'"array.c"' array.w > array.c
17 Notangle is part of Norman Ramsey's noweb literate programming package
18 available from CTAN(ftp.shsu.edu).
20 It's easiest to read or modify this file by working with array.w.
29 typedef struct {struct anode *slink, *ilink ;} DUAL_LINK ;
31 typedef struct anode {
41 #define NOT_AN_IVALUE (-Max_Int-1) /* usually 0x80000000 */
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)
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*)) ;
56 CELL* array_find(A, cp, create_flag)
62 if (A->size == 0 && !create_flag)
63 /* eliminating this trivial case early avoids unnecessary conversions later */
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) ;
77 else if (A->type == AY_NULL) make_empty_table(A, AY_INT) ;
78 ap = find_by_ival(A, ival, create_flag) ;
81 /* convert to string */
84 sprintf(buff, string(CONVFMT)->str, d) ;
85 sval = new_STRING(buff) ;
86 ap = find_by_sval(A,sval,create_flag) ;
93 ap = find_by_sval(A, &null_str, create_flag) ;
96 ap = find_by_sval(A, string(cp), create_flag) ;
99 return ap ? &ap->cell : (CELL *) 0 ;
102 void array_delete(A, cp)
107 if (A->size == 0) return ;
111 double d = cp->dval ;
112 Int ival = d_to_I(d) ;
113 if ((double)ival == d) {
114 if (A->type == AY_SPLIT)
116 if (ival >=1 && ival <= A->size) convert_split_array_to_table(A) ;
117 else return ; /* ival not in range */
119 ap = find_by_ival(A, ival, NO_CREATE) ;
120 if (ap) { /* remove from the front of the ilist */
121 DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
122 table[ap->ival & A->hmask].ilink = ap->ilink ;
125 int index = ap->hval & A->hmask ;
126 p = table[index].slink ;
127 while(p != ap) { q = p ; p = q->slink ; }
128 if (q) q->slink = p->slink ;
129 else table[index].slink = p->slink ;
130 free_STRING(ap->sval) ;
133 cell_destroy(&ap->cell) ;
135 if (--A->size == 0) array_clear(A) ;
142 else { /* get the string value */
145 sprintf(buff, string(CONVFMT)->str, d) ;
146 sval = new_STRING(buff) ;
147 ap = find_by_sval(A, sval, NO_CREATE) ;
153 ap = find_by_sval(A, &null_str, NO_CREATE) ;
156 ap = find_by_sval(A, string(cp), NO_CREATE) ;
159 if (ap) { /* remove from the front of the slist */
160 DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
161 table[ap->hval&A->hmask].slink = ap->slink ;
162 if (ap->ival != NOT_AN_IVALUE) {
164 int index = ap->ival & A->hmask ;
165 p = table[index].ilink ;
166 while(p != ap) { q = p ; p = q->ilink ; }
167 if (q) q->ilink = p->ilink ;
168 else table[index].ilink = p->ilink ;
171 free_STRING(ap->sval) ;
172 cell_destroy(&ap->cell) ;
174 if (--A->size == 0) array_clear(A) ;
180 void array_load(A, cnt)
184 CELL *cells ; /* storage for A[1..cnt] */
185 int i ; /* index into cells[] */
186 if (A->type != AY_SPLIT || A->limit < cnt) {
188 A->limit = (cnt&~3)+4 ;
189 A->ptr = zmalloc(A->limit*sizeof(CELL)) ;
193 for(i=0;i < A->size; i++) cell_destroy((CELL*)A->ptr+i) ;
195 cells = (CELL*) A->ptr ;
197 if (cnt > MAX_SPLIT) {
198 SPLIT_OV *p = split_ov_list ;
200 split_ov_list = (SPLIT_OV*) 0 ;
203 cells[i].type = C_MBSTRN ;
204 cells[i].ptr = (PTR) p->sval ;
205 q = p ; p = q->link ; ZFREE(q) ;
211 for(i=0;i < cnt; i++) {
212 cells[i].type = C_MBSTRN ;
213 cells[i].ptr = split_buff[i] ;
222 if (A->type == AY_SPLIT) {
223 for(i=0;i < A->size; i++) cell_destroy((CELL*)A->ptr+i) ;
224 zfree(A->ptr, A->limit * sizeof(CELL)) ;
226 else if (A->type & AY_STR) {
227 DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
228 for(i=0;i <= A->hmask; i++) {
231 q = p ; p = q->slink ;
232 free_STRING(q->sval) ;
233 cell_destroy(&q->cell) ;
237 zfree(A->ptr, (A->hmask+1)*sizeof(DUAL_LINK)) ;
239 else if (A->type & AY_INT) {
240 DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
241 for(i=0;i <= A->hmask; i++) {
244 q = p ; p = q->ilink ;
245 cell_destroy(&q->cell) ;
249 zfree(A->ptr, (A->hmask+1)*sizeof(DUAL_LINK)) ;
251 memset(A, 0, sizeof(*A)) ;
256 STRING** array_loop_vector(A, sizep)
263 if (!(A->type & AY_STR)) add_string_associations(A) ;
264 ret = (STRING**) zmalloc(A->size*sizeof(STRING*)) ;
266 int r = 0 ; /* indexes ret */
267 DUAL_LINK* table = (DUAL_LINK*) A->ptr ;
268 int i ; /* indexes table */
269 ANODE *p ; /* walks slists */
270 for(i=0;i <= A->hmask; i++) {
271 for(p = table[i].slink; p ; p = p->slink) {
280 else return (STRING**) 0 ;
283 CELL *array_cat(sp, cnt)
287 CELL *p ; /* walks the eval stack */
288 CELL subsep ; /* local copy of SUBSEP */
289 unsigned subsep_len ; /* string length of subsep_str */
292 unsigned total_len ; /* length of cat'ed expression */
293 CELL *top ; /* value of sp at entry */
294 char *target ; /* build cat'ed char* here */
295 STRING *sval ; /* build cat'ed STRING here */
296 cellcpy(&subsep, SUBSEP) ;
297 if ( subsep.type < C_STRING ) cast1_to_s(&subsep) ;
298 subsep_len = string(&subsep)->len ;
299 subsep_str = string(&subsep)->str ;
301 top = sp ; sp -= (cnt-1) ;
303 total_len = (cnt-1)*subsep_len ;
304 for(p = sp ; p <= top ; p++) {
305 if ( p->type < C_STRING ) cast1_to_s(p) ;
306 total_len += string(p)->len ;
309 sval = new_STRING0(total_len) ;
311 for(p = sp ; p < top ; p++) {
312 memcpy(target, string(p)->str, string(p)->len) ;
313 target += string(p)->len ;
314 memcpy(target, subsep_str, subsep_len) ;
315 target += subsep_len ;
318 memcpy(target, string(p)->str, string(p)->len) ;
320 for(p = sp; p <= top ; p++) free_STRING(string(p)) ;
321 free_STRING(string(&subsep)) ;
322 /* set contents of sp , sp->type > C_STRING is possible so reset */
323 sp->type = C_STRING ;
324 sp->ptr = (PTR) sval ;
329 static ANODE* find_by_ival(A, ival, create_flag)
334 DUAL_LINK *table = (DUAL_LINK*) A->ptr ;
335 unsigned index = ival & A->hmask ;
336 ANODE *p = table[index].ilink ; /* walks ilist */
337 ANODE *q = (ANODE*) 0 ; /* trails p */
341 if (A->type & AY_STR) {
342 /* need to search by string */
345 sprintf(buff, INT_FMT, ival) ;
346 sval = new_STRING(buff) ;
347 p = find_by_sval(A, sval, create_flag) ;
349 if (!p) return (ANODE*) 0 ;
351 else if (create_flag) {
353 p->sval = (STRING*) 0 ;
354 p->cell.type = C_NOINIT ;
355 if (++A->size > A->limit) {
356 double_the_hash_table(A) ; /* changes table, may change index */
357 table = (DUAL_LINK*) A->ptr ;
358 index = A->hmask & ival ;
361 else return (ANODE*) 0 ;
367 else if (p->ival == ival) {
368 /* found it, now move to the front */
369 if (!q) /* already at the front */
371 /* delete for insertion at the front */
372 q->ilink = p->ilink ;
375 q = p ; p = q->ilink ;
377 /* insert at the front */
378 p->ilink = table[index].ilink ;
379 table[index].ilink = p ;
383 static ANODE* find_by_sval(A, sval, create_flag)
388 unsigned hval = ahash(sval) ;
389 char *str = sval->str ;
392 ANODE *p ; /* walks list */
393 ANODE *q = (ANODE*) 0 ; /* trails p */
394 if (! (A->type & AY_STR)) add_string_associations(A) ;
395 table = (DUAL_LINK*) A->ptr ;
396 index = hval & A->hmask ;
397 p = table[index].slink ;
405 p->ival = NOT_AN_IVALUE ;
407 p->cell.type = C_NOINIT ;
408 if (++A->size > A->limit) {
409 double_the_hash_table(A) ; /* changes table, may change index */
410 table = (DUAL_LINK*) A->ptr ;
411 index = hval & A->hmask ;
417 else return (ANODE*) 0 ;
419 else if (p->hval == hval && strcmp(p->sval->str,str) == 0 ) {
421 if (!q) /* already at the front */
423 else { /* delete for move to the front */
424 q->slink = p->slink ;
428 q = p ; p = q->slink ;
430 p->slink = table[index].slink ;
431 table[index].slink = p ;
435 static void add_string_associations(A)
438 if (A->type == AY_NULL) make_empty_table(A, AY_STR) ;
441 int i ; /* walks table */
442 ANODE *p ; /* walks ilist */
444 if (A->type == AY_SPLIT) convert_split_array_to_table(A) ;
445 table = (DUAL_LINK*) A->ptr ;
446 for(i=0;i <= A->hmask; i++) {
449 sprintf(buff, INT_FMT, p->ival) ;
450 p->sval = new_STRING(buff) ;
451 p->hval = ahash(p->sval) ;
452 p->slink = table[A->hmask&p->hval].slink ;
453 table[A->hmask&p->hval].slink = p ;
461 static void make_empty_table(A, type)
463 int type ; /* AY_INT or AY_STR */
465 size_t sz = (STARTING_HMASK+1)*sizeof(DUAL_LINK) ;
467 A->hmask = STARTING_HMASK ;
468 A->limit = hmask_to_limit(STARTING_HMASK) ;
469 A->ptr = memset(zmalloc(sz), 0, sz) ;
472 static void convert_split_array_to_table(A)
475 CELL *cells = (CELL*) A->ptr ;
476 int i ; /* walks cells */
478 int j ; /* walks table */
479 unsigned entry_limit = A->limit ;
480 A->hmask = STARTING_HMASK ;
481 A->limit = hmask_to_limit(STARTING_HMASK) ;
482 while(A->size > A->limit) {
483 A->hmask = (A->hmask<<1) + 1 ; /* double the size */
484 A->limit = hmask_to_limit(A->hmask) ;
487 size_t sz = (A->hmask+1)*sizeof(DUAL_LINK) ;
488 A->ptr = memset(zmalloc(sz), 0, sz) ;
489 table = (DUAL_LINK*) A->ptr ;
493 /* insert each cells[i] in the new hash table on an ilist */
494 for(i=0, j=1 ;i < A->size; i++) {
495 ANODE *p = ZMALLOC(ANODE) ;
496 p->sval = (STRING*) 0 ;
499 p->ilink = table[j].ilink ;
501 j++ ; j &= A->hmask ;
504 zfree(cells, entry_limit*sizeof(CELL)) ;
507 static void double_the_hash_table(A)
510 unsigned old_hmask = A->hmask ;
511 unsigned new_hmask = (old_hmask<<1)+1 ;
513 A->ptr = zrealloc(A->ptr, (old_hmask+1)*sizeof(DUAL_LINK),
514 (new_hmask+1)*sizeof(DUAL_LINK)) ;
515 table = (DUAL_LINK*) A->ptr ;
516 /* zero out the new part which is the back half */
517 memset(&table[old_hmask+1], 0, (old_hmask+1)*sizeof(DUAL_LINK)) ;
519 if (A->type & AY_STR) {
520 int i ; /* index to old lists */
521 int j ; /* index to new lists */
522 ANODE *p ; /* walks an old list */
523 ANODE *q ; /* trails p for deletion */
524 ANODE *tail ; /* builds new list from the back */
525 ANODE dummy0, dummy1 ;
526 for(i=0, j=old_hmask+1;i <= old_hmask; i++, j++)
529 q->slink = p = table[i].slink ;
532 if ((p->hval&new_hmask) != i) { /* move it */
533 q->slink = p->slink ;
534 tail = tail->slink = p ;
539 table[i].slink = dummy0.slink ;
540 tail->slink = (ANODE*) 0 ;
541 table[j].slink = dummy1.slink ;
546 if (A->type & AY_INT) {
547 int i ; /* index to old lists */
548 int j ; /* index to new lists */
549 ANODE *p ; /* walks an old list */
550 ANODE *q ; /* trails p for deletion */
551 ANODE *tail ; /* builds new list from the back */
552 ANODE dummy0, dummy1 ;
553 for(i=0, j=old_hmask+1;i <= old_hmask; i++, j++)
556 q->ilink = p = table[i].ilink ;
559 if ((p->ival&new_hmask) != i) { /* move it */
560 q->ilink = p->ilink ;
561 tail = tail->ilink = p ;
566 table[i].ilink = dummy0.ilink ;
567 tail->ilink = (ANODE*) 0 ;
568 table[j].ilink = dummy1.ilink ;
573 A->hmask = new_hmask ;
574 A->limit = hmask_to_limit(new_hmask) ;
578 static unsigned ahash(sval)
581 unsigned sum1 = sval->len ;
582 unsigned sum2 = sum1 ;
583 unsigned char *p , *q ;
585 for(p=(unsigned char*)sval->str; *p ; p++) {
592 p = (unsigned char*)sval->str ; /* p starts at the front */
593 q = (unsigned char*)sval->str + (sum1-1) ; /* q starts at the back */