diff options
Diffstat (limited to 'src/H5Gnode.c')
| -rw-r--r-- | src/H5Gnode.c | 661 |
1 files changed, 661 insertions, 0 deletions
diff --git a/src/H5Gnode.c b/src/H5Gnode.c new file mode 100644 index 0000000..733e637 --- /dev/null +++ b/src/H5Gnode.c @@ -0,0 +1,661 @@ +/*------------------------------------------------------------------------- + * Copyright (C) 1997 National Center for Supercomputing Applications. + * All rights reserved. + * + *------------------------------------------------------------------------- + * + * Created: snode.c + * Jun 26 1997 + * Robb Matzke <matzke@llnl.gov> + * + * Purpose: Functions for handling symbol table nodes. A + * symbol table node is a small collection of symbol + * table entries. A B-tree usually points to the + * symbol table nodes for any given symbol table. + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +#include <assert.h> +#include <stdio.h> +#include <string.h> + +#include "hdf5.h" + +/* Packages needed by this file... */ +#include "H5ACprivate.h" /*cache */ +#include "H5Bprivate.h" /*B-link trees */ +#include "H5Gprivate.h" /*me */ +#include "H5Hprivate.h" /*heap */ +#include "H5MFprivate.h" /*file memory management */ +#include "H5MMprivate.h" /*core memory management */ + +/* PRIVATE PROTOTYPES */ +static void H5G_node_decode_key (hdf5_file_t *f, uint8 *raw, void *_key); +static void H5G_node_encode_key (hdf5_file_t *f, uint8 *raw, void *_key); +static size_t H5G_node_size (hdf5_file_t *f); +static off_t H5G_node_new (hdf5_file_t *f, void *_lt_key, void *_udata, + void *_rt_key); +static herr_t H5G_node_flush (hdf5_file_t *f, hbool_t destroy, off_t addr, + H5G_node_t *sym); +static H5G_node_t *H5G_node_load (hdf5_file_t *f, off_t addr, + const void *_data); +static intn H5G_node_cmp (hdf5_file_t *f, void *_lt_key, void *_udata, + void *_rt_key); +static herr_t H5G_node_found (hdf5_file_t *f, off_t addr, void *_lt_key, + void *_udata, void *_rt_key); +static off_t H5G_node_insert (hdf5_file_t *f, off_t addr, intn *anchor, + void *_lt_key, hbool_t *lt_key_changed, + void *_md_key, void *_udata, + void *_rt_key, hbool_t *rt_key_changed); +static herr_t H5G_node_list (hdf5_file_t *f, off_t addr, void *_udata); +static size_t H5G_node_sizeof_rkey (hdf5_file_t *f); + +/* H5G inherits cache-like properties from H5AC */ +static const H5AC_class_t H5AC_SNODE[1] = {{ + (void*(*)(hdf5_file_t*,off_t,const void*))H5G_node_load, + (herr_t(*)(hdf5_file_t*,hbool_t,off_t,void*))H5G_node_flush, +}}; + +/* H5G inherits B-tree like properties from H5B */ +static const H5B_class_t H5B_SNODE[1] = {{ + 0, /*id */ + 64, /*k */ + sizeof (H5G_node_key_t), /*sizeof_nkey */ + H5G_node_sizeof_rkey, /*get_sizeof_rkey */ + H5G_node_new, /*new */ + H5G_node_cmp, /*cmp */ + H5G_node_found, /*found */ + H5G_node_insert, /*insert */ + H5G_node_list, /*list */ + H5G_node_decode_key, /*decode */ + H5G_node_encode_key, /*encode */ +}}; + + +/*------------------------------------------------------------------------- + * Function: H5G_node_sizeof_rkey + * + * Purpose: Returns the size of a raw B-link tree key for the specified + * file. + * + * Return: Success: Size of the key. + * + * Failure: never fails + * + * Programmer: Robb Matzke + * robb@maya.nuance.com + * Jul 14 1997 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static size_t +H5G_node_sizeof_rkey (hdf5_file_t *f) +{ + return SIZEOF_OFFSET(f); +} + + +/*------------------------------------------------------------------------- + * Function: H5G_node_decode_key + * + * Purpose: Decodes a raw key into a native key. + * + * Return: void + * + * Programmer: Robb Matzke + * robb@maya.nuance.com + * Jul 8 1997 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static void +H5G_node_decode_key (hdf5_file_t *f, uint8 *raw, void *_key) +{ + H5G_node_key_t *key = (H5G_node_key_t *)_key; + + H5F_decode_offset (f, raw, key->offset); +} + + +/*------------------------------------------------------------------------- + * Function: H5G_node_encode_key + * + * Purpose: Encodes a native key into a raw key. + * + * Return: void + * + * Programmer: Robb Matzke + * robb@maya.nuance.com + * Jul 8 1997 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static void +H5G_node_encode_key (hdf5_file_t *f, uint8 *raw, void *_key) +{ + H5G_node_key_t *key = (H5G_node_key_t *)_key; + + H5F_encode_offset (f, raw, key->offset); +} + + +/*------------------------------------------------------------------------- + * Function: H5G_node_size + * + * Purpose: Returns the total size of a symbol table node. + * + * Return: Success: Total size of the node in bytes. + * + * Failure: Never fails. + * + * Programmer: Robb Matzke + * robb@maya.nuance.com + * Jun 23 1997 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static size_t +H5G_node_size (hdf5_file_t *f) +{ + return H5G_HDR_SIZE(f) + (2*H5G_NODE_K) * (2*SIZEOF_OFFSET(f)); +} + + +/*------------------------------------------------------------------------- + * Function: H5G_node_new + * + * Purpose: Creates a new empty symbol table. This function is called + * by the B-tree insert function for an empty tree. It is + * also called internally to split a symbol node with + * LT_KEY and RT_KEY null pointers. + * + * Return: Success: Address of symbol table node. + * + * Failure: 0 + * + * Programmer: Robb Matzke + * robb@maya.nuance.com + * Jun 23 1997 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static off_t +H5G_node_new (hdf5_file_t *f, void *_lt_key, void *_udata, void *_rt_key) +{ + H5G_node_key_t *lt_key = (H5G_node_key_t*)_lt_key; + H5G_node_key_t *rt_key = (H5G_node_key_t*)_rt_key; + H5G_node_t *sym = H5MM_xcalloc (1, sizeof(H5G_node_t)); + size_t size = H5G_node_size (f); + off_t addr = H5MF_alloc (f, size); + + sym->dirty = 1; + sym->entry = H5MM_xcalloc (2 * H5G_NODE_K, sizeof(H5G_entry_t)); + H5AC_set (f, H5AC_SNODE, addr, sym); + + /* + * The left and right symbols in an empty tree are both the + * empty string stored at offset zero by the symtab.c functions. This + * allows the comparison functions to work correctly without knowing + * that there are no symbols. + */ + if (lt_key) lt_key->offset = 0; + if (rt_key) rt_key->offset = 0; + return addr; +} + + +/*------------------------------------------------------------------------- + * Function: H5G_node_flush + * + * Purpose: Flush a symbol table node to disk. + * + * Return: Success: 0 + * + * Failure: -1 + * + * Programmer: Robb Matzke + * robb@maya.nuance.com + * Jun 23 1997 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static herr_t +H5G_node_flush (hdf5_file_t *f, hbool_t destroy, off_t addr, H5G_node_t *sym) +{ + uint8 *buf=NULL, *p=NULL; + size_t size; + + if (sym->dirty) { + size = H5G_node_size (f); + buf = p = H5MM_xmalloc (size); + + /* magic number */ + HDmemcpy (p, H5G_NODE_MAGIC, 4); + p += 4; + + /* version number */ + *p++ = H5G_NODE_VERS; + + /* reserved */ + *p++ = 0; + + /* number of symbols */ + UINT16ENCODE (p, sym->nsyms); + + /* entries */ + H5G_encode_vec (f, &p, sym->entry, sym->nsyms); + + + H5F_block_write (f, addr, p-buf, buf); + buf = H5MM_xfree (buf); + } + + if (destroy) { + sym->entry = H5MM_xfree (sym->entry); + H5MM_xfree (sym); + } + + return 0; +} + + +/*------------------------------------------------------------------------- + * Function: H5G_node_load + * + * Purpose: Loads a symbol table from the file. + * + * Return: Success: Ptr to the new table. + * + * Failure: NULL + * + * Programmer: Robb Matzke + * robb@maya.nuance.com + * Jun 23 1997 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static H5G_node_t * +H5G_node_load (hdf5_file_t *f, off_t addr, const void *_udata) +{ + H5G_node_t *sym = H5MM_xcalloc (1, sizeof(H5G_node_t)); + size_t size = H5G_node_size (f); + uint8 *buf = H5MM_xmalloc (size); + uint8 *p = buf; + + + sym->entry = H5MM_xcalloc (2*H5G_NODE_K, sizeof(H5G_entry_t)); + H5F_block_read (f, addr, size, buf); + + /* magic */ + if (HDmemcmp (p, H5G_NODE_MAGIC, 4)) goto error; + p += 4; + + /* version */ + if (H5G_NODE_VERS!=*p++) goto error; + + /* reserved */ + p++; + + /* number of symbols */ + UINT16DECODE (p, sym->nsyms); + + /* entries */ + H5G_decode_vec (f, &p, sym->entry, sym->nsyms); + + H5MM_xfree (buf); + return sym; + +error: + H5MM_xfree (buf); + H5MM_xfree (sym); + return NULL; +} + + +/*------------------------------------------------------------------------- + * Function: H5G_node_cmp + * + * Purpose: Compares two keys from a B-tree node (LEFT and RIGHT) + * against another key (not necessarily the same type) + * pointed to by UDATA. + * + * Return: Success: negative if the UDATA key is less than + * or equal to the LEFT key. + * + * positive if the UDATA key is greater + * than the RIGHT key. + * + * zero if the UDATA key falls between + * the LEFT key (exclusive) and the + * RIGHT key (inclusive). + * + * Failure: Never fails + * + * Programmer: Robb Matzke + * robb@maya.nuance.com + * Jun 23 1997 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static intn +H5G_node_cmp (hdf5_file_t *f, void *_lt_key, void *_udata, void *_rt_key) +{ + H5G_node_ud1_t *udata = (H5G_node_ud1_t *)_udata; + H5G_node_key_t *lt_key = (H5G_node_key_t *)_lt_key; + H5G_node_key_t *rt_key = (H5G_node_key_t *)_rt_key; + const char *s; + + /* left side */ + s = H5H_peek (f, udata->heap, lt_key->offset); + if (HDstrcmp (udata->name, s)<=0) return -1; + + /* right side */ + s = H5H_peek (f, udata->heap, rt_key->offset); + if (HDstrcmp (udata->name, s)>0) return 1; + + return 0; +} + + +/*------------------------------------------------------------------------- + * Function: H5G_node_found + * + * Purpose: The B-tree search engine has found the symbol table node + * which contains the requested symbol if the symbol exists. + * This function should examine that node for the symbol and + * return information about the symbol through the UDATA + * structure which contains the symbol name on function + * entry. + * + * Return: Success: 0 if found and data returned through the + * UDATA pointer. + * + * Failure: -1 if not found. + * + * Programmer: Robb Matzke + * robb@maya.nuance.com + * Jun 23 1997 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static herr_t +H5G_node_found (hdf5_file_t *f, off_t addr, void *_lt_key, void *_udata, + void *_rt_key) +{ + H5G_node_ud1_t *udata = (H5G_node_ud1_t *)_udata; + H5G_node_t *sn; + intn lt=0, idx=0, rt, cmp=1; + const char *s; + + sn = H5AC_find (f, H5AC_SNODE, addr, NULL); + if (!sn) return -1; + rt = sn->nsyms; + + /* + * Binary search. + */ + while (lt<rt && cmp) { + idx = (lt + rt) / 2; + sn = H5AC_find (f, H5AC_SNODE, addr, NULL); + s = H5H_peek (f, udata->heap, sn->entry[idx].name_off); + cmp = HDstrcmp (udata->name, s); + + if (cmp<0) { + rt = idx; + } else { + lt = idx+1; + } + } + if (cmp) return -1; + + udata->entry = sn->entry[idx]; + return 0; +} + + +/*------------------------------------------------------------------------- + * Function: H5G_node_insert + * + * Purpose: The B-tree insertion engine has found the symbol table node + * which should receive the new symbol/address pair. This + * function adds it to that node unless it already existed. + * + * If the node has no room for the symbol then the node is + * split into two nodes. The original node contains the + * low values and the new node contains the high values. + * The new symbol table entry is added to either node as + * appropriate. When a split occurs, this function will + * write the maximum key of the low node to the MID buffer + * and return the address of the new node. + * + * If the new key is larger than RIGHT then update RIGHT + * with the new key. + * + * Return: Success: Address of new node if the node was + * split. MID has been initialized with + * the high key of the left node, RIGHT + * has the high key of the right node. + * + * Zero if the node didn't split. RIGHT has the + * high key of the right node. + * + * Failure: -1 + * + * Programmer: Robb Matzke + * robb@maya.nuance.com + * Jun 24 1997 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static off_t +H5G_node_insert (hdf5_file_t *f, off_t addr, intn *anchor, + void *_lt_key, hbool_t *lt_key_changed, + void *_md_key, void *_udata, + void *_rt_key, hbool_t *rt_key_changed) +{ + H5G_node_key_t *md_key = (H5G_node_key_t *)_md_key; + H5G_node_key_t *rt_key = (H5G_node_key_t *)_rt_key; + H5G_node_ud1_t *udata = (H5G_node_ud1_t *)_udata; + + H5G_node_t *sn; + H5G_entry_t ent[2*H5G_NODE_K]; + off_t new_node=0, offset; + const char *s; + intn idx=-1, nsyms, cmp=1; + intn lt=0, rt; /*binary search cntrs */ + + /* + * Symbol tables are always split so the new symbol table node is + * to the right of the old one. + */ + *anchor = H5B_ANCHOR_LT; + *lt_key_changed = FALSE; + *rt_key_changed = FALSE; + + /* + * Load the symbol node and buffer the entries so we don't have to + * worry about the cached value disappearing. + */ + sn = H5AC_find (f, H5AC_SNODE, addr, NULL); + if (!sn) return -1; + HDmemcpy (ent, sn->entry, sn->nsyms * sizeof(H5G_entry_t)); + rt = nsyms = sn->nsyms; + sn = NULL; + + /* + * Where does the new symbol get inserted? We use a binary search. + */ + while (lt<rt) { + idx = (lt + rt) / 2; + s = H5H_peek (f, udata->heap, ent[idx].name_off); + if (0==(cmp=HDstrcmp (udata->name, s))) return -1; /*already present*/ + if (cmp<0) { + rt = idx; + } else { + lt = idx+1; + } + } + idx += cmp>0 ? 1 : 0; + + /* + * Add the new name to the heap. The caller will check if the + * heap address changed and update the symbol table object header + * with the new heap address. + */ + offset = H5H_insert (f, udata->heap, strlen(udata->name)+1, udata->name); + + if (nsyms>=2*H5G_NODE_K) { + /* + * The node is full. Split it into a left and right + * node and return the address of the new right node (the + * left node is at the same address as the original node). + */ + + /* The left node */ + sn = H5AC_find (f, H5AC_SNODE, addr, NULL); + HDmemset (sn->entry+H5G_NODE_K, 0, H5G_NODE_K*sizeof(H5G_entry_t)); + sn->nsyms = H5G_NODE_K; + sn->dirty += 1; + + if (idx<=H5G_NODE_K) { + memmove (sn->entry+idx+1, sn->entry+idx, + (H5G_NODE_K-idx) * sizeof(H5G_entry_t)); + sn->entry[idx] = udata->entry; + sn->entry[idx].name_off = offset; + sn->nsyms += 1; + } + + /* The middle key */ + md_key->offset = sn->entry[sn->nsyms-1].name_off; + + /* The right node */ + new_node = H5G_node_new (f, NULL, NULL, NULL); + sn = H5AC_find (f, H5AC_SNODE, new_node, NULL); + HDmemcpy (sn->entry, ent+H5G_NODE_K, + H5G_NODE_K*sizeof(H5G_entry_t)); + sn->nsyms = H5G_NODE_K; + sn->dirty += 1; + + if (idx>H5G_NODE_K) { + idx -= H5G_NODE_K; + HDmemmove (sn->entry+idx+1, sn->entry+idx, + (H5G_NODE_K-idx) * sizeof (H5G_entry_t)); + sn->entry[idx] = udata->entry; + sn->entry[idx].name_off = offset; + sn->nsyms += 1; + + if (idx+1==sn->nsyms) { + rt_key->offset = offset; + *rt_key_changed = TRUE; + } + } + + } else { + /* + * Add the new symbol to the node. + */ + sn = H5AC_find (f, H5AC_SNODE, addr, NULL); + sn->dirty += 1; + HDmemmove (sn->entry+idx+1, sn->entry+idx, + (sn->nsyms-idx) * sizeof (H5G_entry_t)); + sn->nsyms += 1; + sn->entry[idx] = udata->entry; + sn->entry[idx].name_off = offset; + + if (idx+1==sn->nsyms) { + rt_key->offset = offset; + *rt_key_changed = TRUE; + } + } + + return new_node; +} + + +/*------------------------------------------------------------------------- + * Function: H5G_node_list + * + * Purpose: This function gets called during a directory list operation. + * It should fill in data in the UDATA struct. + * + * Return: Success: 0 + * + * Failure: -1 + * + * Programmer: Robb Matzke + * robb@maya.nuance.com + * Jun 24 1997 + * + * Modifications: + * + *------------------------------------------------------------------------- + */ +static herr_t +H5G_node_list (hdf5_file_t *f, off_t addr, void *_udata) +{ + H5G_node_list_t *udata = (H5G_node_list_t *)_udata; + H5G_entry_t *ent; + intn i, nsyms; + const char *s; + H5G_node_t *sn; + + /* + * Read the symbol table and save the entry info. We save it + * in a separate buffer if names are requested because the name + * lookup may invalidate the symbol table. + */ + sn = H5AC_find (f, H5AC_SNODE, addr, NULL); + if (!sn) return -1; + nsyms = sn->nsyms; + if (udata->name) { + ent = H5MM_xmalloc (nsyms * sizeof(H5G_entry_t)); + HDmemcpy (ent, sn->entry, nsyms*sizeof(H5G_entry_t)); + sn = NULL; + } else { + ent = sn->entry; + } + + /* + * Gather the info. + */ + if (udata->name || udata->entry) { + for (i=0; i<nsyms && udata->nused<udata->nentries; i++) { + if (udata->name) { + s = H5H_peek (f, udata->heap, ent[i].name_off); + udata->name[udata->nused] = H5MM_xstrdup (s); + } + if (udata->entry) { + udata->entry[udata->nused] = ent[i]; + } + udata->nused += 1; + } + } else { + udata->nused += sn->nsyms; + } + + if (!sn) H5MM_xfree (ent); + return 0; +} + |