-
Notifications
You must be signed in to change notification settings - Fork 67
/
sqWin32HandleTable.h
131 lines (121 loc) · 4.64 KB
/
sqWin32HandleTable.h
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
/****************************************************************************
* PROJECT: Squeak port for Win32 (NT / Win95)
* FILE: sqWin32HandleTable.h
* CONTENT: Handle table
*
* AUTHOR: Andreas Raab (ar)
* ADDRESS:
* EMAIL: andreas.raab@gmx.de
*
* NOTES:
* 1) This is a simple handle table which can be used to verify whether
* a HANDLE is genuine (e.g., created by a plugin) or not. Useful to
* ensure that operations are only defined over handles that were
* originally created by a plugin and wasn't fabricated in some other way.
* Used (for example) by the file plugin to ensure integrity of file
* operations. See sqWin32FilePrims.c for an example.
* 2) The HandleTable is used by merely including it and then defining
* HandleTable *myTable;
* to use it. Again, see sqWin32FilePrims.c for an example.
*****************************************************************************/
#ifndef SQ_WIN32_HANDLE_TABLE
# define SQ_WIN32_HANDLE_TABLE
# if !NO_HANDLE_TABLES
typedef struct {
int count; /* number of elements in table */
int size; /* size of data array */
HANDLE *data; /* actual data */
} HandleTable;
/* Private. Scan table for the slot containing either NULL or the item */
static int FindHandleInTable(HandleTable *table, HANDLE item) {
int start, index;
HANDLE element, *data = table->data;
if(0 == table->size) return -1; /* so we don't explode below */
/* Compute initial index */
start = ((usqIntptr_t)item) % table->size;
/* search from (hash mod size) to end */
for(index = start; index < table->size; index++) {
element = data[index];
if(NULL == element || item == element) return index;
}
/* search from 0 to where we started */
for(index = 0; index < start; index++) {
element = data[index];
if(NULL == element || item == element) return index;
}
return -1; /* no match and no empty slot */
}
/* Private. Grow table to specified size. */
static void GrowTableToSize(HandleTable *table, int newSize) {
HANDLE *oldData = table->data;
int i, oldSize = table->size;
/* grow table size */
table->size = newSize;
/* allocate new table array */
table->data = (HANDLE*) calloc(newSize,sizeof(HANDLE));
/* copy elements from old to new */
for(i = 0; i < oldSize; i++) {
HANDLE element = oldData[i];
int index = FindHandleInTable(table, element);
table->data[index] = element;
}
/* free old data */
if(oldData) free(oldData);
}
/* Private. Fix a collision chain after removing an element */
static void FixCollisionsInTable(HandleTable *table, int index) {
HANDLE element, *data = table->data;
int newIndex, oldIndex = index;
int length = table->size;
while(1) {
if(++oldIndex == length) oldIndex = 0;
element = data[oldIndex];
if(NULL == element) break; /* we're done here */
newIndex = FindHandleInTable(table, element);
if(newIndex != oldIndex) {
HANDLE tmp = data[oldIndex];
data[oldIndex] = data[newIndex];
data[newIndex] = tmp;
}
}
}
/* Public. Add a handle to an existing table */
static void AddHandleToTable(HandleTable *table, HANDLE item) {
int index;
if(NULL == item) return; /* silently ignore NULL handles */
index = FindHandleInTable(table, item);
if(index == -1) { /* grow and retry */
GrowTableToSize(table, table->size > 1 ? table->size*2-1 : 5);
index = FindHandleInTable(table, item);
}
table->data[index] = item;
table->count++;
}
/* Public. Remove a handle from some table */
static void RemoveHandleFromTable(HandleTable *table, HANDLE item) {
int index;
if(NULL == item) return; /* silently ignore NULL handles */
index = FindHandleInTable(table, item);
if(index == -1) return; /* not in table */
if(NULL == table->data[index]) return; /* not in table */
table->data[index] = NULL; /* clear entry */
table->count--;
FixCollisionsInTable(table, index); /* fix collision chain */
/* Shrink table by half if 75% free but allow no less than 5 entries*/
if(table->size > 5 && table->count*4 < table->size ) {
GrowTableToSize(table, (table->size + 1) / 2);
}
}
/* Public. Test if a handle is in this table */
static int IsHandleInTable(HandleTable *table, HANDLE item) {
int index;
if(NULL == item) return 0; /* silently ignore NULL handles */
index = FindHandleInTable(table, item);
if(index == -1) return 0;
return table->data[index] == item;
}
# else /* !NO_HANDLE_TABLES */
# define AddHandleToTable(a,b) 0
# define IsHandleInTable(a,b) 1
# endif /* !NO_HANDLE_TABLES */
#endif /* SQ_WIN32_HANDLE_TABLE */