1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
|
/*******************************************************************************
* *
* refString.c -- Nirvana editor string handling *
* *
* Copyright (C) 200 Scott Tringali *
* *
* This is free software; you can redistribute it and/or modify it under the *
* terms of the GNU General Public License as published by the Free Software *
* Foundation; either version 2 of the License, or (at your option) any later *
* version. In addition, you may distribute versions of this program linked to *
* Motif or Open Motif. See README for details. *
* *
* This software is distributed in the hope that it will be useful, but WITHOUT *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License *
* for more details. *
* *
* You should have received a copy of the GNU General Public License along with *
* software; if not, write to the Free Software Foundation, Inc., 59 Temple *
* Place, Suite 330, Boston, MA 02111-1307 USA *
* *
* Nirvana Text Editor *
* July, 1993 *
* *
* Written by Mark Edel *
* *
*******************************************************************************/
#include "refString.h"
#include "nedit_malloc.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#define RCS_SIZE 0x10000
struct rcs;
struct rcs_stats
{
int talloc, tshar, tgiveup, tbytes, tbyteshared;
};
struct rcs
{
struct rcs *next;
char *string;
int usage;
};
static struct rcs *Rcs[RCS_SIZE];
static struct rcs_stats RcsStats;
static unsigned const DJB2_SEED = 5381u;
/* djb2s hash for null-terminated string, seeded version */
static unsigned djb2s(char const* key, unsigned hash)
{
char c;
while (!!(c = *key++))
hash = ((hash << 5) + hash) ^ c;
return hash;
}
/* Compute hash address from a string key */
unsigned StringHashAddr(const char *key)
{
return djb2s(key, DJB2_SEED);
}
/* Compute hash address from a null-termintated list of strings */
unsigned StringsHashAddr(const char** keys)
{
unsigned hash = DJB2_SEED;
char const* key;
while (!!(key = *keys++))
hash = djb2s(key, hash);
return hash;
}
/*
** Take a normal string, create a shared string from it if need be,
** and return pointer to that shared string.
**
** Returned strings are const because they are shared. Do not modify them!
*/
const char *RefStringDup(const char *str)
{
unsigned bucket;
size_t len;
struct rcs *rp;
char *newstr;
if (str == NULL)
return NULL;
len = strlen(str);
RcsStats.talloc++;
/* Find it in hash */
bucket = StringHashAddr(str) % RCS_SIZE;
rp = Rcs[bucket];
for (; rp; rp = rp->next)
if (!strcmp(str, rp->string)) break;
newstr = NULL;
if (rp) /* It exists, return it and bump ref ct */
{
rp->usage++;
newstr = rp->string;
RcsStats.tshar++;
RcsStats.tbyteshared += len;
}
else /* Doesn't exist, conjure up a new one. */
{
rp = NEditNew(struct rcs);
rp->usage = 1;
rp->next = Rcs[bucket];
Rcs[bucket] = rp;
rp->string = (char*) NEditMalloc(len + 1);
memcpy(rp->string, str, len + 1);
newstr = rp->string;
}
RcsStats.tbytes += len;
return newstr;
}
/*
** Decrease the reference count on a shared string. When the reference
** count reaches zero, free the master string.
*/
void RefStringFree(const char *rcs_str)
{
int bucket;
struct rcs *rp;
struct rcs *prev = NULL;
if (rcs_str == NULL)
return;
bucket = StringHashAddr(rcs_str) % RCS_SIZE;
/* find it in hash */
for (rp = Rcs[bucket]; rp; rp = rp->next)
{
if (rcs_str == rp->string)
break;
prev = rp;
}
if (rp) /* It's a shared string, decrease ref count */
{
rp->usage--;
if (rp->usage < 0) /* D'OH! */
{
fprintf(stderr, "NEdit: internal error deallocating shared string.");
return;
}
if (rp->usage == 0) /* Last one- free the storage */
{
NEditFree(rp->string);
if (prev)
prev->next = rp->next;
else
Rcs[bucket] = rp->next;
NEditFree(rp);
}
}
else /* Doesn't appear to be a shared string */
{
fprintf(stderr, "NEdit: attempt to free a non-shared string.");
return;
}
}
|
