代码审查（跳过列表） [英] Code Review (Skip List)
问题描述
如果有人有时间，我想要代码审查。该代码实现了一个基本的
跳过列表库，供一般用途使用。我使用以下标题进行调试
宏：
/ *
public.h - 公共声明和宏
* /
#ifndef PUBLIC
#define PUBLIC
#include< assert.h>
#include< stdio.h>
#include< stdlib.h>
#define VERBOSE
#if定义（VERBOSE）
#define trace（msg，file，line，var）printf（msg，file，line，var）
#define call_trace（msg）printf（"％s \ n"，msg）
#else
#define trace（msg，file，line，var）printf（" ;"）
#define call_trace（msg）
#endif
extern unsigned long alloc_count;
#define xmalloc（x）（++ alloc_count，\
trace（"％s - alloc line％d：balance - ％ld \ n"， __FILE __，_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ _ $ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ >
trace（&quo t;％s - 分配行％d：余额 - ％ld \ n"，__ FILE __，_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ />
#define xfree（x）（alloc_count = x？ alloc_count - 1：alloc_count，\
trace（"％s - free line％d：balance - ％ld \ n"，__ FILE __，_ _ _ _ _ _，$ / b
alloc_count），free（x））
#define deref（x）（assert（（x）！= NULL），（x））
＃定义边界（i，n）（断言（（i）> = 0&&（i）<（n）），（i））
#endif
public.h的定义是：
/ *
public.c - 公共定义。
* /
#include" public.h"
unsigned long alloc_count = 0;
我在测试驱动程序中使用以下项目标题：
/ *
版权所有（C）2004 Robin Cole
xitem.h - 特定于应用程序的数据结构内容。
对此文件和xitem.c进行更改以专门化。
* /
#ifndef XITEM
#define XITEM
/ *兼容性所需的typedef * /
typedef struct object xitem;
struct object {
char * item;
};
int compare_xitem（ xitem * a，xitem * b）;
xitem * make_xitem（char * item）;
void destroy_xitem（xitem * old_xitem）;
#endif
xitem定义为：
/ *
版权所有（C）2004 Robin Cole
xitem.c - xitem的应用程序特定定义。
* /
#include< assert.h>
#include< string.h>
#include" public.h"
#include" xitem.h"
/ *
比较两个xitems。返回-1,0，+ 1如果a小于，等于或大于
* /
int
compare_xitem（
xitem * a，
xitem * b
）
{
断言（a！= NULL ）;
断言（b！= NULL）;
返回strcmp（a-> item，b-> item）;
}
/ *
创建一个新的xitem。返回指向内存块的指针。
* /
xitem *
make_xitem（
char * item < br $>
）
{
xitem * new_xitem;
断言（item！= NULL）;
new_xitem = xmalloc（new_xitem）;
call_trace（&＃xmalloc：make_xitem中的new_xitem）;
if（！new_xitem）{
fprintf（stderr，"％s：％d - 内存耗尽\ n，__ FILE __，_ _ _ _ _ _ _ _; $ / b $ b}返回NULL;
}
new_xitem-> item = xnmalloc（new_xitem-> item，strlen（item）+ 1）;
call_trace（" xnmalloc：xitem_item（new_xitem）in make_xitem"）;
if（！new_xitem-> item）{
fprintf（stderr，"％s：％d - Memory exhausted\\\
， __FILE __，_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ br $>
}
strcpy（new_xitem-> item，item）;
返回new_xitem;
}
/ *
销毁现有的xitem及其内容
* /
void
destroy_xitem（
xitem * old_xitem
）
{
assert（old_xitem！= NULL）;
xfree（old_xitem-> item）;
call_trace（&destroyx中的xfree：xitem_item（old_xitem）"）;
xfree（old_xitem）;
call_trace（" xfree：old_xitem in destroy_xitem"）;
}
这里是跳过列表库的代码，测试主要是一个简单的
驱动程序：
/ *
版权所有（C）2004 Robin Cole
- 创建（5/14/2004）Robin Cole
- 最后的接触（5/15/2004） Robin Cole
- 传统化和普遍化（5/21/2004）Robin Cole
xlist - 跳过列表演示实施
* /
#include< assert.h>
#include< stdio.h>
#include< stdlib.h>
＃包括public.h
#include" xitem.h"
typedef struct node xnode;
typedef struct list xlist;
static xnode * nil;
struct node {
void * item; / *客户内容* /
int height; / *下一个链接的数量* /
xnode ** next; / *跳过链接，动态分配* /
};
static void verify_xnode（xnode * node）;
xnode * make_xnode（void * item，int height）;
void destroy_xnode（xnode * node，void（* destroy）（void * old_item））;
struct list {
xnode * head; / *跳过列表的虚拟标题* /
int size; / *客户项目数* /
int max_height; / *最大可能跳过高度
（客户定义）* /
int（* compare）（void * a，void * b）; / *项目的通用比较* /
};
static void verify_xlist（xlist * list）;
xlist * make_xlist （int max_height，int（* compare）（void * a，void * b））;
void destroy_xlist（xlist * list，void（* destroy）（void * old_item））;
int insert_xlist（xlist * list，void * item）;
int remove_xlist（xlist * list，void ** old_item，void * item）;
int search_xlist（xlist * list，void ** found_item，void * item）;
void display_xlist（xlist * list）;
int
main（无效）
{
xlist * list;
xitem * item，* save;
int i;
char * a [] = {
/ *a，h，b，g， " C"，" F"，" d"，" E"，" d"，" A"，" H" / *交替插入
和重复* /
a，b，c，d，e， ; F"，" G"，" H"，" d"，" A"，" H" / *升序插入和
重复* /
/ *h，g，f，e，d等。 ，" C"，" b"，" A"，" d"，" A"，" H" / *降序插入
和重复* /
};
list = make_xlist（4，compare_xitem）;
if（！list）{
fprintf（stderr，致命错误：数据结构创建失败\ n）;
返回EXIT_FAILURE; < （b = 0; i< sizeof a / sizeof * a; i ++）{
xitem * new_item = make_xitem（a）
}
[i]）;
if（！new_item）{
fprintf（stderr，创建项目时出错）;
休息;
}
if（！insert_xlist（list，new_item））{
fprintf（stderr，"插入项目'\\ n'的错误;）;
destroy_xitem（new_item）;
}
display_xlist（list）;
printf（" \ n =============== \ n"）;
getchar（）;
}
item = make_xitem（" e"）;
if（item）{
printf（" Search result：％d \ n"，search_xlist（ list，& save，item））;
remove_xlist（lis t，& save，item）;
if（save）{
destroy_xitem（save）;
}
display_xlist（list）;
printf（" \ n =============== \ n"）;
getchar（）;
printf（"搜索结果：％d \ n"，search_xlist（list，& save，item））;
destroy_xitem（item ）;
}
destroy_xlist（list，destroy_xitem）;
返回EXIT_SUCCESS;
}
/ *
xnode处理程序
* /
/ * xnode断言* /
static void verify_xnode（xnode * node）
{
断言（节点！= NULL）;
断言（node-> height> 0）;
断言（node-> next！= NULL）;
}
/ *分配并初始化xnode * /
xnode *
make_xnode（
void * item，/ *可以为null表示无效项目* /
int height
）
{
xnode * node;
断言（ height> 0）;
node = xmalloc（node）;
call_trace（" xmalloc：make_xnode中的节点）;
if （！节点）{
fprintf（stderr，Memory exhausted\\\
）;
返回NULL;
}
node-> next = xnmalloc（node-> next，height）;
call_trace（" xnmalloc：node-> next in make_xnode"）;
if（！node-> next）{
fprintf（stderr，Memory exhausted\\\
）;
xfree（node）;
call_trace（" xfree：make_xnode中的节点）;
返回NULL;
}
node-> ; item = item;
node-> height = height;
而（height--）{
node-> next [height] = nil;
}
返回节点;
}
/ *释放xnode的内存* /
void
destroy_xnode（
xnode * node，
void（* destroy）（void * old_item）/ *用于销毁物品的功能，可以
be null * /
）
{
verify_xnode（node）;
xfree（node-> next） ;
call_trace（" xfree：node-> next in destroy_xnode"）;
if（node-> item&& destroy）{
destroy（node-> item）;
}
xfree（node）;
call_trace（" xfree：destroy_xnode中的节点）;
}
/ *
xlist处理程序
* /
/ * xlist断言* /
static void verify_xlist（xlist * list）
{
断言（列表！= NULL）;
断言（list-> head！= NULL）;
断言（list-> max_height> ; 0）;
断言（list-> compare！= NULL）;
}
/ *分配并初始化xlist * /
xlist *
make_xlist（
int max_height，/ *节点最大可能高度* /
int（* compare）（void * a，void * b）/ *比较项目的功能* /
）
{
xlist * list;
断言（max_height> 0）;
断言（比较！= NULL）;
list = xmalloc（list）;
call_trace（" xmalloc：make in makelist中的list）;
if（！list）{
fprintf（stderr，Memory exhausted\\\
）;
返回NULL;
}
nil = xmalloc（nil）;
call_trace（&＃xmalloc：在make_xlist中为nil）;
if（！ nil）{
fprintf（stderr，Memory exhausted\\\
）;
xfree（list）;
call_trace（" xfree：make_xlist中的列表"）;
返回NULL;
}
nil-> item = NULL;
list-> head = make_xnode（NULL，max_height）;
if（！list-> head）{
fprintf（stderr，"内部错误： make_xnode \ n"）;
xfree（list）;
call_trace（" xfree：list in make_xlist"）;
返回NULL ;
}
list-> size = 0;
list-> head-> height = 1;
list-> max_height = max_height;
list-> compare = compare;
返回列表;
}
/ * xlist * / <的释放内存br $>
void
destroy_xlist（
xlist * list，
void（* destroy）（void * old_item）/ *破坏物品的功能，可以是
为空* /
）
{
xnode * node; / *遍历列表* /
xnode * save; / *保存内存释放链接* /
verify_xlist（list）;
verify_xnode（list-> head）;
node = list-> head;
while（node！= nil）{
save = node-> next [0];
destroy_xnode（node，destroy）;
node = save;
}
xfree（nil）;
call_trace（" xfree：nil in destroy_xlist"）;
xfree（list）;
call_trace（" xfree：list in destroy_xlist"）;
}
/ *随机高度[0..max_height]概率为1/2 * /
static int
random_height（
int max_height / *独家上限* /
）
{
int height = 1;
while（（double）rand（）/ RAND_MAX< .5&& height< max_height）{
++ height ;
}
返回高度;
}
/ *插入项目到xlist * /
int
insert_xlist（
xlis t * list，
void * item / *要插入的项目* /
）
{
xnode * *更新; / *列表重组的已保存链接* /
xnode * node; / *遍历列表* /
int n; / * Bounds的更新限制* /
int i;
verify_xlist（list）;
verify_xnode（list-> head）;
n = list-> max_height;
update = xnmalloc（update，n）;
call_trace（" xnmalloc：update in insert_xlist"）;
if（！update）{
fprintf（stderr，Memory exhausted\\\
）;
return 0;
}
node = list-> head;
for（i = list-> head-> height - 1 ; i> = 0; i--）{
void * current_item = node-> next [i] - > item;
while（current_item& &（* list-> compare）（current_item，item）< 0）{
node = node-> next [i];
verify_xnode（node ）;
current_item = node-> next [i] - > item;
}
update [i] = node;
}
node = node-> next [0];
if（node-> item&&（* list- >比较）（node-> item，item）== 0）{
fprintf（stderr，"警告：Dupli凯特检测到。列表未更改\ n"）;
xfree（更新）;
call_trace（" xfree：update in insert_xlist"）;
返回0;
}
else {
int height = random_height（list-> max_height）;
if（height> list-> head-> height）{
for（i = list-> head-> height; i< height; i ++）{
update [i] = list-> head;
}
list-> head-> height = height;
}
node = make_xnode（item，height）;
if（！node）{
fprintf（stderr，"内部错误：make_xnode \ n"）;
xfree（更新）;
call_trace（" xfree：update in insert_xlist"）;
return 0;
}
for（i = 0; i< height; i ++）{
node-> next [i] =更新[i] - > next [i];
update [i] - > next [i] = node;
}
++ list-> size;
}
xfree（更新）;
call_trace（" xfree：update在insert_xlist"）;
返回1;
}
/ *从xlist中删除项目* /
int
remove_xlist（
xlist * list，
void ** old_item，/ *拯救旧客户使用项目* /
无效*项目/ *项目搜索* /
）
{
xnode ** update; / *列表重组的已保存链接* /
xnode * node; / *遍历列表* /
int n; / * Bounds的更新限制* /
int i;
verify_xlist（list）;
verify_xnode（list-> head）;
断言（old_item！= NULL）;
n = list-> max_height;
update = xnmalloc（update，n） ;
call_trace（" xnmalloc：update in insert_xlist"）;
if（！update）{
fprintf（stderr，" Memory）耗尽了\ n"）;
返回0;
}
node = list-> head;
for（i = list-> head-> height - 1; i> = 0; i--）{
void * current_item = node-> next [i] - > ; item;
while（current_item&&（* list-> compare）（current_item，item）< 0）{
node = node-> next [i];
verify_xnode（节点）;
current_item = node-> next [i] - > item;
}
update [i] = node;
}
node = node-> next [0];
if（node-> item&&（* list-> compare）（node-> item，item）== 0）{
xnode * next; / *收缩步骤的链接* /
for（i = 0; i< list-> head-> height; i ++）{
if（update [update] i] - > next [i]！= node）{
break;
}
update [i] - > next [ i] = node-> next [i];
}
* old_item = node-> item;
xfree（node- > next）;
call_trace（" xfree：node-> next in remove_xlist"）;
xfree（node）;
call_trace（" xfree：node in remove_xlist"）;
next = list-> head-> next [list-> head-> height - 1];
while（list-> head-> height> 0&& next == nil）{
--list-> head-> height;
next = list-> head-> next [list-> head-> height - 1];
}
--list - >尺寸;
xfree（更新）;
call_trace（" xfree：update in remove_xlist"）;
返回1; < br $>
}
else {
* old_item = NULL;
xfree（更新）;
call_trace（" xfree：更新于remove_xlist"）;
返回0;
}
}
/ *定位xlist中的项目* /
int
search_xlist（
xlist * list，
void ** found_item ，/ *保存找到的项目供客户使用* /
void * item / * item搜索* /
）
{
xnode * node; / *遍历列表* /
int i;
verify_xlist（list）;
verify_xnode（list-> head ）;
断言（found_item！= NULL）;
node = list-> head;
for（i = list-> head-> height - 1; i> = 0; i - ）{
void * current_item = node-> next [i] - > item;
while（current_item&&（* list-> compare）（current_item，item）< 0）{
node = node-> next [i];
verify_xnode（节点）;
current_item = node-> next [i] - > item;
}
}
node = node-> next [0];
if（node-> item&&（* list-> compare）（node-> ; item，item）== 0）{
* found_item = node-> item;
返回1;
}
else {
* found_item = NULL;
返回0;
}
}
/ *来自display_xlist的安全打印* /
静态字符*
get_item（
xitem * item
）
{
if（！item）{
return"（null）" ;;
}
否则{
返回项目 - >项目;
}
}
/ *显示xlist的详细信息和结构* /
void
display_xlist（
xlist * list
）
{
xnode * node;
int i;
verify_xlist（list）;
verify_xnode（list-> head）;
printf（" List size：％d \ n"
" nil：％p \ n"
"最大高度：％d \ n \ n"，list-> size，（void *）nil，list-> max_height）;
node = list-> head;
while（node！= nil）{
printf（" Address：％p \ n"
" Item：％s \ n"
" Height：％d \ nn"
" Next："，（void * ）node，get_item（node-> item），node-> height）;
for（i = 0;我<节点 - >高度; i ++）{
printf（" [％d]：％p"，i，（void *）node-> next [i]）;
}
printf（" \ n \ n"）;
node = node-> next [0];
}
}
I''d like a code review if anyone has the time. The code implements a basic
skip list library for generic use. I use the following header for debug
macros:
/*
public.h - Public declarations and macros
*/
#ifndef PUBLIC
#define PUBLIC
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define VERBOSE
#if defined (VERBOSE)
# define trace(msg, file, line, var) printf(msg, file, line, var)
# define call_trace(msg) printf("%s\n", msg)
#else
# define trace(msg, file, line, var) printf("")
# define call_trace(msg)
#endif
extern unsigned long alloc_count;
#define xmalloc(x) (++alloc_count, \
trace("%s - alloc line %d: balance -- %ld\n", __FILE__, __LINE__,
alloc_count), malloc(sizeof *(x)))
#define xnmalloc(x, n) (++alloc_count, \
trace("%s - alloc line %d: balance -- %ld\n", __FILE__, __LINE__,
alloc_count), malloc((n) * sizeof *(x)))
#define xfree(x) (alloc_count = x ? alloc_count - 1 : alloc_count, \
trace("%s - free line %d: balance -- %ld\n", __FILE__, __LINE__,
alloc_count), free(x))
#define deref(x) (assert((x) != NULL), (x))
#define bounds(i, n) (assert((i) >= 0 && (i) < (n)), (i))
#endif
The definitions for public.h are:
/*
public.c - Public definitions.
*/
#include "public.h"
unsigned long alloc_count = 0;
And I make use of the following item header in the test driver:
/*
Copyright (C) 2004 Robin Cole
xitem.h - Application specific data structure contents.
Make changes to this file and xitem.c to specialize.
*/
#ifndef XITEM
#define XITEM
/* Required typedef for compatibility */
typedef struct object xitem;
struct object {
char *item;
};
int compare_xitem(xitem *a, xitem *b);
xitem *make_xitem(char *item);
void destroy_xitem(xitem *old_xitem);
#endif
With xitem defined as:
/*
Copyright (C) 2004 Robin Cole
xitem.c - Application specific definitions for xitem.
*/
#include <assert.h>
#include <string.h>
#include "public.h"
#include "xitem.h"
/*
Compare two xitems. Return -1, 0, +1 if a is less, equal or greater
*/
int
compare_xitem(
xitem *a,
xitem *b
)
{
assert(a != NULL);
assert(b != NULL);
return strcmp(a->item, b->item);
}
/*
Create a new xitem. Return a pointer to the memory block.
*/
xitem *
make_xitem(
char *item
)
{
xitem *new_xitem;
assert(item != NULL);
new_xitem = xmalloc(new_xitem);
call_trace("xmalloc: new_xitem in make_xitem");
if (!new_xitem) {
fprintf(stderr, "%s : %d -- Memory exhausted\n", __FILE__, __LINE__);
return NULL;
}
new_xitem->item = xnmalloc(new_xitem->item, strlen(item) + 1);
call_trace("xnmalloc: xitem_item(new_xitem) in make_xitem");
if (!new_xitem->item) {
fprintf(stderr, "%s : %d -- Memory exhausted\n", __FILE__, __LINE__);
xfree(new_xitem);
call_trace("xfree: new_xitem in make_xitem");
return NULL;
}
strcpy(new_xitem->item, item);
return new_xitem;
}
/*
Destroy an existing xitem and its contents
*/
void
destroy_xitem(
xitem *old_xitem
)
{
assert(old_xitem != NULL);
xfree(old_xitem->item);
call_trace("xfree: xitem_item(old_xitem) in destroy_xitem");
xfree(old_xitem);
call_trace("xfree: old_xitem in destroy_xitem");
}
Here''s the code for the skip list library with a test main as a simple
driver:
/*
Copyright (C) 2004 Robin Cole
- Created (5/14/2004) Robin Cole
- Final touches (5/15/2004) Robin Cole
- Conventionalized and generalized (5/21/2004) Robin Cole
xlist - Skip list demo implementation
*/
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "public.h"
#include "xitem.h"
typedef struct node xnode;
typedef struct list xlist;
static xnode *nil;
struct node {
void *item; /* Client contents */
int height; /* # of next links */
xnode **next; /* Skip links, dynamically allocated */
};
static void verify_xnode(xnode *node);
xnode *make_xnode(void *item, int height);
void destroy_xnode(xnode *node, void (*destroy)(void *old_item));
struct list {
xnode *head; /* Dummy header of skip list */
int size; /* Number of client items */
int max_height; /* Maximum possible skip height
(client defined) */
int (*compare)(void *a, void *b); /* Generic comparison for items */
};
static void verify_xlist(xlist *list);
xlist *make_xlist(int max_height, int (*compare)(void *a, void *b));
void destroy_xlist(xlist *list, void (*destroy)(void *old_item));
int insert_xlist(xlist *list, void *item);
int remove_xlist(xlist *list, void **old_item, void *item);
int search_xlist(xlist *list, void **found_item, void *item);
void display_xlist(xlist *list);
int
main(void)
{
xlist *list;
xitem *item, *save;
int i;
char *a[] = {
/* "a","h","b","g","c","f","d","e","d","a","h" /* Alternating insertion
and duplicates */
"a","b","c","d","e","f","g","h","d","a","h" /* Ascending insertion and
duplicates */
/* "h","g","f","e","d","c","b","a","d","a","h" /* Descending insertion
and duplicates */
};
list = make_xlist(4, compare_xitem);
if (!list) {
fprintf(stderr, "Fatal error: Data structure creation failed\n");
return EXIT_FAILURE;
}
for (i = 0; i < sizeof a / sizeof *a; i++) {
xitem *new_item = make_xitem(a[i]);
if (!new_item) {
fprintf(stderr, "Error creating item\n");
break;
}
if (!insert_xlist(list, new_item)) {
fprintf(stderr, "Error inserting item\n");
destroy_xitem(new_item);
}
display_xlist(list);
printf("\n===============\n");
getchar();
}
item = make_xitem("e");
if (item) {
printf("Search result: %d\n", search_xlist(list, &save, item));
remove_xlist(list, &save, item);
if (save) {
destroy_xitem(save);
}
display_xlist(list);
printf("\n===============\n");
getchar();
printf("Search result: %d\n", search_xlist(list, &save, item));
destroy_xitem(item);
}
destroy_xlist(list, destroy_xitem);
return EXIT_SUCCESS;
}
/*
xnode handlers
*/
/* xnode assertions */
static void verify_xnode(xnode *node)
{
assert(node != NULL);
assert(node->height > 0);
assert(node->next != NULL);
}
/* Allocate and initialize an xnode */
xnode *
make_xnode(
void *item, /* May be null to represent invalid items */
int height
)
{
xnode *node;
assert(height > 0);
node = xmalloc(node);
call_trace("xmalloc: node in make_xnode");
if (!node) {
fprintf(stderr, "Memory exhausted\n");
return NULL;
}
node->next = xnmalloc(node->next, height);
call_trace("xnmalloc: node->next in make_xnode");
if (!node->next) {
fprintf(stderr, "Memory exhausted\n");
xfree(node);
call_trace("xfree: node in make_xnode");
return NULL;
}
node->item = item;
node->height = height;
while (height--) {
node->next[height] = nil;
}
return node;
}
/* Release memory for an xnode */
void
destroy_xnode(
xnode *node,
void (*destroy)(void *old_item) /* Function for destroying an item, may
be null */
)
{
verify_xnode(node);
xfree(node->next);
call_trace("xfree: node->next in destroy_xnode");
if (node->item && destroy) {
destroy(node->item);
}
xfree(node);
call_trace("xfree: node in destroy_xnode");
}
/*
xlist handlers
*/
/* xlist assertions */
static void verify_xlist(xlist *list)
{
assert(list != NULL);
assert(list->head != NULL);
assert(list->max_height > 0);
assert(list->compare != NULL);
}
/* Allocate and initialize an xlist */
xlist *
make_xlist(
int max_height, /* Largest possible height of a node */
int (*compare)(void *a, void *b) /* Function for comparing items */
)
{
xlist *list;
assert(max_height > 0);
assert(compare != NULL);
list = xmalloc(list);
call_trace("xmalloc: list in make_xlist");
if (!list) {
fprintf(stderr, "Memory exhausted\n");
return NULL;
}
nil = xmalloc(nil);
call_trace("xmalloc: nil in make_xlist");
if (!nil) {
fprintf(stderr, "Memory exhausted\n");
xfree(list);
call_trace("xfree: list in make_xlist");
return NULL;
}
nil->item = NULL;
list->head = make_xnode(NULL, max_height);
if (!list->head) {
fprintf(stderr, "Internal error: make_xnode\n");
xfree(list);
call_trace("xfree: list in make_xlist");
return NULL;
}
list->size = 0;
list->head->height = 1;
list->max_height = max_height;
list->compare = compare;
return list;
}
/* Release memory for an xlist */
void
destroy_xlist(
xlist *list,
void (*destroy)(void *old_item) /* Function for destroying an item, may
be null */
)
{
xnode *node; /* Traverse the list */
xnode *save; /* Save the link for memory release */
verify_xlist(list);
verify_xnode(list->head);
node = list->head;
while (node != nil) {
save = node->next[0];
destroy_xnode(node, destroy);
node = save;
}
xfree(nil);
call_trace("xfree: nil in destroy_xlist");
xfree(list);
call_trace("xfree: list in destroy_xlist");
}
/* Random height [0..max_height) with probability 1/2 */
static int
random_height(
int max_height /* Exclusive upper bound */
)
{
int height = 1;
while ((double)rand() / RAND_MAX < .5 && height < max_height) {
++height;
}
return height;
}
/* Insert an item into an xlist */
int
insert_xlist(
xlist *list,
void *item /* Item to insert */
)
{
xnode **update; /* Saved links for list restructuring */
xnode *node; /* Traverse the list */
int n; /* Bounds limit for update */
int i;
verify_xlist(list);
verify_xnode(list->head);
n = list->max_height;
update = xnmalloc(update, n);
call_trace("xnmalloc: update in insert_xlist");
if (!update) {
fprintf(stderr, "Memory exhausted\n");
return 0;
}
node = list->head;
for (i = list->head->height - 1; i >= 0; i--) {
void *current_item = node->next[i]->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next[i];
verify_xnode(node);
current_item = node->next[i]->item;
}
update[i] = node;
}
node = node->next[0];
if (node->item && (*list->compare)(node->item, item) == 0) {
fprintf(stderr, "Warning: Duplicate detected. List is unchanged\n");
xfree(update);
call_trace("xfree: update in insert_xlist");
return 0;
}
else {
int height = random_height(list->max_height);
if (height > list->head->height) {
for (i = list->head->height; i < height; i++) {
update[i] = list->head;
}
list->head->height = height;
}
node = make_xnode(item, height);
if (!node) {
fprintf(stderr, "Internal error: make_xnode\n");
xfree(update);
call_trace("xfree: update in insert_xlist");
return 0;
}
for (i = 0; i < height; i++) {
node->next[i] = update[i]->next[i];
update[i]->next[i] = node;
}
++list->size;
}
xfree(update);
call_trace("xfree: update in insert_xlist");
return 1;
}
/* Remove an item from an xlist */
int
remove_xlist(
xlist *list,
void **old_item, /* Save the old item for client use */
void *item /* item to search for */
)
{
xnode **update; /* Saved links for list restructuring */
xnode *node; /* Traverse the list */
int n; /* Bounds limit for update */
int i;
verify_xlist(list);
verify_xnode(list->head);
assert(old_item != NULL);
n = list->max_height;
update = xnmalloc(update, n);
call_trace("xnmalloc: update in insert_xlist");
if (!update) {
fprintf(stderr, "Memory exhausted\n");
return 0;
}
node = list->head;
for (i = list->head->height - 1; i >= 0; i--) {
void *current_item = node->next[i]->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next[i];
verify_xnode(node);
current_item = node->next[i]->item;
}
update[i] = node;
}
node = node->next[0];
if (node->item && (*list->compare)(node->item, item) == 0) {
xnode *next; /* Link for shrink step */
for (i = 0; i < list->head->height; i++) {
if (update[i]->next[i] != node) {
break;
}
update[i]->next[i] = node->next[i];
}
*old_item = node->item;
xfree(node->next);
call_trace("xfree: node->next in remove_xlist");
xfree(node);
call_trace("xfree: node in remove_xlist");
next = list->head->next[list->head->height - 1];
while (list->head->height > 0 && next == nil) {
--list->head->height;
next = list->head->next[list->head->height - 1];
}
--list->size;
xfree(update);
call_trace("xfree: update in remove_xlist");
return 1;
}
else {
*old_item = NULL;
xfree(update);
call_trace("xfree: update in remove_xlist");
return 0;
}
}
/* Locate an item in an xlist */
int
search_xlist(
xlist *list,
void **found_item, /* Save the found item for client use */
void *item /* item to search for */
)
{
xnode *node; /* Traverse the list */
int i;
verify_xlist(list);
verify_xnode(list->head);
assert(found_item != NULL);
node = list->head;
for (i = list->head->height - 1; i >= 0; i--) {
void *current_item = node->next[i]->item;
while (current_item && (*list->compare)(current_item, item) < 0) {
node = node->next[i];
verify_xnode(node);
current_item = node->next[i]->item;
}
}
node = node->next[0];
if (node->item && (*list->compare)(node->item, item) == 0) {
*found_item = node->item;
return 1;
}
else {
*found_item = NULL;
return 0;
}
}
/* Safe print from display_xlist */
static char *
get_item(
xitem *item
)
{
if (!item) {
return "(null)";
}
else {
return item->item;
}
}
/* Display details and structure of an xlist */
void
display_xlist(
xlist *list
)
{
xnode *node;
int i;
verify_xlist(list);
verify_xnode(list->head);
printf("List size: %d\n"
"nil: %p\n"
"Max height: %d\n\n", list->size, (void *)nil, list->max_height);
node = list->head;
while (node != nil) {
printf("Address: %p\n"
"Item: %s\n"
"Height: %d\n"
"Next: ", (void *)node, get_item(node->item), node->height);
for (i = 0; i < node->height; i++) {
printf("[%d]: %p ", i, (void *)node->next[i]);
}
printf("\n\n");
node = node->next[0];
}
}
推荐答案
Robin Cole写道：
Robin Cole wrote:
#include< assert .h>
#include< stdio.h>
#include< stdlib.h>
#define VERBOSE
#if defined（VERBOSE）
#define trace（msg，file，line，var）printf（msg，file，line，var）
#define call_trace（msg）printf（"％s\\\
"，msg） #else
#define trace（msg，file，line，var）printf（""）
#define call_trace（msg）
#endif
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define VERBOSE
#if defined (VERBOSE)
# define trace(msg, file, line, var) printf(msg, file, line, var)
# define call_trace(msg) printf("%s\n", msg)
#else
# define trace(msg, file, line, var) printf("")
# define call_trace(msg)
#endif
我到目前为止。尝试：
#define VERBOSE
#if定义（VERBOSE）
#define trace（msg，var）printf（" ;％s（％d）：" msg，__ FILE __，_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ $ $ $ $ b＃define call_trace（msg）printf（"％s \ n"，msg）
#else
#define trace（msg，file，line，var）// nada
#define call_trace（msg）// nada
#endif
您可以在编译器的命令行上传递VERBOSE;检查你的
实现如何。宏NDEBUG可能是可用的。
请注意％s（％d）： msg要求msg是一个字符串文字，因为它
使用文字串联。
但是，正如你在学习的那样，你应该看看C ++及其标准图书馆
可以提供更清晰的代码。
-
Phlip
http://industrialxp.org/community/bi...UserInterfaces
" Phlip" < pH值******* @ yahoo.com>写了
"Phlip" <ph*******@yahoo.com> wrote
我到目前为止。尝试：
#define VERBOSE
#if defined（VERBOSE）
#define trace（msg，var）printf（"％s（％d）：" msg， __FILE __，_ _ _ _ 11，var）
这对我的口味来说有点模糊。我希望立即为我的读者提供明确的信息。
#define call_trace（msg）printf（"％s \ nn"，msg）
#else
#define trace（msg，file，line，var）// nada
printf来自之前的库。我不记得我现在如何使用它
，但是什么都没有替换printf会导致
编译时错误。
#define call_trace（msg）// nada
#endif
你可以在编译器的命令行上传递VERBOSE;检查你的
实现如何。宏NDEBUG可能可用。
我选择不在命令行上为我的测试运行定义VERBOSE。我是b / b
完全了解NDEBUG和编译器开关，它们允许您从命令行定义名称
，但是还是要感谢。
注意％s（％d）： msg要求msg是一个字符串文字，因为它使用文字串联。
然而，正如你在学习的那样，你应该看看C ++及其标准的
库是否可以提供更清洁代码。
I got this far. Try:
#define VERBOSE
#if defined (VERBOSE)
# define trace(msg, var) printf("%s(%d): " msg, __FILE__, __LINE__, var)
That''s a little obscure for my tastes. I like things to be immediately
obvious for my readers.
# define call_trace(msg) printf("%s\n", msg)
#else
# define trace(msg, file, line, var) // nada
The printf was there from a previous library. I can''t recall how I used it
at the moment, but replacing the printf with nothing resulted in a
compile-time error.
# define call_trace(msg) // nada
#endif
You can pass VERBOSE on the compiler''s command line; check with your
implementation how to. The macro NDEBUG might be available.
I chose not to define VERBOSE on the command line for my test runs. I''m
fully aware of both NDEBUG and compiler switches that let you define names
from the command line, but thanks nonetheless.
Note that "%s(%d): " msg requires msg to be a string literal, because it
uses literal concatenation.
However, as you are learning, you should see if C++ and its standard library can provide cleaner code.
代码更慢。在使用C ++的标准
容器类之前，我已经编写了跳过列表，用于更清洁的代码。它的速度只有
等效手动实施的一半。
And slower code. I''ve written skip lists before using C++''s standard
container classes for "cleaner code" that were easily half as fast as the
equivalent hand rolled implementation.
2004年5月24日星期一，格林尼治标准时间18:12:11， comp.lang.c，Robin Cole
< ha ********* @ hotmail.com>写道：
On Mon, 24 May 2004 18:12:11 GMT, in comp.lang.c , "Robin Cole"
<ha*********@hotmail.com> wrote:
Phlip < pH值******* @ yahoo.com>写了
"Phlip" <ph*******@yahoo.com> wrote
我到目前为止。尝试：
#define VERBOSE
#if defined（VERBOSE）
#define trace（msg，var）printf（"％s（％d）：" msg， __FILE __，_ _ _ _ __，var）
I got this far. Try:
#define VERBOSE
#if defined (VERBOSE)
# define trace(msg, var) printf("%s(%d): " msg, __FILE__, __LINE__, var)
这对我的口味来说有点模糊。我希望我的读者可以立即明白这些事情。
That''s a little obscure for my tastes. I like things to be immediately
obvious for my readers.
对于任何了解C的人来说，这是/很明显的（如果有人对
缺少printf说明符）。
原始版本要求您提供msg。这是一个
格式的字符串，否则会调用未定义的行为。
That /is/ immediately obvious to anyone who knows C (if one sorts out the
missing printf specifiers).
The original version either requires to you to supply a "msg" that is a
format string, or else it invokes undefined behaviour.
但是，正如你在学习的那样，你应该看看C ++及其标准库是否可以提供更清晰的代码。
However, as you are learning, you should see if C++ and its standard library
can provide cleaner code.
代码更慢。在使用C ++的标准
容器类清洁代码之前，我已经编写了跳过列表。这相当于
等效的手动实现速度的一半快。
And slower code. I''ve written skip lists before using C++''s standard
container classes for "cleaner code" that were easily half as fast as the
equivalent hand rolled implementation.
然后你或者是
a）有一个糟糕的STL实现（可能或
b）你编码得很糟糕（可能）。
我发现C ++在绝大多数用途中都和C一样快。 br />
我不能快速写好。 ： - （
-
Mark McIntyre
CLC FAQ< http://www.eskimo.com/~ scs / C-faq / top.html>
CLC自述文件：< http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
- --- ==通过Newsfeed.Com发布 - 无限制 - 未经审查 - 安全使用网新闻== ----
http://www.newsfeed.com 世界排名第一的新闻组服务！> 100,000个新闻组
--- = 19个东/西海岸专业服务器 - 通过加密实现全面隐私= ---
---- ==通过Newsfeed.Com发布 - 无限制 - 未经审查 - 安全Usenet新闻== ----
http://www.newsfeed.com 世界排名第一的新闻组服务！> 100,000新闻组
--- = 19东/西海岸专业服务器 - 通过加密的总隐私= ---
Then you either
a) had a bad STL implementation (possiblel or
b) you coded it badly (likely).
I find C++ to be just as fast as C for the vast majority of uses.
I just cant write it well as fast. :-(
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.angelfire.com/ms3/bchambless0/welcome_to_clc.html>
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
这篇关于代码审查（跳过列表）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
