Renato wrote:
> The array is either completely full or it's last index is held in the value
> extract.
> eg if we had a BLOCKSIZE if 2 and we had currently in the list 8 elements
> this would use 4 nodes. Upon inserting a futher element a new node would
> have to be created also containing an array of data of size 2. If we
> inserted the new element in the first postion of the 1st node then all the
> array values would need to be suffle shifteed forward one space.
That largely defeats the object of using a linked list of blocks. The
sensible approach would be to allow for partially-filled blocks. If
you need to insert an object in the middle of a full block, you split
the block into two. That way, you only ever need to move at most
BLOCKSIZE values.
The mechanism which you describe would actually be slower than using a
single array. If you have to insert an element at the beginning of the
first block, you have to copy the rest of the block to the next block,
the contents of that block (except for the first element) to the
following block, and so on.
> Then newly
> created node would then have extract as = 0 this being the forst index
> postion of the last node in the list, all other nodes would be completely
> full so there index values is already know to be BLOCKSIZE - 1.
Anyhow, the attached program should be about right (although I haven't
tested it).
--
Glynn Clements <[EMAIL PROTECTED]>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define BLOCKSIZE 100
typedef struct listNode *listNodePtr;
typedef struct data {
char *key;
char *value;
} Data;
typedef struct listNode {
Data ListNodeData[BLOCKSIZE];
listNodePtr next;
} ListNode;
typedef struct list {
listNodePtr head;
unsigned listSize;
unsigned extract;
} List;
static void shift_forward(
struct list *list, struct listNode *p,
char *key, char *value
);
static struct listNode *new_block(char *key, char *value)
{
struct listNode *p;
p = malloc(sizeof(struct listNode));
p->next = NULL;
p->ListNodeData[0].key = key;
p->ListNodeData[0].value = value;
return p;
}
static int find_index(struct listNode *p, int last, char *key)
{
int i;
for (i = 0; i <= last; i++)
if (strcmp(key, p->ListNodeData[i].key) < 0)
return i;
fprintf(stderr, "find_index failed\n");
exit(1);
return -1;
}
static void shift_forward_block(
struct listNode *p, int first, int last,
char *key, char *value
)
{
struct data *d = &p->ListNodeData[first];
int count = last - first;
memmove(d, d + 1, count * sizeof(struct data));
d->key = key;
d->value = value;
}
static void shift_forward_last(
struct list *list, struct listNode *p,
char *key, char *value
)
{
if (list->extract == BLOCKSIZE - 1)
{
struct data *d = &p->ListNodeData[BLOCKSIZE - 1];
p->next = new_block(d->key, d->value);
}
shift_forward_block(p, 0, list->extract, key, value);
list->extract++;
list->extract %= BLOCKSIZE;
}
static void shift_forward_not_last(
struct list *list, struct listNode *p,
char *key, char *value
)
{
struct data *d = &p->ListNodeData[BLOCKSIZE - 1];
shift_forward(list, p->next, d->key, d->value);
shift_forward_block(p, 0, BLOCKSIZE - 1, key, value);
}
static void shift_forward(
struct list *list, struct listNode *p,
char *key, char *value
)
{
if (p->next)
shift_forward_not_last(list, p, key, value);
else
shift_forward_last(list, p, key, value);
}
static void insert_into_node_not_last(
struct list *list, struct listNode *p,
char *key, char *value
)
{
struct data *d = &p->ListNodeData[BLOCKSIZE - 1];
int i = find_index(p, BLOCKSIZE - 1, key);
shift_forward(list, p->next, d->key, d->value);
shift_forward_block(p, i, BLOCKSIZE - 1, key, value);
}
static void insert_into_node_last(
struct list *list, struct listNode *p,
char *key, char *value
)
{
int i = find_index(p, list->extract, key);
if (list->extract == BLOCKSIZE - 1)
{
struct data *d = &p->ListNodeData[BLOCKSIZE - 1];
p->next = new_block(d->key, d->value);
}
shift_forward_block(p, i, list->extract, key, value);
list->extract++;
list->extract %= BLOCKSIZE;
}
static void insert_into_node(
struct list *list, struct listNode *p,
char *key, char *value
)
{
if (p->next)
insert_into_node_not_last(list, p, key, value);
else
insert_into_node_last(list, p, key, value);
}
void insert_into_list(struct list *list, char *key, char *value)
{
struct listNode *p;
struct listNode *previous = NULL;
for (p = list->head; p; p = p->next)
{
int index = p->next ? BLOCKSIZE - 1 : list->extract;
struct data *d = &p->ListNodeData[index];
if (strcmp(key, d->key) < 0)
{
insert_into_node(list, p, key, value);
return;
}
previous = p;
}
p = new_block(key, value);
if (previous)
previous->next = p;
else
list->head = p;
list->extract = 0;
}
