# 2.11BSD#431 - /usr/src/new/PORT/perl.1.0.0/hash.c

##### Functions

    hdelete           X
    hfetch            X
    hiterinit         X
    hiterkey          X
    hiternext         X
    hiterval          X
    hnew              X
    hshow             X
    hsplit            X
    hstore            X

       1: /* $Header: hash.c,v 1.0 87/12/18 13:05:17 root Exp $
       2:  *
       3:  * $Log:	hash.c,v $
       4:  * Revision 1.0  87/12/18  13:05:17  root
       5:  * Initial revision
       6:  *
       7:  */
       8:
       9: #include <stdio.h>
      10: #include "EXTERN.h"
      11: #include "handy.h"
      12: #include "util.h"
      13: #include "search.h"
      14: #include "perl.h"
      15:
      16: STR *
      17: hfetch(tb,key)
      18: register HASH *tb;
      19: char *key;
      20: {
      21:     register char *s;
      22:     register int i;
      23:     register int hash;
      24:     register HENT *entry;
      25:
      26:     if (!tb)
      27:     return Nullstr;
      28:     for (s=key,     i=0,    hash = 0;
      29:       /* while */ *s;
      30:      s++,       i++,    hash *= 5) {
      31:     hash += *s * coeff[i];
      32:     }
      33:     entry = tb->tbl_array[hash & tb->tbl_max];
      34:     for (; entry; entry = entry->hent_next) {
      35:     if (entry->hent_hash != hash)       /* strings can't be equal */
      36:         continue;
      37:     if (strNE(entry->hent_key,key)) /* is this it? */
      38:         continue;
      39:     return entry->hent_val;
      40:     }
      41:     return Nullstr;
      42: }
      43:
      44: bool
      45: hstore(tb,key,val)
      46: register HASH *tb;
      47: char *key;
      48: STR *val;
      49: {
      50:     register char *s;
      51:     register int i;
      52:     register int hash;
      53:     register HENT *entry;
      54:     register HENT **oentry;
      55:
      56:     if (!tb)
      57:     return FALSE;
      58:     for (s=key,     i=0,    hash = 0;
      59:       /* while */ *s;
      60:      s++,       i++,    hash *= 5) {
      61:     hash += *s * coeff[i];
      62:     }
      63:
      64:     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
      65:     i = 1;
      66:
      67:     for (entry = *oentry; entry; i=0, entry = entry->hent_next) {
      68:     if (entry->hent_hash != hash)       /* strings can't be equal */
      69:         continue;
      70:     if (strNE(entry->hent_key,key)) /* is this it? */
      71:         continue;
      72:     safefree((char*)entry->hent_val);
      73:     entry->hent_val = val;
      74:     return TRUE;
      75:     }
      76:     entry = (HENT*) safemalloc(sizeof(HENT));
      77:
      78:     entry->hent_key = savestr(key);
      79:     entry->hent_val = val;
      80:     entry->hent_hash = hash;
      81:     entry->hent_next = *oentry;
      82:     *oentry = entry;
      83:
      84:     if (i) {                /* initial entry? */
      85:     tb->tbl_fill++;
      86:     if ((tb->tbl_fill * 100 / (tb->tbl_max + 1)) > FILLPCT)
      87:         hsplit(tb);
      88:     }
      89:
      90:     return FALSE;
      91: }
      92:
      93: #ifdef NOTUSED
      94: bool
      95: hdelete(tb,key)
      96: register HASH *tb;
      97: char *key;
      98: {
      99:     register char *s;
     100:     register int i;
     101:     register int hash;
     102:     register HENT *entry;
     103:     register HENT **oentry;
     104:
     105:     if (!tb)
     106:     return FALSE;
     107:     for (s=key,     i=0,    hash = 0;
     108:       /* while */ *s;
     109:      s++,       i++,    hash *= 5) {
     110:     hash += *s * coeff[i];
     111:     }
     112:
     113:     oentry = &(tb->tbl_array[hash & tb->tbl_max]);
     114:     entry = *oentry;
     115:     i = 1;
     116:     for (; entry; i=0, oentry = &entry->hent_next, entry = entry->hent_next) {
     117:     if (entry->hent_hash != hash)       /* strings can't be equal */
     118:         continue;
     119:     if (strNE(entry->hent_key,key)) /* is this it? */
     120:         continue;
     121:     safefree((char*)entry->hent_val);
     122:     safefree(entry->hent_key);
     123:     *oentry = entry->hent_next;
     124:     safefree((char*)entry);
     125:     if (i)
     126:         tb->tbl_fill--;
     127:     return TRUE;
     128:     }
     129:     return FALSE;
     130: }
     131: #endif
     132:
     133: hsplit(tb)
     134: HASH *tb;
     135: {
     136:     int oldsize = tb->tbl_max + 1;
     137:     register int newsize = oldsize * 2;
     138:     register int i;
     139:     register HENT **a;
     140:     register HENT **b;
     141:     register HENT *entry;
     142:     register HENT **oentry;
     143:
     144:     a = (HENT**) saferealloc((char*)tb->tbl_array, newsize * sizeof(HENT*));
     145:     bzero((char*)&a[oldsize], oldsize * sizeof(HENT*)); /* zero second half */
     146:     tb->tbl_max = --newsize;
     147:     tb->tbl_array = a;
     148:
     149:     for (i=0; i<oldsize; i++,a++) {
     150:     if (!*a)                /* non-existent */
     151:         continue;
     152:     b = a+oldsize;
     153:     for (oentry = a, entry = *a; entry; entry = *oentry) {
     154:         if ((entry->hent_hash & newsize) != i) {
     155:         *oentry = entry->hent_next;
     156:         entry->hent_next = *b;
     157:         if (!*b)
     158:             tb->tbl_fill++;
     159:         *b = entry;
     160:         continue;
     161:         }
     162:         else
     163:         oentry = &entry->hent_next;
     164:     }
     165:     if (!*a)                /* everything moved */
     166:         tb->tbl_fill--;
     167:     }
     168: }
     169:
     170: HASH *
     171: hnew()
     172: {
     173:     register HASH *tb = (HASH*)safemalloc(sizeof(HASH));
     174:
     175:     tb->tbl_array = (HENT**) safemalloc(8 * sizeof(HENT*));
     176:     tb->tbl_fill = 0;
     177:     tb->tbl_max = 7;
     178:     hiterinit(tb);  /* so each() will start off right */
     179:     bzero((char*)tb->tbl_array, 8 * sizeof(HENT*));
     180:     return tb;
     181: }
     182:
     183: #ifdef NOTUSED
     184: hshow(tb)
     185: register HASH *tb;
     186: {
     187:     fprintf(stderr,"%5d %4d (%2d%%)\n",
     188:     tb->tbl_max+1,
     189:     tb->tbl_fill,
     190:     tb->tbl_fill * 100 / (tb->tbl_max+1));
     191: }
     192: #endif
     193:
     194: hiterinit(tb)
     195: register HASH *tb;
     196: {
     197:     tb->tbl_riter = -1;
     198:     tb->tbl_eiter = Null(HENT*);
     199:     return tb->tbl_fill;
     200: }
     201:
     202: HENT *
     203: hiternext(tb)
     204: register HASH *tb;
     205: {
     206:     register HENT *entry;
     207:
     208:     entry = tb->tbl_eiter;
     209:     do {
     210:     if (entry)
     211:         entry = entry->hent_next;
     212:     if (!entry) {
     213:         tb->tbl_riter++;
     214:         if (tb->tbl_riter > tb->tbl_max) {
     215:         tb->tbl_riter = -1;
     216:         break;
     217:         }
     218:         entry = tb->tbl_array[tb->tbl_riter];
     219:     }
     220:     } while (!entry);
     221:
     222:     tb->tbl_eiter = entry;
     223:     return entry;
     224: }
     225:
     226: char *
     227: hiterkey(entry)
     228: register HENT *entry;
     229: {
     230:     return entry->hent_key;
     231: }
     232:
     233: STR *
     234: hiterval(entry)
     235: register HENT *entry;
     236: {
     237:     return entry->hent_val;
     238: }

