1 /* Copyright 1998,2001 Mark Pulford
2 * This file is subject to the terms and conditions of the GNU General Public
3 * License. Read the file COPYING found in this archive for details, or
4 * visit http://www.gnu.org/copyleft/gpl.html
5 */
6
7 #include <config.h>
8
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <pwd.h>
12 #include <sys/types.h>
13 #include <sys/stat.h>
14 #include <sys/file.h>
15 #include <unistd.h>
16 #include <string.h>
17 #include <fcntl.h>
18 #include <errno.h>
19 #include <time.h>
20
21 #include "scores.h"
22 #include "iface.h"
23 #include "dict.h"
24 #include "list.h"
25
26 struct assoc {
27 char *str;
28 int num;
29 };
30
31 static int score_open();
32 static int get_username(char *name, int size);
33 static int fill_entry(struct hiscore *hs, const struct score *scr);
34 static int scr_compare(const void *a, const void *b);
35 static int lockfd(int fd, int type);
36 static int worst_score(struct hiscore *hs, int entries);
37 static struct assoc *assoc_new(const char *str);
38 static struct assoc *assoc_find(struct list **l, const char *str);
39 static struct assoc *assoc_get(struct list **l, const char *str);
40 static void assoc_free(struct list **l);
41
42 /* return is same as open(2)
43 * gives file descriptor to score file open for RW */
score_open()44 static int score_open()
45 {
46 int fd, u;
47
48 u = umask(0);
49 fd = open(SCOREFILE, O_CREAT|O_EXCL|O_RDWR, SCOREPERM);
50 umask(u);
51 if(fd<0 && EEXIST==errno) /* File already exists */
52 fd = open(SCOREFILE, O_RDWR);
53
54 return fd;
55 }
56
57 /* Fill buffer name (size bytes long) with user name
58 * Ensures name is NULL terminated */
get_username(char * name,int size)59 static int get_username(char *name, int size)
60 {
61 struct passwd *p;
62
63 p = getpwuid(getuid());
64 if(!p)
65 return 0;
66
67 strncpy(name, p->pw_name, size);
68 name[size-1] = 0;
69
70 return 1;
71 }
72
73 /* -1 = a is higher in the list than b
74 * 0 = a & b are equal
75 * 1 = a is lower in the list than b */
scr_compare(const void * a,const void * b)76 static int scr_compare(const void *a, const void *b)
77 {
78 const struct hiscore *s1 = (const struct hiscore*) a;
79 const struct hiscore *s2 = (const struct hiscore*) b;
80
81 if(s1->total < s2->total)
82 return 1;
83 if(s1->total > s2->total)
84 return -1;
85 if(s1->words < s2->words) /* equal total. low words better */
86 return -1;
87 if(s1->words > s2->words)
88 return 1;
89 if(s1->blocks < s2->blocks) /* equal words?. low blocks better */
90 return -1;
91 if(s1->blocks > s2->blocks)
92 return 1;
93 if(s1->date < s2->date) /* equal blocks??. older games better */
94 return -1;
95 if(s1->date > s2->date)
96 return 1;
97
98 return 0;
99 }
100
101 /* Returns: 1 success
102 * 0 unable to find username */
fill_entry(struct hiscore * hs,const struct score * scr)103 static int fill_entry(struct hiscore *hs, const struct score *scr)
104 {
105 if(!get_username(hs->name, HI_NAME_LEN))
106 return 0;
107 hs->total = scr->total;
108 hs->words = scr->words;
109 hs->blocks = scr->blocks;
110 hs->date = time(NULL);
111 strncpy(hs->dict, dict_get(), HI_DICT_LEN-1);
112 hs->dict[HI_DICT_LEN-1] = 0;
113
114 return 1;
115 }
116
117 /* Load (Merge/Save if scr!=NULL) & return high scores */
118 /* Returns NULL error updating hi score table
119 * otherwise pointer to struct hiscore array.
120 * (last entry has null length name */
121 /* scr may be NULL */
score_update(const struct score * scr,time_t * scr_time,const char ** err)122 struct hiscore *score_update(const struct score *scr, time_t *scr_time, const char **err)
123 {
124 static char errbuf[81];
125 struct hiscore *hs;
126 int entries;
127 int size;
128 int fd;
129
130 *err = NULL;
131
132 fd = score_open();
133 if(fd < 0) {
134 snprintf(errbuf, 81, _("High score open: %s"), strerror(errno));
135 *err = errbuf;
136 return NULL;
137 }
138
139 /* add 1 entry for terminator */
140 hs = malloc(sizeof(*hs)*(SCORE_ENTRIES+1));
141 if(!hs)
142 abort();
143
144 memset(hs, 0, sizeof(*hs)*(SCORE_ENTRIES+1));
145
146 if(!lockfd(fd, F_WRLCK)) {
147 close(fd);
148 snprintf(errbuf, 81, _("High score locking: %s"), strerror(errno));
149 *err = errbuf;
150 free(hs);
151 return NULL;
152 }
153
154 size = read(fd, hs, sizeof(*hs)*SCORE_ENTRIES);
155 if(size < 0) {
156 snprintf(errbuf, 81, _("High score read: %s"), strerror(errno));
157 *err = errbuf;
158 free(hs);
159 close(fd);
160 return NULL;
161 }
162 entries = size / sizeof(*hs);
163 /* entries <= SCORE_ENTRIES since read will never return more bytes */
164
165 /* Put latest score at the end of the array */
166 if(scr) {
167 if(!fill_entry(&hs[entries], scr)) {
168 snprintf(errbuf, 81, _("Unable to get username"));
169 *err = errbuf;
170 close(fd);
171 free(hs);
172 return NULL;
173 }
174 if(scr_time)
175 *scr_time = hs[entries].date;
176 entries++; /* Included latest score */
177 }
178
179 /* Sort the high scores */
180 qsort(hs, entries, sizeof(*hs), scr_compare);
181
182 /* Note: If SCORE_ENTRIES-entries > 1 then chances are the
183 * most worthy score for eviction would have been chopped off
184 * anyway, along with a few scores which don't deserve to go.
185 * This should never happen unless lexter is recompiled
186 * with a smaller SCORE_ENTRIES. */
187 if(entries > SCORE_ENTRIES) {
188 int e;
189
190 e = worst_score(hs, entries);
191 memcpy(&hs[e], &hs[entries-1], sizeof(*hs));
192 entries = SCORE_ENTRIES;
193 /* Re sort after eviction shuffle */
194 qsort(hs, entries, sizeof(*hs), scr_compare);
195 }
196
197 /* Terminate array - removes lowest score if necessary */
198 hs[entries].name[0] = 0;
199
200 /* Seek to start of file and write. Errors aren't fatal
201 * return the high score table either way */
202 if(scr) {
203 if(0 == lseek(fd, 0, SEEK_SET)) {
204 if(write(fd, hs, entries*sizeof(*hs)) <0) {
205 snprintf(errbuf, 81, _("High score write: %s"), strerror(errno));
206 *err = errbuf;
207 }
208 } else {
209 snprintf(errbuf, 81, _("High score seek: %s"), strerror(errno));
210 *err = errbuf;
211 }
212 }
213 close(fd); /* close file & remove lock */
214
215 return hs;
216 }
217
lockfd(int fd,int type)218 static int lockfd(int fd, int type)
219 {
220 struct flock l;
221
222 l.l_type = type;
223 l.l_whence = SEEK_SET;
224 l.l_start = 0;
225 l.l_len = 0;
226 if(-1 == fcntl(fd, F_SETLKW, &l))
227 return 0;
228
229 return 1;
230 }
231
232 /* Quick n dirty assoc funcs - only use for small n */
assoc_new(const char * str)233 static struct assoc *assoc_new(const char *str)
234 {
235 struct assoc *p;
236
237 p = malloc(sizeof(*p));
238 if(!p)
239 abort();
240 p->str = strdup(str);
241 p->num = 0;
242
243 return p;
244 }
245
assoc_find(struct list ** l,const char * str)246 static struct assoc *assoc_find(struct list **l, const char *str)
247 {
248 struct list *p = *l;
249 struct assoc *a;
250
251 for(; p; p = p->next) {
252 a = (struct assoc *)p->data;
253 if(!strcmp(a->str, str))
254 return a;
255 }
256
257 return NULL;
258 }
259
260 /* Get the assoc entry for str, if it doesn't exist create it */
assoc_get(struct list ** l,const char * str)261 static struct assoc *assoc_get(struct list **l, const char *str)
262 {
263 struct assoc *a;
264
265 a = assoc_find(l, str);
266 if(!a) {
267 a = assoc_new(str);
268 *l = list_join(*l, list_element(a));
269 }
270
271 return a;
272 }
273
274 /* list_free helper function */
freeassoc(void * p)275 static void freeassoc(void *p)
276 {
277 struct assoc *a = (struct assoc *)p;
278 free(a->str);
279 free(a);
280 }
281
assoc_free(struct list ** l)282 static void assoc_free(struct list **l)
283 {
284 list_free(*l, freeassoc);
285 *l = NULL;
286 }
287
288 /* Return the index of the score most worthy of eviction.
289 * Evict the lowest score among the set of dictionaries with the most
290 * scores in the table. */
worst_score(struct hiscore * hs,int entries)291 static int worst_score(struct hiscore *hs, int entries)
292 {
293 struct list *dcount = NULL;
294 struct list *dmin = NULL;
295 struct list *p;
296 struct assoc *a;
297 int worst=0, max = 0;
298 int i;
299
300 for(i=0; i<entries; i++) {
301 a = assoc_get(&dcount, hs[i].dict);
302 a->num++;
303 a = assoc_get(&dmin, hs[i].dict);
304 a->num = i;
305 }
306
307 /* Find the maximum number of scores taken by a dictionary */
308 for(p=dcount; p; p=p->next) {
309 a = (struct assoc *)p->data;
310 if(a->num > max)
311 max = a->num;
312 }
313
314 /* Scan the set of greediest dictionaries for the lowest score.
315 * Note that the score with the highest index has the lowest score */
316 for(p=dcount; p; p=p->next) {
317 a = (struct assoc *)p->data;
318 if(a->num == max) {
319 a = assoc_find(&dmin, a->str);
320 if(a->num > worst)
321 worst = a->num;
322 }
323 }
324
325 assoc_free(&dcount);
326 assoc_free(&dmin);
327
328 return worst;
329 }
330