list.c
上传用户:tany51
上传日期:2013-06-12
资源大小:1397k
文件大小:10k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /*
  2.  * Copyright (C) 1998,1999,2000  Ross Combs (rocombs@cs.nmsu.edu)
  3.  *
  4.  * This program is free software; you can redistribute it and/or
  5.  * modify it under the terms of the GNU General Public License
  6.  * as published by the Free Software Foundation; either version 2
  7.  * of the License, or (at your option) any later version.
  8.  *
  9.  * This program is distributed in the hope that it will be useful,
  10.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.  * GNU General Public License for more details.
  13.  *
  14.  * You should have received a copy of the GNU General Public License
  15.  * along with this program; if not, write to the Free Software
  16.  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  17.  */
  18. #define LIST_INTERNAL_ACCESS
  19. #include "common/setup_before.h"
  20. #ifdef HAVE_STDDEF_H
  21. # include <stddef.h>
  22. #else
  23. # ifndef NULL
  24. #  define NULL ((void *)0)
  25. # endif
  26. #endif
  27. #ifdef STDC_HEADERS
  28. # include <stdlib.h>
  29. #else
  30. # ifdef HAVE_MALLOC_H
  31. #  include <malloc.h>
  32. # endif
  33. #endif
  34. #include "common/eventlog.h"
  35. #include "common/list.h"
  36. #include "common/setup_after.h"
  37. static int nodata; /* if data points to this, then the element was actually deleted */
  38. #ifdef USE_CHECK_ALLOC
  39. extern t_list * list_create_real(char const * fn, unsigned int ln)
  40. #else
  41. extern t_list * list_create(void)
  42. #endif
  43. {
  44.     t_list * new;
  45.     
  46. #ifdef USE_CHECK_ALLOC
  47.     if (!(new = check_malloc_real(sizeof(t_list),fn,ln)))
  48. #else
  49.     if (!(new = malloc(sizeof(t_list))))
  50. #endif
  51.     {
  52. eventlog(eventlog_level_error,"list_create","could not allocate memory for new");
  53. return NULL;
  54.     }
  55.     
  56.     new->head = NULL;
  57.     new->tail = NULL;
  58.     new->len = 0;
  59.     
  60.     return new;
  61. }
  62. extern int list_destroy(t_list * list)
  63. {
  64.     if (!list)
  65.     {
  66.         eventlog(eventlog_level_error,"list_destroy","got NULL list");
  67.         return -1;
  68.     }
  69.     
  70.     list_purge(list);
  71.     if (list->head)
  72. eventlog(eventlog_level_error,"list_destroy","got non-empty list");
  73.     
  74.     free(list);
  75.     
  76.     return 0;
  77. }
  78. extern int list_purge(t_list * list)
  79. {
  80.     t_elem *   curr;
  81.     t_elem *   head;
  82.     t_elem *   tail;
  83.     t_elem *   next;
  84.     t_elem * * change;
  85.     
  86.     if (!list)
  87.     {
  88.         eventlog(eventlog_level_error,"list_purge","got NULL list");
  89.         return -1;
  90.     }
  91.     
  92. #ifdef LIST_DEBUG
  93.     list_check(list);
  94. #endif
  95.     
  96.     head = NULL;
  97.     tail = NULL;
  98.     change = NULL;
  99.     for (curr=list->head; curr; curr=next)
  100.     {
  101. next = curr->next;
  102. if (curr->data==&nodata)
  103. {
  104.     if (change)
  105. *change = next;
  106.     free(curr);
  107. }
  108. else
  109. {
  110.     tail = curr;
  111.     if (!head)
  112. head = curr;
  113.     change = &curr->next;
  114. }
  115.     }
  116.     
  117.     list->head = head;
  118.     list->tail = tail;
  119.     
  120.     return 0;
  121. }
  122. extern int list_check(t_list const * list)
  123. {
  124.     unsigned int   emptycnt;
  125.     unsigned int   validcnt;
  126.     t_elem const * tail;
  127.     t_elem const * curr;
  128.     int            ret=0;
  129.     
  130.     if (!list)
  131.     {
  132.         eventlog(eventlog_level_error,"list_check","got NULL list");
  133.         return -1;
  134.     }
  135.     
  136.     emptycnt=validcnt = 0;
  137.     tail = NULL;
  138.     for (curr=list->head; curr; curr=curr->next)
  139.     {
  140. if (tail)
  141. {
  142.     if (curr==tail) /* tail is currently the previous node */
  143.     {
  144. eventlog(eventlog_level_error,"list_check","list is circular (curr==prev==%p)",curr);
  145. return -1;
  146.     }
  147.     if (curr->next==tail)
  148.     {
  149. eventlog(eventlog_level_error,"list_check","list is circular (curr->next==prev==%p)",curr);
  150. return -1;
  151.     }
  152.     if (curr==list->head)
  153.     {
  154. eventlog(eventlog_level_error,"list_check","list is circular (curr==list->head==%p)",curr);
  155. return -1;
  156.     }
  157. }
  158. if (curr->data==&nodata)
  159.     emptycnt++;
  160. else
  161.     validcnt++;
  162. tail = curr;
  163.     }
  164.     
  165.     if (emptycnt>10 && emptycnt>validcnt+5) /* arbitrary heuristic to detect missing list_purge() calls */
  166. eventlog(eventlog_level_warn,"list_check","emptycnt=%u but validcnt=%u",emptycnt,validcnt);
  167.     if (list->len!=validcnt)
  168.     {
  169. eventlog(eventlog_level_error,"list_check","list->len=%u but validcnt=%u",list->len,validcnt);
  170. ret = -1;
  171.     }
  172.     if (list->head && !list->tail)
  173.     {
  174. eventlog(eventlog_level_error,"list_check","list->head=%p but list->tail=%p (len=%u)",list->head,list->tail,list->len);
  175. ret = -1;
  176.     }
  177.     if (list->tail!=tail)
  178.     {
  179. eventlog(eventlog_level_error,"list_check","list->tail=%p but tail=%p",list->tail,tail);
  180. ret = -1;
  181.     }
  182.     if (validcnt!=0 && !list->head)
  183.     {
  184. eventlog(eventlog_level_error,"list_check","validcnt=%u but list->head=%p",validcnt,list->head);
  185. ret = -1;
  186.     }
  187.     
  188.     return ret;
  189. }
  190. extern unsigned int list_get_length(t_list const * list)
  191. {
  192.     if (!list)
  193.     {
  194. eventlog(eventlog_level_error,"list_get_length","got NULL list");
  195. return 0;
  196.     }
  197.     
  198.     return list->len;
  199. }
  200. #ifdef USE_CHECK_ALLOC
  201. extern int list_prepend_data_real(t_list * list, void * data, char const * fn, unsigned int ln)
  202. #else
  203. extern int list_prepend_data(t_list * list, void * data)
  204. #endif
  205. {
  206.     t_elem * elem;
  207.     
  208.     if (!list)
  209.     {
  210. eventlog(eventlog_level_error,"list_prepend_data","got NULL list");
  211. return -1;
  212.     }
  213.     
  214. #ifdef USE_CHECK_ALLOC
  215.     if (!(elem = check_malloc_real(sizeof(t_elem),fn,ln)))
  216. #else
  217.     if (!(elem = malloc(sizeof(t_elem))))
  218. #endif
  219.     {
  220. eventlog(eventlog_level_error,"list_prepend_data","could not allocate memory for elem");
  221. return -1;
  222.     }
  223.     elem->data = data;
  224.     
  225.     elem->next = list->head;
  226.     list->head = elem;
  227.     if (!list->tail)
  228. list->tail = elem;
  229.     list->len++;
  230.     
  231.     return 0;
  232. }
  233. #ifdef USE_CHECK_ALLOC
  234. extern int list_append_data_real(t_list * list, void * data, char const * fn, unsigned int ln)
  235. #else
  236. extern int list_append_data(t_list * list, void * data)
  237. #endif
  238. {
  239.     t_elem * elem;
  240.     
  241.     if (!list)
  242.     {
  243. eventlog(eventlog_level_error,"list_append_data","got NULL list");
  244. return -1;
  245.     }
  246.     
  247. #ifdef USE_CHECK_ALLOC
  248.     if (!(elem = check_malloc_real(sizeof(t_elem),fn,ln)))
  249. #else
  250.     if (!(elem = malloc(sizeof(t_elem))))
  251. #endif
  252.     {
  253. eventlog(eventlog_level_error,"list_append_data","could not allocate memory for elem");
  254. return -1;
  255.     }
  256.     elem->data = data;
  257.     
  258.     elem->next = NULL;
  259.     if (!list->head)
  260. list->head = elem;
  261.     if (list->tail)
  262. list->tail->next = elem;
  263.     list->tail = elem;
  264.     list->len++;
  265.     
  266.     return 0;
  267. }
  268. extern t_elem * list_get_elem_by_data(t_list const * list, void const * data)
  269. {
  270.     t_elem * curr;
  271.     
  272.     if (!list)
  273.     {
  274. eventlog(eventlog_level_error,"list_get_elem_by_data","got NULL list");
  275. return NULL;
  276.     }
  277.     
  278.     LIST_TRAVERSE(list,curr)
  279. if (curr->data==data)
  280.     return curr;
  281.     
  282.     return NULL;
  283. }
  284. extern t_elem const * list_get_elem_by_data_const(t_list const * list, void const * data)
  285. {
  286.     t_elem const * curr;
  287.     
  288.     if (!list)
  289.     {
  290. eventlog(eventlog_level_error,"list_get_elem_by_data_const","got NULL list");
  291. return NULL;
  292.     }
  293.     
  294.     LIST_TRAVERSE_CONST(list,curr)
  295. if (curr->data==data)
  296.     return curr;
  297.     
  298.     return NULL;
  299. }
  300. extern int list_remove_elem(t_list * list, t_elem * elem)
  301. {
  302.     if (!list)
  303.     {
  304. eventlog(eventlog_level_error,"list_remove_elem","got NULL list");
  305. return -1;
  306.     }
  307.     if (!elem)
  308.     {
  309. eventlog(eventlog_level_error,"list_remove_elem","got NULL elem");
  310. return -1;
  311.     }
  312.     if (elem->data==&nodata)
  313.     {
  314. eventlog(eventlog_level_error,"list_remove_elem","got deleted elem");
  315. return -1;
  316.     }
  317.     
  318.     elem->data = &nodata;
  319.     list->len--;
  320.     
  321.     return 0;
  322. }
  323. extern int list_remove_data(t_list * list, void const * data)
  324. {
  325.     t_elem * elem;
  326.     
  327.     if (!list)
  328.     {
  329. eventlog(eventlog_level_error,"list_remove_data","got NULL list");
  330. return -1;
  331.     }
  332.     
  333.     if (!(elem = list_get_elem_by_data(list,data)))
  334. return -1;
  335.     
  336.     return list_remove_elem(list,elem);
  337. }
  338. extern int elem_set_data(t_elem * elem, void * data)
  339. {
  340.     if (!elem)
  341.     {
  342. eventlog(eventlog_level_error,"elem_set_data","got NULL elem");
  343. return -1;
  344.     }
  345.     if (elem->data==&nodata)
  346.     {
  347. eventlog(eventlog_level_error,"elem_set_data","got deleted elem");
  348. return -1;
  349.     }
  350.     if (data==&nodata)
  351.     {
  352. eventlog(eventlog_level_error,"elem_set_data","got bad data");
  353. return -1;
  354.     }
  355.     
  356.     elem->data = data;
  357.     
  358.     return 0;
  359. }
  360. extern void * elem_get_data(t_elem const * elem)
  361. {
  362.     if (!elem)
  363.     {
  364. eventlog(eventlog_level_error,"elem_get_data","got NULL elem");
  365. return NULL;
  366.     }
  367.     if (elem->data==&nodata)
  368.     {
  369. eventlog(eventlog_level_error,"elem_get_data","got deleted elem");
  370. return NULL;
  371.     }
  372.     
  373.     return elem->data;
  374. }
  375. extern void * list_get_data_by_pos(t_list const * list, unsigned int pos)
  376. {
  377.     t_elem const * curr;
  378.     unsigned int   len;
  379.     
  380.     len = 0;
  381.     LIST_TRAVERSE_CONST(list,curr)
  382. if (len++==pos)
  383.     return curr->data;
  384.     
  385.     eventlog(eventlog_level_error,"list_get_data_by_pos","requested position %u but len=%u",pos,len);
  386.     return NULL;
  387. }
  388. #ifdef LIST_DEBUG
  389. extern t_elem * list_get_first_real(t_list const * list, char const * fn, unsigned int ln)
  390. #else
  391. extern t_elem * list_get_first(t_list const * list)
  392. #endif
  393. {
  394.     t_elem * curr;
  395.     
  396.     if (!list)
  397.     {
  398. #ifdef LIST_DEBUG
  399. eventlog(eventlog_level_error,"list_get_first","got NULL list from %s:%u",fn,ln);
  400. #else
  401. eventlog(eventlog_level_error,"list_get_first","got NULL list");
  402. #endif
  403. return NULL;
  404.     }
  405.     
  406.     for (curr=list->head; curr; curr=curr->next)
  407. if (curr->data!=&nodata)
  408.     return curr;
  409.     
  410.     return curr;
  411. }
  412. #ifdef LIST_DEBUG
  413. extern t_elem const * list_get_first_const_real(t_list const * list, char const * fn, unsigned int ln)
  414. #else
  415. extern t_elem const * list_get_first_const(t_list const * list)
  416. #endif
  417. {
  418.     t_elem const * curr;
  419.     
  420.     if (!list)
  421.     {
  422. #ifdef LIST_DEBUG
  423. eventlog(eventlog_level_error,"list_get_first_const","got NULL list from %s:%u",fn,ln);
  424. #else
  425. eventlog(eventlog_level_error,"list_get_first_const","got NULL list");
  426. #endif
  427. return NULL;
  428.     }
  429.     
  430.     for (curr=list->head; curr; curr=curr->next)
  431. if (curr->data!=&nodata)
  432.     return curr;
  433.     
  434.     return curr;
  435. }
  436. extern t_elem * elem_get_next(t_elem const * elem)
  437. {
  438.     t_elem * curr;
  439.     
  440.     if (!elem)
  441.     {
  442. eventlog(eventlog_level_error,"elem_get_next","got NULL elem");
  443. return NULL;
  444.     }
  445.     
  446.     for (curr=elem->next; curr; curr=curr->next)
  447. if (curr->data!=&nodata)
  448.     return curr;
  449.     
  450.     return curr;
  451. }
  452. extern t_elem const * elem_get_next_const(t_elem const * elem)
  453. {
  454.     t_elem const * curr;
  455.     
  456.     if (!elem)
  457.     {
  458. eventlog(eventlog_level_error,"elem_get_next_const","got NULL elem");
  459. return NULL;
  460.     }
  461.     
  462.     for (curr=elem->next; curr; curr=curr->next)
  463. if (curr->data!=&nodata)
  464.     return curr;
  465.     
  466.     return curr;
  467. }