#### Defined functions

hdelete defined in line 94; used 1 times

- in /usr/src/new/PORT/perl.1.0.0/hash.h line 44

hfetch defined in line 16; used 4 times

- in /usr/src/new/PORT/perl.1.0.0/arg.c line 1678, 1692
- in /usr/src/new/PORT/perl.1.0.0/hash.h line 42
- in /usr/src/new/PORT/perl.1.0.0/stab.c line 277

hiterinit defined in line 194; used 3 times

- in line 178
- in /usr/src/new/PORT/perl.1.0.0/arg.c line 1010
- in /usr/src/new/PORT/perl.1.0.0/hash.h line 46

hiterkey defined in line 226; used 3 times

- in /usr/src/new/PORT/perl.1.0.0/arg.c line 1014, 1049
- in /usr/src/new/PORT/perl.1.0.0/hash.h line 48

hiternext defined in line 202; used 3 times

- in /usr/src/new/PORT/perl.1.0.0/arg.c line 1011, 1037
- in /usr/src/new/PORT/perl.1.0.0/hash.h line 47

hiterval defined in line 233; used 4 times

- in /usr/src/new/PORT/perl.1.0.0/arg.c line 1016, 1050, 1061
- in /usr/src/new/PORT/perl.1.0.0/hash.h line 49

hnew defined in line 170; used 2 times

- in /usr/src/new/PORT/perl.1.0.0/hash.h line 45
- in /usr/src/new/PORT/perl.1.0.0/stab.c line 318

hshow defined in line 184; never used
hsplit defined in line 133; used 1 times

- in line 87

hstore defined in line 44; used 3 times

- in /usr/src/new/PORT/perl.1.0.0/arg.c line 1695
- in /usr/src/new/PORT/perl.1.0.0/hash.h line 43
- in /usr/src/new/PORT/perl.1.0.0/perly.c line 170

Last modified: 1988-01-31 Generated: 2016-12-26 | Generated by src2html V0.67 page hit count: 927 |