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
|
/*
* Copyright (C) 2013 Mark Hills <mark@xwax.org>
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* version 2, as published by the Free Software Foundation.
*
* This program 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 version 2 for more details.
*
* You should have received a copy of the GNU General Public License
* version 2 along with this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301, USA.
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "lut.h"
/* The number of bits to form the hash, which governs the overall size
* of the hash lookup table, and hence the amount of chaining */
#define HASH_BITS 16
#define HASH(timecode) ((timecode) & ((1 << HASH_BITS) - 1))
#define NO_SLOT ((unsigned)-1)
/* Initialise an empty hash lookup table to store the given number
* of timecode -> position lookups */
int lut_init(struct lut *lut, int nslots)
{
int n, hashes;
size_t bytes;
hashes = 1 << HASH_BITS;
bytes = sizeof(struct slot) * nslots + sizeof(slot_no_t) * hashes;
fprintf(stderr, "Lookup table has %d hashes to %d slots"
" (%d slots per hash, %zuKb)\n",
hashes, nslots, nslots / hashes, bytes / 1024);
lut->slot = malloc(sizeof(struct slot) * nslots);
if (lut->slot == NULL) {
perror("malloc");
return -1;
}
lut->table = malloc(sizeof(slot_no_t) * hashes);
if (lut->table == NULL) {
perror("malloc");
return -1;
}
for (n = 0; n < hashes; n++)
lut->table[n] = NO_SLOT;
lut->avail = 0;
return 0;
}
void lut_clear(struct lut *lut)
{
free(lut->table);
free(lut->slot);
}
void lut_push(struct lut *lut, unsigned int timecode)
{
unsigned int hash;
slot_no_t slot_no;
struct slot *slot;
slot_no = lut->avail++; /* take the next available slot */
slot = &lut->slot[slot_no];
slot->timecode = timecode;
hash = HASH(timecode);
slot->next = lut->table[hash];
lut->table[hash] = slot_no;
}
unsigned int lut_lookup(struct lut *lut, unsigned int timecode)
{
unsigned int hash;
slot_no_t slot_no;
struct slot *slot;
hash = HASH(timecode);
slot_no = lut->table[hash];
while (slot_no != NO_SLOT) {
slot = &lut->slot[slot_no];
if (slot->timecode == timecode)
return slot_no;
slot_no = slot->next;
}
return (unsigned)-1;
}
|
