AnaGram interim repo (temporary): help2html/stringdict.c annotate

annotate help2html/stringdict.c @ 21:1c9dac05d040

Add lint-style FALLTHROUGH annotations to fallthrough cases. (in the parse engine and thus the output code) Document this, because the old output causes warnings with gcc10.

author	David A. Holland
date	Mon, 13 Jun 2022 00:04:38 -0400
parents	13d2b8934445
children

rev	line source
0 13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	1 #include <string.h>
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	2 #include <stdlib.h>
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	3 #include <stdint.h>
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	4
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	5 #include "must.h"
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	6 #include "array.h"
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	7 #include "stringdict.h"
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	8
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	9 struct stringdict_string {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	10 size_t sds_len;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	11 uint32_t sds_hash;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	12 unsigned sds_index; /* indexes sd_strings */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	13 };
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	14
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	15 struct stringdict_bucket {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	16 struct array sdb_strings; /* array of stringdict_string* */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	17 };
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	18
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	19 struct stringdict {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	20 struct array sd_hashbuckets; /* array of stringdict_bucket* */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	21 struct array sd_strings; /* array of char* */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	22 unsigned sd_totnum;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	23 };
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	24
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	25 ////////////////////////////////////////////////////////////
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	26
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	27 /*
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	28 * Fletcher's check-sum routines for AnaGram
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	29 *
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	30 * Freely adapted from routines published in Dr. Dobbs Journal
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	31 * May 1992, p. 64
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	32 *
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	33 * Revised as portable C in June 2006. Rewritten again in 2007 for no
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	34 * good reason.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	35 *
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	36 * The various copies of this in AG should probably be unified.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	37 */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	38 static uint32_t stringdict_hash(const char *s, size_t len) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	39 uint16_t x1, x2, a;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	40 size_t i;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	41
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	42 x1 = (uint16_t) (len >> 16);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	43 x2 = (uint16_t) (len);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	44 if (x1==0) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	45 x1++;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	46 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	47 if (x2==0) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	48 x2++;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	49 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	50
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	51 for (i=0; i<len; i+=2) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	52 if (i==len-1) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	53 a = (unsigned char)s[i];
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	54 /* don't run off the end of the array */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	55 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	56 else {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	57 a = (unsigned char)s[i] + ((uint16_t)(unsigned char)s[i+1] << 8);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	58 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	59 x1 += a;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	60 if (x1 < a) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	61 x1++;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	62 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	63 x2 += x1;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	64 if (x2 < x1) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	65 x2++;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	66 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	67 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	68
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	69 x1 ^= 0xffff;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	70 x2 ^= 0xffff;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	71 return ((uint32_t)x2)*65535U + x1;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	72 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	73
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	74 static void stringdict_setbuckets(struct stringdict *sd, unsigned newbucks) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	75 /*
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	76 * Because the number of buckets is always a power of 2, and we use the
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	77 * low bits of the hash code to choose the bucket, and we always grow by
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	78 * doubling (not, say, quadrupling) when we grow we know that any string
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	79 * either stays put or moves to bucket i+n0, where n0 is the old number of
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	80 * buckets. Further, we can check hash&n0 to see if the string must move.
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	81 *
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	82 * (n0 == oldbucks)
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	83 */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	84 unsigned oldbucks, i, j;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	85 unsigned numseen;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	86 struct stringdict_bucket sdb, sdb2;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	87 struct stringdict_string *sds;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	88
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	89 oldbucks = array_num(&sd->sd_hashbuckets);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	90 assert(newbucks == oldbucks*2 \|\| (oldbucks == 0 && sd->sd_totnum==0));
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	91 assert((newbucks & (newbucks-1)) == 0); // power of 2
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	92
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	93 // grow the array
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	94 array_setsize(&sd->sd_hashbuckets, newbucks);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	95
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	96 // allocate empty buckets in the new half of the array
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	97 for (i=oldbucks; i<newbucks; i++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	98 sdb = must_malloc(sizeof(*sdb));
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	99 array_init(&sdb->sdb_strings);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	100 array_set(&sd->sd_hashbuckets, i, sdb);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	101 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	102
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	103 // transfer any strings that need to be transferred
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	104 numseen = 0;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	105 for (i=0; i<oldbucks; i++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	106 sdb = array_get(&sd->sd_hashbuckets, i);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	107 sdb2 = array_get(&sd->sd_hashbuckets, i+oldbucks);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	108 for (j=0; j<array_num(&sdb->sdb_strings); j++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	109 sds = array_get(&sdb->sdb_strings, j);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	110 if (sds->sds_hash & oldbucks) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	111 array_set(&sdb->sdb_strings, j, NULL);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	112 array_add(&sdb2->sdb_strings, sds);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	113 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	114 numseen++;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	115 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	116 array_nonulls(&sdb->sdb_strings);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	117 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	118 assert(numseen == sd->sd_totnum);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	119 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	120
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	121 struct stringdict *stringdict_create(void) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	122 struct stringdict *sd;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	123 sd = must_malloc(sizeof(*sd));
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	124 array_init(&sd->sd_hashbuckets);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	125 array_init(&sd->sd_strings);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	126 sd->sd_totnum = 0;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	127 // number of buckets is always a power of 2
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	128 stringdict_setbuckets(sd, 16);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	129 return sd;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	130 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	131
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	132 void stringdict_destroy(struct stringdict *sd) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	133 struct stringdict_bucket *sdb;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	134 struct stringdict_string *sds;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	135 char *str;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	136 unsigned i, j;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	137
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	138 for (i=0; i<array_num(&sd->sd_hashbuckets); i++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	139 sdb = array_get(&sd->sd_hashbuckets, i);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	140 for (j=0; j<array_num(&sdb->sdb_strings); j++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	141 sds = array_get(&sdb->sdb_strings, j);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	142 free(sds);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	143 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	144 array_cleanup(&sdb->sdb_strings);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	145 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	146 array_cleanup(&sd->sd_hashbuckets);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	147
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	148 for (i=0; i<array_num(&sd->sd_strings); i++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	149 str = array_get(&sd->sd_strings, i);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	150 free(str);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	151 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	152 array_cleanup(&sd->sd_strings);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	153
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	154 free(sd);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	155 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	156
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	157 void stringdict_reset(struct stringdict *sd) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	158 struct stringdict_bucket *sdb;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	159 struct stringdict_string *sds;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	160 char *str;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	161 unsigned i, j;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	162
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	163 for (i=0; i<array_num(&sd->sd_hashbuckets); i++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	164 sdb = array_get(&sd->sd_hashbuckets, i);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	165 for (j=0; j<array_num(&sdb->sdb_strings); j++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	166 sds = array_get(&sdb->sdb_strings, j);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	167 free(sds);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	168 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	169 array_setsize(&sdb->sdb_strings, 0);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	170 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	171 /* could reset the bucket count here, but it seems better not to */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	172
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	173 for (i=0; i<array_num(&sd->sd_strings); i++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	174 str = array_get(&sd->sd_strings, i);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	175 free(str);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	176 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	177 array_setsize(&sd->sd_strings, 0);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	178 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	179
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	180 unsigned stringdict_internlen(struct stringdict *sd,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	181 const char *s, size_t len) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	182 uint32_t hash;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	183 unsigned j;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	184 struct stringdict_bucket *sdb;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	185 struct stringdict_string *sds;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	186 char *str;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	187
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	188 hash = stringdict_hash(s, len);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	189 // number of buckets is always a power of 2
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	190 sdb = array_get(&sd->sd_hashbuckets,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	191 hash & (array_num(&sd->sd_hashbuckets) - 1));
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	192 for (j=0; j<array_num(&sdb->sdb_strings); j++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	193 sds = array_get(&sdb->sdb_strings, j);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	194 if (len == sds->sds_len && hash == sds->sds_hash) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	195 str = array_get(&sd->sd_strings, sds->sds_index);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	196 if (!memcmp(s, str, len)) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	197 /* found it */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	198 return sds->sds_index;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	199 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	200 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	201 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	202
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	203 str = must_malloc(len+1);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	204 memcpy(str, s, len);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	205 str[len] = 0;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	206
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	207 sds = must_malloc(sizeof(*sds));
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	208 sds->sds_hash = hash;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	209 sds->sds_len = len;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	210 sds->sds_index = array_add(&sd->sd_strings, str);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	211
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	212 array_add(&sdb->sdb_strings, sds);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	213
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	214 sd->sd_totnum++;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	215 if (sd->sd_totnum / array_num(&sd->sd_hashbuckets) > 12) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	216 stringdict_setbuckets(sd, array_num(&sd->sd_hashbuckets) * 2);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	217 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	218
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	219 return sds->sds_index;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	220 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	221
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	222 unsigned stringdict_intern(struct stringdict sd, const char s) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	223 return stringdict_internlen(sd, s, strlen(s));
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	224 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	225
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	226 unsigned stringdict_count(const struct stringdict *sd) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	227 return sd->sd_totnum;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	228 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	229
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	230 const char stringdict_getbynum(const struct stringdict sd, unsigned index) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	231 return array_get(&sd->sd_strings, index);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	232 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	233
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	234 static struct stringdict_string *
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	235 stringdict_find(const struct stringdict sd, const char key, size_t keylen) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	236 uint32_t hash;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	237 unsigned j;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	238 struct stringdict_bucket *sdb;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	239 struct stringdict_string *sds;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	240 char *str;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	241
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	242 hash = stringdict_hash(key, keylen);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	243 // number of buckets is always a power of 2
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	244 sdb = array_get(&sd->sd_hashbuckets,
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	245 hash & (array_num(&sd->sd_hashbuckets) - 1));
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	246 for (j=0; j<array_num(&sdb->sdb_strings); j++) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	247 sds = array_get(&sdb->sdb_strings, j);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	248 if (keylen == sds->sds_len && hash == sds->sds_hash) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	249 str = array_get(&sd->sd_strings, sds->sds_index);
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	250 if (!memcmp(key, str, keylen)) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	251 /* found it */
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	252 return sds;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	253 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	254 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	255 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	256
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	257 return NULL;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	258 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	259
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	260
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	261 unsigned stringdict_findbyname(const struct stringdict sd, const char str) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	262 struct stringdict_string *sds;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	263 sds = stringdict_find(sd, str, strlen(str));
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	264 return sds ? sds->sds_index : (unsigned)-1;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	265 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	266
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	267 int stringdict_exists(const struct stringdict sd, const char str) {
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	268 struct stringdict_string *sds;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	269 sds = stringdict_find(sd, str, strlen(str));
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	270 return sds != NULL;
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	271 }
13d2b8934445 Import AnaGram (near-)release tree into Mercurial. David A. Holland parents: diff changeset	272

Mercurial > ~dholland > hg > ag > index.cgi

annotate help2html/stringdict.c @ 21:1c9dac05d040