diff options
Diffstat (limited to 'cfile.c')
| -rw-r--r-- | cfile.c | 284 |
1 files changed, 222 insertions, 62 deletions
@@ -37,8 +37,7 @@ void cap_file_init(capture_file *cf) { /* Initialize the capture file struct */ - cf->plist_start = NULL; - cf->plist_end = NULL; + cf->ptree_root = NULL; cf->wth = NULL; cf->filename = NULL; cf->source = NULL; @@ -49,88 +48,249 @@ cap_file_init(capture_file *cf) cf->has_snap = FALSE; cf->snap = WTAP_MAX_PACKET_SIZE; cf->count = 0; - cf->last_found_num = 0; - cf->last_found_fd = NULL; cf->redissecting = FALSE; } -void +/* + * For a given frame number, calculate the indices into a level 3 + * node, a level 2 node, a level 1 node, and a leaf node. + */ +#define LEVEL_3_INDEX(framenum) \ + ((framenum) >> (3*LOG2_NODES_PER_LEVEL)) +#define LEVEL_2_INDEX(framenum) \ + (((framenum) >> (2*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1)) +#define LEVEL_1_INDEX(framenum) \ + (((framenum) >> (1*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1)) +#define LEAF_INDEX(framenum) \ + (((framenum) >> (0*LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1)) + +/* + * Add a new frame_data structure to the capture_file's collection. + */ +frame_data * cap_file_add_fdata(capture_file *cf, frame_data *fdata) { - frame_data *plist_end = cf->plist_end; - fdata->prev = plist_end; - if (plist_end != NULL) - plist_end->next = fdata; - else - cf->plist_start = fdata; - cf->plist_end = fdata; + frame_data *leaf; + frame_data **level1; + frame_data ***level2; + frame_data ****level3; + frame_data *node; + + /* + * The current value of cf->count is the index value for the new frame, + * because the index value for a frame is the frame number - 1, and + * if we currently have cf->count frames, the the frame number of + * the last frame in the collection is cf->count, so its index value + * is cf->count - 1. + */ + if (cf->count == 0) { + /* The tree is empty; allocate the first leaf node, which will be + the root node. */ + leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL); + node = &leaf[0]; + cf->ptree_root = leaf; + } else if (cf->count < NODES_PER_LEVEL) { + /* It's a 1-level tree, and is going to stay that way for now. */ + leaf = cf->ptree_root; + node = &leaf[cf->count]; + } else if (cf->count == NODES_PER_LEVEL) { + /* It's a 1-level tree that will turn into a 2-level tree. */ + level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL); + memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL); + level1[0] = cf->ptree_root; + leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL); + level1[1] = leaf; + node = &leaf[0]; + cf->ptree_root = level1; + } else if (cf->count < NODES_PER_LEVEL*NODES_PER_LEVEL) { + /* It's a 2-level tree, and is going to stay that way for now. */ + level1 = cf->ptree_root; + leaf = level1[cf->count >> LOG2_NODES_PER_LEVEL]; + if (leaf == NULL) { + leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL); + level1[cf->count >> LOG2_NODES_PER_LEVEL] = leaf; + } + node = &leaf[LEAF_INDEX(cf->count)]; + } else if (cf->count == NODES_PER_LEVEL*NODES_PER_LEVEL) { + /* It's a 2-level tree that will turn into a 3-level tree */ + level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL); + memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL); + level2[0] = cf->ptree_root; + level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL); + memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL); + level2[1] = level1; + leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL); + level1[0] = leaf; + node = &leaf[0]; + cf->ptree_root = level2; + } else if (cf->count < NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) { + /* It's a 3-level tree, and is going to stay that way for now. */ + level2 = cf->ptree_root; + level1 = level2[cf->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)]; + if (level1 == NULL) { + level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL); + memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL); + level2[cf->count >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)] = level1; + } + leaf = level1[LEVEL_1_INDEX(cf->count)]; + if (leaf == NULL) { + leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL); + level1[LEVEL_1_INDEX(cf->count)] = leaf; + } + node = &leaf[LEAF_INDEX(cf->count)]; + } else if (cf->count == NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) { + /* It's a 3-level tree that will turn into a 4-level tree */ + level3 = g_malloc((sizeof *level3)*NODES_PER_LEVEL); + memset(level3, 0, (sizeof *level3)*NODES_PER_LEVEL); + level3[0] = cf->ptree_root; + level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL); + memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL); + level3[1] = level2; + level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL); + memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL); + level2[0] = level1; + leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL); + level1[0] = leaf; + node = &leaf[0]; + cf->ptree_root = level3; + } else { + /* cf->count is 2^32-1 at most, and NODES_PER_LEVEL^4 + 2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10, + so cf->count is always less < NODES_PER_LEVEL^4. + + XXX - we should fail if cf->count is 2^31-1, or should + make the frame numbers 64-bit and just let users run + themselves out of address space or swap space. :-) */ + /* It's a 4-level tree, and is going to stay that way forever. */ + level3 = cf->ptree_root; + level2 = level3[LEVEL_3_INDEX(cf->count)]; + if (level2 == NULL) { + level2 = g_malloc((sizeof *level2)*NODES_PER_LEVEL); + memset(level2, 0, (sizeof *level2)*NODES_PER_LEVEL); + level3[LEVEL_3_INDEX(cf->count)] = level2; + } + level1 = level2[LEVEL_2_INDEX(cf->count)]; + if (level1 == NULL) { + level1 = g_malloc((sizeof *level1)*NODES_PER_LEVEL); + memset(level1, 0, (sizeof *level1)*NODES_PER_LEVEL); + level2[LEVEL_2_INDEX(cf->count)] = level1; + } + leaf = level1[LEVEL_1_INDEX(cf->count)]; + if (leaf == NULL) { + leaf = g_malloc((sizeof *leaf)*NODES_PER_LEVEL); + level1[LEVEL_1_INDEX(cf->count)] = leaf; + } + node = &leaf[LEAF_INDEX(cf->count)]; + } + *node = *fdata; + cf->count++; + return node; } /* * Find the frame_data for the specified frame number. - * Do some caching to make this work reasonably fast for - * forward and backward sequential passes through the packets. */ frame_data * cap_file_find_fdata(capture_file *cf, guint32 num) { - frame_data *fdata; + frame_data *leaf; + frame_data **level1; + frame_data ***level2; + frame_data ****level3; if (num == 0) { /* There is no frame number 0 */ return NULL; } - /* - * Did we remember a frame number from a sequential pass through - * the frames? - */ - if (cf->last_found_num != 0) { - /* - * Yes. Is this that frame? - */ - if (num == cf->last_found_num) { - /* Yes - return it. */ - return cf->last_found_fd; - } + /* Convert it into an index number. */ + num--; + if (num >= cf->count) { + /* There aren't that many frames. */ + return NULL; + } - /* - * No. Is it the frame just after that frame? - */ - if (num == cf->last_found_num + 1) { - /* - * Yes - if there is such a frame, remember it and return it. - */ - fdata = cf->last_found_fd->next; - if (fdata != NULL) { - cf->last_found_num = num; - cf->last_found_fd = fdata; - } - return fdata; /* could be null, if there is no such frame */ - } + if (cf->count <= NODES_PER_LEVEL) { + /* It's a 1-level tree. */ + leaf = cf->ptree_root; + return &leaf[num]; + } + if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) { + /* It's a 2-level tree. */ + level1 = cf->ptree_root; + leaf = level1[num >> LOG2_NODES_PER_LEVEL]; + return &leaf[LEAF_INDEX(num)]; + } + if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) { + /* It's a 3-level tree. */ + level2 = cf->ptree_root; + level1 = level2[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)]; + leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)]; + return &leaf[LEAF_INDEX(num)]; + } + /* cf->count is 2^32-1 at most, and NODES_PER_LEVEL^4 + 2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10, + so cf->count is always less < NODES_PER_LEVEL^4. */ + /* It's a 4-level tree, and is going to stay that way forever. */ + level3 = cf->ptree_root; + level2 = level3[num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)]; + level1 = level2[(num >> (LOG2_NODES_PER_LEVEL+LOG2_NODES_PER_LEVEL)) & (NODES_PER_LEVEL - 1)]; + leaf = level1[(num >> LOG2_NODES_PER_LEVEL) & (NODES_PER_LEVEL - 1)]; + return &leaf[LEAF_INDEX(num)]; +} - /* - * No. Is it the frame just before that frame? - */ - if (num == cf->last_found_num - 1) { - /* - * Yes - if there is such a frame, remember it and return it. - */ - fdata = cf->last_found_fd->prev; - if (fdata != NULL) { - cf->last_found_num = num; - cf->last_found_fd = fdata; +/* + * Free up all the frame information for a capture file. + */ +void +cap_file_free_frames(capture_file *cf) +{ + frame_data **level1; + frame_data ***level2; + frame_data ****level3; + guint i, j, k; + + if (cf->count == 0) { + /* Nothing to free. */ + return; + } + if (cf->count <= NODES_PER_LEVEL) { + /* It's a 1-level tree. */ + g_free(cf->ptree_root); + } else if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL) { + /* It's a 2-level tree. */ + level1 = cf->ptree_root; + for (i = 0; i < NODES_PER_LEVEL && level1[i] != NULL; i++) + g_free(level1[i]); + g_free(level1); + } else if (cf->count <= NODES_PER_LEVEL*NODES_PER_LEVEL*NODES_PER_LEVEL) { + /* It's a 3-level tree. */ + level2 = cf->ptree_root; + for (i = 0; i < NODES_PER_LEVEL && level2[i] != NULL; i++) { + level1 = level2[i]; + for (j = 0; j < NODES_PER_LEVEL && level1[i] != NULL; j++) + g_free(level1[j]); + g_free(level1); + } + g_free(level2); + return; + } else { + /* cf->count is 2^32-1 at most, and NODES_PER_LEVEL^4 + 2^(LOG2_NODES_PER_LEVEL*4), and LOG2_NODES_PER_LEVEL is 10, + so cf->count is always less < NODES_PER_LEVEL^4. */ + /* It's a 4-level tree, and is going to stay that way forever. */ + level3 = cf->ptree_root; + for (i = 0; i < NODES_PER_LEVEL && level3[i] != NULL; i++) { + level2 = level3[i]; + for (j = 0; j < NODES_PER_LEVEL && level2[i] != NULL; j++) { + level1 = level2[j]; + for (k = 0; k < NODES_PER_LEVEL && level1[k] != NULL; k++) + g_free(level1[k]); } - return fdata; /* could be null, if there is no such frame */ + g_free(level2); } + g_free(level3); } - - for (fdata = cf->plist_start; fdata != NULL && fdata->num < num; - fdata = fdata->next) - ; - if (fdata != NULL) { - cf->last_found_num = num; - cf->last_found_fd = fdata; - } - return fdata; + cf->ptree_root = NULL; + cf->count = 0; } |